3

I am dealing with an algorithmic problem. I have a known graph algorithm with a single central node. The aim is to deliver goods from this central node to some other, specified nodes by TWO transporters. Every transporter can carry max. one unit of goods at the time, so that after each node visit they come back to the central node for the next. I should calculate the shortest time possible to do this.

My approach was to use dijkstra algorithm for central node to find the shortest paths to all other nodes considering different distances between nodes. Then for all nodes where the transporters should go (sometimes even more than once to the particular node), I doubled values, because of the distance back and forth. I divided values into two groups with the sums as close as possible each to other, because there are two transporters, and printed bigger one.

The solution, however, doesn't seem to be perfect. I need an another thing to build into it. If the first transporter knows he ends work let's say 8 units sooner, he can somewhen during delivery prepare a good for the second transporter on the way, so that he doesn't have to come for it until central node but bit less. Then their total times will be equal, but considering both shorter. This is, unfortunately, not always possible (for example only one delivery to one node etc.). I need to add this aspect to my program.

ludgo
  • 465
  • 1
  • 6
  • 13
  • Do you have a complete example where this maneuver is needed to achieve the optimum time? – David Eisenstat Nov 17 '16 at 14:28
  • I thought about this simple [example](https://drive.google.com/open?id=0BybjAhGDTdlMQXZoYU9XcjRSR00). Imagine they need to deliver three goods from central 1 to nodes 2,3,3. Their times based on my solution would be 16,12. In better solution the first carries item 5 units in node 3 direction, lets it there, gets back to central and handles node 2. The second handles node 3 first and then complete another node 3 task. Times of both are 14. The question is how to determine that this optimalization is possible for given known graph with respect to all possible cases. – ludgo Nov 17 '16 at 15:08
  • Do the 2 transporters need to return to the central node at the very end? If not, you can save time by making them supply far-away nodes last. – j_random_hacker Nov 17 '16 at 15:54
  • This is a vehicle routing problem and under the hood this requires a cost matrix calculated e.g. from a routing engine via the Dijkstra algorithm. Both problems can be solved with open source software, for the vehicle routing software see jsprit: https://github.com/graphhopper/jsprit for the routing engine see https://github.com/graphhopper/graphhopper (note: I'm involved in building this stuff) – Karussell Nov 19 '16 at 13:13

1 Answers1

0

Actually you are working on a "vehicle routing" problem that we can solve it by some methods like heuristics or constructive methods.

You can find something useful (I hope) here about this methods.

mama23n
  • 135
  • 2
  • 3
  • 10