1

I have

  • a depot
  • a fleet of transporters, each can carry up to 10 tons
  • several customers.

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?

Binarian
  • 12,296
  • 8
  • 53
  • 84
Micromega
  • 12,486
  • 7
  • 35
  • 72
  • 3
    This looks like [Multiple TSP](http://stackoverflow.com/questions/6239148/travelling-salesman-with-multiple-salesmen) – John Dvorak Dec 07 '12 at 21:01
  • It's the Vehicle Routing Problem. Open source software, such as [OptaPlanner](https://www.optaplanner.org/learn/useCases/vehicleRoutingProblem.html), solves this daily for tens of thousands of vehicles, by using metaheuristics such as Tabu Search and Late Acceptance. – Geoffrey De Smet May 22 '19 at 12:03

4 Answers4

4

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.

Stefan Schröder
  • 1,037
  • 7
  • 13
  • 1
    No, the saving algorithm is the most important algorithm. – Micromega Dec 16 '13 at 23:55
  • +1 for precisely correcting additional information of answer to your own question. The saving algorithms are widely used to construct an initial solution for simple VRPs, i.e. starting solution for other Improvement steps/algorithms such as 2-opt, Or-opt, Edge-Exchange etc.. However, once you apply these improvement algorithms you require something/one that guides them (efficiently) through the search space. And here, the mentioned heuristics or call them meta-heuristics come into play. – Stefan Schröder Dec 18 '13 at 14:18
3

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.

Stefan Schröder
  • 1,037
  • 7
  • 13
roxdurazo
  • 745
  • 10
  • 21
1

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

fjxx
  • 945
  • 10
  • 20
  • But shortest path isn't tsp. In shortest path the start and last vertices is given. In tsp it's all unknown and in my problem only the starting point is given. – Micromega Dec 07 '12 at 21:16
  • @Phpdevpad you don't want your trucks to return to the depot? – John Dvorak Dec 10 '12 at 12:17
  • 1
    Endpoint is also known(depot) but this is tsp and not shortest-path? Shortest-path is A to B and tsp is A to B to A. – Micromega Dec 10 '12 at 12:31
1

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

Matthias Kricke
  • 4,931
  • 4
  • 29
  • 43
  • I have also thought about the knapsack problem but knapsack solve only 1 instance but I have a fleet. I see the problem with your approach is also partition it geographically doesn't really make sense when the tsp graph satisfy the triangle inequality and literally every permutations of route is possible. I guess it's just itching me because it's pareto optimal. – Micromega Dec 19 '12 at 09:58
  • I see, pareto optimality is itching me quiet often as well ;) . The point in partitioning is splitting the problem in different parts. You have something like a geographically knapsack, I think due to locality the paths are quiet short and it suits the district approach of most supplier companies. TSP on that small subgraph should be easy as well. Otherwise you have to solve a Multi-TSP with side constraints (load of a transporter) I think this is pretty hard but I'm interested in what you will do in the end! – Matthias Kricke Dec 19 '12 at 10:06
  • I have used a brute-force solution together with a hilbert curve. The problem is the huge search space but it's still a lot better then 1d-bin-packing. For small customers it can solve it very good. It's also good to compare the price because the best plan wasn't always the cheapest. – Micromega Jul 12 '13 at 18:36