New formulations and solution approaches for the latency location routing problem

The Latency Location Routing Problem (LLRP) belongs to a relatively new branch of routing problems, where latency, defined as the sum of the arrival times at customers, is the objective function to be minimized. Introduced by Moshref-Javadi and Lee (2016), this problem optimizes the location of depots, the vehicles allocation to open depots, the customers’ assignment to vehicles and the routing strategy in a customer-oriented framework. In this paper, we address the problem from a modeling and computational viewpoint. From a modeling point of view, we propose two new mixed-integer formulations and introduce a general variant of the problem, which considers the presence of opening costs associated to the depots. Under this assumption, the optimal selection of suitable locations for depots is driven not only by the total latency but also by fixed costs related, for instance, to the construction/renting cost of depots. From a methodological standpoint, we propose different exact solution methods and a metaheuristic algorithm able to obtain near-optimal solutions for both variants, with and without opening costs. Extensive numerical experiments validate the effectiveness of the proposed models and the efficiency of the solution approaches. As a byproduct of the research, by slightly adapting our models, we obtained an effective mathematical formulation for the multi-depot cumulative capacitated vehicle routing problem, which outperformed the state-of-the-art model, providing new optimal solutions in the benchmark dataset.