CODEWITHSUNDEEP
graph-theory
Cybercartel
Cybercartel

Reputation: 12592

Vehicle routing algorithm?

I have

How can I maximize the load of a transporter and minimize the tour?

So far I use a 1d bin-packing to group the transporters and an ant-colony-optimization to shorten the tour but it doesn't feel right. I've read about the knappsack algorithm? Can I do better?

Upvotes: 1

Views: 4707

Answers (4)

roxdurazo
roxdurazo

Reputation: 765

Your problem can be solved with this free software for solving VRP https://jsprit.github.io in Java or https://github.com/mck-/Open-VRP in Lisp.

Upvotes: 3

Stefan Schröder
Stefan Schröder

Reputation: 1037

It is the classical vehicle routing problem (VRP). For small/medium sized instances you find optimal solutions by formulating a (mixed) integer problem and using a MIP-solver such as Gurobi.

It is common to apply heuristics. However, they do not necessarily yield optimal solutions. The most important heuristics in this field are Tabu Search, Simulated Annealing and various algorithms inspired by biology. These heuristics proved to generate fairly good solutions, and they are without alternative when it comes to large scale problems with many side constraints. For many problems they even yield optimal solutions which is however often quite hard to prove.

However, understanding and implementing those algorithms is not a matter of a day.

I implemented a project called jsprit. jsprit is a lightweight java toolkit and can solve your problem and let you analyse the generated solutions, e.g. by visualizing them. It uses a large neighborhood search which is a combination of Simulated Annealing and Threshold Accepting (the applied algorithm principle is referenced there). You will find a number of examples that help you implementing your problem.

A straightforward approach for you is to minimize variable costs (whatever your cost measures are, e.g. distance, time, fuel or a combined measure) while considering fixed costs for your vehicles. I am sure you end up with a solution that "minimizes the tour" and utilizes your transporters appropiately. If you have problems setting up your problem, do not hesitate to contact me directly.

Upvotes: 4

Matthias Kricke
Matthias Kricke

Reputation: 4971

I think there is no perfect solution for your problem. If i get it right your problem is pareto optimal. you can optimize your route or your load or the number of fleet cars you need (side constraint daily work time might be also an issue). you have to value yourself what is more important, e.g. a short route due to fuel cost, less cars, and so on.

In my opinion you should partition your customers geographically in a way that for each partition the load sum is not bigger than 10 tons. Afterwards you can use TSP on that small problem to calculate a perfect route. the main "magic" is done in the partition step, if you solve that in a good way your problems might vanish.

hope that helped

Upvotes: 1

fjxx
fjxx

Reputation: 945

A combination of A* search (modified for max-cost path) combined with the shortest path algorithm as described in this Microsoft Research paper might be worth looking into: http://research.microsoft.com/pubs/154937/soda05.pdf

Upvotes: 1

Related Questions