×

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

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
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
Salesforce Developers

Route Level Constraints

Ensure that each of the provided orders is visited as the first stop on the route. Suppose the shift associated with the route has a pre-determined start location. In that case, the order must be the first stop visited after departing the start location. Otherwise, on a route with an open start location, the order must be the first overall stop on the route.

Expand to view request sample

img

Original solution with no first_visit constraint.

img

We add a first visit constraint for order id 674660, north of Stockbridge, boxed in red. This changes the route for vehicle1 significantly as it passes by many other stops on the way to its first stop, far from the start and end location.


Ensure that stops on a route are all within either a particular travel time or a certain distance from a specified home location_id for the shift. The home_location_id must be specified in the shift object.

Expand to view request sample

img

Shown above is the original four-vehicle solution without the home radius constraint.

img

We add a home radius constraint for all vehicles so that the routes are penalized if the vehicle is more than 45 minutes (2700 seconds) from the vehicle's home location. It is now impossible to visit 4 of the orders – some are too far away from any vehicle’s home location. Since we have less freedom in assigning stops to routes, we cannot find room in some routes for stops that could be otherwise visited. In particular, order #10 on the green route (boxed in red) now moves to a different route than in the original solution at the cost of adding travel time. This is because this location is more than 45 minutes from the home location of the blue Vehicle #1.


Ensure that each of the provided orders is the last stop in its route. Suppose the shift associated with the route has a pre-determined end location. In that case, each order must be the last stop visited before reaching the end location. Otherwise, it must be the final stop that terminates the route.

Expand to view request sample

img

Original four-vehicle solution without the last_visit constraint

img

Order 674660 north of Stockbridge must now be the last stop on the route. The green route for vehicle 1 is now relatively inefficient. We visit other nearby stops earlier in the route. Still, We cannot visit this order until it is the last order visited in the route.


Encourage the first or last stops on a route to be within a specified travel time or travel distance of a pre-specified home location. This constraint is useful when a worker’s day begins at the first stop on a route, but you also want to account for the leg to/from the home address. For this constraint, a home_location_id must be specified for each shift, as in the Home Radius constraint. A maximum allowed travel time (in seconds) or travel distance (in meters), and booleans for start_leg and end_leg will enable the user to penalize the time/distance between the home_location and the start or end of the route. For this constraint to be practical, the user should specify shifts that do not include a forced start or end by omitting the start_location_id and end_location_id parameters in the shift object.

Expand to view request sample

img

In the example above, we use the max_commute constraint with a max_travel_time of 600 seconds and add home_location_id 's for each shift.

img

With the max_commute constraint, the three routes now travel in a big loop and end up much closer to where they started. The constraint is still violated as there are no orders within 10 minutes of the home location for some shifts. For example, the green route has a home location in Campbellton, GA, and the shift starts and ends at the two closest orders to Campbellton. This additional restriction on the routes' start and end locations leads to an increase of about 150 minutes of total travel time versus the first solution.


Typically in a routing problem with a sufficient number of orders to ensure full routes, a shift cannot visit any more orders since we pass the end of the shift time. However, in cases where there are limits on the mileage a vehicle can travel during the day or some other reason to be concerned about the distance traveled by a vehicle over the course of a single shift, the max_distance constraint can be used. This constraint ensures that the routes do not exceed a specified distance. Applies to all routes if specific shift_ids are not provided. If violation_increment is provided, then the units are meters.

Expand to view request sample

img

The four-vehicle solution before adding the max_distance constraint.

img

In the example, we use a penalty of 1 and a violation increment of 1. Every meter a vehicle travels beyond the limit of 241,402 (150 miles), we have assessed a penalty of 1. All of the routes are now less than 150 miles in total distance traveled, with the longest route at about 145 miles. We can now visit all the orders since the increased distance necessary to visit the southernmost order would lead to more than 10,000 more meters traveled (10,000 is the magic number here since the visit range penalty is 10,000).


