Abstract This work studies a two-echelon distribution system, in the context of city logistics, where storage is not permitted at intermediate transfer locations. Therefore, vehicles operating at both echelons need to be synchronised in time and space, allowing loads to be directly transferred from the first to the second echelon vehicles. Moreover, the problem considers that vehicles operating at the first echelon can perform direct deliveries to customers, that load transfers may occur at some customers’ locations, and that vehicles operating at the second echelon are able to perform multiple trips before returning to the depot at the end of the day. To address this problem, we propose a novel mixed integer programming (MIP) model for the two-echelon, multi-trip vehicle routing problem with satellite synchronisation and direct deliveries (2E-MTVRPSS-DD). We tighten this formulation with several sets of valid inequalities, including symmetry breaking constraints based on lexicographical ordering, vehicle rounded capacity constraints, and satellite rounded capacity constraints. We test the model using a commercial solver with newly generated instances, and present computational results, as well as an evaluation of the performance of the proposed valid inequalities. The results show that for relatively small instances, the proposed model is able to solve the problem optimally, but in general, is unable to solve large instances in acceptable computational time, even when considering the proposed valid inequalities. Nevertheless, we show that adding these valid inequalities has a positive impact in improving the model’s linear relaxation, with better lower and upper bounds, and ultimately in improving the MIP gaps. Moreover, we show that adding symmetry breaking constraints based on lexicographical ordering has a negative impact, in terms of computational time, for the solver to find a first upper bound, and that this issue may be overcome by warm-starting the MIP model.
Oliveira et al. (Mon,) studied this question.