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

TITRE : A hybrid genetic approach to tackle rich vehicle routing problems

CONFÉRENCIER : Thibaut Vidal, Université de Montréal et Université de Technologie de Troyes, France

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

RESPONSABLE : Gilbert Laporte (514-343-6143)

RÉSUMÉ : Although the vehicle routing problem (VRP) has been extensively studied in the last decades, significant challenges remain to address efficiently real-life applications. In particular, it becomes necessary to tackle complex VRP variants with many additional features called “attributes” (such as multiple depots, multiple periods of planning, time windows constraints or heterogeneous fleets only to name a few). Many efficient meta-heuristic approaches have been designed for the basic VRP and its closest variants. However, working in the same way on “rich problem settings” with many attributes can be time consuming. Hence, many authors proceed by decomposition and successive optimization of sub-problems, but pay the price in terms of solution quality. During this presentation, a novel hybrid genetic algorithm dedicated to rich VRPs will be introduced. This method gathers an effective crossover operator with advanced education schemes based on local searches. To favor exploration and innovation, we manage the diversity during the very evaluation of individuals, which is driven by fitness together with contribution to the population diversity. All these operators work on the general problem, and contribute to obtain high quality solutions on very complex VRP variants like the multidepot periodic VRP with time windows, but also on widely known problems like the periodic VRP.