Heuristics for large constrained vehicle routing problems

This paper presents a heuristic for solving very large routing problems (th ousands of customers and hundreds of vehicles) with side constraints such a s time windows. When applied to traditional benchmarks (Solomon's), we obta in high quality results with short resolution time (a few seconds). We also introduce a LDS (Limited Discrepancy Search) variation that produces state -of-the-art results. The heart of this heuristic is a combination of a look -ahead insertion algorithm, an incremental local optimization scheme and a constraint solver for constrained traveling salesman problems. The incremen tality means that instead of visiting some large neighborhood after an init ial solution has been found, a limited number of moves is examined, after e ach insertion, on the partial solution. This incremental version is not onl y faster, it also yields better results than using local optimization once a full solution has been built. We also show how additional constraints can be used in order to guide the insertion process. Because of its use of sep arate CP (Constraint Programming) modules, this method is flexible and may be used to solve large dispatching problems that include many additional co nstraints such as setup times (asymmetrical distance) or skill matching.