The application of Multilevel Refinement to the Vehicle Routing Problem

D. Rodney, A. Soper & C. Walshaw


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 in an adaptive manner. Experimentation is used to find a suitable combination, which extends the global view of these heuristics. Results comparing both SL and ML are presented.

Key words. Heuristics, metaheuristic, combinatorial optimization, vehicle routing, multilevel refinement, aggregation techniques

Wed Apr 11 14:19:39 BST 2007