Route Level Constraints

First Visit

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.


Home Radius

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.


Last Visit

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.


Maximum Commute

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.


Maximum Distance

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).


Maximum Segment

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).


Number of Stops

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.


Route Balance

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.


Shift Duration

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.


Visit Sequence

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.