The fleet size and mix vehicle routing problem with time windows

Abstract

This paper describes several insertion-based savings heuristics for the fleet size and mix vehicle routing problem with time window constraints. A certain number of candidate fleet compositions are recorded in the construction phase, followed by applying a composite improvement scheme on them to enhance the solution quality. Computational results on 168 sample problems are reported. We found that heuristics with the consideration of a sequential route construction parameter yielded very good results. In addition, results on the 20 benchmarking problems for the fleet and mix vehicle routing problem with no time window constraints also demonstrate the effectiveness of our heuristics.