A biased-randomized discrete-event heuristic for coordinated multi-vehicle container transport across interconnected networks

Modern transport systems are not only large-scale but also highly dynamic, which makes it difficult to optimize by just employing classical methods. This paper analyzes a realistic and novel problem within the Physical Internet initiative which consists of container transportation throughout a spoke-hub network. Containers need to be transported from their origin locations to their final destinations on or before a given deadline, and they can be temporarily stored in network hubs. Each truck can move one container at a time from one hub to another, containers can be transported by different trucks during their path from their origin to their destination, and drivers need to be back at their starting points in due time. A deterministic heuristic, based on discrete-event simulation, is proposed as a first step to address the intrinsic dynamism of this time-evolving system. Then, in a second step, a biased-randomized version of this heuristic is incorporated into a multi-start framework (BR-MS) to generate better solutions. Next, our methodology is extended to a iterated local search (ILS) framework. Finally, a two-stage algorithm, combining both the BR-MS and the ILS frameworks is proposed. Several computational experiments have been carried out on a set of new benchmark instances, adapted from real road networks, to illustrate the problem and compare the performance of the different solving approaches.