Take the point of view of the passenger, part two 2024-10-08

There was a recent question on the OR-Tools forum that asked how to minimize a passenger’s in-vehicle travel time. I summarized what I had done in the past in my previous entry. The OP replied in the final post in the thread that Mizux’s suggestion to use SetPathEnergyCostOfVehicle() was the best solution. I’ve never used that before, so in this post I am revisiting my previous post using that new function.

What is this function?

The function SetPathEnergyCostOfVehicle() was first seen in the git commit logs for the OR-Tools project in May of 2023. So it is not exactly new, but at the same time, it isn’t very old either. I haven’t done much work lately with the routing solver, so I didn’t notice when it popped up.

The function’s documentation and signature are as follows:

  // Sets the energy cost of a vehicle.
  // The energy used by a vehicle is the integral of the force dimension over
  // the distance dimension: it is the sum over nodes visited by the vehicle of
  // force.CumulVar(Next(node)) * distance.TransitVar(node).
  // The energy cost of a vehicle is linear in the energy used by the vehicle,
  // this call sets the coefficient to unit_cost, it is zero if unset.
  void SetPathEnergyCostOfVehicle(const std::string& force,
                                  const std::string& distance,
                                  int64_t unit_cost, int vehicle);

The arguments are two strings, a per-unit cost, and a vehicle number. The first string represents the “force” dimension, and the second string represents the distance dimension. The idea is that it requires a higher cost to transport more goods over the same distance or for the same time. This can be used to model heavy vehicles, or in this case, to reduce the numbers of passengers in a vehicle at the same time.

Using the function

In my simple example program, I have a distance dimension and a capacity dimension. So of course the capacity is the “force” dimension, and the distance is the “distance” dimension. For simplicity’s sake, I set the unit cost to be 1.

# set up the PathEnergyCostOfVehicle using capacity and distance dimensions
for vehicle_id in range(data["num_vehicles"]):
    routing.SetPathEnergyCostOfVehicle("Capacity", "Distance", 1, vehicle_id)

This means that all else being equal, the solver will prefer to have an empty vehicle moving longer distances, and a full vehicle moving shorter distances. This is not quite the same as minimizing the travel time from the perspective of each traveler, but it accomplishes the same thing.

As a digression, often the rationale behind buying larger vehicles is to be able to use them with larger loads. A big bus with one driver can in theory be more efficient than a little bus with one driver, as the fixed cost of the driver is the same in both cases. In a sense, this API call does the opposite. It tries to use as little of the capacity in a vehicle as possible, because using more of the capacity is more expensive. But this also matches up with what we see in real life. Everyday I see cars go by with extra room for passengers, but carrying only the driver, and monstrous pickups with capacious but generally empty truck beds. The capacity exists, but (apparently) using it is expensive and undesirable.

Results

In my previous write up, I relied on hacks related to minimizing distances at the delivery node of a passenger. Because distance is not time, I couldn’t quite use time window tricks to improve this. Still, the result was satisfactory because the absolute distance value for each passenger at the end was minimized:

Objective: 5296
Dropped nodes:
Route for vehicle 0:
 0 Load(0) Distance(0) ->
 1 Load(1) Distance(548) ->
 3 Load(0) Distance(1096) ->
 0 Load(0)
Distance of the route: 1096m
Load of the route: 0

Route for vehicle 1:
 0 Load(0) Distance(0) ->
 2 Load(1) Distance(776) ->
 4 Load(0) Distance(1552) ->
 0 Load(0)
Distance of the route: 1552m
Load of the route: 0

Total Distance of all routes: 2648m

In my new version, with the energy API call but without the hack related to minimizing the distance at the drop off node of each passenger, the result is:

Objective: 3788
Dropped nodes:
Route for vehicle 0:
 0 Load(0) Distance(0) ->
 2 Load(1) Distance(776) ->   # Pickup
 1 Load(2) Distance(1460) ->  # Pickup
 4 Load(1) Distance(2008) ->  # Dropoff
 3 Load(0) Distance(2008) ->  # Dropoff
 0 Load(0)
Distance of the route: 2008m
Load of the route: 0

Route for vehicle 1:
 0 Load(0) Distance(0) ->
 0 Load(0)
Distance of the route: 0m
Load of the route: 0

