Diese Dissertation verknüpft eisenbahnbetriebswissenschaftliche Grundlagen mit Methoden aus den Disziplinen Unternehmensforschung (Operations Research) und Maschinelles Lernen. Gegenstand ist die auf den mittelfristigen Zeithorizont bezogene Ressourcenplanung von Knoten des Schienengüterverkehrs, die sogenannte taktische Planung. Diese spielt eine wesentliche Rolle für eine wirtschaftliche und qualitativ hochwertige Betriebsdurchführung. Knoten des Schienengüterverkehrs stellen neuralgische Punkte in der Transportkette von Waren auf der Schiene dar. Sie dienen der Durchführung einer Vielzahl unterschiedlicher betrieblicher Prozesse zur Sicherstellung eines definierten Outputs an Zügen in Abhängigkeit eines jeweils gegebenen Inputs. Die Bereitstellung eines zu den Betriebsanforderungen passenden Ressourcengerüsts ist Teil der taktischen Planung und hat wesentlichen Einfluss auf die Qualität der Prozesse in den Knoten, im Speziellen, sowie auf die vor- und nachgelagerte Transportdurchführung im Allgemeinen. Die Bemessung des notwendigen Personals, der Betriebsmittel und der Infrastruktur für einen Betriebstag, die sogenannte Ressourcendimensionierung, ist in der Praxis geprägt durch einen erheblichen manuellen Aufwand sowie eine große Abhängigkeit von der Datenqualität. Vor diesem Hintergrund und zur Überwindung dieser Nachteile schlägt diese Dissertation ein neues Verfahren zur Ressourcendimensionierung vor. Exemplarisch wird der Fokus auf die großen Knoten des Einzelwagenverkehrs gelegt, die sogenannten Rangierbahnhöfe. In diesen werden Eingangszüge zerlegt, Güterwagen entsprechend ihrer Ausgangsrichtung sortiert und gesammelt, sowie neue Ausgangszüge gebildet und bereitgestellt. Nach dem Stand der Technik werden für die Ressourcendimensionierung mehrere Monate bis wenige Wochen vor der Betriebsdurchführung Rangierarbeitspläne erstellt. Diese umfassen einen detaillierten Arbeitsfolgenplan inklusive Terminierung von Prozessen sowie deren Ressourcenbelegung. Die Rangierarbeitspläne bilden die Grundlage für die Ressourcenanforderung. Aufgrund sich ändernder Nebenbedingungen vor dem Betriebstag und dem stochastischen Charakter der Betriebsprozesse sowohl im Netz als auch in den Knoten können die in der taktischen Planung erstellten Rangierarbeitspläne nur begrenzt für die Durchführung verwendet werden. Als Beispiele sollen das Einlegen von Sonderzügen, Unregelmäßigkeiten bei den Transporten und Witterungsauswirkungen angeführt werden. Der betriebene Planungsaufwand begründet sich in den komplexen Zusammenhängen zwischen den Betriebsprozessen und der größtenteils fehlenden EDV-Unterstützung, was eine Ermittlung der Ressourcendimensionierung bisher erschwert. Die Folge ist eine Diskrepanz zwischen der Datenqualität als Eingangsgröße für die Planung und der Präzision des Rangierarbeitsplans als Ausgangsgröße, was als Konsequenz eine Scheingenauigkeit der Planung und unter Umständen eine Über- oder Unterdimensionierung der Ressourcen mit sich bringt. Das zeigt, dass die Planung verkürzt werden muss und neue Hilfsmittel erforderlich sind. Motiviert durch diese Diskrepanz und den neuen Möglichkeiten, die die Methoden aus den Bereichen des Operations Research und des Maschinellen Lernens bieten, stellt diese Dissertation ein neues Planungsverfahren Parabola bereit. Parabola ermittelt mit geringerem Planungsaufwand und hoher Qualität relevante Kenngrößen für die Ressourcendimensionierung in Knoten des Schienengüterverkehrs. Dies beschleunigt den taktischen Planungsprozess, reduziert Scheingenauigkeiten bei der Ressourcendimensionierung vor der Betriebsdurchführung und orientiert sich daran, wann welche Entscheidungen zuverlässig und genau zu treffen sind. Folglich wird die Detailtiefe der Planung mit der Zuverlässigkeit der Daten in Einklang gebracht. Das in der Dissertation bereitgestellte Planungsverfahren Parabola analysiert eine ausreichend große Anzahl errechneter Rangierarbeitspläne und / oder historischer Betriebsdaten. Das dabei trainierte Regressionsmodell wird anschließend zur Bestimmung des Ressourcengerüsts genutzt. Die Kalibrierung der Regressionsmodelle erfordert hinreichend viele Rangierarbeitspläne. Für deren Erzeugung wird exemplarisch am Beispiel von Rangierbahnhöfen in dieser Dissertation ein ganzheitliches mathematisches lineares Programm entwickelt, das erstmalig sämtliche für die taktische Planung eines Rangierbahnhofs relevanten Entscheidungsprobleme vom Zugeingang bis zum Zugausgang abbildet. Dieses beinhaltet die Definition der Verknüpfung zwischen Eingangs- und Ausgangszügen, sogenannter Wagenübergänge, sowie die Terminierung sämtlicher Betriebsprozesse mit ihrer Zuweisung zu örtlichen Mitarbeitern, Betriebsmitteln und Infrastruktur. Die bestehenden mathematischen Modelle in der bisherigen Literatur beschränken sich lediglich auf Teile dieses Problems. Es folgt die systematische Erzeugung von Problemstellungen, sogenannten Instanzen, zur Generierung eines repräsentativen Testpools. Die Instanzen dieses NP-schweren Problems sind für generische, exakte Lösungsverfahren in akzeptabler Zeit nicht zuverlässig lösbar. Daher wird eine maßgeschneiderte Metaheuristik, konkret ein Verfahren der Klasse Adaptive Large Neighborhood Search (ALNS), entwickelt. Diese bewegt sich durch den Lösungsraum, indem schrittweise mittels mehrerer miteinander konkurrierender Subheuristiken eine vorher gefundene Lösung erst zerstört und anschließend wieder repariert wird. Durch unterschiedliche Charakteristika der Subheuristiken und einer statistischen Auswertung ihres jeweiligen Beitrags zum Lösungsfortschritt, gelingt es der ALNS, sich an das Stadium der Lösungssuche und an die jeweilige Problemstruktur anzupassen. Die in dieser Dissertation entwickelte ALNS erzeugt für realistische Instanzen eines Betriebstages Lösungen in hoher Qualität binnen weniger Minuten Rechenzeit. Basierend auf den erzeugten Rangierarbeitsplänen wurden für die Entwicklung des Planungsverfahrens insgesamt fünf Regressionstechniken getestet, die die Ausgangsgrößen der Pläne – Bedarf an Lokomotiven, Personal und Infrastruktur – prognostizieren. Die vielversprechendsten Ergebnisse werden durch die Methoden Tree Boosting sowie Random Forest erzielt, die in über 90 % der Fälle den Ressourcenbedarf für Personale und Lokomotiven exakt und für Infrastruktur mit einer Toleranz von einem Gleis je Gleisgruppe prognostizieren. Damit ist dieses Regressionsmodell nach ausreichender Kalibrierung entsprechend örtlicher Randbedingungen geeignet, komplexere Planungsverfahren zu ersetzen. Die Regressionsmodelle ermöglichen die Abstrahierung von Mengengerüsten und Leistungsverhalten von Knoten des Schienengüterverkehrs. Daher ist beispielsweise ein konkreter Fahrplan von und zu den Knoten nicht mehr notwendige Voraussetzung für die taktische Planung in Rangierbahnhöfen. Da das Regressionsverfahren aus vielen Rangierarbeitsplänen lernt, verringert sich die Abhängigkeit von einzelnen Instanzen. Durch die Kenntnis von vielen anderen Plänen können robustere Ressourcengerüste prognostiziert werden. Neben dem in dieser Dissertation ausgearbeiteten Anwendungsfall in der taktischen Planung in Knoten des Schienengüterverkehrs, eröffnet das vorgeschlagene neue Planungsverfahren Parabola eine Vielzahl an weiteren Einsatzfeldern. Die Interpretation des trainierten Regressionsmodells erlaubt das tiefgründige Verständnis des Verhaltens von Knoten des Schienengüterverkehrs. Dies ermöglicht ein besseres Verstehen der Engpässe in diesen Knoten sowie die Identifikation relevanter Treiber der Ressourcendimensionierung. Weiter können diese Modelle bei der Erstellung von netzweiten Leistungsanforderungen Berücksichtigung finden. Mit der in dieser Dissertation erfolgten Bereitstellung von Parabola wird durch Nutzung neuartiger Methoden aus dem Operations Research und Maschinellen Lernen das Instrumentarium der eisenbahnbetriebswissenschaftlichen Verfahren und Modelle sinnvoll erweitert. / This dissertation combines the knowledge of railway operations management with methods from operations research and machine learning. It focuses on rail freight facilities, especially their resource planning at a tactical level. The resource planning plays a crucial role for economical operations at high quality. The rail freight facilities represent neuralgic points in the transport chain of goods by rail. Their task is to carry out a multitude of different operational processes to ensure a defined output of trains, depending on a given input. Providing resource requirements appropriate to the amount of work has a significant impact on the quality of the processes in the facilities in particular and on the up- and downstream transport performance in general. The correct dimensioning of resource requirements, which include the necessary staff, locomotives, and infrastructure for an operating day, is characterized by a considerable manual effort and a large dependency on the data accuracy. Against this background and to overcome these drawbacks, this dissertation proposes a new method for resource requirements. The focus is on the large facilities of single wagonload traffic, the so-called classification yards, in which inbound trains are disassembled, railcars are classified according to their outbound direction, and new outbound trains are formed. Nowadays, shunting work plans are created several months to a few weeks before operations. These operating plans comprise a detailed work sequence plan, including process scheduling, and resource allocation. The operating plans form the basis for resource requirements. Due to the changing constraints prior to operations, e.g., the addition of special trains, and the stochastic nature of the operational processes, for instance caused by weather conditions, shunting work plans can only be used for execution to a limited extent. This effort is made for planning due to the complex interdependencies between the operational processes and the predominant lack of IT support, which makes it difficult to determine resource requirements. The result is a discrepancy between the accuracy of the data as an input variable and the precision of the shunting work plan as an output variable. This leads to an illusory precision of the planning and possibly to an oversizing or undersizing of the resources. Hence, planning must be shortened and new tools are required. Motivated by this discrepancy and the new possibilities offered by methods from the _elds of operations research and machine learning, this dissertation provides a new planning method Parabola. Parabola determines with less planning effort and at high quality relevant parameters for resource requirements in rail freight facilities. This accelerates the planning process, reduces illusory precision before operations are carried out and enables decision-making with sufficient reliability due to the data accuracy. Consequently, the level of detail of the planning is harmonized with the reliability of the data. The planning procedure Parabola involves the analysis of numerous calculated operating plans and / or historical operating data. This trains a regression model that can then be used to determine the resource requirements. The calibration of the regression models requires many operating plans. For their generation, an integrated mathematical linear program is developed in this dissertation using the example of classification yards; for the first time, one program covers all relevant decision problems of tactical planning in a classification yard, from the train arrival to the train departure. This includes the definition of the connection between inbound and outbound trains, so-called railcar interchanges, as well as the scheduling of all operational processes with their assignment to local staff, locomotives, and infrastructure. All existing mathematical models in the literature are limited to parts of the problem. Thereafter follows a systematic generation of a test pool of problems named instances. The instances of this NP-hard problem cannot be reliably solved within an acceptable time frame with general-purpose solvers. Therefore, a tailored metaheuristic, namely an adaptive large neighborhood search (ALNS), is developed. It moves through the solution space by first destroying and then repairing a solution stepwise. Several competing subheuristics are available for this purpose. The ALNS combines multiple subheuristics, which have different characteristics and contribute to the solution progress, as determined by statistical evaluation. Consequently, the ALNS successfully adapts to the progress of the solution and to the problem structure. The ALNS, which is developed in this dissertation, generates high-quality solutions for realistic instances of an operating day in a few minutes of computing time. Based on the generated operating plans, five regression methods predicting the output variables of the operating plans – demand for locomotives, staff, and infrastructure – are tested. The most promising results are achieved by the methods tree boosting and random forest, which predict the resource requirements in over 90% of the cases for staff and locomotives accurately and for infrastructure with a tolerance of one track per bowl. Thus, a regression model can replace the more complex planning procedures after sufficient calibration according to local restrictions. The regression models allow the abstraction of quantity structures and performance behavior. Hence, for example, a dedicated timetable is no longer a prerequisite for tactical planning in classification yards. Since regression methods learn from many operating plans, the dependence on individual instances is reduced. By knowing many other plans, the regression model can predict robust resource requirements. In addition to the use case in tactical planning in rail freight facilities, the proposed new planning method Parabola opens a multitude of further _elds of application. By interpreting the trained regression model, the behavior of rail freight facilities can be understood in depth. Under certain circumstances, this allows a better understanding of the bottlenecks in these facilities and the relevant drivers of resource dimensioning. Furthermore, these models have potential applications in the design of network-wide performance requirements. By providing Parabola in this dissertation, the toolbox of railroad management science procedures and models is sensibly extended by using novel methods from operations research and machine learning.

This dissertation integrates the strengths of individual emergent delivery technologies with package characteristics, and rural community needs to meet the demand for equitable, accessible, and inclusive rural delivery that is also cost-effective. To find ways to meet the package delivery service needs in rural areas and to fill research gaps in rural package delivery modeling, this study introduced a novel model known as the Parallel Scheduling Vehicle Routing Problem (PSVRP) in an endeavor to revolutionize package delivery by enhancing its efficiency, accessibility, and cost-effectiveness. The PSVRP represents a state-of-the-art approach to vehicle routing problems, incorporating a diversified fleet of innovative delivery modes. The multi-modal fleet of electric vans, ADVs, drones, and truck-drone systems works in unison to minimize operational costs in various settings. A solution methodology that implemented the Adaptive Large Neighborhood Search (ALNS) algorithm was designed to solve the PSVRP in this research to produce optimal or near-optimal solutions. A variety of scenarios in a rural setting that include different quantities of customers to deliver to and different package weights are tested to evaluate if a multi-modal fleet of electric vans, ADVs, drones, and truck-drone systems can provide cost-effective, low emissions, and efficient rural delivery services from local stores. Different fleet combinations are compared to demonstrate the best combined fleet for rural package delivery. It was found that implementation of electric vans, ADVs, drones, and truck-drone systems does decrease rural package delivery cost, but it does not yet decrease cost enough for the return on investment to be high enough for industry to implement the technology. Additionally, it was found that electric technologies do significantly decrease emissions of package delivery in rural areas. However, without a carbon tax or regulation mandating reduced carbon emissions, it is unlikely that the delivery industry will quickly embrace these new delivery modes. This dissertation not only advances academic understanding and practical applications in vehicle routing problems but also contributes to social equity by researching methods to improve delivery services in underserved rural communities. The PSVRP model could benefit transportation professionals considering technology-enabled rural delivery, developing rural delivery plans, looking for cost-effective rural delivery solutions, implementing a heterogeneous fleet to optimize rural delivery, or planning to reduce rural delivery emissions. It is anticipated that these innovations will spur further research and investment into rural delivery optimization, fostering a more inclusive and accessible package delivery service landscape. / Doctor of Philosophy / This dissertation integrates the strengths of individual emergent delivery technologies with package characteristics, and rural community needs to meet the demand for equitable, accessible, and inclusive rural delivery that is also cost-effective. To find ways to meet the package delivery service needs in rural areas and to fill research gaps in rural package delivery modeling, this study introduced a novel model known as the Parallel Scheduling Vehicle Routing Problem (PSVRP) in an endeavor to revolutionize package delivery by enhancing its efficiency, accessibility, and cost-effectiveness. The PSVRP represents a state-of-the-art approach to vehicle routing problems, incorporating a diversified fleet of innovative delivery modes. The multi-modal fleet of electric vans, ADVs, drones, and truck-drone systems works in unison to minimize operational costs in various settings. A solution methodology that implemented the Adaptive Large Neighborhood Search (ALNS) algorithm was designed to solve the PSVRP in this research to produce optimal or near-optimal solutions. A variety of scenarios in a rural setting that include different quantities of customers to deliver to and different package weights are tested to evaluate if a multi-modal fleet of electric vans, ADVs, drones, and truck-drone systems can provide cost-effective, low emissions, and efficient rural delivery services from local stores. Different fleet combinations are compared to demonstrate the best combined fleet for rural package delivery. It was found that implementation of electric vans, ADVs, drones, and truck-drone systems does decrease rural package delivery cost, but it does not yet decrease cost enough for the return on investment to be high enough for industry to implement the technology. Additionally, it was found that electric technologies do significantly decrease emissions of package delivery in rural areas. However, without a carbon tax or regulation mandating reduced carbon emissions, it is unlikely that the delivery industry will quickly embrace these new delivery modes. This dissertation not only advances academic understanding and practical applications in vehicle routing problems but also contributes to social equity by researching methods to improve delivery services in underserved rural communities. The PSVRP model could benefit transportation professionals considering technology-enabled rural delivery, developing rural delivery plans, looking for cost-effective rural delivery solutions, implementing a heterogeneous fleet to optimize rural delivery, or planning to reduce rural delivery emissions. It is anticipated that these innovations will spur further research and investment into rural delivery optimization, fostering a more inclusive and accessible package delivery service landscape.

Cette thèse porte sur le développement de modèles mathématiques et d’algorithmes d’optimisation pour la conception de chaînes logistiques durables. Nous proposons des modèles mono-périodiques, multi-produits et multi-modes de transport à quatre niveaux (fournisseurs, unités de production, entrepôts et clients) couvrant les piliers économique et environnemental du développement durable. Les variables de décision concernent la localisation des sites logistiques intermédiaires (unités de production et entrepôts), les choix de technologie et de mode de transport, et la détermination des flux de produits. Un premier modèle est basé uniquement sur la minimisation des coûts totaux. Ce modèle est étendu au cas bi-objectif en considérant la minimisation des émissions de CO2. Nous proposons une procédure d’optimisation basée sur la recherche à voisinage large (LNS : Large Neighborhood Search). L’application de cette méthode à un problème à variables mixtes tel que la conception de chaîne logistique est inédite. Notre extension au cas bi-objectif fait intervenir l’algorithme récent de recherche locale multi-directionnelle. Les expérimentations numériques permettent d’évaluer la pertinence de nos modèles et de comparer les performances de nos algorithmes à celles d’un solveur du marché. / This thesis focuses on the development of mathematical models and optimization algorithms for the design of sustainable supply chains. We propose single-period, multi-commodity, multi-mode, four level models (suppliers, production facilities, warehouses and customers) covering economic and environmental pillars of sustainable development. The decision variables are related to the location of the intermediate logistics sites (production units and warehouses), the choice of technology and mode of transport, and the determination of product flow. A first model is based solely on minimizing total costs. This model is extended to bi-objective minimization by considering CO2 emissions. We propose an optimization procedure based on the Large Neighborhood Search (LNS) metaheuristic, which had almost never been applied to problems with mixed variables such as design supply chain. Our extension to the bi-objective case involves the use of the multi-directional local search (MDLS). Extensive numerical experiments assess the relevance of our model and compare the performance of our algorithms to those of a state-of-the-art solver.

