A recursive algorithm for synchronized rich vehicle routing in air cargo ground handling

We study a rich vehicle coordination problem met by Liège Airport, a major cargo airport in Europe. We focus on 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, and 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 greedy heuristic 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 aircraft delays. Tests on real instances show that the algorithm performs well.