Total Distance of all routes: 2008m
Total Load of all routes: 0

So this is objectively worse for the passenger at node 2, as she now needs to travel to pickup the passenger at node 1, then travel to the depot. However, the overall travel distance is better at 2008, rather than 2648.

My next question was whether the energy penalty could be pushed enough to cause the first passenger to be dropped off before picking up the second passenger. The answer is 2; the smallest possible increase in the weight causes the solver to prefer pickup then drop off of each passenger individually. The second vehicle is not used, of course, as there are no real limits on the vehicles' total travel. But the solution is certainly passenger-optimal now.

Objective: 5296
Dropped nodes:
Route for vehicle 0:
 0 Load(0) Distance(0) ->
 2 Load(1) Distance(776) ->   # Pickup
 4 Load(0) Distance(1552) ->  # Dropoff
 1 Load(1) Distance(2100) ->  # Pickup
 3 Load(0) Distance(2648) ->  # Dropoff
 0 Load(0)
Distance of the route: 2648m
Load of the route: 0

Route for vehicle 1:
 0 Load(0) Distance(0) ->
 0 Load(0)
Distance of the route: 0m
Load of the route: 0

Total Distance of all routes: 2648m

A larger problem

Moving on to the larger problem with many pickups and dropoffs, and with a more varied quantity of passengers to pickup at each node, analyzing the solution is more complex.

The first pass with a weight of 1 again uses just a single vehicle, but seems to do a reasonable job of minimizing loaded flows.

Objective: 23870
Dropped nodes:
Route for vehicle 0:
 0 Load(0) Distance(0) ->
 7 Load(8) Distance(194) ->
 19 Load(0) Distance(388) ->
 2 Load(1) Distance(1164) ->
 6 Load(7) Distance(1438) ->
 8 Load(15) Distance(1632) ->
 14 Load(14) Distance(1940) ->
 18 Load(8) Distance(1940) ->
 20 Load(0) Distance(1940) ->
 5 Load(3) Distance(2214) ->
 17 Load(0) Distance(2488) ->
 1 Load(1) Distance(3036) ->
 3 Load(4) Distance(3344) ->
 4 Load(10) Distance(3458) ->
 16 Load(4) Distance(4040) ->
 15 Load(1) Distance(4040) ->
 13 Load(0) Distance(4040) ->
 10 Load(2) Distance(4576) ->
 9 Load(3) Distance(4918) ->
 21 Load(2) Distance(5112) ->
 22 Load(0) Distance(5112) ->
 11 Load(1) Distance(5614) ->
 12 Load(3) Distance(5728) ->
 23 Load(2) Distance(6116) ->
 24 Load(0) Distance(6116) ->
 0 Load(0)
Distance of the route: 6116m
Load of the route: 0

Route for vehicle 1:
 0 Load(0) Distance(0) ->
 0 Load(0)
Distance of the route: 0m
Load of the route: 0

Total Distance of all routes: 6116m

Bumping up the weight to 2 slightly increases the total travel distance, but not significantly. The majority of the sojourns visit multiple nodes before returning to the depot to perform the drop off events.

Objective: 41260
Dropped nodes:
Route for vehicle 0:
 0 Load(0) Distance(0) ->
 1 Load(1) Distance(548) ->
 7 Load(9) Distance(902) ->
 13 Load(8) Distance(1096) ->
 19 Load(0) Distance(1096) ->
 2 Load(1) Distance(1872) ->
 6 Load(7) Distance(2146) ->
 8 Load(15) Distance(2340) ->
 14 Load(14) Distance(2648) ->
 18 Load(8) Distance(2648) ->
 20 Load(0) Distance(2648) ->
 5 Load(3) Distance(2922) ->
 17 Load(0) Distance(3196) ->
 3 Load(3) Distance(3892) ->
 4 Load(9) Distance(4006) ->
 16 Load(3) Distance(4588) ->
 15 Load(0) Distance(4588) ->
 10 Load(2) Distance(5124) ->
 9 Load(3) Distance(5466) ->
 21 Load(2) Distance(5660) ->
 22 Load(0) Distance(5660) ->
 11 Load(1) Distance(6162) ->
 12 Load(3) Distance(6276) ->
 23 Load(2) Distance(6664) ->
 24 Load(0) Distance(6664) ->
 0 Load(0)