No description available.

Dans ce mémoire, nous étudions un problème de tournées de véhicules dans lequel une flotte privée de véhicules n’a pas la capacité suffisante pour desservir les demandes des clients. Dans un tel cas, on fait appel à un transporteur externe. Ce dernier n’a aucune contrainte de capacité, mais un coût est encouru lorsqu’un client lui est affecté. Il n’est pas nécessaire de mettre tous les véhicules de la flotte privée en service si cette approche se révèle plus économique. L’objectif consiste à minimiser le coût fixe des véhicules, puis le coût variable de transport et le coût chargé par le transporteur externe. Notre travail consiste à appliquer la métaheuristique de recherche adaptative à grand voisinage sur ce problème. Nous comparons nos résultats avec ceux obtenus précédemment avec différentes techniques connues sur les instances de Christofides et celles de Golden. / In this master thesis, we study a vehicle routing problem in which a private fleet does not have sufficient capacity to serve all customers. Therefore, an external common carrier is required. The external common carrier has no constraint of capacity, but there is a cost when a customer it assigned to it. It is not necessary for all the vehicles of the private fleet to be used. The objective is to minimize the sum of the fixed cost of the private fleet, the variable routing cost and the external carrier cost. Our work applies the adaptative large neighborhood search metaheuristic on this problem. We compare our results with those obtained previously with different well-known techniques on the benchmark instances of Christofides and Golden.

De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire. / Many practical problems arising in real-world applications in the field of logistics can be modeled as vehicle routing problems (VRP). In broad terms, VRPs deal with designing optimal routes for delivering goods or services to a number of geographically scattered customers in a context in which, routing costs are minimized. Depending on the type of problem, one or several depots may be present. Routing problems are among the most difficult combinatorial optimization problems. In this dissertation we study a special combinatorial optimization problem, belonging to the class of the vehicle routing problem that is strongly linked to the context of the transportation networks. We introduce a new problem setting, which is mainly inspired by the activities of collecting milk from production farms and distributing the collected product to processing plants in Quebec. Two different variants of this problem setting are considered. The first variant seeks a tactical routing plan for the milk collection-distribution problem over a given planning horizon assuming that the production level over the considered horizon is fixed. The second variant aims to provide a more accurate plan by taking into account potential variations in terms of production level, which may occur during the course of a horizon. This thesis is cast into three main parts, as follows: In the first part, we describe an exact algorithm for the first variant of the problem, which is characterized by the presence of time windows, multiple depots, and a heterogeneous fleet of vehicles, where the objective is to minimize the routing cost. To this end, the problem is modeled as a multi-attribute vehicle routing problem. The exact algorithm proposed is based on the column generation approach, coupled with an elementary shortest path algorithm with resource constraints. In the second part, we design an exact framework to address the second variant of the problem. To this end, the problem is modeled as a multi-period vehicle routing problem, which explicitly takes into account potential production level variations over a horizon. New strategies are proposed to tackle the particular structure of the multi-period elementary shortest path algorithm with resource constraints. To solve realistic instances of the second variant of the problem in reasonable computation times, a heuristic approach is required. In the third part of this thesis, we propose an adaptive large neighborhood search, where various new exploration and exploitation strategies are proposed to improve the performance of the algorithm in terms of solution quality and computational efficiency.

Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future. / This thesis studies vehicle routing problems with time windows, where a gain is associated with each customer and where the objective is to maximize the total gain collected minus the routing costs. Furthermore. the same vehicle might be assigned to different routes during the planning horizon. This problem has received little attention in the literature in spite of its importance in practice. For example, in the home delivery of perishable goods (like food), routes of short duration must be combined to form complete workdays. We believe that this type of problem will become increasingly important in the future with the advent of electronic services, like e-groceries, where customers can order goods through the Internet and get these goods delivered at home. In the first chapter of this thesis, we present a review of vehicle routing problems with gains, as well as vehicle routing problems with multiple use of vehicles. We discuss the general classes of problem-solving approaches for these problems, namely, exact methods, heuristics and metaheuristics. We also introduce dynamic vehicle routing problems, where new information is revealed as the routes are executed. In the second chapter, we describe an exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, where the first objective is to maximize the number of served customers. To this end, the problem is modeled as a vehicle routing problem with gains. The exact algorithm is based on column generation, coupled with an elementary shortest path algorithm with resource constraints. To solve realistic instances in reasonable computation times, a heuristic approach is required. The third chapter proposes an adaptative large neighborhood search where the various hierarchical levels of the problem are exploited (i.e., complete vehicle workdays, routes within workdays and customers within routes). The fourth chapter deals with the dynamic case. In this chapter, a strategy for accepting or rejecting new customer requests is proposed. This strategy is based on the generation of multiple scenarios for different realizations of the requests in the future. An opportunity cost for serving a new request is then computed, based on an evaluation of the scenarios with and without the new request. Finally, the last chapter summarizes the contributions of this thesis and proposes future research avenues.

