Séminaire conjoint CIRRELT-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport

TITRE : The Synchronized Arc and Node Routing Problem

CONFÉRENCIER : Maria Angélica Salazar Aguilar, HEC Montréal, Canada

DATE et ENDROIT : 14 mars 2012, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal

RESPONSABLE : Gilbert Laporte

RÉSUMÉ : In this work, we introduce the synchronized arc and node routing problem which will be referred to as SANRP. The SANRP is originally inspired by a real application related to the process of marking to roads with paint. Several capacitated vehicles are used to paint the roads and a tank vehicle is used to replenish the painting vehicles once or several times depending on the quantity of paint they need. Therefore, the goal is to determine a set of routes for the painting vehicles as well as a route for the replenishment vehicle so that the pavement marking is completed within the least possible time. Hence, it is desirable to synchronize the routes of the replenishment vehicle and of the painting vehicles. The SANRP can appear in other real applications such as home distribution of mail and publicity material. Two optimization problems must be solved simultaneously in order to provide a good solution to the SANRP: a capacitated arc routing problem with multiple vehicles and a node routing problem. Additionally, the routes generated should be synchronized to reduce the waiting time at the refilling points. To solve this NP-hard problem, an Adaptive Large Neighborhood Search Heuristic has been developed and evaluated over a large set of instances. We study two different strategies of replenishment: i) the painting vehicles do not return to the depot when they have to refill their tank; instead, the replenishment vehicle is in charge of the replenishment; ii) the painting vehicles can be refilled from the replenishment vehicle or directly from the depot. These strategies are compared with the strategy generally adopted in practice where the replenishment vehicle does not exist and all painting vehicles have to return to the depot each time they need a refill.