Der Trend zu kleinteiligeren und kapitalintensiveren Transportgütern führt in Kombination mit der in Europa angestrebten Reduktion von Treibhausgasemissionen im Transportsektor zu einer Zunahme der Bedeutung von effizienten Konsolidierungsnetzwerken des Schienengüterverkehrs. Zugehörige Produktionsformen mit Bündelung von Warenströmen wie der Einzelwagenverkehr und der intermodale Verkehr sind somit erfolgskritisch für die Zukunftsfähigkeit des Schienengüterverkehrs. Deren Wettbewerbsfähigkeit kann durch die Einführung und Nutzung von Innovationen gestärkt werden. Beispiele hierfür sind eine Digitale Automatische Kupplung (DAK) sowie Sensoren an Güterwagen und Lokomotiven. Diese Innovationen werden oftmals von einem hohen monetären Aufwand sowie Unsicherheiten hinsichtlich ihrer genauen betrieblichen Wirkung in den Netzwerken begleitet. Für strategische Entscheidungen hinsichtlich einer Einführung solcher Innovationen sind die ökonomischen und betrieblichen Effekte für gezielte Nutzen-Kosten-Betrachtungen aufzuzeigen sowie mögliche Pfade für eine Migration der jeweiligen Innovation für die Produktionsformen und deren zugehörigen Netzwerke zu eruieren. Dabei sind insbesondere die Veränderungen im sogenannten Service Network Design (SND) von großer Bedeutung. Das SND ist Teil der taktischen Netzwerkplanung und definiert das Zuggerüst sowie die Wagenroutenplanung im Netzwerk. Dabei werden die Kosten für den Betrieb von Netzwerken unter Einhaltung definierter Qualitätsstandards minimiert. Das Ergebnis des SND stellt den Rahmen für konkrete Wagenrouten in der betrieblichen Durchführung dar und definiert das zu behandelnde Zuggerüst in den Bündelungsknoten der Netzwerke. Trotz der wichtigen Funktion des SND, ist dieser taktische Planungsprozess in der Praxis noch stark manuell geprägt und daher zeitaufwändig. Außerdem liefert er oft zu ungenaue Aussagen. Das trifft insbesondere auf Aussagen zu den Netzeffekten durch Innovationen zu. Aufgrund der hohen Komplexität von Konsolidierungsnetzwerken des Schienengüterverkehrs und fehlender EDV-Unterstützung basieren Betrachtungen zu den Effekten von Innovationen in Netzwerken im Status Quo auf Expertenbefragungen und Abschätzungen. Insbesondere für Innovationen, deren Migration mit weitreichenden Prozessänderungen im Netzwerk und neuen Betriebsstrategien verbunden ist, bedarf es jedoch objektiver modellbasierter Verfahren zur Entscheidungsunterstützung. Durch deren Einsatz könnten die Auswirkungen in Bezug auf Netzwerkstrukturen und Kosten ermittelt und für Entscheidungsträger:innen transparent dargestellt werden. Die vorliegende Dissertation leistet einen wissenschaftlichen Beitrag, um dieses Potenzial zu erschließen. Hierfür wird im Rahmen der Dissertation eine neue Methode als Beitrag zur Entscheidungsunterstützung für die Einführung und Migration von Innovationen in Konsolidierungsnetzwerken des Schienengüterverkehrs entwickelt: TRENO (TRansparent Evaluation of InNOvation Effects in Rail Freight Service Networks). Die Methode kombiniert dabei eisenbahnbetriebswissenschaftliche Grundlagen mit Ansätzen aus dem Operations Research und dem maschinellen Lernen. Prozessveränderungen durch Innovationen werden analysiert und in einem neuartigen mathematischen Optimierungsmodell für das SND abgebildet. Das Modell ermöglicht die Definition von verschiedenen Betriebsstrategien im Netzwerk und bildet erstmals zeitbezogene Infrastrukturnutzungen von Zügen in den Knoten des Netzwerks ab. Da die Einführung von Innovationen mit hoher Unsicherheit hinsichtlich der Annahmen und Eingangsparameter verbunden ist, sind zahlreiche Szenarien für eine fundierte Entscheidungsunterstützung zu definieren und zu bewerten. Aufgrund der hohen Komplexität von SND Modellen sind Berechnungen mittels mathematischer Optimierung sehr zeitintensiv. Daher nutzt TRENO Klassifizierungs- und Regressionsmodelle aus dem Bereich des maschinellen Lernens, welche die mathematische Optimierung ergänzen. Auf Basis eines Pools von Szenarien, für welche optimale Netzwerkstrukturen mithilfe mathematischer Optimierung berechnet wurden, lernen die Klassifizierungs- und Regressionsmodelle den Zusammenhang zwischen Eingangsdaten und den resultierenden Kennzahlen des Netzwerks. Nach diesem Training können die Modelle dazu eingesetzt werden, die Kennzahlen von Netzwerken (insbesondere Kosten, Zuggerüste sowie Auslastungen von Zügen und Bündelungsknoten) für zahlreiche neue Szenarien innerhalb von Sekunden vorherzusagen. Dies stellt eine maßgebliche Beschleunigung gegenüber der mathematischen Optimierung dar. Die Klassifizierungsmodelle werden genutzt, um die grundsätzliche (Un-)Lösbarkeit eines Szenarios vorherzusagen, die beispielsweise durch unzureichende Kapazitäten in den Zugbildungsanlagen resultieren kann. Die Regressionsmodelle prognostizieren spezifische metrische Kennzahlen des Netzwerks wie Kosten, Zuggerüste und Kapazitätsauslastungen. Neben dieser Kernfunktionalität von TRENO ermöglicht die Integration der SHAP Methode (shapley additive explanations) eine Analyse bezüglich des Einflusses der Eingangsparameter auf die Kennzahlen eines Konsolidierungsnetzwerks. Dies erlaubt den Aufbau eines tiefgründigen Verständnisses der Wirkungszusammenhänge in Konsolidierungsnetzwerken des Schienengüterverkehrs (z. B. durch die Identifikation von maßgeblichen Kostentreibern) und wirkt einem grundsätzlichen Problem aus dem Bereich des maschinellen Lernens, der mangelnden Interpretierbarkeit der Modelle, entgegen. TRENO wird anhand eines praxisnahen Anwendungsfalls validiert, der Planung einer Migration einer DAK in einem exemplarischen europäischen Einzelwagenverkehrsnetz. Hierbei wird mit TRENO untersucht, welchen Einfluss verschiedene Betriebsstrategien während einer Migration einer DAK auf die Kosten und Strukturen im Netzwerk haben. Das Anwendungsbeispiel zeigt auf, dass sich mit TRENO verschiedene komplexe Betriebsstrategien mathematisch modellieren lassen. Durch die Anwendung der Methode werden die konkreten Effekte der Betriebsstrategien auf die definierten Kennzahlen des Netzwerks transparent gemacht. Dies ermöglicht neue Schlussfolgerungen aus eisenbahnbetriebswissenschaftlicher Sicht hinsichtlich der Wahl von Betriebsstrategien während einer Migration. Ferner zeigen die Ergebnisse die hohe Qualität der Prognosen durch die Klassifizierungs- und Regressionsmodelle auf. Beim Test von vier Klassifizierungs- und fünf Regressionsmodellen erzielen Modelle auf Basis des Gradient Boosting Verfahrens die besten Ergebnisse. Für die Klassifizierung erzielt das Modell in 94% der Fälle richtige Vorhersagen. Das Regressionsmodell erzielt im Durchschnitt über alle Kennzahlen ein Bestimmtheitsmaß von 93% und kann damit einen Großteil der Varianz in den Datensätzen erklären. TRENO stellt somit einen anwendbaren Beitrag dar, um den manuellen Prozess zur Planung von Konsolidierungsnetzwerken im Schienengüterverkehr insbesondere für den Fall der Einführung von Innovationen maßgeblich zu beschleunigen und zu automatisieren. Der modellbasierte Ansatz objektiviert die Entscheidungsunterstützung gegenüber dem Status Quo und ermöglicht zudem eine weitreichende Exploration des Einflusses von Innovationen auf die Strukturen des Netzwerks über zahlreiche Szenarien. Hierdurch erweitert die Dissertation das Methodenspektrum der Eisenbahnbetriebswissenschaften durch die Verzahnung mit Verfahren aus dem Operations Research sowie des maschinellen Lernens. / The trend towards small-scale and more capital-intensive transport goods means that the importance of rail freight consolidation networks is increasing. Production forms such as single wagonload transport and intermodal transport are therefore critical for the future potential of rail freight. The competitiveness of rail freight networks can be strengthened through the introduction of innovations such as a Digital Automatic Coupling (DAC) and sensors on freight wagons and locomotives. These innovations are often accompanied by high investment costs and uncertainties regarding their specific operational impact in the networks. For strategic decisions regarding the introduction of such innovations, the economic and operational effects must be identified and quantified, e.g., for benefit-cost considerations. In this context, the changes in the so-called Service Network Design (SND) are of particular importance. The SND determines train service structures and the freight distribution in networks at the tactical planning level. The number and schedule of operated train services in the network significantly determines the costs and quality of consolidation networks in rail freight. It provides the framework for specific railcar routings at the operational level and defines the number of trains to be handled in the bundling nodes of the networks. Despite this outstanding importance of the SND, the tactical planning of consolidation networks is still a manual process in practice lacking computer-based decision support. This is particularly true for statements on network effects of innovations. Due to the high complexity of consolidation networks in rail freight transport and the lack of computer-based decision support, analyses regarding the effects of innovations in service networks are mainly based on expert interviews in the status quo. Especially for innovations whose migration is associated with extensive process transformations and new operating strategies in the network, there is a need for objective model-based methods to support decision-making. Thereby, the operational effects of innovations on service network structures and costs could be determined and made transparent to decision-makers. This dissertation contributes to close this gap and to enable an efficient planning of consolidation networks. For this purpose, the dissertation develops a new method as a contribution to decision support for the introduction and migration of innovations in consolidation networks of rail freight transport: TRENO (TRansparent Evaluation of InNOvation Effects in Rail Freight Service Networks). The method combines rail transport planning with approaches from operations research and machine learning. Process changes due to innovations are analyzed and depicted in a novel mathematical optimization model for the SND. The model enables the definition of different operating strategies in the network and incorporates dynamic infrastructure usages of trains in the nodes of the network. Since the introduction of innovations is associated with a high degree of uncertainty regarding the underlying assumptions and input parameters, numerous scenarios have to be defined and evaluated for a sound decision support. Due to the high complexity of SND models, mathematical optimization is computationally expensive and time-consuming. Therefore, TRENO applies classification and regression models from the field of machine learning complementing mathematical optimization. Based on a set of scenarios for which optimal network structures have been computed using mathematical optimization, the classification and regression models learn the relationship between input data and the resulting key figures of the network. After training, the models can be used to predict the key figures of networks for various new scenarios within seconds (in particular cost structures, the number of operated train services and utilization of trains and yards). This represents a significant acceleration compared to mathematical optimization. The classification models are used to predict the feasibility of a scenario, which can, for example, result from insufficient capacities in the nodes of the network. The regression models predict specific metrics of the network such as costs, train service structures and capacity utilization. In addition to this core functionality of TRENO, the integration of the SHAP method (shapley additive explanations) allows an analysis of the influence of input parameters on the key figures of a consolidation network. This contributes to the understanding of the interdependencies in consolidation networks of rail freight transport (e.g., by identifying major cost drivers) and counteracts a fundamental problem from the field of machine learning, the lack of interpretability of the models. TRENO is validated on the basis of a relevant use case, the planning of a migration of a DAC in an exemplary European single wagonload network. Here, TRENO is used to investigate the influence of different operating strategies during a migration of a DAC on the costs and service structures in the network. The example shows that different complex operating strategies can be modelled with TRENO. By applying the method, the specific effects of the operating strategies on the defined key figures of the network are made transparent. This enables to draw new conclusions from a rail transport planning perspective regarding the choice of operating strategies during a migration. Furthermore, the results show the high quality of the predictions by the classification and regression models. When testing four classification and five regression algorithms, models based on gradient boosting achieve the best results. For classification, the model yields correct predictions in 94% of the cases. The regression model achieves an average coefficient of determination of 93% across all key figures and can thereby explain a large part of the variance in the data. TRENO thus represents an applicable contribution to significantly automate and accelerate the manual process for planning consolidation networks in rail freight transport, especially for the case of the introduction of innovations. The model-based approach provides a more objective decision support compared to the status quo and enables to study the influence of innovations on the structures of service networks over numerous scenarios. Hereby, the dissertation expands the methodological spectrum of rail transport planning by linking it with methods from operations research and machine learning.

In the distribution network of a large retailer, shipments can either be transported by the retailer's own trucks or outsourced to third-party logistics (3PL) companies. In the former case, shipments are consolidated and transported from their origins through an intermediate facility, namely a crossdock. At a crossdock, shipments are unloaded, sorted, re-consolidated, loaded and transported to their destinations. The consolidation process offers economies of scale that reduce the transportation costs. At the same time, it increases travel distances and incurs handling costs at a crossdock. For this reason, consolidation is uneconomic for a shipment in which origin and destination are located close to one other, especially through a distant crossdock. It is cheaper to outsource transportation of such a shipment to 3PL companies. This shipping decision raises a series of questions. Should a shipment be consolidated through a crossdock or outsourced to 3PL companies? How do facility locations, the operational cost of a crossdock and mode of shipments influence the shipping decision? Can the robustness and potential growth of a crossdock be measured? How does outsourcing affect the robustness and potential growth of a crossdock? We formulate a strategic model of a retailer's distribution network as an economic trade-off between consolidated shipments through a crossdock and outsourced shipments to 3PL companies. We study the locus of facility locations where the costs of a consolidated shipment and an outsourced shipment are equal and discover that the trade-off can be modeled by classical geometric curves, particularly an ellipse, a hyperbola, a limacon and a Cartesian oval. These curves can be developed into a preliminary routing and locating tool. We also observe interesting connections between the single hub crossdocking network and other fields of geometric study, such as Voronoi diagrams and geometric inversion. In addition, the area bounded by these curves represents the likelihood in which a particular shipment is consolidated through a crossdock. We expand this concept to multiple vendor-store pairs and suggest an index that measures robustness and potential growth of a particular crossdock. This asymptotic-probability index explains economic driving factors of consolidation and outsourcing. Although the derivation of the index is limited by the dimension and spatial distribution of facilities, its numerical value can be determined by a computer simulation. Therefore, we use Monte Carlo simulation to compute the proposed index to explain the outsourcing and the interaction between TL threshold0.1 and mode of shipments. The analysis and computer simulation suggest that outsourcing may cause an adverse effect in a single hub crossdocking network, resulting in the abrupt reduction of consolidated shipments in the network. Furthermore, we propose transportation planning to alleviate this effect and compare them to the optimal allocation. The routing and locating application of the model is illustrated using the Home Depot distribution network. Our model predicts 5.5% and additional 1.0% savings in transportation cost by re-allocation of shipments and re-location of crossdocks, respectively. The empirical study shows that the adverse effect of outsourcing can be eliminated by limiting the number of crossdocks used by each store.

