Optimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: II. Routing

This is the second part of a two-part study treating the single vehicle many-to-many pickup and delivery problem with desired delivery times. Part I detailed the use of the single vehicle algorithm in a multivehicle context, presented a mathematical formulation of the problem, described the application of Benders' decomposition procedure to attack the problem through alternation between a routing, or sequencing, component and a scheduling component, and illustrated a noniterative optimal algorithm for the scheduling subproblem. This part focuses on the routing subproblem, presenting a heuristic algorithm for finding an initial route and a second heuristic algorithm for improving the route sequence. It then integrates the routing and scheduling algorithms, and describes the results of a number of computational experiments on actual data. An example of the complete routing and scheduling algorithm appears as an appendix.