I need to solve capacitated asymmetrical vehicle routing problem with time windows on ~30k points. Time limits for calculations are 2 hours. I've tried using Clarke and Wright savings algorithm, it is very fast but too inaccurate, and I've tried using LKH-3 util for solving my task. It finds almost optimal solution, but unfortunately it takes up to several days to calculate. Is there some intermediate option with best solution quality on 2 hour runs?

Currently I'm using python 3 for solving this task, although any language is acceptable. The graph is the graph of garbage producers in modern cities and around 20% of the points have time bounds, constraining time it can be visited e.g. from 16:00 to 17:00. The edges of the graph is an estimated time, that a vehicle will spend traveling between nodes.

  • 2
    $\begingroup$ Hello Dimitrius! Can you elaborate a bit on your routing problem? What is your data structure? Do you have a graph on which you do the routing. What language /Packages are you using so far? What exactly are time windows in this respect? $\endgroup$ – MPIchael May 16 '19 at 11:52
  • $\begingroup$ If you're using Python 3 and have a solution implemented, perhaps you can post a link to it? $\endgroup$ – Richard May 20 '19 at 22:10

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.