An Adaptive Large Neighborhood Search Algorithm for Tactical Planning of a Single-Segment Corridor Network in a Many-to-one-to-many Transportation System

Le transport de marchandises est un processus physique de transport de marchandises et d'expéditions entre différents terminaux par voie maritime, aérienne ou terrestre entre différentes zones. Cette thèse porte sur un réseau Many-to-One-to-Many (M1M), un cadre décisionnel où un côté du système comprend de nombreux expéditeurs, producteurs, grossistes, distributeurs, prestataires de services logistiques, etc. -demandes de demande de transport efficace en termes de coûts et de temps de chargements de produits. De l'autre côté du système M1M, de nombreux transporteurs font des offres de capacité de transporteur pour le transport, demandant des chargements rentables. Dans ce contexte, les transporteurs peuvent être des fournisseurs de services de transport de divers modes, par exemple, les chemins de fer, les compagnies aériennes, la navigation fluviale et océanique, et différents types, par exemple, des transporteurs complets ou partiels. Le modèle proposé considère un réseau de corridor à segment unique comprenant de nombreuses demandes de demande des expéditeurs à transférer d'un terminal d'origine à un terminal de destination, qui ont tous deux une capacité d'entreposage à toutes les périodes. Pour résoudre le modèle proposé, une solution initiale est construite par un algorithme heuristique. Ensuite, cette solution est améliorée par une Recherche Adaptive Large Voisinage (ALNS) combinant une recherche locale utilisant huit opérateurs de suppression pour détruire une solution et quatre opérateurs d'insertion pour la réparer. Enfin, l'algorithme proposé est testé sur différents benchmarks et analysé avec soin pour évaluer les performances de chaque opérateur et de l'algorithme heuristique constructif. L'une des principales conclusions de la comparaison d'algorithmes est que l'ALNS proposé peut obtenir des solutions avec un écart d'optimalité de 11 % pour résoudre de très grands ensembles de données en moins d'une minute. Cependant, le solveur exact peut trouver les solutions en une heure environ pour résoudre les données mentionnées ou ne peut pas les obtenir dans les délais. Les solutions obtenues par ALNS montrent des écarts d'environ 10%, et ce fait signifie que l'ALNS n'a pas été très efficace pour résoudre notre problème.

Abstract

Freight transportation is a physical process for the transportation of commodities and shipments among different terminals by sea, air, or land between different zones. This thesis focuses on a Many-to-One-to-Many (M1M) networks, a decision-making framework where one side of the system includes many shippers, producers, wholesalers, distributors, logistics service providers and so on, making shipper-demand requests for cost and time-efficient transportation of product loads. On the other side of the M1M system, many carriers make carrier-capacity offers for transportation, requesting profitable loads. In this context, carriers may be transportation service providers of diverse modes, e.g., railroads, airlines, river and ocean navigation, and different types, e.g., full or less-than-truckload carriers. The proposed model considers a single-segment corridor network including many shipper-demand requests to be transferred from an origin terminal to a destination terminal, both of which have a warehousing capacity in all time periods. To solve the proposed model, an initial solution is constructed by a heuristic algorithm. Then, this solution is improved by an Adaptive Large Neighborhood Search (ALNS) combining a local search using eight removal operators to destroy a solution and four insertion operators to repair it. Finally, the proposed algorithm is tested on different benchmarks and analyzed carefully to assess the performance of each operator and of the constructive heuristic algorithm. One main finding of the algorithm comparison is that the proposed ALNS can achieve solutions with an 11% optimality gap for solving very large data sets in less than one minute. However, the exact solver either can find the solutions in around one hour for solving the mentioned data or cannot get them in time limitation. The solutions obtained by ALNS shows gaps around 10% and this fact represents that the ALNS was not very efficient for addressing our problem.