Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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 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 Springer Verlag, pp. 63-74. 10.1007/978-3-642-29124-1_6

[img]
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
Last Modified: 06 Aug 2018 14:48
URI: http://orca.cf.ac.uk/id/eprint/27718

Citation Data

Cited 4 times in Google Scholar. View in Google Scholar

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

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics