A Recursive Algorithm for Synchronized Rich Vehicle Routing in Air Cargo Ground Handling

We study a rich vehicle coordination problem that arises in air cargo ground handling: a set of services should be provided by different vehicle types to different clients at different locations within defined time intervals, and various vehicle interdependencies exist. We first formalize the problem as a set of rich Vehicle Routing Problems that are bound together by multiple synchronization constraints. In particular, we consider compulsory vehicle pairings, precedence constraints between services, as well as goods transfers between vehicles of different types. The latter can involve more than two vehicles, implying cascading dependencies that greatly complicate the problem. We then develop a client-centered heuristic approach using a recursive procedure that is able to solve the problem as a whole without having to handle constraints separately, as is often the case in vehicle routing problems with such complex structures. We seek to minimize total service time to produce safety time buffers that would help absorb the impact of disruptions and subsequently reduce the number and duration of delays. The algorithm is designed to be easily adaptable to other application domains, and tests on real instances from a major cargo airport in Europe show that it performs well.