Suppose more compact routes with shorter travel times or shorter distances between stops are desired. In that case, these two constraints allow you to penalize long segments in the solution. The idea behind both constraints is similar: penalize segments in the solution that exceed either a certain distance or travel time. The example below utilizes max_segment_distance and can be trivially modified to exercise max_segment_time .

Expand to view request sample

img

Shown above is the original four-vehicle solution with no penalties for long segments.

img

Solution after penalizing segments that exceed 20km. Note that two orders are not visited (Cumming in the north, Locust Grove in the south) since the segments in and out of these locations far exceed 20km. The penalty assessed for adding the required long segments exceeds the penalty for not visiting them. So the trade-off here is to accept a visit_range penalty of 10,000. Additionally, note the changes in the pink northwest route versus the first solution. The Lithia Springs stop is now moved to another route to avoid the very long segment to return to the start location near Taylorsville (the northwestern-most stop).


This constraint controls the number of stops on each route to encourage min_stops and max_stops stops in the route. If the the start location or end location isis pre-determined for the shift corresponding to this route, these are not counted as stops in this computation. In other words, the constraint only considers active stops. If a route has many stops outside this range, then the violation increment is computed in terms of stops. For example, if a route has 5 stops and the constraint specifies min_stops = 10 with a penalty of 10,000 and a violation_increment of 1, then the total penalty would be 10,000 + (10-5)*10,000 = 60,000.

Expand to view request sample

img

Shown above is the original solution with no num_stops constraint. The green route visits only four orders, and the blue route visits only five while the red route visits 15 orders.

img

The constraint specifies that the routes should be more balanced – between 5-9 stops on all routes (excluding the start and end locations). The result is an increase in travel time, but much more balanced routes in terms of the number of stops. Vehicle 2 (upper left) now visits six orders as opposed to 4 in the previous solution. Vehicle 1 (bottom route) now visits only nine orders versus 15 in the solution without this constraint.


The num_stops constraint allows one to balance routes based on the number of stops. However, there are cases where one may want to balance the routes in terms of other metrics . For example, suppose there is a sales dollar amount at each order. In that case, one may want to balance the amount of sales amounts or opportunities across the routes. The route_balance constraint allows this behavior, and balance can be enforced across multiple dimensions by specifying which metric to balance across as well as the min and max amounts of this metric.


This constraint allows us to prevent shifts from lasting more than a specified duration ( max_seconds ). Each shift already has a fixed starting time and ending time, and our solutions will never produce routes that extend past this ending time. However, in some cases (such as paid overtime), we may want to encourage shifts to end earlier than this fixed ending time if possible. This constraint can apply to all shifts or specific shifts if the shift_ids array is populated.

Expand to view request sample

img

The solution before adding the shift_duration constraint.

img

Suppose that vehicle 1 (pink bottom route) is operated by a more expensive contractor than using the other vehicles. We restrict the duration of vehicle 1 to 10,800 seconds with the shift duration constraint. Since this penalty is the same as the penalty for the visit range constraint, and since we have a violation increment of 600 seconds, the optimization chooses to shorten this shift to <= 3 hours instead of adding more orders to the route. The result is that vehicle one now works for 173 minutes visiting only four orders. The other vehicles pick up the slack, but there are three unrouted orders.


Ensure that order A is visited before order B. Note that if either A or B is not visited in the solution, then the constraint is deemed violated, and a penalty is assessed.

Expand to view request sample

img

The original solution before adding the Visit_Sequence constraint

img

Multiple uses of the constraint forces order id 691287, 665537, and 674660 (boxed in red) are on the same route, and 691287 and 674660 must both before order id 665537. In the original solution, 66537 (near Jonesboro) is the first stop in the route. It now becomes the last stop in the route after adding the constraint. The first stop in the basic solution for the bottom route is now the last (stop #11) in the new route. Stop #8 in the new solution (order id 674660) was formerly stop #4. Stop #11 in the original solution (order id 691287) is now stop #4 after adding the constraint.


Read article
Salesforce Developers

Vehicle Level Constraints

Constraints that operate at the vehicle level allow one to control properties of the solution that apply to the individual vehicles. In cases where there is only one shift per vehicle, these are equivalent to constraints at the route level as there is exactly one route per vehicle. However, for multi-day, multi-vehicle problems, one may wish to control the properties of all the routes associated with a particular vehicle.

Very similar to the route_balance constraint, this constraint allows us to provide a min and max value for a metric summed across all the routes associated with the vehicles specified. If a list is provided for vehicle_ids , then the constraint is only applied to the specified vehicles. Otherwise, the constraint applies to all vehicles. When specifying the constraint, values for metric_id , min_metric_value , and max_metric_value must be given. The metrics are summed across all orders in the routes for the specified vehicle(s).

There are some cases where the duration of an order depends on who is servicing it. For example, a particular technician may complete a repair much faster than his/her colleagues. This variability can be expressed by using the work_speed parameter as a property of the shift. Since a vehicle can have multiple shifts, the work_speed parameter can be tied to the vehicle's operator instead of the vehicle itself.

In the example below, we illustrate a simple request where a manager explores the impact of "What if all my employees could work faster?" This can be achieved by trying different values of work_speed as shown below in the example vehicles array where a work_speed of 0.5 indicates that these workers are twice as fast as the default case.

Expand to view request sample

This experiment shows the manager that five more orders can be completed on this day if the workers are twice as fast since the 0.5 work_speed solution allows 22 order to be completed as opposed to 17 in the default case. The first image below shows the default work_speed 1 case. The second shows how additional orders are satisfied when workers are twice as fast.

img

A solution with work_speed = 1.0

img

A solution with work_speed = 0.5

Read article
Salesforce Developers

Order Level Constraints

There are solutions where items remain on a vehicle longer than desired in problems involving pickup and dropoff. Still, the solutions have shorter overall travel times. The additional_journey_time constraint controls consideration of these solutions. Additional journey time is the difference between an item's journey_time and the travel time directly from the pickup location to the delivery/dropoff location. The associated violation_increment is in seconds.

In the passenger pickup and dropoff example below, the journey_time , additional_journey_time , and dropoff_deadline constraints are used simultaneously. In the example, several vans start and end their routes at an Atlanta hotel. Each van has a six (6) passenger capacity expressed using the capacity_by_item array with passengers described as "items" using "item_type": "person" .

Expand to view request sample

img

The solution for this example does not violate any constraints. It utilizes all three (3) vehicles with a total travel time of approximately 7.5 hours. The longest journey for any passenger is short of one (1) hour. In contrast, removing the constraints and adding ones that enforce meeting pickup time windows and minimizing travel time, the solution requires two (2) vehicles and only six (6) hours of total travel time. Why would one not want a shorter overall travel time? Because in not considering the passengers' dropoff time, Mark and Oscar needlessly wait 3.5 hours at the airport before their eventual dropoff at the tennis tournament 5 hours later! This example illustrates many of the tradeoffs inherent in complex routing problems. Punishing customers with a terrible experience can be avoided with the right mix of constraints.


Prevent orders from being assigned to vehicles with attributes that are “undesirable” for some orders. The attributes_to_avoid are specified at the order level, and then vehicle attributes are compared against these values when evaluating the constraint. Thus there are no additional constraint parameters beyond the default. Violation increment has no impact on this constraint.

Expand to view request sample

img

Solution with no attempt to avoid incompatible attributes

img

We assign the attribute “Loud vehicle” to Vehicle 1, represented by the new solution's pink route. Many orders now request to avoid this attribute via the constraint, forcing the route for vehicle 1 to be very inefficient, traveling far from the start location to service orders. In particular, order 693192 boxed in red is right next to the start/end location for Vehicle 1. However, since this order has “Loud vehicle” in its attributes_to_avoid, Vehicle 1 does not visit it, forcing the green route to travel very far out of the way to hit this order.


Given an order with a dropoff_location_id , a dropoff_deadline enforces the latest time that the dropoff occurs. The associated violation_increment is in seconds.

In the passenger pickup and dropoff example below, the journey_time , additional_journey_time , and dropoff_deadline constraints are used simultaneously. In the example, several vans start and end their routes at an Atlanta hotel. Each van has a six (6) passenger capacity expressed using the capacity_by_item array with passengers described as "items" using "item_type": "person" .

Expand to view request sample

img

The solution for this example does not violate any constraints. It utilizes all three (3) vehicles with a total travel time of approximately 7.5 hours. The longest journey for any passenger is short of one (1) hour. In contrast, removing the constraints and adding ones that enforce meeting pickup time windows and minimizing travel time, the solution requires two (2) vehicles and only six (6) hours of total travel time. Why would one not want a shorter overall travel time? Because in not considering the passengers' dropoff time, Mark and Oscar needlessly wait 3.5 hours at the airport before their eventual dropoff at the tennis tournament 5 hours later! This example illustrates many of the tradeoffs inherent in complex routing problems. Punishing customers with a terrible experience can be avoided with the right mix of constraints.


The journey_time constraint specifies the maximum number of seconds between when an item is picked up and dropped off, delivered, or the route ends. For example, if refrigerated goods can only be on a vehicle for one hour before beginning to spoil, add the journey_time constraint with the max_journey_seconds parameter set to 3600. The associated violation_increment is in seconds.

In the passenger pickup and dropoff example below, the journey_time , additional_journey_time , and dropoff_deadline constraints are used simultaneously. In the example, several vans start and end their routes at an Atlanta hotel. Each van has a six (6) passenger capacity expressed using the capacity_by_item array with passengers described as "items" using "item_type": "person" .

Expand to view request sample

img

The solution for this example does not violate any constraints. It utilizes all three (3) vehicles with a total travel time of approximately 7.5 hours. The longest journey for any passenger is short of one (1) hour. In contrast, removing the constraints and adding ones that enforce meeting pickup time windows and minimizing travel time, the solution requires two (2) vehicles and only six (6) hours of total travel time. Why would one not want a shorter overall travel time? Because in not considering the passengers' dropoff time, Mark and Oscar needlessly wait 3.5 hours at the airport before their eventual dropoff at the tennis tournament 5 hours later! This example illustrates many of the tradeoffs inherent in complex routing problems. Punishing customers with a terrible experience can be avoided with the right mix of constraints.


Matches the attributes of an order with the attributes of the vehicle servicing the order. This can be used to enforce “skill matching” type constraints. Each order can be given a set of attributes. If any one of these attributes is not present in the vehicle's attributes that services this order, then a penalty is assessed. The violation_increment is in terms of the percentage points of the attributes matched in order. For example, suppose an order has five attributes, and three are matched by the vehicle that services it. In that case, 60% of the attributes are matched. A violation increment of 10 would mean that this scenario would incur a penalty of 4 times the original penalty amount since 40% of the attributes are unmatched and 40/10 =4.

Suppose some attributes are more important than others when assigning vehicles to orders. In that case, the constraint can assign different penalties at the attribute level. This is illustrated in the second example below.

Expand to view request sample

img

A solution to the original problem with no Match Attributes constraint.

img

Vehicle 1 (blue route) is assigned the attribute “speaks Spanish.” In contrast, Vehicle 4 (red route) has the attributes “speaks Russian” and “speaks Spanish.” Various order is now assigned these attributes, and we see that the blue route (vehicle 1) and red route (vehicle 2) now cover a much larger geographical area since the Match_Attributes constraints have a high penalty, effectively forbidding any vehicle from visiting these orders unless they have the correct attributes.

In this example, we have a more nuanced approach towards attribute matching. Our vehicles now have various attributes: paint, drywall, gutters, Charles, and Gavin. The skill (paint, drywall, or gutter) is enforced to match a very high penalty. The penalty for matching these attributes is higher than visit_range. The optimization will only visit an order if the skill is matched – visiting an order with inadequate skills incurs a higher penalty than missing to enforce this behavior. Additional Match_Attributes constraints enforce a “soft matching” with the preferred driver, either Gavin or Charles. These assignments are violated due to the lower penalty.

Expand to view request sample

img

In this example, the two unserved orders have the attribute “gutter.” The only route with the “gutter” attribute is the light blue route, which has less than a minute of extra time and can not visit any more orders. The pink route has 2.5 hours of slack time. Still, since the vehicle does not have the “gutter” attribute, the two unserved “gutter” orders are not visited by this vehicle.


Favor visiting high priority orders. If the priority p is greater than one and order with min_visits: m is visited k times in the solution with k < m , then we assess a penalty amount of (p – 1) * (m – k) . Thus, an order with a priority of 1 will not receive a penalty. Otherwise, the higher the order’s priority, the higher the penalty for not visiting at least min_visits times. No additional parameters are necessary for this constraint beyond the defaults as the priority information is part of each order object.

Expand to view request sample

img

Original solution with two vehicles and no order_priority constraint.

img

In the original two vehicle solution, we have 12 unvisited orders. We now add the order_priority constraint and specify a priority for many orders. In the resulting solution, we have 17 unvisited orders. Still, we visit all of the orders that have a priority greater than 1. In other words, we visit fewer customers but hit the important ones. Order 688798 at the bottom is boxed in black – we do not visit this order in the original solution since it is so far out of the way. However, the penalty for missing this priority ten order is now high enough that a lower overall score is obtained by adding this order to the solution.


There may be some cases where traversing a particular segment in a solution is undesirable (here, a segment refers to the path between two stops, not particular streets or roads). Such segments can be avoided by using the Prevent_Segment constraint, which takes in an array of pairs of location_ids and penalizes the solution if the segment connecting these pairs is present in the solution.

Expand to view request sample

img

The original four-vehicle solution before any segments is penalized.

img

The example introduces a Prevent_Segment constraint that penalizes links that start or end at location “loc36” (boxed in black) and the five other locations boxed in red. This results in the blue northeast route now traveling far out of the way since the Cumming order is effectively prevented from being serviced by the green route. This results in an overall increase in travel time, but all of these undesirable segments are avoided.


A scheduled appointment is more stringent than a time window. Appointments are expressed inside the order object, and they must include an appointment_start and appointment_end time. One can additionally specify a specific shift_id or a vehicle_id if the appointment should be satisfied by a particular shift or vehicle. Given some appointments at an order, service must begin precisely at the specified time and end at the specified time. Meeting an appointment can sometimes force the vehicle to idle/wait to meet the appointment, often resulting in fewer orders being visited due to the lack of flexibility in determining the routes. The scheduled_appointment constraint ensures that the appointment times given in each order are met – note that if appointments are given in the orders but there is no scheduled_appointment constraint, the appointments will virtually be ignored. To ensure that a specific shift or vehicle satisfies the appointment, one should invoke the scheduled_appointment_shift or scheduled_appointment_vehicle constraint. By applying a combination of these constraint types to a particular appointment, one can ensure that service at the order begins at the right time by a specific vehicle or shift. This technique can be useful when an existing schedule has been determined. A new disruptive event occurs - this leads to a so-called "schedule repair" problem. One of the considerations is to produce a new schedule that is "similar" to what was planned. By expressing this previously determined schedule as a set of appointments, one can generate a new optimization problem. Part of the objective is to adhere to this former plan.

Expand to view request sample

img

Shown above is the original two vehicle solution with no scheduled appointments. With two vehicles, we are left with 12 orders that cannot be feasibly visited.

img

Solution with scheduled appointments met at the orders with black boxes around them. This results in 14 unvisited orders vs. 12 unvisited in the case of 2 vehicles with no scheduled appointments. Also, note the pink route's relative inefficiency where stop three must be added to this route since a single-vehicle can't satisfy both of the scheduled appointments.


The span constraint allows us to ensure that the service at all orders in a provided set is completed within a specific time limit. The constraint offers an array of order_id ’s and a max_seconds value. The constraint is violated if the difference between the latest departure and earliest service starts exceeds max_seconds .

Expand to view request sample

img

The solution before adding the Span constraint.

img

In this example, we force a set of 9 orders in the center of Atlanta (inside the black region) to all be visited around the same time – the time between the earliest arrival and the latest departure must be <= 120 minutes. These orders are visited by two routes (cyan and purple), the earliest arrival being at and the cyan route, in particular, becomes relatively inefficient due to this constraint. Overall, travel time increases by about 30 minutes when we don’t have this constraint.


Individual orders can have time windows – intervals during which a vehicle must arrive and begin service. This constraint determines the importance of meeting time windows for each customer. By default, it applies to all orders. Still, if specific orders have more critical time windows, this constraint can be used multiple times for sets of order_ids. The constraint checks each order’s visit(s) against the time windows defined inside the order object.

Expand to view request sample

img

Original four-vehicle solution with no time window constraints

img

Shown above is the four vehicle solution after adding time window constraints. The bottom orange route changes substantially, and we can see backtracking in this route to satisfy the time windows. We add about an hour to the total travel time across all routes to satisfy all the time windows.


This constraint encourages the solution to visit orders with higher urgency values earlier on in the planning period. An order’s urgency must be in the range 1-99 and should be viewed as a percentile. An urgency of 90 means that we want to visit this order in the first 10% of the planning period. If violation_increment is specified, then an additional penalty is assessed for each percentile outside the desired range. So if the planning period is 10,000 seconds and an order has urgency 89, we will penalize a solution that has us visiting this order after ((100-89)/100)*10,000 = 1100 seconds. In this case, the violation increment is in percentage points.

Expand to view request sample

img

Original four-vehicle solution with no urgency enforced.

img

We add an urgency of 99 to 4 orders, indicating that we want them to be visited in the first 1% of the planning period's available time. These four orders now become one of the first two orders visited on the cyan and orange routes. This comes at the expense of increasing total travel time by about 90 minutes. Since it is impossible to visit all these orders in the first 1% of the planning period, we still incur a penalty from this constraint. However, since the constraint in the example utilizes violation_increment, a lower total score of the solution is obtained when we visit these orders as early as possible, even if we still violate the constraint.


The vehicle_coverage constraint allows one to specify that a small number of vehicles must visit a certain set of orders. Typically, this would be to force a set of orders to be covered by a single-vehicle. Still, it is flexible enough to handle more complex use cases. The constraint must specify a set of orders and values for min_vehicles and max_vehicles. If violation_increment is specified, then the units are expressed in the # of vehicles used to cover the set of orders. For example, if we have a penalty of 1000 with min_vehicles=1, max_vehicles=2, violation_increment=1, and four vehicles are used to service a set of orders. A penalty of 3000 will be assessed: 1000 for using too many vehicles, and an additional penalty of 2000 for exceeding the limit by 2.

Expand to view request sample

img

Original solution with no vehicle_coverage constraint.

img

Three widely spread orders (boxed in black) are added to the vehicle_coverage constraint with min_vehicles equal to 1 and max_vehicles equal to 1. The result is that Vehicle 1 now covers a huge territory and visits all three of these orders. Note that Vehicle 2 is now not used, leading to a very unbalanced solution in terms of the # stops per route and total travel time per route.


The visit_gap constraint will enable one to constrain these visits. The constraint can be restricted to a subset of orders if desired by specifying an optional order_id 's array, as shown below.

Ensure the spacing of visits at an order meets requirements. The gap between consecutive visits at a single order is measured as the difference in the first arrival time and the next arrival time. The constraint checks the visit spacing at each order against the values for min_days and max_days . If the amount of time between visits at an order falls outside this range, a penalty is assessed. The units of violation_increment are days.

In the full example below, we specify a problem with four vehicles where each vehicle has two shifts over two consecutive days. Many of the orders now require a minimum of two visits with a gap (min_days) of 1. If the visit gap constraint is not given, then the routes consecutively visit each of these orders that require two visits. This allows a solution with only three vehicles and another vehicle that is only active on one of the days. With the visit gap constraint in place, we must have at least one day (24 hours) between visits – all visit requirements are still met, but all eight shifts are required. The request below contains both the visit_range and Visit_Gap constraints.

Expand to view request sample

img

Shown above is the solution where no visit gap constraint is specified. All the orders that require multiple visits are now visited back to back on the route since there is no incentive to space out the visits. The vehicle starting at the northwest-most location is not needed at all.

img

The solution when we use both visit range and visit gap constraints. Visits to each customer location now do not occur within 24 hours of one another. All four vehicles are active on both days.


The visit_range constraint allows one to specify the number of times an order is visited. The constraint can be restricted to a subset of orders if desired by specifying an optional order_id 's array, as shown below.

Ensure an order receives a minimum or a maximum number of visits over the entire planning period. This constraint is particularly useful in problems that span multiple days where vehicles have numerous shifts. The default value of min_visits is 1 for any order. Suppose the visit range constraint is not included in a request. In that case, the optimization has no incentive to visit the orders. The default behavior would be not to visit any orders and return an empty solution. Since this is undoubtedly not the desired behavior, the user is protected if they do not include a visit range constraint. The optimization proceeds as if one wants to visit all the orders one time.

Suppose we use the default travel_time constraint so that one second of travel by a vehicle is equivalent to one penalty unit. In that case, we can use the visit range to express our problem as a revenue optimization problem. In the example below, we have two visit_range constraints – one for generic orders with a penalty of 1000 and another with a penalty of 40,000 for a set of “high profit” orders. Now the tradeoff is that for the specific order, if we must travel more than 2000 seconds out of the way to visit a location, we will choose not to do so. For the high-profit orders, if we must travel more than 40,000 seconds out of the way to hit these, we will decide not to do so. Suppose one has a dollar cost associated with a vehicle traveling 1 second and a dollar revenue amount for visiting each location. In that case, the objective function becomes an excellent proxy for the route's profit. The request below includes both visit range constraints (for the generic orders and the high-profit orders). Note that it is also possible to achieve this behavior with the order_priority constraint – here, we are just expressing this differently.

Expand to view request sample

img

When we account for revenue at the generic orders and do not treat any of the high-profit orders differently, note the unserviced orders boxed in red – these will be added to the second visit_range constraint in the next request.

img

After adding the second visit_range constraint for the high-profit orders, "constraint_name": "service high-profit orders" . Now note that all of the outlying orders missed in the first solution are now visited (green boxes above).

Read article
Salesforce Developers

CHANGELOG

Added

  • Details of the territory optimization service.
  • Introduced new constraints:
    • order_dependency
    • promptness
    • vehicle_attribute
    • vehicle_attribute_distribution
    • vehicle_attribute_duration_distribution
    • vehicle_balance
    • visit_range_across_shifts
  • Documented "easter egg" parameters which output debugging information. These parameters can be searched for using the phrase " FOR DEBUGGING ".
  • Unlimited mixing of vehicle types is supported. For example, one vehicle object can have a "type": "car" and another vehicle object can be "type": "truck" and so on.
  • Additional truck parameters:
    • num_trailers
    • weight_per_axle .
  • Where relevant, parameters now have default , minimum , and maximum .
  • OpenAPI Specification validators now included in pre-publication to ensure standardization followed.

Added

  • Documented the shift_duration_sum constraint
  • Documented the visit_same_location constraint
  • Documented the max_flights constraint
  • Added values for default constraint values when a request is sent without a constraints object

Changed

  • Updated max_distance docs to indicate 0 baseline is equivalent to minimizing distance travel
  • Corrected docs to indicate URLs expect one of /sync or /async
  • Clarified sources and destinations usage in matrix documentation
  • Clarified shifts description in routing
  • Corrected volume and weight descriptions in item object to indicate arbitrary units
  • Updated description of priority and urgency in order object
  • Updated directions description to reflect richness of response

Added

  • Published a "coverage status" map per country based on random matrix and routing tests
  • Added a strict, finite request/response data retention policy of maximum 90 days

Changed

  • Improved driving directions for mainland China
  • Fixed bug related to floating breaks some times not being honored
  • Improved handling of null values in request and updated to a meaningful error message.

Added

  • Routing optimization requests can now contain multiple vehicles of type: "truck" each with different parameters, e.g., height , weight , volume_capacity , etc. The routes for each truck are guaranteed to be compliant for that truck's parameters.
  • Standardized the expression of driving directions and polylines across all regions, including China and Japan.
  • Verbose driving directions included for all routing responses.

Added

  • Addition of a work_speed parameter to the shift object which controls the speed of work at an order. This parameter helps account for historical variations of technicians work speed versus the baseline duration one expects to complete an order.

    The default value is one (1). When set to a value other than 1, the duration at any order_id serviced during the shift is longer/shorter than the stated duration of the order. For example, "work speed": 1.2 results in the order taking 20% longer to complete.

  • Additional info incorporated into the response for problems involving drop-offs. Each stop in the route object's stops array now includes an array of order_ids_dropped_off .

  • New constraints to handle appointments:

    • scheduled_appointment_shift
    • scheduled_appointment_vehicle
  • New constraints for problems involving drop-offs:

    • journey_time
    • additional_journey_time
    • dropoff_deadline

Changed

  • Minor bugfixes in lesser used constraints involving journey time
  • In visit_gap constraint, time intervals expressed via seconds as well as days by using min_seconds and max_seconds to express desired visit spacing. Previously allowed only min_days and max_days .

Added

  • Documentation for existing constraints shown in examples but not explicitly noted in technical documentation.

Removed

  • Removed num_visits constraint since it is redundant with the visit_range constraint.

Added

  • New Max_Commute constraint added to handle first and last legs of routes
  • Optional rounding_minutes added to the round start of service events to nearest k minutes
  • For matrix calls with no path between source/end locations, added count and warning message to response

Changed

  • Updated worldwide map with latest street network and traffic data
  • A more cost-effective and efficient method of traffic window interpolation and storage
  • Improved error checking for errors in input requests (e.g., empty orders, invalid parameters)
  • Improved handling of complex pickup/delivery/-drop-off/replenishment problems
  • Improved handling of truck routing with changes to underlying map service
  • For cases of non-obvious input in routing JSON, changed HTTP return code from 409 to 422
  • Bug fixed in output JSON for items_delivered and items_picked up in pickup/delivery problems

Changed

  • Enforce the requirement that all vehicles with type truck have identical dimensions. Previously, the routing endpoint in the Optimization API accepted mixed dimension fleets; Now, the routing endpoint in the Optimization API responds with an error.

Added

  • Enforce requirement that all vehicles in a problem be the same type vehicle, i.e., do not allow the mixed fleet problem.
  • Submitting a request with an empty vehicle array now results in an error response.

Changed

  • Updated the behavior of the Visit Sequence constraint.
  • Solutions are now deterministic for repeatable behavior.

Added

  • Forced route structures are now supported

Added

  • A constraint for limiting distance traveled from a home location.

  • A constraint for handling orders at the same physical location, e.g., apartment buildings.

  • Handling of hard, soft, and floating breaks.

  • A constraint for handling orders at the same physical location, e.g., apartment buildings.

  • Handling of hard, soft, and floating breaks.

Added

  • Initial major release of all functionality.
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!