The vehicle routing problem with coupled time windows

In this article we introduce the vehicle routing problem with coupled time windows (VRPCTW), which is an extension of the vehicle routing problem with time windows (VRPTW) where additional coupling constraints on the time windows are imposed. VRPCTW is applied to model a real-world planning problem concerning the integrated optimization of school starting times and public bus services. A mixed integer programming formulation for VRPCTW within this context is given. It is solved using a new meta-heuristic that combines classical construction aspects with mixed-integer preprocessing techniques, and improving hit-and-run, a randomized search strategy from global optimization. Solutions for several randomly generated and real-world instances are presented.