Optimisation de systèmes synchromodaux urbains – OPUSS

L'ambition principale du projet est de croiser les méthodes de résolution traditionnellement utilisées par chacune des deux équipes de recherche impliquées dans le projet.

L'équipe de l'Université de Mayence possède une expertise dans la résolution exacte de problèmes d'optimisation combinatoire, en particulier avec des techniques de génération de colonnes. L'équipe du LS2N possède une expertise dans la résolution approchée de ces mêmes problèmes, en particulier avec la métaheuristique LNS (Large Neighborhood Search).

Le programme de recherche comporte des phases pendant lesquelles les deux équipes résolvent de manière disjointe des problèmes d'optimisation en logistique urbaine, chacune avec ses propres méthodes. Ensuite, le projet comporte des phases de mise en commun de nos expertises, en vue de développer des méthodes dites matheuristiques, c'est-à-dire mêlant techniques de résolution exacte et approchées.

Un exemple est le renforcement de l'algorithme LNS utilisé pour résoudre le problème de tournées de véhicules avec options de livraisons, en utilisant des techniques de set partitioning et le voisinage proposé par Balas et Simonetti. Un autre exemple est l'utilisation du LNS pour générer un ensemble de routes qui sera utilisé comme «matière première« par un algorithme de génération de colonnes.

Après deux ans et demi de travaux, les travaux sur le problème de tournées de véhicules avec plusieurs options de livraisons a donné lieu à deux publications dans des revues internationales avec comité de lecture. un troisième article mesurant l'intérêt du renforcement de la méthode LNS par des approches de type set partitioning et voisinage de Balas-Simonetti est en cours d'arbitrage.

Des efforts importants de recherche ont été consacrés à la résolution du problème de tournées dans un réseau à deux échelons (VRP-2E), avec présence simultanée de flux aller et retour. Pour résoudre ce problème extrêmement difficile, les approchées de résolution exacte et approchées ont été combinées et un algorithme de type matheuristique a été mis au point. Un article sera prochainement soumis pour publication.

Plus généralement, le projet a permis aux deux équipes de recherche de confronter leurs approches de résolution et d'enrichir ainsi leur domaine de compétences.

Les perspectives immédiates concernent le perfectionnement de l'algorithme mis au point pour le VRP-2E avec flux aller et retour. En particulier, la possibilité de livrer des clients finaux dès le premier échelon constitue une extension réaliste de notre étude.

Les travaux actuels s'orientent vers des extensions de problèmes d'optimisation de type «truck and trailer problem« à la logistique urbaine. Plus précisément, il s'agit de résoudre le cas de modèles de distribution ou les derniers mètres (ou hectomètres) sont parcourus à pied par les chauffeurs depuis un lieu de stationnement de leur véhicule. Ce problème pourra ensuite être étendu au cas où les véhicules embarquent plusieurs livreurs.

Les algorithmes développées peuvent être étendus à une grande variété de problèmes d'optimisation présentant des caractéristiques similaires.

Le projet OPUSS a été réalisée de manière concomitante après plusieurs projets de recherche appliquée en logistique urbaine, dont les publications à venir aideront l'équipe à se positionner comme un acteur majeur dans ce domaine de recherche.

(avril 2021)

ARTICLE EN REVUES INTERNATIONALES:

A Large Neighborhood Search approach to the Vehicle Routing Problem with Delivery Options, D Dumez, F Lehuédé, O Péton, Transportation Research Part B: Methodological 144, 103-132, 2021.

The Last-mile Vehicle Routing Problem with Delivery Options, C. Tilk, K. Olkis, S. Irnich, à paraître dans OR Spectrum, 2021.

Hybridizing Large Neighborhood Search and Exacts Methods for Generalized Vehicles Routing Problems with Time Windows, D Dumez, C Tilk, S Irnich, F Lehuédé, O Péton. Soumis à EJTL, 2021.


A matheuristic for a 2-echelon-vehicle routing problem with satellite capacities and reverse flows, D Dumez, C. Tilk, S. Irnich, F. Lehuédé, K. Olkis, O. Péton, 2021.


CONFERENCES INTERNATIONALES :

Large Neighborhood Search with set partitioning and dynamic programming for the VRP with Delivery Options, D Dumez, I Stefan, F Lehuédé, K Olkis, O Péton, C Tilk, SynchroTrans 2019, Nantes.

