An adaptive large neighborhood search with path relinking for a class of vehicle‐routing problems with simultaneous pickup and delivery. Issue 3 (15th April 2019)

• Record Type: Journal Article
• Authors: Hof, Julian; Schneider, Michael
• Is Part Of: Networks. Volume 74:Issue 3(2019)
• Page Start: 207
• Page End: 250
• Publication Date: 2019-04-15
• Subjects: large neighborhood search -- path relinking -- simultaneous pickup and delivery -- vehicle routing; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21879
• Languages: English
• ISSNs: 0028-3045

Abstract

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.