Using VRPy and OR-tools in Python to solve the DCVRP

Question

This question is a follow-up to this one.

Since I understand the complexity of the problem I have been underestimating, I turned my attention to off-the-shelf solvers, like VRPy and OR-tools. I would like to use these tools either to completely solve the problem or to obtain a heuristic solution to feed into the formulation provided in here. The size of the problem I am trying to deal with is around 1,000-1,500 nodes, single depot, single vehicle type, node varying demand and service time, and fixed load capacity and tour durations.

To solve the problem with VRPy in Python, I coded is as follows, and I want to make sure it is coded correctly. Another concern is that does VRPy minimize only the travel time or does it include the service time?

from networkx import DiGraph
from vrpy import VehicleRoutingProblem
G = DiGraph()
for i, j in TT.keys():
    if i != j:
        if i == Depot_loc:
            k = "Source"
        else:
            k = i
        if j == Depot_loc:
            l = "Sink"
        else:
            l = j
        G.add_edge(k, l, cost = TT[i,j], time = TT[i,j])
for j in [i for i in I if i != Depot_loc]:
    G.nodes[j]["demand"] = 3
    G.nodes[j]["service_time"] = 100
prob = VehicleRoutingProblem(G, load_capacity=120, duration = 36000)
prob.solve()

Here, TT is a dictionary keyed by a tuple of node indices and valued as the travel time between all nodes (including the depot, represented by $I$), and the Depot_loc is the index for depot. In TT, TT[i,j] = 0, when $i=j$. For simplicity, I assume all nodes demand 3 units to be delivered, and the service time at all nodes are 100 seconds (so, a vehicle arriving at a node will spend 100 seconds additional to driving times). I further assume, each vehicle can carry 120 units, and the total tour time for each should not exceed 36,000 seconds.

I thought over the OR-tools application in Python but found it a bit complicated to implement. Your help for comparison is appreciated!

Answer 1

1 500 nodes is a lot... don't expect any MILP solver to find decent solutions quickly (or at all). See for example @LocalSolver's benchmarks. Which brings me to my next point: for big graphs, maybe LocalSolver is the way to go.

I also think its worth giving or tools a try. The API is not that user friendly (in my opinion), but the optimization engine is powerful, and its all free. Also, the examples are very useful and well documented. Your example would be quite straightforward to implement.

Now if you insist on wanting to use VRPy, I am not going to argue, but don't expect good performances with such graphs.

The Python code looks good, except for TT[i,j], I am pretty sure you will get an error. Instead use TT[(i,j)].

Note that if you constrain the routes to have maximum duration, the route duration does include the travel time, and the service time, which is logical.

You can also minimize the global time span with VehicleRoutingProblem(minimize_global_span=True). This may however have an impact on computation times, because the linear relaxation of the formulation becomes weak. This was discussed in this post some time ago.