5
$\begingroup$

I am trying to model a min-max VRP problem with multiple delivery vehicles and I have come up with a model using branch and cut but I do not think it is strong enough as it takes lot of time to converge.

Is there any model which is basic enough to implement (I can implement branch and cut). What I mean is not something like genetic algorithms or ant-colony kind of things. Just a simple MILP model with cut generation to eliminate sub-tours. I do not have capacity constraints or time windows. I just need to minimize the maximum travel distance.

I can provide my model if it is necessary

Improve this question
$\endgroup$
  • $\begingroup$ Feel free to check out VRPy (github.com/Kuifje02/vrpy), a python framework for such problems. Although min max is not directly implemented, it can be done easily (submit an issue if you don't know how to). It is all open source. $\endgroup$ – Kuifje Aug 6 '20 at 18:53
  • $\begingroup$ @Kuifje I want to do it using Gurobi. But thanks for the info. Edit: I also think they use column generation $\endgroup$ – Morpheus Aug 6 '20 at 19:14
  • $\begingroup$ @Morpheus Such a min-max problem is really hard to model and solve using MILP solvers. If you are open to something new, then you can try LocalSolver, a commercial solver like Gurobi. A ready-to-use CVRP model can be found at localsolver.com/docs/last/exampletour/vrp.html. Your min-max objective is just one line to change in this model. You will obtain state-of-the-art solutions in minutes for hundreds of clients to deliver. $\endgroup$ – LocalSolver Aug 7 '20 at 9:41
  • $\begingroup$ @LocalSolver Thanks for the info. I am trying to do it by the open source route. You can probably find the problem I am trying to solve here (problem 7) books.google.ch/… $\endgroup$ – Morpheus Aug 7 '20 at 9:50
  • $\begingroup$ I have a model which works fine for smaller instances but struggles badly for bigger instances. I was just hoping if there is a stronger model. $\endgroup$ – Morpheus Aug 7 '20 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.