Zhiyuan Shi Urban Mobility Institute, Tongji University, Shanghai TSP-DS+A0028

La croissance rapide du commerce électronique a posé des défis importants pour la livraison du dernier kilomètre en milieu urbain. Dans ce document, nous étudions un problème de livraison collaborative camion-drone, appelé le problème du voyageur de commerce avec une station de drones (TSP-DS), qui est bien adapté aux environnements urbains densément peuplés. Le TSP-DS étend le problème bien connu de la planification parallèle des drones (PDSTSP). Le camion part du dépôt et peut livrer des colis à la station de drone pour livraison par drones. Pour minimiser la durée de l’ensemble des livraisons, nous proposons une nouvelle formulation pour le TSP-DS en utilisant la programmation linéaire entière mixte (MILP). Nous développons ensuite un algorithme exact basé sur l’approche de décomposition de Benders basée sur la logique. Pour évaluer l’efficacité de notre formulation et de notre algorithme, nous effectuons des expériences informatiques approfondies à l’aide d’instances de test générées à partir de points de référence existants. Les résultats numériques valident les améliorations offertes par notre formulation, notamment une réduction du nombre de variables et de contraintes et des temps de calcul plus courts, par rapport à la formulation TSP-DS dans la littérature existante. Notre approche de Benders surpasse également le solveur commercial de pointe Gurobi et résout avec succès une instance avec 101 clients à l’optimum global. Nous effectuons également des analyses de sensibilité pour obtenir des renseignements précieux sur l’impact des paramètres critiques du modèle, notamment le nombre, la vitesse et la durée de vol des drones, ainsi que l’emplacement de la station de drone, sur les performances de ce système de livraison. Les résultats montrent que la configuration des paramètres est essentielle dans les applications pratiques, car ces facteurs peuvent affecter de manière significative les performances globales du système.

Auteurs : Zhiyuan Shi Shaozhi Hong Zeling Wang

Mots-clés Problème du voyageur de commerce, Programmation parallèle de drones, Programmation linéaire à nombre mixte, Décomposition de Benders basée sur la logique