The selective pickup and delivery problem: Formulation and a memetic algorithm

Chuan-Kang Ting and Xin-Lan Liao

International Journal of Production Economics, 2013, vol. 141, issue 1, 199-211

Abstract: The pickup and delivery problem addresses the real-world issues in logistic industry and establishes an important category of vehicle routing problems. The problem is to find the shortest route to collect and distribute commodities under the assumption that the total supply and the total demand are in equilibrium. This study presents a novel problem formulation, called the selective pickup and delivery problem (SPDP), by relaxing the constraint that all pickup nodes must be visited. Specifically, the SPDP aims to find the shortest route that can supply delivery nodes with required commodities from some pickup nodes. This problem can substantially reduce the transportation cost and fits real-world logistic scenarios. Furthermore, this study proves that the SPDP is NP-hard and proposes a memetic algorithm (MA) based on genetic algorithm and local search to resolve the problem. A novel representation of candidate solutions is designed for the selection of pickup nodes. The related operators are also devised for the MA; in particular, it adapts the 2-opt operator to the sub-routes of the SPDP for enhancement of visiting order. The experimental results on several SPDP instances validate that the proposed MA can significantly outperform genetic algorithm and tabu search in terms of solution quality and convergence speed. In addition, the reduced route lengths on the test instances and the real-world application to rental bikes distribution demonstrate the benefit of the SPDP in logistics.

Keywords: Pickup and delivery; Logistics; Evolutionary computation; Memetic algorithm (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S092552731200237X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:proeco:v:141:y:2013:i:1:p:199-211

DOI: 10.1016/j.ijpe.2012.06.009

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().