×

Welcome to Knowledge Base!

KB at your finger tips

This is one stop global knowledge base where you can learn about all the products, solutions and support features.

Categories
All
CRM-Salesforce
Salesforce Developers

Pickup and Dropoff Problems

In our routing problems, items are loaded onto our vehicles in a variety of ways: they may be loaded onto the vehicle at the start of the route, items may be picked up at a customer order, or supply can be replenished at a specially designated "replenishment order". Once an item is onboard the vehicle, then it is eligible for a delivery event for orders that specify this item type in delivery_item_quantities . However, when these items are delivered, there is no way to specify that a specific item of that type should be delivered to a specific location. In other words, if the items are boxes, then with the typical usage of pickup_item_quantities and delivery_item_quantities there is no way to guarantee that a specific box is delivered to a specific location. However, this behavior can be guaranteed with the notion of a dropoff .

Given an order with items to be picked up, one can designate that these items are dropped off later in the route at a specific location by specifying a dropoff_location_id as part of the order object. An optional dropoff_deadline can be specified inside the order object to specify the latest time that the dropoff occurs. Adherence to this deadline is enforced via the dropoff_deadline constraint. Additionally, in cases where a deadline is less important than the amount of time an item spends on the vehicle (as in passenger pickup and dropoff or the transport of perishable goods), one can use the journey_time to limit the time between the pickup event and the eventual dropoff. The example order below demonstrates how to specify this sort of dropoff event.

For all problems involving the pickup of items that are then dropped off at a subsequent stop later in the same route, the optimization keeps track of the items on the vehicle and ensures that a vehicle's load never exceeds its capacity (specified in the vehicle object via capacity_by_item , weight_capacity , and/or volume_capacity ).

In the example request below, we have a fleet of three passenger vans that can each carry up to 6 people (this limit is set via the capacity_by_item for each vehicle). The vans start and end at different hotels in Atlanta, and the task is to pickup a variety of individuals and groups at locations throughout the city and drop them off later on at a different location. Many orders consist of multiple passengers and many orders also have a dropoff_deadline that is enforced with the dropoff_deadline constraint. In order to provide high quality service and to try to ensure that customers do not remain on the vehicle too long, we also provide a journey_time constraint that penalizes any route that has a customer on the vehicle for longer than 60 minutes.

Expand to view request sample
Salesforce Developers

Balanced Pickup and Unloading

In this example, we have a fictitious company that picks up various sizes of boxes and can unload them at a central facility when the vehicle is full. We have a fleet of heterogeneous vehicles that pick up the three item types as seen in the items array below

The vehicles are constrained in terms of how much of each item they can carry as well as by volume and weight. Each vehicle’s capacity is expressed separately as part of the vehicle object, and an example vehicle object now looks like this

Similar to delivery problems, we express the amount to be picked up at each order with pickup_item_quantities . In problems involving pickups, the vehicle may become full during the shift and be therefore unable to service any more orders. By specifying certain orders to have the ability to receive unloaded items , we can extend the shift since the vehicle can empty its contents at these orders. An example of such an order is below. Note that the amount that can be unloaded must be set – typically this should be a very large value to allow essentially unlimited unloading.

A full request involving pickups, unloading events, and a num_stops constraint to balance the routes is given below.

Expand to view request sample

img

All orders are visited and the routes are very balanced in terms of number of stops (either 10 or 11 orders serviced in each route). The unloading facility (boxed in red) is visited a total of 8 times to allow the vehicles to empty their contents and continue the route.

In the routes returned in the API response, any stop where items are picked up will have details of what is picked up, and how much of each item is in the vehicle at that time

In the API response, the orders array contains the details of all the visits to the order. Of interest is the Unload at trash facility order :

Additionally, for every stop at the unloading facility, an items_unloaded array is included to describe the activity at the stop.

Other features of the pickup/delivery aspects of the route are also included in the route object, such as max_volume_in_vehicle , max_num_items_in_vehicle , and max_weight_in_vehicle . Since vehicle capacity constraints are never violated, the optimization engine ensures that no vehicle will ever be carrying more than its capacity at any point during the route (in terms of weight/volume/number of items). The unloading stops are strategically inserted by the algorithm in order to satisfy as many orders as possible while still respecting the vehicle capacities.

Read article
Salesforce Developers

Delivery Only Problem

In this example, we have a fleet of heterogeneous vehicles that deliver two item types, box (volume of 1 unit) and big_box (volume of 2 units) as seen in the items array below

The vehicles are constrained both in terms of how much of each item they can carry as well as by maximum volume carried. Each vehicle’s capacity is expressed separately allowing for a truly heterogeneous fleet. Our vehicle object now looks like this

The orders also have a demand for some number of items of these types – this is expressed in their delivery_item_quantities as seen in the full request below. Note that there are no pickup_item_quantities at any of the orders so that this is a pure delivery problem where the optimization engine will determine how much of each item type each vehicle must start the route with.

Expand to view request sample

img

In this case we use all 4 vehicles but are unable to visit 4 of the orders due to the capacity constraints on the vehicles. Below, we see the impact of doubling each vehicle’s capacity – we are now able to visit all the orders and actually only need 3 of the 4 vehicles to do so.

img

The impact of doubling vehicle capacity. In the API response, the items_delivered at each stop is given in an array

The optimization engine also determines how many items the vehicle must have on board when the shift begins. This is recorded in the start_items object of the route. By loading the vehicle with these items at the start of the route, all orders in the route will have their delivery demand satisfied.

Other features of the delivery aspect of the route are also included in the route object, such as max_volume_in_vehicle , max_num_items_in_vehicle .

Read article
Salesforce Developers

Single Vehicle

Jimmy and Sally have just started a lighting company to service a number of commercial addresses. Lucky for them, their first major assignment is a government contract. They start and end their day at the White House, and here are the places they were assigned to service.

  • The Washington Monument: 38.889484, -77.035278
  • Ford’s Theatre: 38.8967, -77.0257
  • Abe Lincoln Memorial: 38.8893, -77.0502
  • The Vietnam Memorial: 38.8913, -77.0477
  • The Thomas Jefferson Memorial: 38.8814, -77.0365

We begin by building out a JSON payload and add the locations of the job sites as a simple array of locations objects:

Jimmy and Sally also think about the time they want to start and end their day. They estimate the amount of time (in seconds) required to service each order and add this as the duration. They also prioritize the orders since there is a chance they may not be able to service all the orders in a single day (shift). Note that an order is directly related to a location. Conceptually, orders represent a request for service (such as delivering goods to a store), and a higher priority indicates that if it is not possible to visit all orders, then the higher priority orders should be favored.

With the locations and orders specified, the next step is to define constraints. the Optimization API has an extensive library of constraints that allows you to very precisely define what a “good” solution looks like. In this case, the objective is simple: visit as many orders as possible, minimize travel time, and make sure that if we can’t visit all the orders, we at least visit the highest priority orders. Each constraint has a penalty which determines how important it is to satisfy. For many constraints, the degree of the constraint violation can also be included in the penalty via the violation_increment . We do this below with the travel_time constraint so that each second that a vehicle travels is assessed a penalty of 1. This gives us a standard way of thinking about penalties and is recommended in all use cases. The visit_range constraint tells the Optimization API that we want to visit as many orders as possible. Since the penalty for this constraint is 10,000, if we miss an order then the solution is assessed a penalty of 10,000. The order_priority constraint indicates that orders with higher priority should be favored if all orders cannot be serviced (see the documentationof this constraint for additional details).

Sally and Jimmy also need to specify a vehicle and their shift. The shift is how the Optimization API knows when the vehicle and associated workers are allowed to operate. In this case, Sally and Jimmy define the shift as being from 8:30am to 5:00pm, and they also specify where the shift must start and end (the White House). Note that a shift can start and end at somewhere other than an order, for example a worker’s home address. Also, they specify vehicle type “car”. If routes for trucks and other restricted vehicles are desired, then the vehicle type can be set to “truck” with other parameters in order to ensure that the routes returned by the Optimization API are compliant.

You’ll notice that the vehicles parameter is actually an array. This is because the Optimization API can support multiple vehicles for a given problem. Additionally, each vehicle can operate for multiple shifts so that the Optimization API is able to solve problem involving many disjoint shifts. We will return to this more advanced functionality in later examples. Putting it all together, the payload looks like this.

Expand to view request sample

img

Four of the five orders are visited. The lowest priority Vietnam Memorial (red pin) is missed, but otherwise the route is efficient in terms of travel and meets our objectives.

The urgencyconstraint is different from Order Priority in that it tries to satisfy visiting more urgent orders earlier during the planning period (represented by a vehicle’s shift object). In the original solution, we visited the Lincoln Memorial as the last order. Now suppose we need to visit the Lincoln Memorial and Ford’s Theater earlier in the planning horizon. We could either add time windows for these orders or use the urgency constraint to encourage visiting them earlier in the day. First we will demonstrate this capability by adding urgency values for these two orders and then adding a new constraint of type urgency. The new request is below (only change to first request is addition of urgency constraint).

Expand to view request sample

img

img

The high urgency orders at Ford’s Theater and the Lincoln Memorial are now visited earlier in the day. The route is less efficient from a travel perspective but the sequence better meets our objectives. The Vietnam memorial is still not visited since we still have the order_priority constraint in place.

Sally and Jimmy received some changes – they will also have to service the Ravens football stadium in Baltimore. They reflected on how they might change their trip around. Some of the job sites are more complex than others and require more time. Instead of spending one quick day in DC, they need to spread their trip over two days. As such, they reserve a night or two at a hotel north of DC. Sally appends this location (39.064295, -76.965838) to their list. They will start each day at the hotel, plan on ending at the White House on day 1 to do some sightseeing, and will also plan on celebrating the end of the DC work by going to a sushi restaurant in Annapolis – this will be the end_location of their shift on the second day.

Let’s summarize how these stipulations change the the Optimization API payload.

  • LOCATIONS — Not much changes here. Sally just adds the latitude and longitude of the stadium, hotel and restaurant to the array.

  • SHIFTS — Sally adds another shift to the shift array to account for the extra day. Additionally, with all this new work they will be hungry so lunch breaks are now added each day from noon to 1pm.

  • ORDERS — The amount of work changes at each order, so the durations change, we add an appointment at the Lincoln Memorial and Vietnam Memorial, and also add a new long job at the Ravens stadium. Note that adding the appointment to the order doesn’t guarantee that we will visit it – we need a constraint to enforce that.

  • CONSTRAINTS — Sally now specifies a scheduled_appointment constraint with a high penalty to ensure the appointments are met.

Expand to view request sample

Luckily it is still possible for the pair to complete all the work, do some sightseeing and finish with a celebration in Annapolis. Since the Optimization API accounts for predicted traffic in its routing calculations, the pair takes paths between locations that minimize the estimated travel time. Nevertheless, the pair expect their total travel time to be about 39 minutes longer due to traffic over the two day period (total_traffic_time in the response).

img

The first day in purple, the second day is in green. Note that the shifts are for the same vehicle but the Optimization API allows you to have different start or end locations for individual shifts.

Sally and Jimmy have now received word that some of the locations they are servicing have other events planned, and they must arrive at the orders only during certain times. These are referred to as time windows and the Optimization API allows us to ensure that service at an order only begins during a time window. We remove the appointments from the existing orders and now update each order with a time window. This will lead to a less efficient route from a travel perspective, but they will now be starting service at each order only during the allowed window.

  • Orders : Each order now receives a time window.
  • Constraints : The scheduled_appointment constraint is removed in favor of a time_window constraint. Note that we use a violation_increment of 3600 in this constraint which makes the penalty depend on by how much we violate a time window. For example, if we are 3 hours late for a time window, then we will be hit with a penalty of 5000 for the initial violation plus another 3*5000 = 15,000 to penalize the fact that we are 3 hours late. The total penalty in this case is then 20,000 – equivalent to about 6 hours of travel.
Expand to view request sample

Luckily it is still possible to service all the orders where the pair arrives during a time window, eat lunch, and start/end each day at the desired location. Now the workload is more spread out across each day with 3 orders serviced on each day.

img

The Full solution for the two-day situation where all time windows are honored.

img Zoomed in view of the 5 orders visited in the city. Note that time windows often force us to visit orders in a less efficient sequence than we would do otherwise.

Read article
Salesforce Developers

Constraints Introduction

The Routing Optimization service allows users to model many different tradeoffs in a complex vehicle routing problem using constraints and penalties. The underlying optimization goal is to find the best feasible solution to your problem that minimizes the total number of penalty points. For every constraint violated, the solution incurs a penalty, so the more critical a constraint is to your problem, the higher the penalty should be.

The optimization engine can accept a problem with no constraints. Still, it returns the first solution it finds (which may be a "solution" with no orders routed). Receiving a simple, initial solution is not a meaningful or useful exercise! So a routing problem should always specify constraints. Detailed descriptions of all constraints are in the linked sections below.

For example, let us consider the nearly universal goals in routing optimization problems of seeking to visit all stops and minimize travel time. In a simple problem where each order is to be visited one time:

  1. We penalize orders that are not visited using the visit_range constraint.
  2. We penalize travel times using the travel_time constraint.

Suppose we have a visit_range constraint with a penalty of 1000. In that case, the optimization engine seeks to visit all orders unless they are more than 1000 seconds "out of the way." If it is essential to see all orders, then an even higher penalty can be used, for example, 100,000 or even 1,000,000. However, eventually, the solution may become constrained by not having enough time in the fleet's shifts or enough vehicles. Blindly increasing the penalties cannot guarantee that they are satisfied.

The Routing Optimization service offers various constraints to control multiple aspects of the solutions returned by the underlying optimization engine. These controls loosely divided into three categories:

  1. Solution Level — Control global properties such as total travel time or the number of routes.
  2. Route Level — Control individual route features such as the number of stops, stop sequence, or total working time.
  3. Order Level — Control treatment of orders such as obeying time windows, appointments, and priorities.
  4. Vehicle Level — Control treatment of vehicles such as obeying work speed.

For each constraint category, we provide a list of all supported constraints, a description of each, and an example showing how the constraint impacts a routing problem solution.

Requests to the Optimization API routing service can include an array of constraint objects that describe constraints used to control the routing solution. If there are no constraints , a set of defaults is defined for your problem by the optimization engine.

Expand to view request sample
Read article
Salesforce Developers

Solution Level Constraints

Travel time is arguably the most fundamental constraint for a typical vehicle routing problem. The goal is to make the routes efficient from a travel perspective. As alluded to in other parts of the documentation, it is convenient to use this constraint to align a single unit of the penalty with a single second traveled by a vehicle.

Expand to view request sample

To understand the travel time constraint's impact, it is best to see what happens when it is NOT included. In the below example, we send only a visit range constraint. The optimization engine will focus on visiting as many orders as possible but with no incentive to minimize travel time. The result is a set of routes that visit all orders but with very inefficient travel.

img

Four vehicle solution with all orders visited and travel time constraint included so that routes are efficient from a travel perspective.

img

Four vehicle solution with no travel time constraint included. In this case, we visit all the orders, but the sequence of stops on the route is inefficient. The total travel time, in this case, is about 400 minutes longer than in the solution produced when we include the travel time constraint.


Another ubiquitous goal in many vehicle routing problems is to minimize the total number of routes. In single day problems, this is equivalent to reducing the number of vehicles since there is a 1-to-1 correspondence between vehicles and routes. On multiple day problems, the situation can be slightly different as a vehicle may have routes assigned to it on only a subset of the days of the planning period. To generalize this, the num_shifts constraint seeks to minimize the total number of shifts in the solution (recall that a shift is simply a period during which a vehicle is allowed to be active).

In the example for this constraint, we add the fifth vehicle to our typical four-vehicle problem that is used throughout many of the other examples. This vehicle has a start/end location in the eastern portion of the area, and a single order is very close to it. Without the num_shifts constraint, we use this vehicle as it adds very little travel time. However, adding a high penalty num_shifts constraint eliminates this route at the expense of additional travel time.

Expand to view request sample

img

Shown above is the original solution to the five-vehicle problem with no num_shifts constraint. Note the purple route in the east near Walnut Grove – this vehicle visits only a single stop near the start/end location.

img

Adding the high penalty num_shifts constraint eliminates the Walnut Grove vehicle. Total travel time increases by about 30 minutes since we no longer use this vehicle.


In some cases, an individual vehicle may be more expensive to use than other options in the fleet, for example, if a vehicle gets worse gas mileage or is operated by a contractor whose rate is more expensive than other employees. This constraint allows us to avoid using this vehicle or minimize at least how much it is used. The violation_increment option can be beneficial for this constraint. The units are in the number of stops, so if the violation_increment is set to 5, then a penalty is assessed for every five stops that this vehicle makes (other than the route's start/end location). This is done as shown below.

Expand to view request sample

img

Shown above is the original four-vehicle solution with no vehicle_usage constraint. Note that the route for Vehicle 1 (Red, southwest) visits 15 total orders.

img

The vehicle_usage constraint has a penalty of 20,000 and a violation_increment of 5 for using Vehicle 1 (southwest). If Vehicle 1 has between 1 and 5 stops, the penalty is 20,000, between 6 and 9 stops, the penalty is 40,000, and so on. In this solution, we visit nine orders with Vehicle 1 and can still visit all 34 orders in the problem. While stop 3 in the red route is very inefficient, if we were to add it to Vehicle 1’s green route after stop 6, this would lead to an additional 20,000 units of penalty since we would now have ten stops on this route. Since this route modification does not save 20,000 seconds of travel time, the solution above achieves a much lower score even though the red route goes out of the way to hit its stop #3.


In problems where we have items to pick up or deliver, it can sometimes be desirable to prevent certain items from being included in the same route. For example, we may be carrying livestock and wish to avoid horned animals from sharing the truck with non-horned animals. This can be achieved with the prevent_item_mixture constraint. If violation_increment is specified, then the units are the count of item types.

In the example, we have two item types: bleach and ammonia . We do not want the bleach to ever come in contact with ammonia for everyone's safety, so we use a high penalty prevent_item_mixture constraint to prevent this from ever occurring.

Expand to view request sample

img

Shown above is the original four-vehicle solution with no restriction on which items can be mixed on the route.

img

Shown above is the solution where multiple item types cannot be included in the same route. Note the yellow route for Vehicle 1, which now must visit many disparate locations. Because the routes now must cover larger areas, we are unable to visit 2 of the orders.

Some routing problems have multiple orders at the same location. For example, an apartment building may have multiple orders for package delivery. A document shredding company may have numerous customers in the same office building. In some cases, the optimization may counterintuitively find a "better" solution where multiple vehicles visit these orders at different times of the day. Typically, this would occur due to time windows and appointments that would lead to other vehicles to satisfy a subset of orders that are all at a single location. The visit_same_location constraint allows you to force the stops at these orders to occur consecutively and be visited by the same vehicle.

In the example for this constraint, we have one location that is associated with three orders. Each of these three orders has a different time window: 9:15 am to 9:30 am, 11:00 am to 11:10 am, and 4:00 pm to 4:30 pm.

Expand to view request sample

Suppose we do not have the visit_same_location constraint; single-vehicle visits these three orders but spaces the visits throughout the day. In contrast, when we apply this constraint, the vehicle is forced to sit idle at this location. The overall solution is less efficient, requiring about 30 minutes total travel time.

img

The dark purple route visits its stop one. It then stops 2, 3, and 4 are all at the same location. The vehicle idles in between the service events at this location, waiting for the time window to start to arrive.

img

The dark blue route now services the same location that has three orders with time windows. However, these are now at stops 1,2, and 12 during the order, and the vehicle visits many other stops. The fourth vehicle is still needed in this solution but only has one stop. This can be eliminated in this case with a num_shifts constraint.

We pick up an item in many problems, and it does not matter how long it remains on the vehicle. However, in other cases, such as passenger pickup/dropoff and the transport of perishable goods, limiting the amount of time an item spends on a vehicle is critical. Three related constraint types allow you to control this behavior.

  • dropoff_deadline : Given an order with a dropoff_location_id , a dropoff_deadline can be added to the order - this is the latest time that the dropoff should occur, assuming that the pickup event is serviced. The dropoff_deadline constraint can then enforce these deadlines specified as part of the orders. Is with other constraints involving time limits, the violation_increment units are in seconds.
  • journey_time : The journey_time of an item that is picked up is defined as the elapsed time between when the item is picked up and either a dropoff or delivery event or the end of the route. The journey_time constraint allows you to specify the maximum number of seconds for this elapsed time. If refrigerated goods can only be on the vehicle for one hour before starting to spoil, then by specifying this constraint with max_journey_seconds value of 3600.
  • additional_journey_time : In problems involving passenger pickup and dropoff, it may be possible to have a solution with low total travel but where some passengers remain on the vehicle much longer than necessary. The additional_journey_time constraint allows you to bound this amount of extra time that items spend - it is defined as the difference between an item's journey_time and the travel time necessary travel directly from the pickup event to the delivery/dropoff of the item. The violation_increment units for these journey-related constraints are in seconds.

In the example below, we simultaneously utilize all three of these constraints in a tricky passenger pickup and dropoff problem. In this problem, we have several vans that start and end their routes at an Atlanta hotel. Each van can carry six passengers (note that we have a single item of item_type person and a capacity_by_item of 6 for each vehicle).

Expand to view request sample

Suppose we apply all three of these constraints. In that case, we end up with a solution that does not violate any of them, and we utilize three vehicles for a total travel time of 7.5 hours. The longest journey for any passenger is just under an hour. When we remove these constraints and focus on meeting time windows for the pickups and minimizing travel time, the solution requires more than 1.5 hours less total travel time. However, since we are now not considering the dropoff time of any of our passengers, we have one unfortunate group of passengers (Albert, Enrico, Robert) who are picked up at the Atlanta airport at 9:00 am but are not dropped off at their SunTrust Park destination until more than 5 hours later. This example illustrates many of the tradeoffs inherent in complex routing problems, and punishing customers with a terrible experience can be avoided with the right mix of constraints.

img

Read article

Still Thinking?
Give us a try!

We embrace agility in everything we do.
Our onboarding process is both simple and meaningful.
We can't wait to welcome you on AiDOOS!