Combining heuristic and exact methods to solve the vehicle routing problem with pickups, deliveries and time windows

Holborn, Penny Louise, Thompson, Jonathan Mark and Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X 2012. Combining heuristic and exact methods to solve the vehicle routing problem with pickups, deliveries and time windows. Presented at: EvoCOP 2012: 12th European Conference on Evolutionary Computation in Combinatorial Optimization, Malaga, Spain, 11-13 April 2012. Published in: Hao, J. K. and Middendorf, M. eds. Evolutionary Computation in Combinatorial Optimization: 12th European Conference, EvoCOP 2012, Málaga, Spain, April 11-13, 2012. Proceedings. Lecture Notes in Computer Science. Lecture Notes in Computer Science , vol.7245 Springer Verlag, pp. 63-74. 10.1007/978-3-642-29124-1_6

Preview

PDF - Accepted Post-Print Version Download (255kB) | Preview

Abstract

The vehicle routing problem with pickups, deliveries and time windows (PDPTW) is an important member in the class of vehicle routing problems. In this paper a general heuristic to construct an initial feasible solution is proposed and compared with other construction methods. New route reconstruction heuristics are then shown to improve on this. These reconstruction heuristics look to reorder individual routes and recombine multiple routes to decrease the number of vehicles used in the solution. A tabu search scheme where the attribute to be recorded has been specifically adapted to the PDPTW is proposed. A new method based on branch and bound optimisation attempts to optimise the final ordering of requests in routes to further improve the solutions. Results are analysed for a standard set of benchmark instances and are shown to be competitive with the state of the art.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Additional Information:	Pdf uploaded in accordance with the publisher’s policy at http://www.sherpa.ac.uk/romeo/issn/0302-9743/ (accessed 07/08/2014)
Publisher:	Springer Verlag
ISBN:	9783642291234
ISSN:	0302-9743
Date of First Compliant Deposit:	30 March 2016
Last Modified:	08 Jan 2025 13:15
URI:	https://orca.cardiff.ac.uk/id/eprint/27718

Citation Data

Cited 7 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item