Cette thèse a pour but d’apporter des solutions méthodologiques pour la mutualisation des transports entre les fournisseurs et les plateformes de la grande distribution. Cette mutualisation permet en effet de réduire les coûts, les émissions de CO2, et d’augmenter la qualité de service. Elle est organisée autour d’un réseau de plateformes de cross-docking appelées Centres de Routage Collaboratifs, développé par la société 4S Network. Nos travaux consistent à modéliser et résoudre à l’aide de techniques de recherche opérationnelle plusieurs problèmes d’optimisation du transport dans le réseau mutualisé. Le verrou scientifique majeur est de résoudre conjointement un problème de plan de chargement (Service Network Design Problem) dans un réseau logistique national, et des problèmes de tournées de véhicules à une échelle régionale. Nous prenons en compte des contraintes additionnelles issues du monde industriel et les tarifs réellement pratiqués par les transporteurs, notamment des coûts non linéaires.Les problèmes d’optimisation résultants sont résolus au moyen de méthodes ditesmatheuristiques, c’est-à-dire combinant des approches exactes telles que la génération de colonnes et des approches (méta)heuristiques telles que la recherche tabou. Les algorithmes développés dans cette thèse ont donné lieu à unoutil logiciel aujourd’hui en exploitation chez 4S Network. / The main purpose of this PhD. thesis is to provide methodological solutions for a collaborative transport between suppliers and retail platforms. The outcomes of this collaboration are numerous:cost reduction, greenhouse gas emission reduction and higher quality of service. The network is structured around cross-docking platforms developed by the company 4S Network. We model and solve several optimization problems in this collaborative network, using operationsresearch techniques. The major scientific challenge is to simultaneously solve a Service Network Design Problem in a national logistics network and several Vehicle Routing Problems at regional level. We consider additional constraints and prevailing pricing arising from the carriers, in particular non-linear costs. The resulting optimization problems are solved by matheuristic methods, that combine exact approaches as column generation and (meta)heuristic approaches as tabu search. The algorithms developed in this thesis are the core functions of a software tool developed for 4S network.

Le mémoire présente le problème de la planification tactique des “blocks” pour le transport ferroviaire intermodal, qui a été peu étudié jusqu’à présent. Nous proposons un nouveau modèle de design de réseau en tenant compte de la spécificité du transport intermodal. La recherche se concentre sur le contexte nord-américain et fait suite à une étroite collaboration avec l’une des principales compagnies ferroviaires nord-américaines. Le “blocking” constitue une importante opération de transport ferroviaire de marchandises, par laquelle des wagons d’origines et de destinations potentiellement différentes sont regroupés pour être d´eplacés et manipulés comme une seule unité, ce qui permet des économies d’échelle. La littérature se limite aux travaux traitant le problème classique du blocage des trains, où la demande est exprimée en termes de wagons. A notre connaissance, aucun travail préalable n’a été consacrè à un contexte de transport intermodal, où la demande est exprimée en termes de conteneurs à dèplacer d’un terminal d’origine donné vers un terminal de destination donné, introduisant ainsi un processus de consolidation supplémentaire. Nous proposons un modèle de “blocking” qui prend en compte plusieurs types de conteneurs et wagons, intégrant l’affectation conteneur-wagon. Nous présentons un nouveau modèle de design de réseau à trois couches en temps continu formulé sous la forme d’un programme linéaire mixte en nombres entiers (MILP), dans le but de minimiser le coût total de transport composé par la sélection de blocs, les coûts d’exploitation et la gestion du coût de la demande. Le modèle peut être résolu en utilisant un solveur commercial pour des tailles réalistes. Nous illustrons les performances et l’intérêt de la méthode proposée à travers une étude de cas approfondie d’un important chemin de fer nord-américain. / The thesis presents the tactical block-planning problem for intermodal railroads, which has been little studied so far. We propose a new block service network design model considering the specificity of intermodal rail. The research focuses on the North American context and follows a close collaboration with one of the major North American railroad companies. Blocking constitutes an important rail freight transport operation, by which cars with potentially different origins and destinations are grouped to be moved and handled as a single unit, yielding economies of scale. The literature is limited to works addressing the classical train blocking problem, where demand is given in terms of cars to be blocked among specific OD pairs. To the best of our knowledge, no prior work has been dedicated to an intermodal transportation context, where demand is expressed in terms of containers to be moved from a given origin terminal to a given destination terminal, hence introducing an additional consolidation process. We propose a blocking model that considers several types of containers and railcars, integrating the container-to-car assignment. We present a new continuous-time, three-layer service network design model formulated as a Mixed Integer Linear Program (MILP), with the objective of minimizing the total transportation cost composed by block selection, operation costs, and handling demand cost. The model can be solved using commercial solver for realistic sizes. We illustrate the performance and interest of the proposed method through an extensive case study of a major North American railroad.

Cette thèse étudie une approche intégrant la gestion de l’horaire et la conception de réseaux de services pour le transport ferroviaire de marchandises. Le transport par rail s’articule autour d’une structure à deux niveaux de consolidation où l’affectation des wagons aux blocs ainsi que des blocs aux services représentent des décisions qui complexifient grandement la gestion des opérations. Dans cette thèse, les deux processus de consolidation ainsi que l’horaire d’exploitation sont étudiés simultanément. La résolution de ce problème permet d’identifier un plan d’exploitation rentable comprenant les politiques de blocage, le routage et l’horaire des trains, de même que l’habillage ainsi que l’affectation du traffic. Afin de décrire les différentes activités ferroviaires au niveau tactique, nous étendons le réseau physique et construisons une structure de réseau espace-temps comprenant trois couches dans lequel la dimension liée au temps prend en considération les impacts temporels sur les opérations. De plus, les opérations relatives aux trains, blocs et wagons sont décrites par différentes couches. Sur la base de cette structure de réseau, nous modélisons ce problème de planification ferroviaire comme un problème de conception de réseaux de services. Le modèle proposé se formule comme un programme mathématique en variables mixtes. Ce dernie r s’avère très difficile à résoudre en raison de la grande taille des instances traitées et de sa complexité intrinsèque. Trois versions sont étudiées : le modèle simplifié (comprenant des services directs uniquement), le modèle complet (comprenant des services directs et multi-arrêts), ainsi qu’un modèle complet à très grande échelle. Plusieurs heuristiques sont développées afin d’obtenir de bonnes solutions en des temps de calcul raisonnables. Premièrement, un cas particulier avec services directs est analysé. En considérant une cara ctéristique spécifique du problème de conception de réseaux de services directs nous développons un nouvel algorithme de recherche avec tabous. Un voisinage par cycles est privilégié à cet effet. Celui-ci est basé sur la distribution du flot circulant sur les blocs selon les cycles issus du réseau résiduel. Un algorithme basé sur l’ajustement de pente est développé pour le modèle complet, et nous proposons une nouvelle méthode, appelée recherche ellipsoidale, permettant d’améliorer davantage la qualité de la solution. La recherche ellipsoidale combine les bonnes solutions admissibles générées par l’algorithme d’ajustement de pente, et regroupe les caractéristiques des bonnes solutions afin de créer un problème élite qui est résolu de facon exacte à l’aide d’un logiciel commercial. L’heuristique tire donc avantage de la vitesse de convergence de l’algorithme d’ajustement de pente et de la qualité de solution de la recherche ellipsoidale. Les tests numériques illustrent l’efficacité de l’heuristique proposée. En outre, l’algorithme représente une alternative intéressante afin de résoudre le problème simplifié. Enfin, nous étudions le modèle complet à très grande échelle. Une heuristique hybride est développée en intégrant les idées de l’algorithme précédemment décrit et la génération de colonnes. Nous proposons une nouvelle procédure d’ajustement de pente où, par rapport à l’ancienne, seule l’approximation des couts liés aux services est considérée. La nouvelle approche d’ajustement de pente sépare ainsi les décisions associées aux blocs et aux services afin de fournir une décomposition naturelle du problème. Les résultats numériques obtenus montrent que l’algorithme est en mesure d’identifier des solutions de qualité dans un contexte visant la résolution d’instances réelles. / This thesis studies a scheduled service network design problem for rail freight transportation planning. Rails follow a special two level consolidation organization, and the car-to-block, block-to-service handling procedure complicates daily operations. In this research, the two consolidation processes as well as the operation schedule are considered simultaneously, and by solving this problem, we provide an overall cost-effective operating plan, including blocking policy, train routing, scheduling, make-up policy and traffic distribution. In order to describe various rail operations at the tactical level, we extend the physical network and construct a 3-layer time-space structure, in which the time dimension takes into consideration the temporal impacts on operations. Furthermore, operations on trains, blocks, and cars are described in different layers. Based on this network structure, we model the rail planning problem to a service network design formulation. The proposed model relies on a complex mixed-integer programming formulation. The problem is very hard to solve due to the computational difficulty as well as the tremendous size of the application instances. Three versions of the problem are studied, which are the simplified model (with only non-stop services), complete model (with both non-stop and multi-stop services) and very-large-scale complete model. Heuristic algorithms are developed to provide good feasible solutions in reasonable computing efforts. A special case with non-stop services is first studied. According to a specific characteristic of the direct service network design problem, we develop a tabu search algorithm. The tabu search moves in a cycle-based neighborhood, where flows on blocks are re-distributed according to the cycles in a conceptual residual network. A slope scaling based algorithm is developed for the complete model, and we propose a new method, called ellipsoidal search, to further improve the solution quality. Ellipsoidal search combines the good feasible solutions generated from the slope scaling, and collects the features of good solutions into an elite problem, and solves it with exact solvers. The algorithm thus takes advantage of the convergence speed of slope scaling and solution quality of ellipsoidal search, and is proven effective. The algorithm also presents an alternative for solving the simplified problem. Finally, we work on the very-large-size complete model. A hybrid heuristic is developed by integrating the ideas of previous research with column generation. We propose a new slope scaling scheme where, compared with the previous scheme, only approximate service costs instead of both service and block costs are considered. The new slope scaling scheme thus separates the block decisions and service decisions, and provide a natural decomposition of the problem. Experiments show the algorithm is good to solve real-life size instances.

