Please use this identifier to cite or link to this item:
Title: Evaluation of solution generating methods for various types of pickup and delivery problems
Authors: CARIS, An 
Issue Date: 2005
Source: ORBEL '05 Booklet of Abstracts. p. 105-105.
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.
Keywords: Vehicle routing, Heuristics, Pickups and deliveries
Document URI:
Link to publication:
Category: C2
Type: Proceedings Paper
Appears in Collections:Research publications

Show full item record

Page view(s)

checked on May 25, 2022

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.