4
$\begingroup$

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!

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Then, let’s invite @LocalSolver here first of all. Interestingly, Python doesn’t complain about TT[i,j], although I also expected it to throw an error all the time. My keys are in the form of (i, j), and yet it doesn’t care about those parentheses. Saying these, I will make those changes as a good practice. For the global time span, I actually do not want to include service times in the objective; I just wanted to make sure it doesn’t. Overall, I really appreciate for all the time given to solve this problem! $\endgroup$
    – tcokyasar
    May 13, 2021 at 19:22
  • $\begingroup$ From this page (developers.google.com/optimization/routing/cvrp), I feel like the number of vehicles needs to be an input, which is not a big deal. But, considering the problem size, I wouldn't want to iteratively solve this problem for number of vehicles = 1,2,3... $\endgroup$
    – tcokyasar
    May 13, 2021 at 19:39
  • 1
    $\begingroup$ Yes, what you can do is feed the solver an upper bound on the number of vehicles (e.g., the number of nodes), and or tools will just ignore the ones that are not necessary. $\endgroup$
    – Kuifje
    May 13, 2021 at 19:45
  • 1
    $\begingroup$ @Kuifje This is nice of you to cite LocalSolver. Thank you very much. I think indeed that LocalSolver will be good for such a problem, even for large networks. You can start from the 20-line CVRP example in Python localsolver.com/docs/last/exampletour/vrp.html and then iterate to add your additional time constraints. We will be glad to help you in doing so. $\endgroup$ May 14, 2021 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.