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.

Marco, B., Vittorio, M. (2015). A set covering based matheuristic for a real-world city logistics problem. INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 22(1), 169-195 [10.1111/itor.12110].

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

#### Abstract

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.
##### Scheda breve Scheda completa Scheda completa (DC)
2015
Marco, B., Vittorio, M. (2015). A set covering based matheuristic for a real-world city logistics problem. INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 22(1), 169-195 [10.1111/itor.12110].
Marco, Boschetti; Vittorio, Maniezzo
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11585/407972`
##### Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

• ND
• ND
• 23