A Study on the Pickup and Delivery Problem with Time Windows: Matheuristics and New Instances

Abstract In the present work, we study the Pickup and Delivery Problem with Time Windows, which generalizes the well-known Vehicle Routing Problem and has many potential applications to transportation services. The contributions span from an improved hybrid algorithm with a mathematical programming component (matheuristic) to a new method to generate instances for routing problems based on open data. We further provide a thorough component analysis of the proposed algorithm, a comparison to state-of-the-art methods, and investigate the differences in results obtained for a standard instance set and a new testbed. Numerical experiments show the proposed matheuristic works well for the standard benchmark set, whereas results in the new set are surprisingly divergent. The possible reasons and future research directions are discussed. In addition, a number of solutions to the standard instances have been improved.