An adaptive large neighborhood search with path relinking for a class of vehicle‐routing problems with simultaneous pickup and delivery

Journal Article

Abstract We study a class of vehicle‐routing problems with simultaneous pickup and delivery (VRPSPD). In VRPSPDs, each customer may require a certain quantity of goods delivered from the depot and a quantity of goods to be picked up and returned to the depot. Besides the standard VRPSPD, we address (1) the VRPSPD with time limit (VRPSPDTL), which imposes a time limit on the routes of the transportation vehicles, (2) the VRPSPD with time windows (VRPSPDTW), which takes customer time windows into account, (3) the VRP with divisible deliveries and pickups (VRPDDP), which allows for fulfilling the delivery and pickup requests of each customer in two separate visits, (4) the previously unstudied VRP with restricted mixing of divisible deliveries and pickups (VRPRMDDP), which accounts for the difficulty of rearranging the vehicle load by additionally requiring that a certain percentage of the vehicle capacity must remain unoccupied when both types of demand are simultaneously loaded, and (5) the previously unstudied VRPDDP with time windows (VRPDDPTW). We develop a hybrid heuristic solution method which combines an adaptive large neighborhood search algorithm with a path relinking approach, called ALNS‐PR, and we demonstrate the competitiveness of our algorithm on benchmark instances proposed in the literature. Especially on VRPSPDTL, VRPSPDTW, and VRPDDP instances, our ALNS‐PR proves to be superior to the majority of comparison algorithms and is able to obtain numerous new best solutions.

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.