What is a warehouse delivery driver?

What is the most efficient algorithm for determining a delivery route for an outbound truck moving from a starting point to an end point with multiple stops in between and no return to starting point?

• Picture it this way, I have a van that starts at a warehouse and the driver always makes the deliveries on his way home, i.e. he doesn't return to the warehouse. The van has multiple delivery addresses it has to reach along the way home. What is the most efficient routing algorithm in this case? I'd assume some traveling salesman implementations could work but given that these usually assume a return to the starting point, what changes need to be made and are there any  more efficient algorithms that come into play?

• Answer:

  Since so much time and effort have gone into optimizing TSP solvers, the path of least resistance is probably to try to turn your problem into a TSP instance. One way to do this is to set it up as a directed TSP instance with the all nodes except for the starting and ending nodes connected to the other nodes with their true distances, and the starting node connected to all the nodes in the forward direction, the ending node connected to all nodes in the reverse direction, and the ending node connected to the starting node in the forward direction, and then convert this problem to an instance of the undirected TSP and solve it with a tool like Concorde: http://www.math.uwaterloo.ca/tsp/concorde.html The construction to go from directed to undirected multiplies the number of nodes by a constant, so we would like to avoid this if possible; another way that I just thought of that I believe works is to give a very large negative weight to the edge between the starting and ending nodes, or a node that only connects to the start and end with weight 0, to ensure the resulting cycle will allow you to start at the starting node and hit all the other nodes going around in the other direction.