Les véhicules modulaires transforment l'efficacité de la livraison de colis

Des avancées récentes montrent que les véhicules modulaires (VM) peuvent améliorer les systèmes de transport parce qu'ils peuvent se connecter et se séparer pendant un trajet. Bien que les VM aient été étudiés dans différents domaines, leur utilisation dans la logistique, en particulier pour la livraison de marchandises, n'a pas encore été beaucoup explorée. Cette étude examine comment les VM peuvent être utilisés pour la livraison de marchandises afin d'économiser de l'argent. On aborde le problème de la livraison de biens avec des VM comme une nouvelle version du problème de tournées de véhicules, qu'on appelle le Problème de Tournée de Véhicules Modulaire (PTVM).

Dans le PTVM, les VM peuvent soit livrer aux clients seuls, soit se regrouper avec d'autres VM pour former un groupe, ce qui aide à réduire les coûts. Pour résoudre ce problème, on a d'abord créé un modèle de Programmation Linéaire en Nombres Entiers Mixtes qui peut être résolu avec des outils d'optimisation commerciaux. Comme le problème peut être assez complexe, on a aussi conçu un algorithme de Recherche Tabou (RT) avec des outils spéciaux adaptés au PTVM. Pour éviter de se coincer dans des solutions locales, on a ajouté des stratégies à notre algorithme RT.

En outre, on a examiné différentes manières d'utiliser le PTVM dans la logistique. Les résultats de nos tests montrent que l'algorithme proposé identifie efficacement des solutions optimales pour des problèmes plus petits et performe bien dans des cas plus grands. Notre méthode peut économiser environ 5 % de coûts par rapport aux méthodes de livraison traditionnelles. Le code et les données utilisés dans ce travail seront partagés une fois l'article accepté.

#Introduction

La croissance rapide des achats en ligne et des magasins locaux a entraîné une demande pour de meilleurs services de livraison dans les villes. Typiquement, la logistique urbaine implique de grands camions qui acheminent des biens vers des hubs centraux, d'où de plus petits véhicules gèrent le dernier tronçon de la livraison vers des endroits locaux. Cette méthode traditionnelle signifie que les entreprises de logistique ont besoin d'un mélange de types de véhicules, ce qui entraîne des coûts plus élevés pour le travail, le temps et l'infrastructure à cause des transferts nécessaires.

Avec les nouvelles technologies de VM, les véhicules peuvent maintenant s'amarrer, se diviser et transférer des biens tout en mouvement. Le principal avantage des VM est leur design flexible, qui leur permet de se connecter ou de se séparer pendant un trajet, formant des groupes de tailles variées. En utilisant des VM pour les livraisons, le besoin de différents types de véhicules est éliminé, réduisant ainsi les frais liés aux véhicules. De plus, les VM peuvent ajuster leur capacité pendant un trajet, économisant du temps qui aurait été passé à charger et décharger. Contrairement aux groupes de véhicules traditionnels, les VM se connectent physiquement, ce qui réduit la consommation de carburant.

L'utilisation des VM dans la logistique, surtout pour les livraisons de dernière minute, présente plusieurs avantages.

Bien que quelques études se soient penchées sur les applications des VM, la plupart se concentrent sur les systèmes de transport public, comme les services de navette et de taxi. La recherche indique que les VM peuvent réduire considérablement les coûts dans ces systèmes. Peu d'études ont examiné les VM pour les services médicaux d'urgence (SMU) et le transport combiné de passagers et de fret, confirmant aussi leurs avantages dans ces domaines. Des entreprises comme Next Future Transportation Inc. sont en tête du développement des technologies de VM et ont déjà créé des bus modulaires qui peuvent changer leur capacité par arrimage et séparation, répondant efficacement à des problèmes comme les retards.

Malgré l'intérêt pour les VM, la plupart des recherches existantes se sont centrées sur les transports publics plutôt que sur les applications logistiques. L'intégration des VM dans les problèmes de livraison traditionnels présente des défis uniques tant en modélisation qu'en conception d'algorithmes.

Le PTVM prend en compte la nature dynamique de la capacité des VM puisque ces derniers peuvent s'amarrer ensemble pour former des groupes. Cela signifie que la capacité de ces groupes change au fur et à mesure que les VM se joignent ou se retirent, nécessitant un suivi continu de leur statut dans l'espace et le temps.

#Définition du Problème

Notre problème est défini dans un graphe orienté, où les nœuds représentent le dépôt et les clients. Le dépôt est le point de départ et de fin de tous les trajets. Chaque client a une demande spécifique, et les véhicules doivent répondre à ces demandes tout en minimisant les coûts. L'objectif est de garder les véhicules en fonctionnement à leur plus haute efficacité.

L'objectif de notre problème est de minimiser les coûts globaux de livraison de marchandises tout en s'assurant que toutes les demandes des clients soient satisfaites. Le coût associé à la livraison de biens peut varier en fonction du nombre de VM dans un groupe et de la distance parcourue.

Pour formaliser notre problème, nous avons utilisé un modèle de Programmation Linéaire en Nombres Entiers Mixtes à trois indices.

#Développement d'Algorithmes

Bien que le modèle MILP puisse trouver des solutions optimales, il peut être chronophage pour des problèmes plus grands. Le PTVM est complexe, car certains de ses éléments peuvent rendre sa résolution plus difficile avec des méthodes traditionnelles. Pour s'attaquer efficacement à des problèmes plus grands, nous avons introduit un algorithme de Recherche Tabou (RT).

#Représentation de la Solution

Pour mieux comprendre nos solutions, nous utilisons un format spécifique impliquant une structure en deux parties : le Graphe Acyclique Orienté (DAG) et un diagramme de Gantt. Le DAG représente le mouvement des VM, tandis que le diagramme de Gantt montre le timing et la séquence des tâches de livraison.

#Structure de Voisinage

L'algorithme RT repose fortement sur la structure de voisinage, où différents opérateurs peuvent être utilisés pour modifier les solutions existantes afin de trouver de meilleurs résultats. Les méthodes couramment utilisées dans les Problèmes de Tournées de Véhicules traditionnels ne peuvent pas être directement appliquées au PTVM en raison de leurs structures différentes. Par conséquent, nous avons développé des techniques de fusion spécialisées.

1. Opérateur de Fusion Séquentielle (OFS) : Cette méthode combine les itinéraires en insérant des clients séquentiellement dans un segment. L'objectif est de réduire le nombre de VM utilisées tout en maintenant l'efficacité.

2. Opérateur de Fusion Parallèle (OFP) : Cette méthode intègre un itinéraire mono-brin dans un segment pour former un groupe, permettant des combinaisons plus flexibles de VM.

3. Opérateurs de Relocalisation : Ceux-ci permettent de déplacer un client d'une position à une autre pour trouver un meilleur itinéraire de livraison.

En combinant ces opérateurs, l'algorithme RT peut explorer un plus large éventail de solutions potentielles.

#Génération de Solutions Initiales

Pour éviter de se coincer dans un optimum local, une stratégie de multi-démarrage est incorporée. L'algorithme d'économies de Clarke-Wright est utilisé pour produire des solutions initiales, qui sont ensuite optimisées à l'aide de notre algorithme RT.

#Variantes du PTVM

Nous avons également considéré différentes versions du PTVM :

1. Transfert de Fret en Route : Cela permet le transfert de marchandises entre VM pendant un trajet, ajoutant de la flexibilité au processus de livraison.

2. Synchronisation Temporelle : Cela permet de suivre le timing des livraisons, s'assurant que les VM peuvent attendre les unes les autres si nécessaire pour optimiser leurs itinéraires.

3. Unités Modulaires Hétérogènes : Différents types de VM peuvent être utilisés pour différents types de fret, garantissant que la méthode de transport la plus efficace soit utilisée.

#Expériences Computationnelles

Nos expériences ont impliqué plusieurs cas de test pour mesurer la performance de notre algorithme RT. Nous avons adapté des benchmarks bien connus pour les Problèmes de Tournées de Véhicules traditionnels, les ajustant pour s'adapter au PTVM.

#Évaluation de la Performance

L'algorithme RT a été évalué par rapport au modèle MILP. Les résultats ont montré que même si le modèle MILP pouvait résoudre certains petits problèmes de manière optimale, il était significativement plus lent. En revanche, l'algorithme RT a bien performé tant sur les petits que sur les grands problèmes, trouvant souvent de meilleures solutions en moins de temps.

#Évaluation des Composantes de l'Algorithme

Pour comprendre la contribution de chaque composante au sein de l'algorithme RT, nous avons réalisé des tests sans certains opérateurs pour voir comment cela affectait les résultats. Chaque opérateur a apporté des bénéfices importants, surtout pour les problèmes plus grands.

#Évaluation du Platoon de VM

Nous avons analysé les effets de la variation de la taille maximale des platoons de VM. À mesure que la taille du platoon augmentait, nous avons systématiquement observé une réduction des coûts globaux. Cela souligne les avantages de regrouper des VM, mettant en avant le potentiel d'économie que représente une utilisation efficace des VM.

#Conclusion

Cet article a présenté une nouvelle approche au Problème de Tournée de Véhicules en intégrant des véhicules modulaires qui peuvent s'amarrer et se diviser en cours de route. Nous avons créé un modèle de Programmation Linéaire en Nombres Entiers Mixtes pour représenter ce problème et développé un algorithme de Recherche Tabou pour trouver des solutions efficaces.

Les résultats ont montré que notre méthode découvre efficacement des solutions optimales dans des cas petits et parvient à offrir de bonnes performances dans des instances plus grandes. De plus, l'utilisation du platoon de VM semble réduire considérablement les coûts, jusqu'à environ 5 % par rapport aux méthodes traditionnelles.

Les travaux futurs pourraient se concentrer sur l'amélioration de l'algorithme pour des problèmes plus grands et plus complexes, et explorer les différentes extensions du PTVM. Il y a aussi un besoin de recherches sur des méthodes exactes plus efficaces pour résoudre le PTVM tout en analysant les propriétés des problèmes à travers des tests et de la théorie.