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
Original solution with no
first_visit
constraint.
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
Shown above is the original four-vehicle solution without the home radius constraint.
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
Original four-vehicle solution without the
last_visit
constraint
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
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.
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
The four-vehicle solution before adding the
max_distance
constraint.
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
Shown above is the original four-vehicle solution with no penalties for long segments.
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
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.
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
The solution before adding the
shift_duration
constraint.
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
The original solution before adding the Visit_Sequence constraint
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.
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.
