Multi-vehicle one-to-one pickup and delivery problem with split loads

Official URL: http://192.168.1.20/record=b1378280 (Table of Contents)

In this study, we consider the Multi-vehicle One-to-one Pickup and Delivery Problem with Split Loads (MPDPSL). This problem is a generalization of the one-to-one Pickup and Delivery Problem (PDP) where each load can be served by multiple vehicles as well as multiple stops by the same vehicle. In practice, split deliveries is a viable option in many settings where the load can be physically split, such as courier services of third party logistics operators. We also consider two other variants of the problem where it is possible to outsource the pickup and delivery requests for a fixed charge (MPDPSLO) and where the routes are cyclic without depot (MPDPSL-C). We propose an efficient heuristic that combines the strengths of Tabu Search and Simulated Annealing for the solution of MPDPSL and its variants. Results from experiments on a problem set in the literature indicate that the heuristic is capable of producing good quality solutions in reasonable time, we present first results on another problem set in the literature and discuss the merits of load splitting with respect to the network distribution. We compare the results of MPDPSL and MPDPSL-O in order to illustrate the potential benefits of outsourcing under various outsourcing cost schemes. Finally, we present a solution for a real life case of MPDPSL-C.