heterogeneous fleet issue

[Nicolas Collignon]

Hello,

I've been trying to solve a VRP problem with vehicles of different speeds and capacities with multiple returns to depot possible.

This github issue helped to get me started.

For some reason, the solver seems to strongly favour vehicles with larger capacity,  ignoring the speed advantage, and outputs suboptimal solutions.

If I run the solver with two vehicles and one has a slightly lower capacity but faster speed,  then most of the jobs are assigned to the other vehicle (larger capacity and slow).

To take different speeds into account I'm passing weighted matrices to the distance callback.

Here's an output for equal capacity:

> vehicle 0 (speed: 10, capacity: 100): 21 stops. duration: 113 min. total load: 61

> vehicle 1 (speed: 25, capacity: 100): 86 stops. duration: 144 min. total load: 300

--> duration of trips is similar, as expected

Here's the output when changing the capacity slightly:

> vehicle 0 (speed: 10, capacity: 100): 76 stops. duration: 282 min. total load: 262

> vehicle 1 (speed: 25, capacity: 99): 30 stops. duration: 56 min. total load: 99

--> very different duration of trips here

Any thoughts and tips would be appreciated!

My code is below:

# keep transit callback alive
transit_callback = []
transit_callback_index_arr = []
for vehicle_id in range(data['num_vehicles']):
    distance_matrix = data['distance_matrix'][vehicle_id]

    # Use default value to capture distance_matrix current value
    def distance_callback_vehicle(from_index, to_index, data=distance_matrix):
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return int(data[from_node][to_node])

    transit_callback.append(distance_callback_vehicle)
    transit_callback_index_arr.append(routing.RegisterTransitCallback(transit_callback[-1]))
                                     
for vehicle_id in range(data['num_vehicles']):
    routing.SetArcCostEvaluatorOfVehicle(transit_callback_index_arr[vehicle_id], vehicle_id)

# Add Distance constraint.
dimension_name = 'Distance'
routing.AddDimensionWithVehicleTransits(
    transit_callback_index_arr,  # list of transit callback, one per vehicle
    0,  # no slack
    300000,  # vehicle maximum travel distance
    True,  # start cumul to zero
    dimension_name)

distance_dimension = routing.GetDimensionOrDie(dimension_name)
# makes the global span the predominant factor in the objective function
# (minimizes the length of the longest route)
distance_dimension.SetGlobalSpanCostCoefficient(100)

# # Add Capacity constraint
demand_evaluator_index = routing.RegisterUnaryTransitCallback(create_demand_evaluator(data, manager))
add_capacity_constraints(manager,routing, data, demand_evaluator_index)

[Nicolas Collignon]

Hi again,

It'd be great to have some feedback on this. I was thinking it might help to first optimise with the faster / lower capacity vehicle first, and then pass this initial solution to the full problem with the other vehicle(s)?

Thanks,

[Mizux Seiha]

I'm not sure you should use
```
distance_dimension.SetGlobalSpanCostCoefficient(100)
```
this will give incentive to the solver to minimize the longest route aka use a large capacity vehicle than doing multiple trips with a faster vehicles.

If I were you I would disable this constraint or I'd put this constraint on a time dimension instead...

[Nicolas Collignon]

Thanks a lot for your answer :)

 I tried to remove SetGlobalSpanCostCoefficient and I got the same result. My distance matrix is effectively using time as unit since I'm scaling the distances using the respective vehicle speeds.

I.e. in my data model, I do the following:

    # takes distance matrix in meters and outputs time matrices
    dms = []
    for v in range(n_vehicles):
        tm = np.round(distance_m/speeds[v]*60)
        dms.append(tm)
   
    data["distance_matrix"] = dms

From doing more experiments, my hunch is that when vehicles have different capacities only one of them is able to reload. I'm not sure why that would be the case.