Distance Ratio Constraint

Optimizing route directness is crucial for balancing operational costs and carrier agreements. The distance ratio constraint allows planners to control how much a route can deviate from the most direct path, ensuring efficiency and cost predictability.

Impact on Route Planning:

The distance ratio constraint in the Vehicle Routing Problem (VRP) imposes a limit on the circuity of a route. It ensures that the actual distance traveled by a vehicle does not exceed a specified multiple of the direct distance to the furthest point. This constraint is vital for:

Cost Control: Prevents excessive mileage and fuel consumption by disallowing highly circuitous routes.
Carrier Compliance: Aligns with 3PL payment models often based on direct distance, ensuring the payer doesn't subsidize inefficient routing.
Service Quality: Reduces travel time for goods, potentially leading to faster deliveries and less wear on cargo.

Distance Ratio:

The distance ratio is defined as the ratio between the total actual distance of the route and the direct distance from the depot to the furthest delivery location.

\text{Distance Ratio} = \frac{\text{Total Distance}}{\text{Direct Distance to the farthest store}}

The ratio is a constant applied to all vehicles.

One-way trip: Minimum ratio is 1.
Round trip: Minimum ratio is 2 (since the vehicle must return).

A lower ratio forces tighter, more direct routes, while a higher ratio allows for more detours to visit intermediate stops.

Example:

Consider a logistics company contracting a 3PL fleet. The 3PL is paid based on the "Direct" distance from the Distribution Center (DC) to the furthest drop-off point. If the driver takes a winding route to hit many scattered stops, the actual distance might be 300km, but the direct distance is only 100km.

Without a constraint, the company might pay for 100km worth of value but incur 300km worth of operational wear or time. By setting a total_to_furthest_distance_ratio, the company enforces that the route length cannot exceed, for example, 2.5 times the direct distance.

Visualizing Tightness:

The "tightness" of a route refers to how closely it adheres to the direct path between the depot and the furthest stop.

Distance Ratio Tightness

Ratio ~2 (Tight): The route is very narrow. The vehicle travels almost directly to the furthest point and back, with stops located very close to this direct line. This is efficient for distance but limits the number of reachable stops.
Ratio ~2.5: The route begins to widen, allowing for stops that are slightly further off the direct path.
Ratio ~3 (Flexible): The route forms a wide "diamond" shape. The vehicle can deviate significantly to visit scattered stops, covering a broader area but increasing total mileage relative to the direct distance.

tip

This constraint is a hard limit. For a similar soft contraint refer to route compactness

Implementation

The constraint is controlled by the total_to_furthest_distance_ratio parameter within solver_parameters.

The solver enforces that: Total Route Distance <= ratio * Distance(Pickup, Furthest Delivery Node)

It can be configured as follows:

"solver_parameters": {
  "algorithm": "static",
  "first_solution_strategy": 3,
  "solution_limit": 100000000,
  "use_local_search_metaheuristic": true,
  "guided_local_search_lambda_coefficient": 0.95,
  "use_tsp_opt": false,
  "time_limit_ms": 600000,
  "log_search": true,
  "lns_time_limit_ms": 1000,
  "savings_neighbors_ratio": 0.0,
  "waypoints_optimization_second_phase": false,
  "waypoints_solution_limit": 1000,
  "total_to_furthest_distance_ratio": 2.5
}

warning

For round trips, a ratio close to 2.0 is extremely restrictive and may result in unassigned jobs if the stops are not perfectly aligned. A value between 2.2 and 3.0 is typically a good starting point for balancing efficiency and feasibility.

Implementation​

Implementation