Spatial Temporal and Hybrid Decompositions for L

Authors: Russell Bent Pascal Van Hentenryck

Publish Date: 2010/9/6

Volume: , Issue: , Pages: 99-113

PDF Link

Abstract

This paper studies the use of decomposition techniques to quickly find highquality solutions to largescale vehicle routing problems with time windows It considers an adaptive decomposition scheme which iteratively decouples a routing problem based on the current solution Earlier work considered vehiclebased decompositions that partitions the vehicles across the subproblems The subproblems can then be optimized independently and merged easily This paper argues that vehiclebased decompositions although very effective on various problem classes also have limitations In particular they do not accommodate temporal decompositions and may produce spatial decompositions that are not focused enough This paper then proposes customerbased decompositions which generalize vehiclebased decouplings and allows for focused spatial and temporal decompositions Experimental results on class R2 of the extended Solomon benchmarks demonstrates the benefits of the customerbased adaptive decomposition scheme and its spatial temporal and hybrid instantiations In particular they show that customerbased decompositions bring significant benefits over large neighborhood search in contrast to vehiclebased decompositions

Keywords: