1
$\begingroup$

I would like to solve a particular VRP problem encountered in industrial applications, where the model needs to plan the assignment of each customer point before performing path planning, and then optimize the shortest distance for vehicles to reach each customer node, so that the delivery can end as early as possible.

I have constructed a simple genetic algorithm for solving it, and my idea is to optimize the allocation of customer nodes first and then consider routing. So the crossover, mutation and other operations of my chromosome are performed on the customer node assignment, and when the customer node locations on a chromosome are determined, I then plan a feasible solution for the vehicle routing using a simple way such as a greedy algorithm. As for the selection operator of the genetic algorithm, I use the simplest binary tournament selection as well.

I have tested the algorithm several times, and so far the algorithm's results are not stable enough, and the distribution distance results obtained from each convergence fluctuate widely. However the company's main concern at the moment is the computation time, they want the algorithm to be able to complete all scenarios in 10sec, and my algorithm is currently facing a 5000 points, 1000 vehicles (the largest application scenario envisioned) in about 19sec, which is not up to par. But I think that 10sec is a bit harsh for a VRP problem of this size. So I would like to know, based on your experience with VRP problems, if we discuss only the simplest and most classical VRP problem (not even considering the capacity of the vehicles), are there any open source solvers or heuristics that can give a feasible solution in 10sec when trying to deal with a 5000 point scale? If so, can you describe them.Thx for any suggestions

Improve this question
$\endgroup$
5
  • $\begingroup$ It will depend on the instances, but I suggest you look at column generation for VRP. In these TSP-variants, using dynamic programming along with domination rules to eliminate solutions makes pricing much much faster. Still, 5000 points, 1000 vehicles, is a pretty big instance, I would say. Perhaps incorporate into your ideas the fact that the vehicles will, on average, only visit 5 cities, so the tours should be rather small. $\endgroup$
    – J. Dionisio
    Commented Jul 29 at 9:01
  • 1
    $\begingroup$ The answer is simply: no. This is very unrealistic even when relaxing "solving" to "find a good solution".. $\endgroup$
    – Erwin Kalvelagen
    Commented Jul 29 at 9:29
  • $\begingroup$ Try this evolutionary-algorithm tool: pyvrp.org . DIMACS had a workshop on this topic last year: youtube.com/playlist?list=PLKVCRT3MRed7p5R0fZWK_gjTIsdONYsUj $\endgroup$
    – Brannon
    Commented Jul 29 at 22:42
  • $\begingroup$ Have you considered using Real-Time Planning AKA warm starts to workaround the 10 second limit? It's a common approach that works well in production, even on 10k+ visits. $\endgroup$
    – Geoffrey De Smet
    Commented Jul 30 at 21:07
  • $\begingroup$ Try logisticsOS, 10s is hard, but 100s is possible. $\endgroup$
    – Yuzhe Yan
    Commented Nov 2 at 7:42

1 Answer 1

Reset to default
4
$\begingroup$

An (parallel) insertion-style heuristic as described in:

Potvin, Jean-Yves, and Jean-Marc Rousseau. "A parallel route building algorithm for the vehicle routing and scheduling problem with time windows." European Journal of Operational Research 66.3 (1993): 331-340.

is quite popular and can work in O(N^3) time following careful implementation:

Campbell, Ann Melissa, and Martin Savelsbergh. "Efficient insertion heuristics for vehicle routing and scheduling problems." Transportation science 38.3 (2004): 369-378.

With N=5000; N^3=125.000.000.000, this 10s eval should be feasible to achieve given todays hardware, especially when exploiting SIMD (harder; but fits the implementation of the 2nd citation well) and multi-core (easier).

Edit: 10s might be a bit hard...

An implementation of above will be memory-bound, as the calculations are trivial but z=125.000.000.000 evals will touch at least z * 4bytes * 10(values) in bytes: 5.000.000.000.000. (i have chosen the 10 arbritrary but it can be deduced from the papers algorithm -> how many values to read for each evaluation)

As a modern server-cpu (more mem-channels) will have a max mem-bandwith of ~ 300.000.000.000 (300GB/s) we have an lower-bound of 17 seconds.

A GPU would have 10x the bandwith and would fit more. In theory. In practice i also think it's one of the few use-cases in combinatorial-optimization where i would assume a GPU implementation will actually work out (but i never tried it).

Note on memory-bandwith estimations

Often code is cpu-bound (lots of complex calculations) but when algorithms are optimized heavily, often those implementations become memory-bound: you are slowed down by reading from memory and your calculations are starving!.

A popular example is dense matrix-multiplication. In gaming/AI there are more examples which explain why GPUs have much more memory-bandwith than CPUs!

The 2nd-resource algorithm will be memory-bound! It's a simple calculation but we need to read from large distance-matrices with little chance of caching (steps are not that local).

If we already now it's memory-bound, we can quickly estimate how much memory we will need to read during the execution of the whole algorithm.

If we know we will need to read X bytes, we can compare it to the theoretical maximum memory-bandwith our hardware provides to obtain a lower-bound!

Caveats:

  • In practice, mem-bandwith will be lower
  • The lower-bound is only relevant if mem-bandwith is the bottleneck
    • I would argue it's never the case without using low-level programming languages
      • For scripting-languages (python) or probably even Java, all of this is probably too optimistic
Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your help, I'm interested in this estimation of algorithmic memory calculation that you used, please can you share this method, I would like to use it for my own code's memory requirement estimation $\endgroup$
    – CangWangu
    Commented Jul 29 at 9:27
  • $\begingroup$ @CangWangu It's nothing special and probably won't help you as your algorithm seems to lack worst-case bounds (aka when to stop / how many iterations). $\endgroup$
    – sascha
    Commented Jul 29 at 9:38
  • $\begingroup$ Are there any papers or books that teach this part? I feel like I need a refresher course on the subject. $\endgroup$
    – CangWangu
    Commented Jul 29 at 9:49
  • $\begingroup$ I'm not aware of any. I also think it's rather niche and will only be relevant in very few cases (e.g. won't give much insights to most discrete-opt approaches of this board like tree-search). $\endgroup$
    – sascha
    Commented Jul 29 at 9:55

Your Answer

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

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