De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire. / Many practical problems arising in real-world applications in the field of logistics can be modeled as vehicle routing problems (VRP). In broad terms, VRPs deal with designing optimal routes for delivering goods or services to a number of geographically scattered customers in a context in which, routing costs are minimized. Depending on the type of problem, one or several depots may be present. Routing problems are among the most difficult combinatorial optimization problems. In this dissertation we study a special combinatorial optimization problem, belonging to the class of the vehicle routing problem that is strongly linked to the context of the transportation networks. We introduce a new problem setting, which is mainly inspired by the activities of collecting milk from production farms and distributing the collected product to processing plants in Quebec. Two different variants of this problem setting are considered. The first variant seeks a tactical routing plan for the milk collection-distribution problem over a given planning horizon assuming that the production level over the considered horizon is fixed. The second variant aims to provide a more accurate plan by taking into account potential variations in terms of production level, which may occur during the course of a horizon. This thesis is cast into three main parts, as follows: In the first part, we describe an exact algorithm for the first variant of the problem, which is characterized by the presence of time windows, multiple depots, and a heterogeneous fleet of vehicles, where the objective is to minimize the routing cost. To this end, the problem is modeled as a multi-attribute vehicle routing problem. The exact algorithm proposed is based on the column generation approach, coupled with an elementary shortest path algorithm with resource constraints. In the second part, we design an exact framework to address the second variant of the problem. To this end, the problem is modeled as a multi-period vehicle routing problem, which explicitly takes into account potential production level variations over a horizon. New strategies are proposed to tackle the particular structure of the multi-period elementary shortest path algorithm with resource constraints. To solve realistic instances of the second variant of the problem in reasonable computation times, a heuristic approach is required. In the third part of this thesis, we propose an adaptive large neighborhood search, where various new exploration and exploitation strategies are proposed to improve the performance of the algorithm in terms of solution quality and computational efficiency.

Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future. / This thesis studies vehicle routing problems with time windows, where a gain is associated with each customer and where the objective is to maximize the total gain collected minus the routing costs. Furthermore. the same vehicle might be assigned to different routes during the planning horizon. This problem has received little attention in the literature in spite of its importance in practice. For example, in the home delivery of perishable goods (like food), routes of short duration must be combined to form complete workdays. We believe that this type of problem will become increasingly important in the future with the advent of electronic services, like e-groceries, where customers can order goods through the Internet and get these goods delivered at home. In the first chapter of this thesis, we present a review of vehicle routing problems with gains, as well as vehicle routing problems with multiple use of vehicles. We discuss the general classes of problem-solving approaches for these problems, namely, exact methods, heuristics and metaheuristics. We also introduce dynamic vehicle routing problems, where new information is revealed as the routes are executed. In the second chapter, we describe an exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, where the first objective is to maximize the number of served customers. To this end, the problem is modeled as a vehicle routing problem with gains. The exact algorithm is based on column generation, coupled with an elementary shortest path algorithm with resource constraints. To solve realistic instances in reasonable computation times, a heuristic approach is required. The third chapter proposes an adaptative large neighborhood search where the various hierarchical levels of the problem are exploited (i.e., complete vehicle workdays, routes within workdays and customers within routes). The fourth chapter deals with the dynamic case. In this chapter, a strategy for accepting or rejecting new customer requests is proposed. This strategy is based on the generation of multiple scenarios for different realizations of the requests in the future. An opportunity cost for serving a new request is then computed, based on an evaluation of the scenarios with and without the new request. Finally, the last chapter summarizes the contributions of this thesis and proposes future research avenues.

