Evaluation of solution generating methods for various types of pickup and delivery problems

Abstract

The Pickup and Delivery Problem (PDP) is an extension to the classical Vehicle RoutingProblem (VRP) where customers may both receive and send goods. A fleet of vehicles is required to pickup and deliver goods at customer locations. A wide variety of commercial service companies can be modelled as a PDP. PDP appears in literature in various forms: delivery-first, pickup-second PDP, mixed pickups and deliveries and simultaneous pickups and deliveries. In the first model a vehicle can pick up goods only after its complete load has been delivered. The second model allows pickups anddeliveries in any sequence on a vehicle route. In these two models customers are divided into line-hauls (customers receiving goods) and back-hauls (customers sending goods). When the assumption is made that all goods have to either originate from or end up at a depot, the first two models are jointly referred to as the vehicle routing problem with backhauling. In the final model customers may simultaneously receive and send goods. The work on PDP concentrates for the greater part on the development of heuristics. Classical heuristics focus on obtaining a feasible solution quickly with the option of applying a post-optimisation procedure on it. First, construction heuristics build routes sequentially or in parallel until the vehicle’s capacity is reached, without violating other constraints. Second, improvement heuristics try to enhance an initial solution. Also metaheuristics as tabu search, simulated annealing and genetic algorithms have been applied to some types of PDP. Metaheuristics either generate solutions from a neighbourhood of a current solution or generate solutions for a population in a genetic algorithm. Due to the inherent difficulty of satisfying a capacity constraint at each customer’s site, this generation process needs to be efficient. An investigation is made on how initial solutions and neighbourhood solutions are generated. Aspects of speed, feasibility and ability to generate diverse but high-quality solutions are considered.