Cette thèse étudie une approche intégrant la gestion de l’horaire et la conception de réseaux de services pour le transport ferroviaire de marchandises. Le transport par rail s’articule autour d’une structure à deux niveaux de consolidation où l’affectation des wagons aux blocs ainsi que des blocs aux services représentent des décisions qui complexifient grandement la gestion des opérations. Dans cette thèse, les deux processus de consolidation ainsi que l’horaire d’exploitation sont étudiés simultanément. La résolution de ce problème permet d’identifier un plan d’exploitation rentable comprenant les politiques de blocage, le routage et l’horaire des trains, de même que l’habillage ainsi que l’affectation du traffic. Afin de décrire les différentes activités ferroviaires au niveau tactique, nous étendons le réseau physique et construisons une structure de réseau espace-temps comprenant trois couches dans lequel la dimension liée au temps prend en considération les impacts temporels sur les opérations. De plus, les opérations relatives aux trains, blocs et wagons sont décrites par différentes couches. Sur la base de cette structure de réseau, nous modélisons ce problème de planification ferroviaire comme un problème de conception de réseaux de services. Le modèle proposé se formule comme un programme mathématique en variables mixtes. Ce dernie r s’avère très difficile à résoudre en raison de la grande taille des instances traitées et de sa complexité intrinsèque. Trois versions sont étudiées : le modèle simplifié (comprenant des services directs uniquement), le modèle complet (comprenant des services directs et multi-arrêts), ainsi qu’un modèle complet à très grande échelle. Plusieurs heuristiques sont développées afin d’obtenir de bonnes solutions en des temps de calcul raisonnables. Premièrement, un cas particulier avec services directs est analysé. En considérant une cara ctéristique spécifique du problème de conception de réseaux de services directs nous développons un nouvel algorithme de recherche avec tabous. Un voisinage par cycles est privilégié à cet effet. Celui-ci est basé sur la distribution du flot circulant sur les blocs selon les cycles issus du réseau résiduel. Un algorithme basé sur l’ajustement de pente est développé pour le modèle complet, et nous proposons une nouvelle méthode, appelée recherche ellipsoidale, permettant d’améliorer davantage la qualité de la solution. La recherche ellipsoidale combine les bonnes solutions admissibles générées par l’algorithme d’ajustement de pente, et regroupe les caractéristiques des bonnes solutions afin de créer un problème élite qui est résolu de facon exacte à l’aide d’un logiciel commercial. L’heuristique tire donc avantage de la vitesse de convergence de l’algorithme d’ajustement de pente et de la qualité de solution de la recherche ellipsoidale. Les tests numériques illustrent l’efficacité de l’heuristique proposée. En outre, l’algorithme représente une alternative intéressante afin de résoudre le problème simplifié. Enfin, nous étudions le modèle complet à très grande échelle. Une heuristique hybride est développée en intégrant les idées de l’algorithme précédemment décrit et la génération de colonnes. Nous proposons une nouvelle procédure d’ajustement de pente où, par rapport à l’ancienne, seule l’approximation des couts liés aux services est considérée. La nouvelle approche d’ajustement de pente sépare ainsi les décisions associées aux blocs et aux services afin de fournir une décomposition naturelle du problème. Les résultats numériques obtenus montrent que l’algorithme est en mesure d’identifier des solutions de qualité dans un contexte visant la résolution d’instances réelles. / This thesis studies a scheduled service network design problem for rail freight transportation planning. Rails follow a special two level consolidation organization, and the car-to-block, block-to-service handling procedure complicates daily operations. In this research, the two consolidation processes as well as the operation schedule are considered simultaneously, and by solving this problem, we provide an overall cost-effective operating plan, including blocking policy, train routing, scheduling, make-up policy and traffic distribution. In order to describe various rail operations at the tactical level, we extend the physical network and construct a 3-layer time-space structure, in which the time dimension takes into consideration the temporal impacts on operations. Furthermore, operations on trains, blocks, and cars are described in different layers. Based on this network structure, we model the rail planning problem to a service network design formulation. The proposed model relies on a complex mixed-integer programming formulation. The problem is very hard to solve due to the computational difficulty as well as the tremendous size of the application instances. Three versions of the problem are studied, which are the simplified model (with only non-stop services), complete model (with both non-stop and multi-stop services) and very-large-scale complete model. Heuristic algorithms are developed to provide good feasible solutions in reasonable computing efforts. A special case with non-stop services is first studied. According to a specific characteristic of the direct service network design problem, we develop a tabu search algorithm. The tabu search moves in a cycle-based neighborhood, where flows on blocks are re-distributed according to the cycles in a conceptual residual network. A slope scaling based algorithm is developed for the complete model, and we propose a new method, called ellipsoidal search, to further improve the solution quality. Ellipsoidal search combines the good feasible solutions generated from the slope scaling, and collects the features of good solutions into an elite problem, and solves it with exact solvers. The algorithm thus takes advantage of the convergence speed of slope scaling and solution quality of ellipsoidal search, and is proven effective. The algorithm also presents an alternative for solving the simplified problem. Finally, we work on the very-large-size complete model. A hybrid heuristic is developed by integrating the ideas of previous research with column generation. We propose a new slope scaling scheme where, compared with the previous scheme, only approximate service costs instead of both service and block costs are considered. The new slope scaling scheme thus separates the block decisions and service decisions, and provide a natural decomposition of the problem. Experiments show the algorithm is good to solve real-life size instances.

