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.

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.

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.

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.

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.

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, adropoff_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 acapacity_by_item of 6 for each vehicle).

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.