Constructing initial solutions for the multiple vehicle pickup and delivery problem with time windows

Hosny, Manar I. and Mumford, Christine Lesley ORCID: https://orcid.org/0000-0002-4514-0272 2012. Constructing initial solutions for the multiple vehicle pickup and delivery problem with time windows. Journal of King Saud University - Computer and Information Sciences 24 (1) , pp. 59-69. 10.1016/j.jksuci.2011.10.006

Preview

Text - Published Version Download (208kB) | Preview

Abstract

The Multiple Vehicle Pickup and Delivery Problem with TimeWindows (MV-PDPTW) is an important problem in logistics and transportation. However, this problem is characterized by having a large number of constraints that are difficult to deal with in a solution algorithm. Indeed, merely constructing a feasible solution to this hard problem is a challenge in itself. In this research, we compare several construction algorithms that generate initial feasible solutions to the problem. The suggested algorithms all utilize a simple routing heuristic to create individual vehicle routes. The algorithms differ, though, in whether routes are generated sequentially or in parallel. They also have different criteria for selecting requests and the routes in which they will be inserted. Inserting a request in a route is either based on a first acceptance criterion, in which a request is inserted in the first route where a feasible insertion is found, or a best acceptance criterion, in which a request is inserted in the estimated best route for insertion. Experimental results on several benchmark problem instances indicate that the sequential construction heuristic may be the most suitable construction algorithm for this problem, in terms of simplicity of coding, solution quality as well as processing speed.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science Q Science > QA Mathematics > QA76 Computer software
Uncontrolled Keywords:	Combinatorial optimization; Pickup and delivery; Vehicle routing; Heuristics; Meta-heuristics; Construction algorithms
Publisher:	Elsevier
ISSN:	1319-1578
Date of First Compliant Deposit:	30 March 2016
Last Modified:	22 May 2023 19:38
URI:	https://orca.cardiff.ac.uk/id/eprint/31843

Citation Data

Actions (repository staff only)

Edit Item