La gestion des ressources, équipements, équipes de travail, et autres, devrait être prise en compte lors de la conception de tout plan réalisable pour le problème de conception de réseaux de services. Cependant, les travaux de recherche portant sur la gestion des ressources et la conception de réseaux de services restent limités. La présente thèse a pour objectif de combler cette lacune en faisant l’examen de problèmes de conception de réseaux de services prenant en compte la gestion des ressources. Pour ce faire, cette thèse se décline en trois études portant sur la conception de réseaux. La première étude considère le problème de capacitated multi-commodity fixed cost network design with design-balance constraints(DBCMND). La structure multi-produits avec capacité sur les arcs du DBCMND, de même que ses contraintes design-balance, font qu’il apparaît comme sous-problème dans de nombreux problèmes reliés à la conception de réseaux de services, d’où l’intérêt d’étudier le DBCMND dans le contexte de cette thèse. Nous proposons une nouvelle approche pour résoudre ce problème combinant la recherche tabou, la recomposition de chemin, et une procédure d’intensification de la recherche dans une région particulière de l’espace de solutions. Dans un premier temps la recherche tabou identifie de bonnes solutions réalisables. Ensuite la recomposition de chemin est utilisée pour augmenter le nombre de solutions réalisables. Les solutions trouvées par ces deux méta-heuristiques permettent d’identifier un sous-ensemble d’arcs qui ont de bonnes chances d’avoir un statut ouvert ou fermé dans une solution optimale. Le statut de ces arcs est alors fixé selon la valeur qui prédomine dans les solutions trouvées préalablement. Enfin, nous utilisons la puissance d’un solveur de programmation mixte en nombres entiers pour intensifier la recherche sur le problème restreint par le statut fixé ouvert/fermé de certains arcs. Les tests montrent que cette approche est capable de trouver de bonnes solutions aux problèmes de grandes tailles dans des temps raisonnables. Cette recherche est publiée dans la revue scientifique Journal of heuristics. La deuxième étude introduit la gestion des ressources au niveau de la conception de réseaux de services en prenant en compte explicitement le nombre fini de véhicules utilisés à chaque terminal pour le transport de produits. Une approche de solution faisant appel au slope-scaling, la génération de colonnes et des heuristiques basées sur une formulation en cycles est ainsi proposée. La génération de colonnes résout une relaxation linéaire du problème de conception de réseaux, générant des colonnes qui sont ensuite utilisées par le slope-scaling. Le slope-scaling résout une approximation linéaire du problème de conception de réseaux, d’où l’utilisation d’une heuristique pour convertir les solutions obtenues par le slope-scaling en solutions réalisables pour le problème original. L’algorithme se termine avec une procédure de perturbation qui améliore les solutions réalisables. Les tests montrent que l’algorithme proposé est capable de trouver de bonnes solutions au problème de conception de réseaux de services avec un nombre fixe des ressources à chaque terminal. Les résultats de cette recherche seront publiés dans la revue scientifique Transportation Science. La troisième étude élargie nos considérations sur la gestion des ressources en prenant en compte l’achat ou la location de nouvelles ressources de même que le repositionnement de ressources existantes. Nous faisons les hypothèses suivantes: une unité de ressource est nécessaire pour faire fonctionner un service, chaque ressource doit retourner à son terminal d’origine, il existe un nombre fixe de ressources à chaque terminal, et la longueur du circuit des ressources est limitée. Nous considérons les alternatives suivantes dans la gestion des ressources: 1) repositionnement de ressources entre les terminaux pour tenir compte des changements de la demande, 2) achat et/ou location de nouvelles ressources et leur distribution à différents terminaux, 3) externalisation de certains services. Nous présentons une formulation intégrée combinant les décisions reliées à la gestion des ressources avec les décisions reliées à la conception des réseaux de services. Nous présentons également une méthode de résolution matheuristique combinant le slope-scaling et la génération de colonnes. Nous discutons des performances de cette méthode de résolution, et nous faisons une analyse de l’impact de différentes décisions de gestion des ressources dans le contexte de la conception de réseaux de services. Cette étude sera présentée au XII International Symposium On Locational Decision, en conjonction avec XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. En résumé, trois études différentes sont considérées dans la présente thèse. La première porte sur une nouvelle méthode de solution pour le "capacitated multi-commodity fixed cost network design with design-balance constraints". Nous y proposons une matheuristique comprenant la recherche tabou, la recomposition de chemin, et l’optimisation exacte. Dans la deuxième étude, nous présentons un nouveau modèle de conception de réseaux de services prenant en compte un nombre fini de ressources à chaque terminal. Nous y proposons une matheuristique avancée basée sur la formulation en cycles comprenant le slope-scaling, la génération de colonnes, des heuristiques et l’optimisation exacte. Enfin, nous étudions l’allocation des ressources dans la conception de réseaux de services en introduisant des formulations qui modèlent le repositionnement, l’acquisition et la location de ressources, et l’externalisation de certains services. À cet égard, un cadre de solution slope-scaling développé à partir d’une formulation en cycles est proposé. Ce dernier comporte la génération de colonnes et une heuristique. Les méthodes proposées dans ces trois études ont montré leur capacité à trouver de bonnes solutions. / Resource management in freight transportation service network design is an important issue that has been studied extensively in recent years. Resources such as vehicles, crews, etc. are factors that can not be ignored when designing a feasible plan for any service network design problem. However, contributions related to resource management issues and service network design are still limited. The goal of the thesis is to fill this gap by taking into account service network design problems with resource management issues. In this thesis, we propose and address three service network design problems that consider resource management. In the first study, we consider the capacitated multi-commodity fixed cost network design with design-balance constraints which is a basic sub-problem for many service design problems because of the capacitated multi-commodity structure as well as its design-balance property. We propose a three-phase matheuristic that combines tabu-search, path-relinking and an exactbased intensification procedure to find high quality solutions. Tabu-search identifies feasible solutions while path-relinking extends the set of feasible solutions. The solutions found by these two meta-heuristics are used to fix arcs as open or close. An exact solver intensifies the search on a restricted problem derived from fixing arcs. The experiments on benchmark instances show that the solution approach finds good solutions to large-scale problems in a reasonable amount of time. The contribution with regard to this study has been accepted in the Journal of Heuristics. In the second study, together with the consideration of the design of routes to transport a set of commodities by vehicles, we extend resources management by explicitly taking account of the number of available vehicles at each terminal. We introduce a matheuristic solution framework based on a cycle-based formulation that includes column generation, slope-scaling, heuristic and exact optimization techniques. As far as we know, this is the first matheuristic procedure developed for a cycle-based formulation. The column generation solves the linear relaxation model and provides a set of cycles to define the approximation model used in slopescaling loop. A heuristic is used to convert each solution to the approximation problem into a feasible solution. Memory-based perturbation procedure is used to enhance the performance of the algorithm. Experiments show that the proposed algorithm is able to find good feasible solutions for the problem. The contribution with regard to this study has been accepted for publication in Transportation Science. In the third study, we examine resources allocation issues in service network design. We aim to address a number of fleet utilization issues which usually appear at the beginning of the season because of the change of demand patterns: 1) reposition resources among terminals to account for shifts in demand patterns; 2) acquire (buy or long-term rent) new resources and as sign them to terminals; 3) outsource particular services. We present an integrated formulation combining these selection-location and scheduled service design decisions. The mixed-integer formulation is defined over a time-space network, the initial period modeling the location de cisions on resource acquisition and positioning, while the decisions on service selection and scheduling, resource assignment and cycling routing, and demand satisfaction being modeled on the rest of the network. We also present a matheuristic solution method combining slope scaling and column generation, discuss its algorithmic performance, and explore the impact of combining the location and design decisions in the context of consolidation carrier service design. This study will be presented at XII International Symposium On Locational Deci sion, in conjunction with the XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. In summary, three studies are considered in this thesis. The first one considers the capaciated multi-commodity fixed cost network design with design-balance constraints, a basic problem in many service network design problems with design-balance constraints. We propose an ef ficient three-phase matheuristic solution method that includes tabu search, path relinking and exact optimization. In the second study, we propose a new service network design model that takes into account resources limitations at each terminal. We also propose an advanced matheuristic framework solution method based on a cycle-based formulation which includes slope-scaling, column generation, heuristics and exact optimization for this problem. The last study addresses resources allocation issues in service network design. We introduce formula tions that model the reposition, acquisition/renting of resources and outsourcing of services. A solution framework based on the slope-scaling approach on cycle-based formulations is pro posed. Tests indicate that these proposed algorithms are able to find good feasible solutions for each of threse problems.

