Optimizing combined tours : The truck-and-cargo-bike case

In this paper, we introduce a last-mile delivery concept that is well suited for urban areas. By jointly optimizing the tour of a truck and a cargo bike, we ensure that each vehicle is used optimally. Here, we assume that the bike is restocked by meeting up with the truck so that no dedicated mini-hubs have to be constructed. We model different objective functions and analyze the different variants in comparison to the traveling salesperson problem as well as the capacitated vehicle routing problem. In an experimental evaluation, we compare MIP formulations for different problem variants and assess several heuristic approaches to solve large-scale instances. These results show that we can outperform the truck-only delivery in terms of completion time while reducing the distance driven by the truck.