Skip navigation

The application of multilevel refinement to the vehicle routing problem

The application of multilevel refinement to the vehicle routing problem

Rodney, Demane, Soper, Alan and Walshaw, Christopher (2007) The application of multilevel refinement to the vehicle routing problem. 2007 IEEE Symposium on Computational Intelligence in Scheduling. Institute of Electrical and Electronics Engineers, Inc., New York, USA, pp. 212-219. ISBN 9781424407040 (doi:10.1109/SCIS.2007.367692)

[img] PDF
07_97.pdf
Restricted to Repository staff only

Download (264kB)

Abstract

We discuss the application of the multilevel (ML)
refinement technique to the Vehicle Routing Problem (VRP),
and compare it to its single-level (SL) counterpart. Multilevel refinement recursively coarsens to create a hierarchy of approximations to the problem and refines at each level. A SL heuristic, termed the combined node-exchange composite heuristic (CNCH), is developed first to solve instances of the VRP. A ML version (the ML-CNCH) is then created, using the construction and improvement heuristics of the CNCH at each level. Experimentation is used to find a suitable combination, which extends the global view of these heuristics. Results comparing both SL and ML are presented.

Item Type: Book Section
Additional Information: This paper forms part of the published proceedings from 2007 IEEE Symposium on Computational Intelligence in Scheduling (CISched), held 1-5 April 2007, Hilton Hawaiian Village, Honolulu, Hawaii.
Uncontrolled Keywords: heuristics, metaheuristic, combinatorial optimization, vehicle routing, multilevel refinement, aggregation techniques
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Pre-2014 Departments: School of Computing & Mathematical Sciences
School of Computing & Mathematical Sciences > Computer & Computational Science Research Group
School of Computing & Mathematical Sciences > Department of Computer Science
School of Computing & Mathematical Sciences > Department of Mathematical Sciences
Related URLs:
Last Modified: 11 Jul 2018 13:52
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/1142

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics