Solving the biobjective selective pickup and delivery problem with memetic algorithm
Authors:
- 1 April 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 107-114
Abstract
The pickup and delivery problem (PDP) arises in many real-world scenarios such as logistics and robotics. This problem combines the traveling salesman problem (or the vehicle routing problem) and object distribution. The selective pickup and delivery problem (SPDP) is a novel variant of the PDP that enables selectivity of pickup nodes for particular applications. Specifically, the SPDP seeks a shortest route that can supply all delivery nodes with required commodities from some pickup nodes. The two key factors in the SPDP-travel distance and vehicle capacity required-form a tradeoff in essence. This study formulates the biobjective selective pickup and delivery problem (BSPDP) for minimization of travel distance and vehicle capacity required. To resolve the BSPDP, we propose a multiobjective memetic algorithm (MOMA) based on NSGA-II and local search. Furthermore, a repair strategy is developed for the MOMA to handle the constraint on vehicle load. Experimental results validate the efficacy of the proposed algorithm in approaching the lower bounds of both objectives. Moreover, the results demonstrate the characteristics of the BSPDP.Keywords
This publication has 28 references indexed in Scilit:
- The preemptive swapping problem on a treeNetworks, 2011
- A heuristic two‐phase solution approach for the multi‐objective dial‐a‐ride problemNetworks, 2009
- Solving the Dial-a-Ride problem using genetic algorithmsJournal of the Operational Research Society, 2007
- A dial-a-ride problem for client transportation in a health-care organizationComputers & Operations Research, 2007
- A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windowsComputers & Operations Research, 2006
- A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windowsTransportation Research Part B: Methodological, 2004
- An Evolutionary Approach to Pickup and Delivery Problem with Time WindowsLecture Notes in Computer Science, 2004
- A metaheuristic for the pickup and delivery problem with time windows2002
- Solving the pickup and delivery problem with time windows using reactive tabu searchTransportation Research Part B: Methodological, 2000
- The swapping problemNetworks, 1992