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.
Four vehicle solution with all orders visited and travel time constraint included so that routes are efficient from a travel perspective.
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
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.
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
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.
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
Shown above is the original four-vehicle solution with no restriction on which items can be mixed on the route.
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.
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.
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.
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.