A two-phase heuristic for full truckload routing and scheduling with split delivery and resource synchronization in public works

This paper presents a two-phase method to solve a routing and scheduling problem that arises in public works. In this problem, the quantity of demands generally exceeds the capacity of a truck. As a result, demands have to be split into full truckloads, taking into account the various capacities in the heterogeneous fleet of vehicles that perform the transportation. Full truckload routes have to be designed and scheduled according to construction or loading constraints on pickup and delivery sites. In the first phase, we propose a linear program to split demands into full truckload requests. The second phase is a heuristic that solves a heterogeneous full truckload pickup and delivery problem with time windows and resource synchronization. The method is evaluated on instances from a real case study.