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
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
Solution with no attempt to avoid incompatible attributes
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
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
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
A solution to the original problem with no Match Attributes constraint.
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
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
Original solution with two vehicles and no
order_priority
constraint.
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
The original four-vehicle solution before any segments is penalized.
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
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.
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
The solution before adding the Span constraint.
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
Original four-vehicle solution with no time window constraints
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
Original four-vehicle solution with no urgency enforced.
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
Original solution with no
vehicle_coverage
constraint.
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
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.
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
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.
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).