Vehicle Routing Problem with Alternative Delivery Options and Customer Preferences, O Péton, D Dumez, F Lehuédé, IWUOR 2019, Nagoya.

Integrating lockers and multiple delivery options in a city logistics distribution system, D Dumez, F Lehuédé, O Péton, EURO 2019, Dublin.

A Large Neighborhood Search approach to integrate delivery options in last mile delivery, D. Dumez, F. Lehuédé, O. Péton, VeRoLog 2019, Séville.

The Last-mile Vehicle Routing Problem with Delivery Options, C. Tilk, K. Olkis, S. Irnich, , VeRoLog, 2019, Séville.



CONFERENCES NATIONALES :


Renforcements de la recherche à voisinage large pour les problèmes de tournées de véhicules généralisés, D. Dumez, K. Olkis, S. Irnich, F. Lehuédé, O. Péton, C. Tilk, ROADEF 2020, Montpellier, 2020.

The Last-mile Vehicle Routing Problem with Delivery Options, K. Olkis, C. Tilk, S. Irnich, OR 2019, Dresde.

Les projets récents en logistique urbaine montrent que la distribution de marchandises en ville doit reposer sur l'interopérabilité de différents niveaux et moyens de transport pour la livraison des magasins et des particuliers depuis des espaces logistiques urbains (ELU).
Face à la croissance du commerce électronique, la distribution dernier kilomètre en ville est un verrou pour lequel de nouveaux systèmes de logistique urbaine ont été proposés. Une gestion plus durable de la mobilité des biens en ville est nécessaire pour satisfaire la demande en réduisant la congestion et la pollution. Les propositions comprennent de nouveaux moyens de transport (véhicules électriques, cargo bikes, transport mixte passagers-marchandises) et de nouveaux modes de distribution (consignes, relais-colis). La planification efficace d'un tel réseau rejoint le concept de synchromodalité en transport long-courrier. Cette synchromodalité vise à réduire les coûts et à améliorer la résilience et l'efficacité énergétique des réseaux.
L'objectif du projet OPUSS est de concevoir des algorithmes d'optimisation avancés pour permettre la planification des réseaux de distribution urbains. Ces réseaux comportent plusieurs échelons, chacun capables de livrer directement des clients. En outre, nous traitons à la fois des flux de distribution et de retours de marchandises. L'optimisation globale d'un tel réseau requiert la synchronisation des différents moyens de transport, à la fois dans l'espace et dans le temps. Dans ce cadre, OPUSS propose des avancées fondamentales sur les principaux points qui limitent aujourd'hui cette planification globale des réseaux. Ceux-ci concernent la sélection et la planification de la capacité des points de distribution et des ELU et la synchronisation temporelle des moyens de transport.
Le projet reposera sur une coopération étroite entre deux groupes de recherche basés à Nantes et Mayence, renforcés par deux étudiants en thèse de doctorat. Le consortium est formé d'experts en optimisation exacte pour une part et en méthodes heuristiques pour l'autre part,
notamment sur la question de synchronisation des transports. Notre objectif est de concevoir et mettre en oeuvre des méthodes d'optimisation récentes, appelées matheuristiques, qui combinent les approches exactes et heuristiques. Les principaux défis scientifiques concernent la représentation des solutions, la mise en place de procédures efficaces de vérification de la réalisabilité, le guidage d'heuristiques par la programmation mathématique et la résolution heuristique de sous-problèmes au sein de méthodes exactes.
L'apport d'OPUSS porte avant tout sur l'acquisition de connaissances sur la structure des problèmes d'optimisation des systèmes synchromodaux urbains. Ces connaissances seront traduites en propriétés mathématiques, utilisées pour la conception d'algorithmes efficaces. En second lieu, OPUSS définira les composants algorithmiques essentiels capables de répondre aux principales caractéristiques des systèmes étudiés. Troisièmement, l'objectif final d'OPUSS est d'intégrer l'ensemble de ces composants en un algorithme unifié, adaptable à la plupart des systèmes de distribution urbaine. Ces résultats auront un impact important au sein des communautés scientifiques en logistique urbaine et optimisation des transport. Ils lèveront des verrous techniques pour les concepteurs de systèmes de transport intelligents, en permettant l'intégration de moyens de transport agiles et durables. A plus long terme, ces apports bénéficieront aux éditeurs de logiciels dans le domaine de l'optimisation des transports, aux transporteurs qui pourront diversifier leur offre et réduire leur impact environnemental, et finalement aux agglomérations.