Distance of the route: 6664m

However, with the larger problem set, it is not possible to convince the solver to choose a solution with individual pickups and dropoffs for each node. Even increasing it to 10000 gave exactly the same result as increasing it to 2, just with a much higher objective value:

Objective: 172986664
Dropped nodes:
Route for vehicle 0:
 0 Load(0) Distance(0) ->
 2 Load(1) Distance(776) ->
 6 Load(7) Distance(1050) ->
 8 Load(15) Distance(1244) ->
 14 Load(14) Distance(1552) ->
 18 Load(8) Distance(1552) ->
 20 Load(0) Distance(1552) ->
 1 Load(1) Distance(2100) ->
 7 Load(9) Distance(2454) ->
 19 Load(1) Distance(2648) ->
 13 Load(0) Distance(2648) ->
 5 Load(3) Distance(2922) ->
 17 Load(0) Distance(3196) ->
 3 Load(3) Distance(3892) ->
 4 Load(9) Distance(4006) ->
 16 Load(3) Distance(4588) ->
 15 Load(0) Distance(4588) ->
 10 Load(2) Distance(5124) ->
 9 Load(3) Distance(5466) ->
 21 Load(2) Distance(5660) ->
 22 Load(0) Distance(5660) ->
 11 Load(1) Distance(6162) ->
 12 Load(3) Distance(6276) ->
 23 Load(2) Distance(6664) ->
 24 Load(0) Distance(6664) ->
 0 Load(0)
Distance of the route: 6664m
Load of the route: 0

Route for vehicle 1:
 0 Load(0) Distance(0) ->
 0 Load(0)
Distance of the route: 0m
Load of the route: 0

Total Distance of all routes: 6664m

My guess is that the solver is not really rejiggering all of the node values to reflect different choices. That would be incredibly slow. My guess is that the solver is still the same basic routing solver under the hood, with perhaps a slightly augmented decision tree that allows for one or two more options to represent different values of the “force” dimension at a node. But the force dimension is not allowed to run through its full gamut.

Either that, or the routing component is still primary. It might be the case that the solver generates a decent route, and then uses that route to set up the first set of candidate values for the force dimension at each node.

(I could read the C++ to figure it out, but where’s the fun in that?)

The conclusion as far as I’m concerned is that this energy value API is great, but it is still not a dimension-dependent dimension. It still works best in conjunction with other tricks. For example, if I turn back on the requirement that passengers minimize the distance at their destination, the result is this:

Objective: 173006816
Dropped nodes:
Route for vehicle 0:
 0 Load(0) Distance(0) ->
 7 Load(8) Distance(194) ->
 19 Load(0) Distance(388) ->
 11 Load(1) Distance(890) ->
 12 Load(3) Distance(1004) ->
 24 Load(1) Distance(1392) ->
 23 Load(0) Distance(1392) ->
 3 Load(3) Distance(2088) ->
 4 Load(9) Distance(2202) ->
 15 Load(6) Distance(2784) ->
 16 Load(0) Distance(2784) ->
 10 Load(2) Distance(3320) ->
 22 Load(0) Distance(3856) ->
 0 Load(0)
Distance of the route: 3856m
Load of the route: 0

Route for vehicle 1:
 0 Load(0) Distance(0) ->
 9 Load(1) Distance(194) ->
 21 Load(0) Distance(388) ->
 2 Load(1) Distance(1164) ->
 6 Load(7) Distance(1438) ->
 8 Load(15) Distance(1632) ->
 18 Load(9) Distance(1940) ->
 20 Load(1) Distance(1940) ->
 14 Load(0) Distance(1940) ->
 5 Load(3) Distance(2214) ->
 17 Load(0) Distance(2488) ->
 1 Load(1) Distance(3036) ->
 13 Load(0) Distance(3584) ->
 0 Load(0)
Distance of the route: 3584m
Load of the route: 0

Total Distance of all routes: 7440m

This solution has a lot more cases in which passengers are taken directly from pickup to dropoff, and, as expected, a slightly longer overall distance measure over all routes. I need to exercise this function more, and perhaps dig into the C++ before I use it for a paying customer, but it certainly is a helpful addition to the routing solver API.