Path Equalizer

In complex vehicle routing scenarios, it's common for optimization algorithms, focused solely on minimizing total cost, to produce unbalanced routes. For example, one vehicle might be assigned a long, 8-hour route while another gets a short, 3-hour route. This can lead to issues with driver fairness, overtime costs, and inconsistent vehicle utilization.

The Path Equalizer is a specialized heuristic designed to address this by promoting a more equitable distribution of workload (measured in travel time or distance) across all vehicles in the fleet.

Purpose of the Path Equalizer

The primary goal of the Path Equalizer is to minimize the variance between route durations or distances. Instead of letting one driver work a significantly longer day than another, the Path Equalizer encourages a solution where all drivers have a more similar workload.

This contributes to:

• Improved Driver Fairness: Prevents situations where some drivers are consistently overworked while others are underutilized.
• Operational Predictability: Leads to more consistent end-of-shift times for the entire fleet.
• Better Resource Utilization: Ensures that the vehicle fleet's capacity is used more evenly.

How It Works: The Balancing Act

When activated, the Path Equalizer introduces an additional "fairness" cost into the solver's total cost calculation. This cost is based on how much each vehicle's route length deviates from the average route length.

The solver then works to minimize this fairness cost alongside all other costs (like travel time, vehicle usage, and penalties). To do this, it strategically reassigns stops between vehicles. It might move a stop from a vehicle with a very long route to one with a shorter route, even if it slightly increases the total travel distance for the fleet, because the reduction in the "fairness" penalty makes it a better overall solution.

Example Scenario:

Imagine two vehicles, A and B, with the following initial routes:

• Vehicle A: Total travel time = 8 hours
• Vehicle B: Total travel time = 4 hours

With the Path Equalizer enabled, the solver might identify that moving a few of Vehicle A's stops to Vehicle B's route results in a more balanced plan:

• Vehicle A (Adjusted): Total travel time = 6.5 hours
• Vehicle B (Adjusted): Total travel time = 6 hours

While the total fleet travel time might have increased slightly (from 12 to 12.5 hours), the routes are now much more balanced, which was the goal.

Implementation in the Stateless API

The Path Equalizer is configured within the model_parameters of your Stateless API request.

"model_parameters": {
    ...
    "use_path_equalizer": true,
    "path_equalizer_weight": 1000,
    ...
}

Parameters

1. use_path_equalizer (boolean, optional):

   • Set this to true to activate the Path Equalizer heuristic.
   • By default, it is false.

2. path_equalizer_weight (number, optional):

   • This parameter controls how strongly the solver should prioritize fairness. It defines the weight of the penalty for unbalanced routes.
   • A higher weight tells the solver that route balance is very important, and it should be willing to accept higher travel costs to achieve it.
   • A lower weight tells the solver to prioritize fairness but not at the expense of significant increases in other costs.
   • Finding the right value often requires experimentation to achieve the desired balance between route equity and overall efficiency for your specific operation.

警告

Activating the Path Equalizer introduces a trade-off. While it creates more balanced routes for individual vehicles, it may lead to a slight increase in the total travel time or distance for the entire fleet.

Playground

You can try out the Path Equalizer concept using the playground below. The example defines two vehicles and two clusters of jobs. The use_path_equalizer parameter is set to true with a high weight to encourage balanced routes. Try changing use_path_equalizer to false to see how the solver might otherwise assign routes based purely on cost/distance.

Loading...