The Long-Haul Parcel Transportation Problem : Path-based Models and Divide-and-Conquer Algorithms

Autor: Gras, Camille
Přispěvatelé: Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Université Grenoble Alpes [2020-....], Van-Dat Cung, STAR, ABES
Jazyk: angličtina
Rok vydání: 2021
Předmět:
Zdroj: Software Engineering [cs.SE]. Université Grenoble Alpes [2020-..], 2021. English. ⟨NNT : 2021GRALI073⟩
Popis: With the advent of e-commerce, many studies have been carried out on urban logistics and last-mile delivery.In this work, we optimize another stage of parcel delivery, the long-haul parcel transportation.The long-haul transportation is from the collection sorting centers to delivery depots. We do not consider how the parcels are brought from their departure post office to their collection sorting center, neither how they are transported to the post offices and then to individuals.The Long-Haul Parcel Transportation Problem (LHPTP), which we formally define, is a Service Network Design with Asset Management problem which integrates the sorting operation allowing a better consolidation of parcels in containers.The LHPTP is a tactical design optimization problem which consists in defining an annual transportation plan composed of fixed links, based on mid-term volume forecasts, while minimizing the total cost. This cost is composed of the logistics cost and the transportation cost. The parcel transportation is made with two types of vehicles (trucks with one or two containers) which are balanced over the network on a daily basis with the management of empty containers.The transportation is optimized over a two-level hybrid hub-and-spoke network at the scale of a country. Indeed, this industrial problem originates from a postal company and their datasets permit to address realistic size data (around 225 sites with 2500 demands).The complexity is increased by the fact that a single demand (origin, destination, number of parcels) can be routed over multiple paths simultaneously. Thus the number of possible transportation plans explodes.We propose a path-based Mixed Integer Linear Program (MILP) for the LHPTP and two divide-and-conquer algorithms exploiting this model to create better transportation plans.The first algorithm, the k-Clusters Algorithm, optimizes the LHPTP over a set of sites which are clustered beforehand. We test classical clustering techniques (spectral clustering, hierarchical clustering, k-means and random) using appropriate similarity functions (demand-based and distance-based) in order to see if it impacts the results. The original problem is divided into intercluster and intracluster subproblems which are solved with the MILP. Then the solutions of the subproblems are merged. The results obtained are compared to those obtained with a direct use of the MILP without clustering. It shows that certain properties of the clustering, such as obeying the hierarchy of the sites in the current postal network, have the most impact on the results.Thus we design a second algorithm, the Hierarchical Algorithm with Aggregation of Demands which exploits the two-level structure of the network. Its performance is related to the value of a truck filling rate threshold. The demands above this threshold can be routed directly while the ones below this threshold have to follow the hierarchical structure of the network.The routing of the two types of demands is optimized, first separately and then together in a multi-step process in which the subproblems are solved with the MILP.Various threshold values are tested to find out which one is the best, in terms of solution quality obtained and computational time.These tests show that the better filling rate do not result in the cheaper transportation plan in our case study. Moreover, the Hierarchical Algorithm allows to have clearly better transportation plans than the ones applied on the ground, the ones obtained via a direct use of the MILP and even the ones obtained with the k-Clusters Algorithm.Finally we implement these algorithms and present computational results.This shows that the divide-and-conquer paradigm is effective on service network design when addressing a large-scale industrial problem.
Avec l’essor du e-commerce, de nombreuses études ont été menées sur la logistique urbaine et la livraison du dernier kilomètre. Nous optimisons ici une autre étape de la livraison des colis : le transport long-courrier. Il a lieu entre les centres de tri de collecte et les dépôts de livraison. Ni la manière dont les colis sont acheminés de leur bureau de poste de départ à leur centre de tri de collecte, ni comment ils sont transportés vers les bureaux de poste puis aux particuliers ne sont pris en considération. Le problème du transport long-courrier de colis (PTLCC), défini formellement, est un problème de conception de réseau de services avec gestion des actifs. Il intègre l'opération de tri permettant une meilleure mutualisation des colis dans les conteneurs. C’est un problème tactique d'optimisation qui consiste à définir un plan de transport annuel composé de liaisons fixes, basé sur des prévisions de volumes à moyen terme, dont on minimise le coût total. Ce coût est composé du coût logistique et du coût de transport. Le transport de colis se fait avec deux types de véhicules (camions à un ou deux conteneurs) qui sont équilibrés chaque jour sur le réseau grâce à la gestion des conteneurs vides. Le transport est optimisé sur un réseau hybride hub-and-spoke biniveau à l'échelle d'un pays. En effet, ce problème industriel provient d'une entreprise postale et leurs ensembles de données sont de taille réaliste (environ 225 sites avec 2500 demandes). Une même demande (origine, destination, nombre de colis) peut être acheminée sur plusieurs chemins simultanément ce qui augmente la complexité du problème. Ainsi, le nombre de plans de transport possibles explose.Nous proposons un programme linéaire mixte (PLM) orienté chemin pour le PTLCC etdeux algorithmes diviser-pour-régner exploitant ce modèle pour créer de meilleurs plans de transport. Le premier algorithme, l'algorithme k-Clusters, optimise le PTLCC après avoir regroupé les sites du réseau en clusters. Nous testons des techniques classiques de clustering (clustering spectral, clustering hiérarchique, k-means et aléatoire) en utilisant des fonctions de similarité appropriées (basées sur les demandes et sur les distances) pour étudier l’impact sur les résultats.Le problème d'origine est divisé en sous-problèmes intercluster et intracluster résolus avec le PLM. Les solutions des sous-problèmes sont ensuite fusionnées. Les résultats obtenus sont comparés à ceux obtenus avec une utilisation directe du PLM sans clustering. Ces tests montrent que le respect de la hiérarchisation des sites du réseau postal est la propriété qui a le plus d'impact sur les résultats.Ainsi, nous concevons un deuxième algorithme, l'algorithme hiérarchique avec agrégation de demandes qui exploite la structure à deux niveaux du réseau. Ses performances sont liées à un seuil du taux de remplissage des camions. Les demandes au-dessus de ce seuil peuvent être acheminées directement. Celles en dessous de ce seuil doivent suivre la structure hiérarchique du réseau. L’acheminement des deux types de demandes est optimisé, d'abord séparément puis conjointement via plusieurs étapes dans lesquelles les sous-problèmes sont résolus avec le PLM. Différents seuils sont testés pour déterminer lequel donne les meilleurs solutions et temps de calcul. Ces tests montrent qu’un meilleur taux de remplissage n’aboutit pas à un plan de transport moins cher dans notre cas.De plus, l'algorithme hiérarchique permet d'avoir des plans de transport nettement meilleurs que ceux appliqués sur le terrain, ceux obtenus via une utilisation directe du PLM et même ceux obtenus avec l'algorithme k-Clusters. Enfin, nous implémentons ces algorithmes et présentons les résultats numériques. Cela montre que le paradigme diviser-pour-régner est efficace pour la conception de réseau de services lorsqu'il s'applique à un problème industriel de grande taille.
Databáze: OpenAIRE
Externí odkaz: