A set covering based matheuristic for a real-world city logistics problem

This paper describes an application of a matheuristic algorithm to a real-world city logistics problem for a mid-sized town, whose core could be modeled as a multitrip vehicle routing problem with time windows, pickup and deliveries, and heterogeneous fleet. The proposed matheuristic is based on a dual ascent procedure applied to an extended set covering model (SCC) and on a randomized constructive heuristic. It starts by constructing an initial set of feasible solutions. The corresponding routes are the starting subset of columns of SCC. At each iteration, the dual ascent based on a Lagrangian optimization of the SCC computes a near-optimal dual solution that is returned along with a primal solution obtained by a Lagrangian heuristic. The dual costs are used for generating new feasible solutions by means of the constructive heuristic, and the corresponding routes are the new columns added to the SCC. At the end of the algorithm, the best heuristic solution is pruned to get a feasible solution for the city logistics problem. The matheuristic could actually solve different city logistics scenarios to be used as a basis for a successive stakeholders concertation process. A further interesting byproduct of this research is the dual ascent procedure that also proved effective on the classical set covering problem, in addition to its extension considered in this paper.