Vehicle Routing with Pickup and Delivery: Heuristic and Meta-heuristic Solution Algorithms

Solving the Vehicle Routing Problem (VRP) and its related variants is at the heart of scientific research for optimizing logistics planning. One important variant of the VRP is the Pickup and Delivery Problem (PDP). In the PDP, it is generally required to find one or more minimum cost routes to serve a number of customers, where two types of services may be performed at a customer location, pickup or a delivery. We considered two variants of the PDP, the Pickup and Delivery Problem with Time Windows (PDPTW), and the One-commodity Pickup and Delivery Problem (1-PDP). We investigated heuristic and meta-heuristic approaches for solving the selected PDP variants. Our research focuses on handling the difficult problem constraints in a simple and effective way. Two main aspects of the solution algorithm are directed to achieve this goal, the solution representation and the neighborhood moves. In general, the findings of the research indicate the success of our approach in devising simple and robust solution mechanisms that can be integrated with vehicle routing optimization tools and used in a variety of real world applications.