5

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

Morpheus
  • 253
  • 1
  • 5
  • Feel free to check out VRPy (https://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. – Kuifje Aug 06 '20 at 18:53
  • @Kuifje I want to do it using Gurobi. But thanks for the info. Edit: I also think they use column generation – Morpheus Aug 06 '20 at 19:14
  • @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 https://www.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. – Hexaly Aug 07 '20 at 09:41
  • @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) https://books.google.ch/books?id=LybZDwAAQBAJ&pg=PA243&lpg=PA243&dq=two+cyclists+must+deliver+newspapers+in+manhattan&source=bl&ots=QzWlrUWZGv&sig=ACfU3U2bTjUjjB-b9i5b-qUNwSAmTgQMLg&hl=en&sa=X&ved=2ahUKEwiIn4226IjrAhXKyYUKHXc2DXoQ6AEwAHoECAoQAQ#v=onepage&q=two%20cyclists%20must%20deliver%20newspapers%20in%20manhattan&f=false – Morpheus Aug 07 '20 at 09:50
  • 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. – Morpheus Aug 07 '20 at 09:52
  • @Morpheus Just so you know, VRPy is interfaced with Gurobi. As LocalSolver said, it is a one liner there too if I am not mistaken. A similar example to your problem 7 is described here:https://vrpy.readthedocs.io/en/dev/examples.html#an-example-borrowed-from-ortools . Also note that or-tools is another good open source option for such problems. – Kuifje Aug 07 '20 at 13:35
  • @Kuifje Thanks! I will look into it. If I have any trouble, I will ask you again – Morpheus Aug 07 '20 at 17:31

0 Answers0