<p>Online retail sales and grocery/food orders have been breaking records every year. As a result, third-party delivery companies have found an opportunity to get their share from the growing transportation network. Electric vehicles (EVs) are becoming a preferable choice for such large delivery systems due to their environmental benefits. However, EVs have limited-service ranges; therefore, intra-route facilities are needed for EVs to stay operational. These facilities offer charging stations for EVs and storage areas for requests, e.g., food and packages. In this dissertation, we propose a novel <em>Pickup and Delivery Problem</em> (PDP) with EVs and transfers. There are requests to be picked up and delivered. EVs leave their origin depot, serve requests, and return to their destination depot. Unlike the generic PDP, intra-route facilities allow EVs to exchange requests. Thus, a request can be transported by more than one vehicle. In this dissertation, three new problems are introduced, and the following research questions are investigated: 1) "How valuable is to include intra-route facilities and allow transfers in a pickup and delivery network with EVs?", 2) "What is the cost of locating intra-route facilities randomly rather than finding the best locations while creating the routes for EVs?", and 3) "How much can drones improve the delivery speed in a pickup and delivery network with EVs and transfers?". A <em>Mixed-integer Linear Programming</em> (MILP) model and a <em>Simulated Annealing</em> (SA) algorithm are developed and compared with each other to answer the first question. For the second question, a MILP model is formulated; however, due to unreasonable computational runtimes, a SA algorithm and an <em>Adaptive Large Neighborhood Search</em> (ALNS) algorithm are proposed. Finally, a MILP model is developed for the hybrid-fleet problem. The overall results highlight that intra-route facilities shorten the total traveled distance in the PDP network by allowing exchanges and recharging.</p>