Le transport fluvial de conteneurs constitue une activité économique importante qui suscite un intérêt grandissant de la part de scientifiques. Considéré comme durable et économique, le transport par barge a été identifié comme étant une alternative compétitive pour le transport de marchandises, en complément des modes traditionnels de transport, routier et ferroviaire. Néanmoins, les travaux de recherche en rapport avec la planification et le management du transport par barge, en particulier dans le contexte du transport intermodal, sont encore peu abondants. Le but de cette thèse est d’apporter une contribution dans ce domaine, par la proposition de modèles et de méthodes de planification et gestion avancées, dans le cadre d’un système d’aide à la décision pour le transport de conteneurs par barge développé pour accompagner les opérateurs de transport. La méthodologie proposée fait appel à des concepts et principes de gestion du revenu, des ressources et des services de transport pour la conception de plans de services réguliers avec horaires, au niveau tactique. Les opérateurs de transport peuvent ainsi offrir des plans de transport avec des services plus flexibles pour leurs clients, tout en assurant un meilleur niveau de fiabilité. Plus de demandes de transport pourront ainsi être satisfaites, avec globalement une plus grande satisfaction des chargeurs. Une originalité importante proposée par notre approche est l’utilisation de principes et techniques de gestion du revenu (segmentation du marché, classes tarifaires...) aussi bien au niveau opérationnel de la modélisation qu’au niveau tactique. Les problèmes d’optimisation sont formalisés sous forme de modèles de programmation linéaire mixte en nombres entiers (PLNE), implémentés et testés sous différentes configurations de réseaux de transport et différents scénarios de demandes, et ce pour chaque niveau de décision. Au niveau tactique, une nouvelle approche de résolution, combinant la recherche adaptative à voisinage large (ALNS) et la recherche taboue, est proposée pour résoudre des problèmes PLNE de grande taille. Une plateforme de simulation, qui intègre les niveaux tactique et opérationnel de prise de décision, est proposée pour la validation du système d’aide à la décision sous différentes configurations : différentes topologies du réseau physique, différents paramètres pour la gestion du revenu, différents degrés de précision caractérisant les prévisions de demande. Pour l’analyse des résultats numériques ainsi obtenus, plusieurs types d’indicateurs de performance sont proposés et utilisés. / Barge transportation is an important research topic that started to draw increasing scientific attention in the recent decade. Considered as sustainable, environment-friendly and economical, barge transportation has been identified as a competitive alternative for freight transportation, complementing the traditional road and rail modes. However, contributions related to barge transportation, especially in the context of intermodal transportation, are still scarce. The objective of this thesis is to contribute to fill this gap by proposing a reactive decision support system for freight intermodal barge transportation from the perspective of the carriers. The proposed system incorporates resource and revenue management concepts and principles to build the optimal set of scheduled services plans at the tactical level. Carriers may thus benefit from transportation plans offering increased flexibility and reliability. They could thus serve more demands and better satisfy customers. One novelty of the approach is the application of revenue management considerations (e.g., market segmentation and price differentiation) at both operational and tactical planning levels. The optimization problems are mathematically formalized and mixed integer linear programming (MILP) models are proposed, implemented and tested against various network settings and demand scenarios, for each decision level. At the tactical level, a new solution approach, combining adaptive large neighborhood search (ALNS) and Tabu search is designed to solve large scale MILP problems. An integrated simulation framework, including the tactical and the operational levels jointly, is proposed to validate the decision support system in different settings, in terms of physical network topology, revenue management parameters and accuracy degree of demand forecasts. To analyze the numerical results corresponding to the solutions of the optimization problems, several categories of performance indicators are proposed and used.