Tesi sul tema "Railway problems"

Cette thèse est dédiée à la conception et à l’application d’algorithmes quantiques pour la résolution de problèmes d’optimisation combinatoire ferroviaires. Aujourd’hui, les problèmes d’optimisation auxquels fait face la SNCF sont complexes, empêchant souvent une résolution à l’optimalité via des méthodes classiques en un temps raisonnable. L’informatique quantique est pressentie pour améliorer la qualité des solutions et diminuer le temps de calcul pour certains de ces problèmes. Actuellement, les algorithmes quantiques pour l’optimisation se divisent en deux classes : les algorithmes exacts et les heuristiques. Les premiers présentent un avantage théorique pour plusieurs problèmes, mais ne sont pas implémentables sur les machines actuelles car trop gourmands en ressources. Les seconds sont implémentables dès aujourd’hui, au moins sur de petites instances, ouvrant la porte aux premières applications, bien qu’ils ne présentent pas encore de garanties de performances ni d'avantage quantique. Dans cette thèse, nous analysons et proposons des algorithmes qui appartiennent à chacune de ces deux classes.D’une part, nous étudions une classe d’heuristiques appelée Algorithmes Variationnels Quantiques. Il s’agit d’algorithmes hybrides quantique-classique, qui alternent entre l’exécution d’un circuit quantique paramétré et l’optimisation classique des paramètres. Ils permettent de résoudre des problèmes non contraints à variables binaires, et nous proposons une méthode générale pour reformuler des problèmes contraints à variables entières sous cette forme. Nous présentons certaines propriétés des Algorithmes Variationnels Quantiques, nécessaires pour envisager des preuves théoriques de garanties de performances. En particulier, nous étudions QAOA (Quantum Approximate Optimization Algorithm) en l'analysant à la lumière des précédentes propriétés et en donnant une décomposition universelle de son circuit quantique pour des problèmes dont la fonction objectif est polynomiale. Avec cet algorithme, nous résolvons un problème de conception de plan de transport de la SNCF. Ce problème a pour but de trouver un plan de transport qui correspond au meilleur compromis économique entre les bénéfices générés par la vente de billets aux voyageurs et les coûts d'exploitation, tout en respectant la disponibilité du réseau ferroviaire. Pour résoudre ce problème avec QAOA, nous proposons deux simplifications correspondant à différentes adaptations du problème métier initial.D’autre part, nous élaborons des algorithmes quantiques-classiques exacts pour deux grandes familles de problèmes combinatoires. La première famille concerne les problèmes d’ordonnancement. L’algorithme proposé s’applique à une large classe de problèmes d’ordonnancement à une machine, NP-difficiles, qui satisfont une propriété de programmation dynamique particulière (Dynamic Programming Across the Subsets). L’algorithme, reprenant l’idée de Ambainis et al. (2019), allie la programmation dynamique classique et l’algorithme quantique de recherche du minimum dans une table (basé sur l’algorithme de Grover). Il permet de réduire la complexité en temps pire-cas, parfois au détriment de l’introduction d’un terme pseudo-polynomial. Nous étendons cet algorithme au problème du flowshop à trois machines, pour lequel une accélération est aussi obtenue. La deuxième famille relève des problèmes d’optimisation robuste où l’ensemble d’incertitude est un polytope. Nous proposons un algorithme qui, partant de l’algorithme classique traitant de ces problèmes, remplace certaines opérations par des routines quantiques afin d’obtenir une accélération. Précisément, nous étudions l'utilisation des deux routines quantiques suivantes : la recherche du minimum dans une table et la résolution d’un système linéaire<br>This thesis is dedicated to the conception and application of quantum algorithms for railway combinatorial optimization problems. Today, the optimization problems that SNCF faces are complex, often prohibiting finding the optimal solution for industrial instances with classical methods within a reasonable amount of time. Quantum computing is expected to improve the quality of solutions and reduce the computation time for some of these problems. Quantum algorithms for optimization are divided into two classes: exact algorithms and heuristics. The former demonstrate theoretical advantages for several problems but cannot be implemented on current quantum machines because they require too high-quality quantum resources. On the contrary, the latter can be implemented, at least for small instances, but there are no performance guarantees or proven quantum advantages yet. In this thesis, we analyze and propose algorithms that belong to each of these two classes.On the one hand, we study the Variational Quantum Algorithms, which belong to the class of heuristics. These are hybrid quantum-classical algorithms that alternate between a parametrized quantum circuit and a classical optimizer. They allow solving unconstrained problems with binary variables, and we propose a general method to reformulate constrained integer problems into such problems. We highlight some properties of Variational Quantum Algorithms necessary for potential theoretical guarantees. In particular, we study QAOA (Quantum Approximate Optimization Algorithm) in light of the previous properties, and we provide a universal decomposition of the quantum circuit for problems whose objective function is polynomial. We solve with this algorithm a railway timetabling problem of SNCF. It consists of finding the transportation plan maximizing the operating profit according to the customers' demand taking into account the availability and cost of both the network and the rolling stock. To solve it with QAOA, we propose two simplifications with different adaptations of the original problem.On the other hand, we design exact quantum-classical algorithms for two broad families of combinatorial problems. The first family relates to scheduling problems. We propose an algorithm that tackles a large class of NP-hard single-machine scheduling problems, which satisfy a specific dynamic programming property (Dynamic Programming Across the Subsets). Our algorithm, based on the seminal idea of Ambainis et al. (2019), combines classical dynamic programming and quantum search of the minimum in a table (generalization of Grover Search). It reduces the worst-case time complexity, sometimes at the cost of an additional pseudopolynomial factor. We extend this algorithm to the 3-machine flowshop problem, also leading to a reduction of the complexity. The second family concerns robust optimization problems where the uncertainty set is a polytope. We present an algorithm that, relying on the classical method that deals with these problems, replaces some computations with quantum subroutines to achieve a speedup. Specifically, we study the two following quantum subroutines: the search of the minimum in a table and the resolution of a linear system

Recovering the timetable after a delay is essential to the smooth and efficient operation of the railways for both passengers and railway operators. Most current railway rescheduling research concentrates on static problems where all delays are known about in advance. However, due to the unpredictable nature of the railway system, it is possible that further unforeseen incidents could occur while the trains are running to the new rescheduled timetable. This will change the problem, making it a dynamic problem that changes over time. The aim of this work is to investigate the application of ant colony optimisation (ACO) to dynamic and dynamic multiobjective railway rescheduling problems. ACO is a promising approach for dynamic combinatorial optimisation problems as its inbuilt mechanisms allow it to adapt to the new environment while retaining potentially useful information from the previous environment. In addition, ACO is able to handle multi-objective problems by the addition of multiple colonies and/or multiple pheromone and heuristic matrices. The contributions of this work are the development of a junction simulator to model unique dynamic and multi-objective railway rescheduling problems and an investigation into the application of ACO algorithms to solve those problems. A further contribution is the development of a unique two-colony ACO framework to solve the separate problems of platform reallocation and train resequencing at a UK railway station in dynamic delay scenarios. Results showed that ACO can be e ectively applied to the rescheduling of trains in both dynamic and dynamic multi-objective rescheduling problems. In the dynamic junction rescheduling problem ACO outperformed First Come First Served (FCFS), while in the dynamic multi-objective rescheduling problem ACO outperformed FCFS and Non-dominated Sorting Genetic Algorithm II (NSGA-II), a stateof- the-art multi-objective algorithm. When considering platform reallocation and rescheduling in dynamic environments, ACO outperformed Variable Neighbourhood Search (VNS), Tabu Search (TS) and running with no rescheduling algorithm. These results suggest that ACO shows promise for the rescheduling of trains in both dynamic and dynamic multi-objective environments.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-03-10T12:31:18Z No. of bitstreams: 1 eduardopestanadeaguiar.pdf: 7884545 bytes, checksum: 182caace21281f7afce6554505811116 (MD5)<br>Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-03-13T17:18:31Z (GMT) No. of bitstreams: 1 eduardopestanadeaguiar.pdf: 7884545 bytes, checksum: 182caace21281f7afce6554505811116 (MD5)<br>Made available in DSpace on 2017-03-13T17:18:31Z (GMT). No. of bitstreams: 1 eduardopestanadeaguiar.pdf: 7884545 bytes, checksum: 182caace21281f7afce6554505811116 (MD5) Previous issue date: 2016-09-26<br>-<br>This thesis presents new fuzzy models applied to classification problems. With this regards, we introduce the use of set-membership concept, derived from the adaptive filter theory, into the training procedure of type-1 and singleton/non-singleton fuzzy logic systems, in order to reduce computational complexity and to increase convergence speed. Also, we present different criteria for using together with set-membership. Furthermore, we discuss the usefulness of delta rule delta, local Lipschitz estimation, variable step size and variable step size adaptive algorithms to yield additional improvement in terms of computational complexity reduction and convergence speed. Another important contribution of this thesis is to address the height type-reduction and to propose a modified version of interval singleton type-2 fuzzy logic system, so−called upper and lower singleton type-2 fuzzy logic system. The obtained results are compared with other models reported in the literature, demonstrating the effectiveness of the proposed classifiers and revealing that the proposals are able to properly handle with uncertainties associated with the measurements and with the data that are used to tune the parameters of the model. Based on data set provided by a Brazilian railway company, the models outlined above are applied in the classification of three possible faults and the normal condition of the switch machine, which is an equipment used for handling railroad switches. Finally, this thesis discusses the use of set-membership concept into the training procedure of an interval and singleton type-2 fuzzy logic system and of an upper and lower singleton type-2 fuzzy logic system, aiming to reduce computational complexity and to increase the convergence speed and the classification ratio. Also, we discuss the adoption of different criteria together with set-membership based-techniques. The performance is based on the data set composed of images provided by the same Brazilian railway company, which covers the four possible rail head defects and the normal condition of the rail head. The reported results show that the proposed models result in improved convergence speed, slightly higher classification ratio and remarkable computation complexity reduction when we limit the number of epochs for training, which may be required due to real time constraint or low computational resource availability.

Sveriges järnvägsnät är gammalt och utsätts för en allt högre belastning varje år i takt med att trafiken på spåren ökar. Detta medför att slitaget på järnvägarna ökar och en väldigt känslig del är spårväxlar. Då ca 20 % av alla fel beror på problem med spårväxlar läggs fokus i rapporten på att utreda denna problematik. Syftet med arbetet är att kartlägga vilka spårväxelfel som uppstår och orsaken till dessa, samt att komma med åtgärdsförslag för att minska problemen med spårväxlar som leder till förseningar och stopp i trafiken. Rapportens inledande del består av ett teoriavsnitt som beskriver hur en växel är uppbyggd och hur den fungerar. Tre bandelar i Sverige har studerats, en i norr, en i söder och en i Stockholm. Studierna har baserats på samtliga felrapporter tillhörande spårväxlar i Ofelia som rapporterats in mellan åren 2009 och 2012. Statistiken ger generella svar på vilka problem som uppstår i spårväxlar och i vilken omfattning de förekommer. Den visar också tydliga skillnader på år med svåra vintrar respektive år med mindre svåra vintrar. Resultatet av studierna visar att det är felkategorierna ”ingen känd orsak”, ”snö eller is” och ”materialutmattning/åldring” som förekommer mest frekvent. I rapportens avslutande del redovisas de mest frekventa kategorierna djupare. Idéer och förslag presenteras på eventuella lösningar. Förslagen är framför allt framtagna för att hantera problem orsakade av snö och is.<br>The Swedish railway network is old and it is subjected to an increasing load each year as the traffic on the railway tracks increases. This increases the wear on the tracks and a very sensitive part that constantly suffers problems is the railway switch. As the switches account for 20% of all the errors on the railway this report is focused on the problems related to switches. The aim of this work is to identify the problems with switches and what causes them. The aim is also to come up with proposals for measures to reduce the problems of switches that lead to delays and traffic jams. The first part of the report consists of a theory section that describes how a switch is constructed and how it works. Three railway distances in Sweden have been studied, one in the north parts of the country, one in the south and one in the city of Stockholm. These studies are based on all errors associated with switches that were reported in the Swedish error report system Ofelia during the years 2009 and 2012. These statistics provide general information about the problems that arise in switches in Swedish railway and to what extent they arise. The statistics also show a clear difference in the number of error reports during years with severe winter weather compared to less harsh winters. The report shows that errors reported as "no known cause", "snow and ice" and "material fatigue / aging" occurs most frequently. In the concluding section of the report the most frequent categories are presented in further detail. Based on this research, ideas and suggestions are presented. These proposals are mainly designed to handle problems caused by snow and ice.

Through this master’s degree thesis, I will try to investigate the development, the characteristics and the weak points of the Chongqing-Xinjiang-Europe International Railway line (also known as Yuxinou). It was created in 2011 and it links the municipality of Chongqing to the city of Duisburg in Germany. The municipality as well as the Yuxinou railway line are increasingly important for the Chinese propaganda, which has identified Chongqing as an important economic hub for the whole nation and the Yuxinou railway as the forerunner of the rail trade’s development between China and Europe. But how much is this railway contributing to the development of Sino-European trade relations? Can rail transport really replace the maritime transport or at least be a viable alternative? The first chapter focuses on the birth and development of Chongqing since 1997, when it became a municipality, until today. Its role in the Western Development Strategy and in the Belt and Road Initiative will be analyzed. The second chapter gives an overview of the rail and maritime connections that China has developed with the European countries and it makes a description of the two types of transport, highlighting their advantages and disadvantages, critical points and strengths. Finally, the third chapter focuses on the Yuxinou railway, it describes the context in which the railway was born and the complexities and difficulties that still characterize it today.

Les nouvelles attentes vis-à-vis des nouveaux trains à grande vitesse sont nombreuses: on les voudrait plus rapides, plus confortables, plus stables, tout en étant moins consommateur d'énergie, moins agressif vis-à-vis des voies, moins bruyants... Afin d'optimiser la conception de ces trains du futur, il est alors nécessaire de pouvoir se baser sur une connaissance précise de l'ensemble des conditions de circulations qu'ils sont susceptibles de rencontrer au cours de leur cycle de vie. Afin de relever ces défis, la simulation a un très grand rôle à jouer. Pour que la simulation puisse être utilisée dans des perspectives de conception, de certification et d'optimisation de la maintenance, elle doit alors être tout à fait représentative de l'ensemble des comportements physiques mis en jeu. Le modèle du train, du contact entre les roues et le rail, doivent ainsi être validés avec attention, et les simulations doivent être lancées sur des ensembles d'excitations qui sont réalistes et représentatifs de ces défauts de géométrie. En ce qui concerne la dynamique, la géométrie de la voie, et plus particulièrement les défauts de géométrie, représentent une des principales sources d'excitation du train, qui est un système mécanique fortement non linéaire. A partir de mesures de la géométrie d'un réseau ferroviaire, un paramétrage complet de la géométrie de la voie et de sa variabilité semblent alors nécessaires, afin d'analyser au mieux le lien entre la réponse dynamique du train et les propriétés physiques et statistiques de la géométrie de la voie. Dans ce contexte, une approche pertinente pour modéliser cette géométrie de la voie, est de la considérer comme un champ aléatoire multivarié, dont les propriétés sont a priori inconnues. En raison des interactions spécifiques entre le train et la voie, il s'avère que ce champ aléatoire n'est ni Gaussien ni stationnaire. Ce travail de thèse s'est alors particulièrement concentré sur le développement de méthodes numériques permettant l'identification en inverse, à partir de mesures expérimentales, de champs aléatoires non Gaussiens et non stationnaires. Le comportement du train étant très non linéaire, ainsi que très sensible vis-à-vis de la géométrie de la voie, la caractérisation du champ aléatoire correspondant aux défauts de géométrie doit être extrêmement fine, tant du point de vue fréquentiel que statistique. La dimension des espaces statistiques considérés est alors très importante. De ce fait, une attention toute particulière a été portée dans ces travaux aux méthodes de réduction statistique, ainsi qu'aux méthodes pouvant être généralisées à la très grande dimension. Une fois la variabilité de la géométrie de la voie caractérisée à partir de données expérimentales, elle doit ensuite être propagée au sein du modèle numérique ferroviaire. A cette fin, les propriétés mécaniques d'un modèle numérique de train à grande vitesse ont été identifiées à partir de mesures expérimentales. La réponse dynamique stochastique de ce train, soumis à un très grand nombre de conditions de circulation réalistes et représentatives générées à partir du modèle stochastique de la voie ferrée, a été ainsi évaluée. Enfin, afin d'illustrer les possibilités apportées par un tel couplage entre la variabilité de la géométrie de la voie et la réponse dynamique du train, ce travail de thèse aborde trois applications

This is a study of male occupational structure in the hinterland of the market town of Alcester, Warwickshire, c.1660 – c.1840. Various primary sources are used including the 1841 census, probate records, marriage licences and parish registers in order to compare occupations in thirty-six rural parishes centred on Alcester. The investigation focuses on various themes such as the changing interplay between agriculture and manufactures, specialisation and diversification by individuals and communities and the different economic paths taken by neighbouring settlements. The changing role of the market town and of the larger villages is discussed as some settlements become more industrialised and urbanised, while others stagnate and de-industrialise. To a large extent the economic development of the study area mirrors what was happening elsewhere in the nation, with an early growth in secondary occupations and a growth of tertiary occupations as the primary sector retreated. However, the unique feature of the study area is the rapid growth of the manufacture of needles and fish-hooks, firstly in the countryside, but later concentrating more on centres such as Redditch, which grew from a hamlet into a manufacturing town during the study period, eventually outgrowing the ancient market town of Alcester.

За останнє 10-річчя проблема негативного впливу транспорту в цілому і залізничного транспорту зокрема, на стан навколишнього середовища, отримала глобальний масштаб. У зв'язку з цим комісія Європейського Співтовариства (ЄС) визначила транспорт як одне із найбільш значних джерел забруднення. Тому, вирішення питання екологічної безпеки населення, вимагає удосконалення рухомого складу залізниці; освоєння нових екологічно безпечних технологій на залізницях України – запровадження інноваційних способів утилізації сміття та нечистот. При цитуванні документа, використовуйте посилання http://essuir.sumdu.edu.ua/handle/123456789/11780

The Single Track Railway Scheduling Problem can be modelled as a special case of the Job-Shop Scheduling Problem. This can be achieved by considering the train trips as jobs, which will be scheduled on tracks regarded as resources. A train trip may have many tasks that consist of traversing from one point to another on a track. Each of these distinct points can be a station or a signal placed along the track. Conflicts may occur when the desired timetable would result in two trains occupying the same section of the track at the same time. The mapping of the problem we have proposed in this thesis is a more realistic approach when modelling the physical representation of a track railway. This is because we take into account the actual signals placed along the track delimiting each track segment, avoiding thus the possibility of trains running into each other. Previous authors adopted an approximation to what is found in practice by adding minimum headway constraints between trains into their model. Two strategies for resolving the conflicts in a desired timetable are presented. The two strategies have their applicability in practice. For instance, resolving a conflict in the first strategy stems from the observed practice of train operators: in the first strategy a conflict is resolved by re-timing one of the trips at its departure time up to the point the conflict is resolved. Train operating companies do not typically want to plan for passenger trains being delayed after their departure. On the other hand, the second strategy resolves a conflict by delaying only the conflicting piece of one of the two trips (and subsequent pieces of that trip). In this way, the section of the trip before the conflicting point does not need to be re-timed. This procedure yields solutions with lower total delay. Moreover, with this second strategy, we can also handle the usual practice with passenger trains of not delaying them after their departure, as well as situations in which a train may be delayed along a trip in order to reslove a conflict. Furthermore, we present a group of practical constraints, incorporated into our software to solve the problem, that arise in real-life problems to which little attention has been paid. Using the algorithms developed in this thesis, we are able to solve 21 real-life single-track railway scheduling instances of problems, 19 of them to optimality.

COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR<br>A alta complexidade do processo logístico de transporte ferroviário de carga, propicia um ambiente favorável para o desenvolvimento de ferramentas de apoio à decisão que possibilitam uma melhor utilização dos recursos envolvidos. Neste trabalho é apresentado um modelo de programação inteira original para o Problema da Alocação ótima de Vagões e Locomotivas no curto prazo (PAVL). Esse problema consiste em determinar a movimentação de vagões (carregados e vazios) e locomotivas na malha de maneira a maximizar o retorno obtido pela demanda atendida no período considerado. Além disso, é apresentada uma extensão para esse modelo onde se permite atrasar ou adiantar trens no primeiro dia do horizonte de planejamento. Esse problema foi resolvido de maneira ótima ou quase ótima em tempo razoável, tanto em termos acadêmicos como para sua utilização prática. São apresentados o problema, a formulação do modelo, as técnicas de pré-processamento utilizadas, assim como resultados computacionais de instâncias reais.<br>The complexity of the logistic process in railway freight transportation provides a natural environment for the development of decision support tools that allow the companies to make a more efficient use of their resources. In this work we present an original integer programming model for the Cars and Locomotives short-term Allocation Problem. This problem consists in determining the movement of the cars (loaded and empty) and locomotives on the railway network in order to maximize the profit obtained with the requested demand in the given period. We also present an extension of the model in which certain delays and anticipations of trains on the first day of the period are allowed. For all instances tested, this problem was solved to optimality or near-optimality in a reasonable time, either for academic or practical purposes. We present a description of the problem, the mathematical formulation, the preprocessing techniques used, as well as the computational results obtained.

The journey of this research work got initiated through identification of recent challenges in strategic planning faced by the decision-makers at managerial levels. Through interactions with practitioners of various sectors of the Industry, it started becoming clear that a peculiar situation is predominantly encountered by decision-makers. During a majority of situations of strategic planning, the selection of a move as a course of action by a decision- maker gets a reaction from one or more concerned parties, which in turn affects the objective of the decision-maker under consideration. The introspection of the literature in mathematical programming enabled us to realize that the mathematical modelling of such situations is possible through bilevel programming framework. The industrial interactions and literature review provided the motivation to address these challenges of strategic planning by modelling such decision-making issues as bilevel programming problems. For meticulously and precisely modelling the problems and to test the models with appropriate data, we narrowed down our study to the problems of Railways and supply chain management, due to approachability to the practitioners in these two sectors. Subsequent to the task of modelling the addressed issues, another challenge which we faced during our research is the unavailability of solution algorithms to solve the problems modelled as variants of bilevel programming framework. Wherever any algorithms were available for solving such a problem, we discovered those as incapable of handling the problems of a practical scale of ours. This motivated us to work towards the development of solution algorithms for the variants of bilevel programming problems being dealt with, and thus achieve success in our main objective. In our study, we have addressed both of these challenges collectively and contributed towards the development of decision support for some of the identified challenges of decision-makers which can be categorized within the scope of modelling through the bilevel programming. Further, we have supported our study by an implementation of developed algorithms on the relevant data obtained for appropriate cases from firms facing such problems. This has enabled us to contribute to the society through an optimal utilization of available opportunities. The thesis entitled “Strategic Planning and Decision Making Problems in the Bilevel Programming Framework” comprises of five chapters followed by the bibliography and the list of publications. The precursory Chapter 1 manifests strategic planning and decision-making, and decision-support for the same. The concept of bilevel programming along with its variants is then introduced. A survey of literature on decision-making models using bilevel programming framework developed for assisting managerial decisions of firms from various sectors is presented thereafter. Noting some practical issues in the approaches followed in strategic planning, a scope of research for developing a decision-support is observed to fix the objective of thesis along with the plan of research work. Preliminary concepts from different areas are used in our research work for development of solution algorithms. They need to be introduced with a bit detailed explanation before using them in the presentation of our work in subsequent chapters. All of such relevant concepts are presented in Chapter 2 for providing the readers with a clear understanding of our interdisciplinary work. Additionally, an independent discussion on a special case of a variant of bilevel programming problem is explicated as a ground work for developing a GA-based solution methodology in a later chapter. In Chapter 3, problem of railways is studied for decision-making on an operational issue of running special trains to tackle higher demand on specific routes during seasons of festivals and holidays. The study includes development of decision support for operational decisions on optimal utilization of rolling-stocks and determining optimal fare-price structure in a competitive environment coerced by other travelling service providers. The influence on the demand-shares by the competitors of railways is incorporated in decision making to utilize the rolling-stock accordingly. The problem is modelled as a mixed integer single- leader-multi-follower bilevel programming problem. A diversified-elitist genetic algorithm is introduced to solve the constructed model. The suggested methodology is illustrated by taking a test situation from Indian Railways. The work presented in this chapter has been published as a research paper entitled “A Bilevel Programming Model for Operative Decisions on Special Trains: An Indian Railways Perspective”, in Journal of Rail Transport Planning & Management (Elsevier), 8, (2018), 184-206. doi: 10.1016/j.jrtpm.2018.03.001. xv Chapter 4 develops a decision support for strategic pricing and aggregate production distribution planning for a small scale supplier intending to penetrate into a potential market engendered by a single buyer. A novel mixed integer single-leader-single-follower bilevel programming model is developed to formulate the problem in which the supplier is considered as a leader and the buyer as a follower. The proposed model subsumes the assessment of demand share against the price quotation, enabling the supplier to prepare an aggregate production distribution plan accordingly. An integer coded genetic algorithm is developed to solve the model and its implementation is exhibited through a test scenario. The work presented in this chapter is published as a research paper entitled “A Bilevel Programming Model for a Cohesive Decision Making on Strategic Pricing and Production Distribution Planning for a Small Scale Supplier”, in the journal International Game Theory Review (World Scientific Publishing Company), 22(2), 2020, doi: 10.1142/S0219198920400095. Chapter 5 studies a strategic problem of price negotiation of the buyer with its multiple suppliers in an oligopolistic-monopsony market. The problem is studied to develop a decision support for identifying target prices for negotiation through which the common goal of all stakeholders viz maintaining a sustainable business environment can be achieved. For this purpose it is suggested for the buyer to identify the Nash-equilibrium prices of the suppliers’ oligopolistic-competition as target prices, as adopting this strategy helps in avoiding adverse actions from either side. In order to develop a decision support for this strategic issue a mathematical model is formulated as a multi-leader-single-follower bilevel programming problem. A GA-based solution approach is proposed to solve such a bilevel programming problem. The proposed methodology is demonstrated by an implementation of a case of a manufacturing firm of the FMCG sector. The work presented in this chapter is communicated as a research paper entitled “A Bilevel Game Model for Ascertaining Competitive Target Prices for a Buyer in Negotiation with Multiple Suppliers” to the Journal Omega (Elsevier). A summary followed by future scope of the research work is evinced to conclude the thesis. Finally, two independent results on convex optimization are presented in Appendix, which are referred in Chapter 3 for developing a methodology to solve a problem modelled there.

Reproduction de : Thèse de doctorat : Électronique : Lille 1 : 2005. Tesi di dottorato : Ingeneria Ellectronica e delle Comunicazioni : Politecnico di Torino : 2005.<br>Thèse en cotutelle. N° d'ordre (Lille 1) : 3635. Texte en anglais. Résumé en français et en anglais. Titre provenant de la page de titre du document numérisé. Bibliogr. p. 145-149.

In the field of Reinforcement Learning the task is learning how agents should take sequences of actions in an environment in order to maximize a numerical reward signal. This learning process employed in combination with neural networks has given rise to Deep Reinforcement Learning (DRL), that is nowadays applied in many domains, from video games to robotics and self-driving cars. This work investigates possible DRL approaches applied to Flatland, a multi-agent railway simulation where the main task is to plan and reschedule train routes in order to optimize the traffic flow within the network. The tasks introduced in Flatland are based on the Vehicle Rescheduling Problem, for which determining an optimal solution is a NP-complete problem in combinatorial optimization and determining acceptably good solutions using heuristics and deterministic methods is not feasible in realistic railway systems. In particular, we analyze the tasks of navigation of a single agent inside a map, that from a starting position has to reach a target station in the minimum number of time steps and the generalization of this task to a multi-agent setting, with the new issue of conflicts avoidance and resolution between agents. To solve the problem we developed specific observations of the environment, so as to capture the necessary information for the network, trained with Deep Q-Learning and variants, to learn the best action for each agent, that leads to the solution that maximizes the total reward. The positive results obtained on small environments offer ideas for various interpretations and possible future developments, showing that Reinforcement Learning has the potential to solve the problem under a new perspective.

During the last three decades, electronic devices have conquered the railway domain, taking the place previously held by electromechanical devices, thanks to higher performances and lower costs. The price of this "revolution" is the fact that, in order to work properly and reliably, electronic systems must be fairly immune to the effect of external interferers, while, at the same time, they are not to electromagnetically pollute the environment they work in. These issues are dealt with by electromagnetic Compatibility (EMC) whereas several international EMC standardization committees work on the definition of tests and rules the manufacturers must comply with. In the European Union, the reference for EMC issues in the railway domain is set by the CENELEC standard EN 50121, which deals with several aspects of a generic railway system, from the power-supply infrastructure to rolling stocks and signalling circuits. The introduction of this standard in 1996 has had a strong impact on rolling stock manufacturers, who are now required to test their products for EMC compliancy. As opposed to the automotive domain, the testing of trains cannot be performed in standard facilities, such as anechoic chambers, so that they have to be tested on actual railway lines, typically on the customer's. Industrial experience has shown that results obtained in this way are usually site-dependent, something that is against the very idea of a standard. The aim of this work is to prove the importance of the infrastructure in radiated emission tests, showing that the test results are site-dependent, thus subject to misunderstandings and misinterpretations. To this end, the features of a generic railway system are briefly described, pointing out the great variability in actual configurations, together with the absence of standard solutions. Subsequently, the electromagnetic modelling of a railway system is introduced, dealing with both propagation and radiation phenomena; in particular, the main topic here addressed is the modelling of supply-lines, through a quasi-TEM approach. The finite conductivity of the soil is taken into account by means of a closed-form formulation, thus avoiding numerical methods, and overcoming the limitations of Carson's model. Moreover, special attention is paid to discontinuities that would increase the model complexity, proposing approximated descriptions supported by numerical results. Results obtained with this model are then validated through several measurement campaigns carried out on actual railway lines, proving the effectiveness of the approach here pursued. The model is then employed in order to prove that some criteria in the standard EN 50121, specifically introduced in order to avoid site-dependency, are not realistic, thus leaving this issue unresolved. To this end, numerical examples are considered, assessing the impact of the infrastructure by comparing results obtained with realistic site configurations and with the ideal one envisaged by the standard. These comparisons are at the base of a tentative procedure that would allow to avoid the misinterpretations that triggered this work. Unfortunately, this approach requires an accurate description of the test-site. Since this is hardly the case, an alternative experimental characterization of the site is proposed, based on magnetic field measurements. This approach, involving the solution of an inverse problem, is shown to be feasible through a numerical validation, though its practical utilization requires efficient optimization techniques.

Prior to 1980, the practice in multilevel autorack management was to load the railcars at various origin points, ship them to the destination ramps, unload them, and then return each car to the loading point where it originated. Recognizing the inefficiency of such a practice with respect to the fleet size that had to be maintained, and the associated poor utilization due to the excessive empty miles logged, a consolidation of the railcars was initiated and completed by February 1982. Under this pooling program, a central management was established to control the repositioning of three types of empty railcars for eight principal automobile manufacturers. Today, the practice is to consolidate the fleets of all automobile manufacturers for each equipment type, and to solve the distribution problem of repositioning empty multilevel autoracks of each type from points at which they are unloaded to automobile assembly facilities where they need to be reloaded. Each such problem is referred to in the railroad industry as a repositioning scenario. In this dissertation, we present two tactical models to assist in the task of centrally managing the distribution of empty railcars on a day-to-day basis for each repositioning scenario. These models take into account various practical issues such as uncertainties, priorities with respect to time and demand locations, multiple objectives related to minimizing different types of latenesses in delivery, and blocking issues. It is also of great practical interest to the central management team to have the ability to conduct various sensitivity analyses in its operation. Accordingly, the system provides for the capability to investigate various what-if scenarios such as fixing decisions on running a specified block of cars (control orders) along certain routes as dictated by business needs, and handling changes in supplies, demands, priorities, and transit time characteristics. Moreover, the solution methodology provides a flexible decision-making capability by permitting a series of runs based on a sequential decision-fixing process in a real-time operational mode. A turn-around response of about five minutes per scenario (on a Pentium PC or equivalent) is desired in practice. This dissertation begins by developing several progressive formulations that incorporate many practical considerations in the empty railroad car distribution planning system. We investigate the performance of two principal models in this progression to gain more insights into the implementation aspects of our approach. The first model (TDSS1: Tactical Decision Support System-1) considers all the identified features of the problem except for blocking, and results in a network formulation of the problem. This model examines various practical issues such as time and demand location-based priorities as well as uncertainty in data within a multiple objective framework. In the second model (TDSS2: Tactical Decision Support System-2), we add a substantial degree of complexity by addressing blocking considerations. Enforcement of block formation renders the model as a network flow problem with side-constraints and discrete side-variables. We show how the resulting mixed-integer-programming formulation can be enhanced via some partial convex hull constructions using the Reformulation-Linearization Technique (RLT). This tightening of the underlying linear programming relaxation is shown to permit the solution of larger problem sizes, and enables the exact solution of certain scenarios having 5,000 - 8,000 arcs. However, in order to accommodate the strict run-time limit requirements imposed in practice for larger scenarios having about 150,000 arcs, various heuristics are developed to solve this problem. In using a combination of proposed strategies, 23 principal heuristics, plus other hybrid variants, are composed for testing. By examining the performance of various exact and heuristic procedures with respect to speed of operation and the quality of solutions produced on a test-bed of real problems, we prescribe recommendations for a production code to be used in practice. Besides providing a tool to aid in the decision-making process, a principal utility of the developed system is that it provides the opportunity to conduct various what-if analyses. The effects of many of the practical considerations that have been incorporated in TDSS2 can be studied via such sensitivity analyses. A special graphical user interface has been implemented that permits railcar distributors to investigate the effects of varying supplies, demands, and routes, retrieving railcars from storage, diverting en-route railcars, and exploring various customer or user-driven fixed dispositions. The user has the flexibility, therefore, to sequentially compose a decision to implement on a daily basis by using business judgment to make suggestions and studying the consequent response prompted by the model. This system is currently in use by the TTX company, Chicago, Illinois, in order to make distribution decisions for the railroad and automobile industries. The dissertation concludes by presenting a system flowchart for the overall implemented approach, a summary of our research and provides recommendations for future algorithmic enhancements based on Lagrangian relaxation techniques. NOTE: (03/2011) An updated copy of this ETD was added after there were patron reports of problems with the file.<br>Ph. D.

Dans plusieurs pays européens, la capacité de l’infrastructure est complètement exploitée aux heures de pointe et aux points critiques : une grande quantité de trains traversent ces points critiques dans un laps de temps très réduit. Dans cette situation le retard d’un train provoqué par un conflit de circulation peut se propager dans tout le réseau. Le problème de la gestion opérationnelle du trafic ferroviaire consiste à trouver les modifications des itinéraires et des ordonnancements des trains qui minimisent la propagation des retards. Dans cette thèse, nous proposons une approche de décomposition de Benders pour la formulation linéaire en nombres entiers à variables mixtes utilisée dans l’algorithme RECIFE-MILP. Après avoir constaté que l’approche de décomposition standard de Benders ne permet pas de trouver rapidement une solution de bonne qualité pour certaines instances du problème, nous étudions trois approches alternatives afin d’améliorer la performance de notre algorithme. Nous proposons d’abord une approche que nous appelons la reformulation réduite de Benders. Ensuite, nous introduisons des inégalités dans la formulation du problème maître de Benders. Finalement, nous scindons le processus de résolution en trois étapes au lieu de deux comme dans la décomposition standard de Benders. L'analyse expérimentale montre que la combinaison de la première et dernière approche surpasse l’algorithme original RECIFE-MILP dans la résolution de grandes instances sous certaines conditions<br>In railway systems, during congested traffic situations, the infrastructure capacity is completely exploited for trains circulation. In these situations, when traffic is perturbed some trains must be stopped or slowed down for ensuring safety, and delays occur. The real-time Railway Traffic Management Problem (rtRTMP) is the problem of modifying trains route and schedule to limit delay propagation. In this thesis, we propose a Benders decomposition of a MILP-based algorithm for this problem, named RECIFE-MILP. After observing that the standard Benders decomposition (BD) does not allow the effective solution of rtRTMP instances, we study three possible approaches to improve the performance. Specifically, we first propose a modification of the problem reformulation which is typical of BD, obtaining what we call reduced BD. Then, we introduce some inequalities to the Benders master problem. Finally, we split the solution process in three steps rather than two as in the standard BD. As we show in a thorough experimental analysis, the combination of the first and last approaches outperforms the original RECIFE-MILP algorithm when tackling large instances with some specific features

Cette thèse traite de l’incertitude et de la robustesse dans les problèmes de d´décision, avec le cas d’application des affectations de quais en gare en cas de retards. Une m´méthodologie en deux parties est proposée pour aborder ce problème. Dans un premier temps, les archives de données de retards sont utilisées pour construire des modèles de prédiction de distribution de probabilités conditionnellement aux valeurs d’un ensemble de variables explicatives. Une m´méthodologie de validation et d’évaluation de ces prédictions est mise en place afin d’assurer leur fiabilité pour de la prise de d´décision. Le problème d’affectations de quais pouvant être vu comme une recherche de clique de taille maximum, ces distributions prédites sont utilisées dans une seconde partie pour ajouter des pondérations pénalisant les risques de rupture des arêtes en cas de retard. Des algorithmes de recherche locale ont ´été utilisés et les expériences ont montré une importante baisse de conflits<br>This thesis deals with uncertainty and robustness in decision problems, with the case of the train platforming problem subject to delays. A two-part methodology is proposed to address this problem. First, delay records are used to build models predicting probability distributions conditionnaly to a set of explanatory variables. A methodology to validate and evaluate these predictions is proposed to ensure their reliability for decision-making. As the train platforming problem can be seen as a weighted clique problem, these predicted distributions are used in a second part to add weights on edges to penalize risk of conflict. Local search algorithms are used and experiments show a significant decrease in conflicts

This dissertation addresses five fundamental resource allocation problems on networks, all of which have applications to support Homeland Security or industry challenges. In the first application, we model and solve the strategic problem of minimizing the expected loss inflicted by a hostile terrorist organization. An appropriate allocation of certain capability-related, intent-related, vulnerability-related, and consequence-related resources is used to reduce the probabilities of success in the respective attack-related actions, and to ameliorate losses in case of a successful attack. Given the disparate nature of prioritizing capital and material investments by federal, state, local, and private agencies to combat terrorism, our model and accompanying solution procedure represent an innovative, comprehensive, and quantitative approach to coordinate resource allocations from various agencies across the breadth of domains that deal with preventing attacks and mitigating their consequences. Adopting a nested event tree optimization framework, we present a novel formulation for the problem as a specially structured nonconvex factorable program, and develop two branch-and-bound schemes based respectively on utilizing a convex nonlinear relaxation and a linear outer-approximation, both of which are proven to converge to a global optimal solution. We also investigate a fundamental special-case variant for each of these schemes, and design an alternative direct mixed-integer programming model representation for this scenario. Several range reduction, partitioning, and branching strategies are proposed, and extensive computational results are presented to study the efficacy of different compositions of these algorithmic ingredients, including comparisons with the commercial software BARON. The developed set of algorithmic implementation strategies and enhancements are shown to outperform BARON over a set of simulated test instances, where the best proposed methodology produces an average optimality gap of 0.35% (compared to 4.29% for BARON) and reduces the required computational effort by a factor of 33. A sensitivity analysis is also conducted to explore the effect of certain key model parameters, whereupon we demonstrate that the prescribed algorithm can attain significantly tighter optimality gaps with only a near-linear corresponding increase in computational effort. In addition to enabling effective comprehensive resource allocations, this research permits coordinating agencies to conduct quantitative what-if studies on the impact of alternative resourcing priorities. The second application is motivated by the author's experience with the U.S. Army during a tour in Iraq, during which combined operations involving U.S. Army, Iraqi Army, and Iraqi Police forces sought to interdict the transport of selected materials used for the manufacture of specialized types of Improvised Explosive Devices, as well as to interdict the distribution of assembled devices to operatives in the field. In this application, we model and solve the problem of minimizing the maximum flow through a network from a given source node to a terminus node, integrating different forms of superadditive synergy with respect to the effect of resources applied to the arcs in the network. Herein, the superadditive synergy reflects the additional effectiveness of forces conducting combined operations, vis-à-vis unilateral efforts. We examine linear, concave, and general nonconcave superadditive synergistic relationships between resources, and accordingly develop and test effective solution procedures for the underlying nonlinear programs. For the linear case, we formulate an alternative model representation via Fourier-Motzkin elimination that reduces average computational effort by over 40% on a set of randomly generated test instances. This test is followed by extensive analyses of instance parameters to determine their effect on the levels of synergy attained using different specified metrics. For the case of concave synergy relationships, which yields a convex program, we design an inner-linearization procedure that attains solutions on average within 3% of optimality with a reduction in computational effort by a factor of 18 in comparison with the commercial codes SBB and BARON for small- and medium-sized problems; and outperforms these softwares on large-sized problems, where both solvers failed to attain an optimal solution (and often failed to detect a feasible solution) within 1800 CPU seconds. Examining a general nonlinear synergy relationship, we develop solution methods based on outer-linearizations, inner-linearizations, and mixed-integer approximations, and compare these against the commercial software BARON. Considering increased granularities for the outer-linearization and mixed-integer approximations, as well as different implementation variants for both these approaches, we conduct extensive computational experiments to reveal that, whereas both these techniques perform comparably with respect to BARON on small-sized problems, they significantly improve upon the performance for medium- and large-sized problems. Our superlative procedure reduces the computational effort by a factor of 461 for the subset of test problems for which the commercial global optimization software BARON could identify a feasible solution, while also achieving solutions of objective value 0.20% better than BARON. The third application is likewise motivated by the author's military experience in Iraq, both from several instances involving coalition forces attempting to interdict the transport of a kidnapping victim by a sectarian militia as well as, from the opposite perspective, instances involving coalition forces transporting detainees between interment facilities. For this application, we examine the network interdiction problem of minimizing the maximum probability of evasion by an entity traversing a network from a given source to a designated terminus, while incorporating novel forms of superadditive synergy between resources applied to arcs in the network. Our formulations examine either linear or concave (nonlinear) synergy relationships. Conformant with military strategies that frequently involve a combination of overt and covert operations to achieve an operational objective, we also propose an alternative model for sequential overt and covert deployment of subsets of interdiction resources, and conduct theoretical as well as empirical comparative analyses between models for purely overt (with or without synergy) and composite overt-covert strategies to provide insights into absolute and relative threshold criteria for recommended resource utilization. In contrast to existing static models, in a fourth application, we present a novel dynamic network interdiction model that improves realism by accounting for interactions between an interdictor deploying resources on arcs in a digraph and an evader traversing the network from a designated source to a known terminus, wherein the agents may modify strategies in selected subsequent periods according to respective decision and implementation cycles. We further enhance the realism of our model by considering a multi-component objective function, wherein the interdictor seeks to minimize the maximum value of a regret function that consists of the evader's net flow from the source to the terminus; the interdictor's procurement, deployment, and redeployment costs; and penalties incurred by the evader for misperceptions as to the interdicted state of the network. For the resulting minimax model, we use duality to develop a reformulation that facilitates a direct solution procedure using the commercial software BARON, and examine certain related stability and convergence issues. We demonstrate cases for convergence to a stable equilibrium of strategies for problem structures having a unique solution to minimize the maximum evader flow, as well as convergence to a region of bounded oscillation for structures yielding alternative interdictor strategies that minimize the maximum evader flow. We also provide insights into the computational performance of BARON for these two problem structures, yielding useful guidelines for other research involving similar non-convex optimization problems. For the fifth application, we examine the problem of apportioning railcars to car manufacturers and railroads participating in a pooling agreement for shipping automobiles, given a dynamically determined total fleet size. This study is motivated by the existence of such a consortium of automobile manufacturers and railroads, for which the collaborative fleet sizing and efforts to equitably allocate railcars amongst the participants are currently orchestrated by the \textit{TTX Company} in Chicago, Illinois. In our study, we first demonstrate potential inequities in the industry standard resulting either from failing to address disconnected transportation network components separately, or from utilizing the current manufacturer allocation technique that is based on average nodal empty transit time estimates. We next propose and illustrate four alternative schemes to apportion railcars to manufacturers, respectively based on total transit time that accounts for queuing; two marginal cost-induced methods; and a Shapley value approach. We also provide a game-theoretic insight into the existing procedure for apportioning railcars to railroads, and develop an alternative railroad allocation scheme based on capital plus operating costs. Extensive computational results are presented for the ten combinations of current and proposed allocation techniques for automobile manufacturers and railroads, using realistic instances derived from representative data of the current business environment. We conclude with recommendations for adopting an appropriate apportionment methodology for implementation by the industry.<br>Ph. D.

La conception d’un plan de transport d’un service ferroviaire est un processus qui se réalise entre deux ans et six mois avant la mise en service de celui-ci. Les principales phases de la conception sont la définition des dessertes, le calcul de la grille horaire et enfin l’organisation des roulements de rames et des conducteurs. La manière dont le plan de transport est conçu peut avoir de nombreuses conséquences sur la qualité de service : fréquence en gare insuffisante qui peut entrainer une perte de clients, robustesse de la grille horaire face à de petits incidents... En zone dense, tous ces éléments sont à prendre en compte, dès la conception de la grille horaire.Aujourd’hui, SNCF Transilien conçoit ses plans de transport en prenant d’abord en compte l’optimisation des ressources de production (sillons, rames et agents de conduite). Toutefois, l’augmentation des ressources mises en œuvre n’améliore plus l’adéquation du plan de transport à la demande des voyageurs. Ce mode de conception ne permet donc plus de faire face à l’augmentation de la demande de mobilité. C’est pourquoi il faut repenser la conception du plan de transport en intégrant immédiatement la dimension voyageuse.Nos travaux se concentrent sur les problématiques de conception de dessertes et de grille horaire, en prenant en compte le point de vue des voyageurs. Nous présentons un modèle multiobjectif de conception de dessertes, puis nous présentons un modèle de conception de grille horaire intégrant le choix d’itinéraire des voyageurs. Ensuite, nous présentons une méthode cherchant à intégrer ces deux modèles. Enfin, nous présentons une évaluation de nos résultats grâce à des indicateurs de fiabilité<br>The design of a railway transportation plan is a process achieved between two years and six months before it is put into service. The main phases in the design of a transportation plan are the line planning, the timetabling, the rolling stock and the crew scheduling.The design of the transportation plan can have many consequences on the quality of service: an inadequate frequency in station can cause a loss of passengers, sufficient number of seated places, robustness of the timetable in the face of small incidents... In dense area, as in the Ile-de-France region, all these elements must be taken into account as the transportation plan is designed.Today, SNCF Transilien designs its transportation plans by first taking into account the optimization of production resources (train paths, rolling stock units and drivers). However, today, the increase in resources implemented no longer improves the adequacy of the transportation plan to passengers’ demand. This design method no longer makes it possible to cope with the increase in the demand for mobility (+3% each year since 2000). This is why we must rethink the design of the transport plan by immediately integrating the passenger dimension. Our work focuses on issues of line planning and timetabling in a passenger-oriented approach. First, we present a multi-objective model for line planning. Then, we present a model of timetabling incorporating passenger route choice. Then, we initiate a method to integrate these two models. Finally, we present an evaluation of our results thanks to reliability indicators from the literature and a macroscopic simulation of the timetables

En raison de problèmes opérationnels et d'autres événements inattendus, un grand nombre d'incidents se produisent quotidiennement dans les systèmes de transport ferroviaire. Certains d'entre eux ont un impact local, mais quelques fois, essentiellement dans les réseaux ferroviaires plus saturés, des petits incidents peuvent se propager à travers tout le réseau et perturber de manière significative les horaires des trains. Dans cette thèse doctorale, nous présentons le problème de réordonnancement de plan de circulation ferroviaire en cas d'incident comme la problématique de créer un plan de circulation provisoire de manière à minimiser les effets de la propagation des incidents. Ce travail est issu du projet MAGES (Module d'Aide à la Gestion des Sillons) qui développe des systèmes de régulation pour le trafic ferroviaire. Nous présentons deux modèles différents qui permettent de trouver des solutions à ce problème : Programmation Linéaire en Nombres Entiers (PLNE) et Programmation Par Contraintes (PPC). Du fait de la nature fortement combinatoire du problème et de la nécessité de répondre rapidement aux incidents, il ne paraît pas raisonnable d'envisager une résolution exacte. Les méthodes correctives proposées consistent donc à explorer un voisinage restreint des solutions : right-shift rescheduling; une méthode basée sur des coupes de proximité; une méthode d'analyse statistique de la propagation des incidents (SAPI) et un méthode basée sur la PPC. Additionnellement, certaines de ces méthodes ont été adaptées sous forme d'algorithmes itératifs avec l'objectif d'améliorer progressivement la solution quand le temps d'exécution le permet. SAPI est une des principales contributions de cette thèse. SAPI intègre les concepts de right-shift rescheduling avec les coupes de proximité. Du fait de la taille des réseaux en jeu et du nombre de circulations, les phénomènes complexes de propagation d'un incident font qu'il est très difficile de connaitre de manière précise les événements qui seront affectés. Toutefois, il est tout de même envisageable d'évaluer la probabilité qu'un événement soit affecté. Pour calculer cette probabilité, un modèle de régression logistique est utilisé avec des variables explicatives dérivées du réseau et des circulations. Diverses variantes de ces méthodes sont évaluées et comparées en utilisant deux réseaux ferroviaires localisés en France et au Chili. À partir des résultats obtenus, il est possible de conclure que SAPI est meilleure que les autres méthodes en terme de vitesse de convergence vers l'optimum pour les instances de petite taille et moyenne alors qu'une méthode coopérative PNLE/PPC est capable de trouver des solutions pour les instances de plus grande taille. La difficulté de comparer SAPI avec d'autres méthodes présentées dans la littérature nous a encouragés à appliquer la méthode à un autre problème. Ainsi, cette méthodologie a été également adaptée au problème de réordonnancement de passagers, vols et appareils (avions) en cas de perturbations, problème originalement proposé dans le contexte du Challenge ROADEF 2009. Les résultats montrent que SAPI est efficace pour résoudre ce problème avec des solutions au-dessus de la moyenne des équipes finalistes en obtenant la troisième place du challenge

Cette thèse, effectuée à la demande de la SNCF, apporte une contribution à la résolution du problème des grilles de service des agents roulants. Elle a donné lieu à AFGAR. Le problème posé est un problème complexe, combinatoire, pour lequel il n'existe pas d'algorithme efficace. Concrètement il s'agit, partant d'un ensemble de journées de travail, de trouver si possible la meilleure succession de journées de travail et de repos périodiques qui respectent les contraintes temporelles, règlementaires et humaines. Le principe méthodologique de la démarche de modélisation a été de faire une séparation nette entre un modèle du processus avec sa logique de fonctionnement et un modèle de la stratégie de résolution (du problème) avec sa logique de raisonnement. Ayant à représenter deux types de connaissances (structurelles et fonctionnelles d'une part, expertes et déductives d'autre part), le choix d'un formalisme hybride (objets et règles) s'imposait. Nous avons donc opté pour le générateur (hybride : règles et objets) de systèmes experts SMECI. La partie raisonnement est basée sur le modèle systémique Opérand, Information et Décision (OID). La partie fonctionnement est basée sur une méthodologie objet qui permet de structurer tant les classes que les instances. En synthèse, nous proposons une ébauche de méthodologie de développement des systèmes à base de connaissances

The aim of this diploma thesis is to describe localization and calculation load identification of dynamic systems using piezoelectric sensors. Finding methods, which would allow us to evaluate loads on simple systems is the key to their application in the structural health monitoring of more complex systems. A theory necessary for understanding and application in aerospace, civil engineering, automobile industry, and train traffic of presented methods is given in the first part of the thesis. In these applications, the methods of wave propagation and different types of neural network methods are used to evaluate load identification. It is possible to evaluate loads by using a time reverse method, a method based on signal deconvolution, and a method based on a voltage amplitude ratio of the piezoelectric sensor. In the next part, the methods are described, the suitable place for gluing of a sensor, and the number of sensors for using method is given. These methods were verified and compared to a simple experimental system. In the following part, the model of the piezoelectric sensor is presented. It is possible to use the model for calculating voltage output from the strain. For methods verification, the problem of train passage in a specific place of the railway is chosen. The speed of the train and its load on the railway was calculated by using these methods.

Railway scheduling problems are quite popular scheduling and optimization problems which are treated in a large variety of papers and projects. Many special and even quite general situations have been investigated theoretically and also a variety of applied approaches tested on real-world instances has been developed.This thesis mainly deals with the problem of scheduling trains in railway networks with respect to given routings, fixed minimal travelling times, and other constraints like time-windows. It combines the theory of some well-known scheduling models with its applications in railway scheduling. The railway scheduling problems considered in this work are closely related to job-shop scheduling problems with blocking and some additional constraints. Therefore part of this research is related to these shop scheduling problems. Theoretical scheduling models are extended, complexity results are derived and solution methods are proposed. Most results are applied to the considered railway scheduling problems. In addition to approaches which treat railway problems as a whole also decomposition methods for these problems and corresponding solution methods are presented. These solution methods are tested and compared with simple greedy procedures.

In Deutschland nehmen die Fahrgastzahlen und die Verkehrsleistung im Schienenpersonennah- und -fernverkehr in den letzten Jahrzehnten stetig zu. So stieg beispielsweise die Zahl der beförderten Fahrgäste im Schienenpersonennahverkehr von 1,96 Milliarden im Jahr 2004 auf 2,72 Milliarden im Jahr 2018. Dies entspricht einer Zunahme von fast 39%. Allerdings wird es für die Eisenbahnverkehrsunternehmen aufgrund des Fachkräftemangels immer schwieriger, die erforderlichen Transportleistungen durch Triebfahrzeugführer und Zugbegleiter abzudecken. Dies bedeutet, dass mit weniger Ressourcen mehr Transportleistung erbracht werden muss, so dass eine ressourcenschonende und gleichzeitig kosteneffiziente Personalplanung unerlässlich ist. Ziel dieser Arbeit ist die Entwicklung eines Lösungskonzepts zur optimierten und automatisierten Planung des Bahnpersonals, insbesondere zur Sicherstellung der Zugbegleitquoten von Zugbegleitern in Regionalzügen. Da es bereits eine Vielzahl von Publikationen zu Modellierungsansätzen und Lösungsmethoden im Zusammenhang mit der Schichtplanung des Bahnpersonals gibt, wird in einem ersten Schritt die relevante Literatur identifiziert und klassifiziert. Dies ist notwendig, um geeignete mathematische Formulierungen und Lösungsansätze zu ermitteln, die auch für den Spezialfall der Schichtplanungsprobleme für Zugbegleiter mit Zugbegleitquoten angewendet oder weiter modifiziert werden können. Durch die Systematisierung der relevanten Artikel nach Modellformulierungen, Zielsetzungen, betrachteten Rahmenbedingungen und Lösungsmethoden können Forschungslücken leicht identifiziert und Möglichkeiten für weitere Forschungen aufgezeigt werden. Nach einer Analyse der gegebenen rechtlichen Anforderungen, Regelungen aus Tarifverträgen, operativen Bedingungen und der Forderungen aus Verkehrsverträgen ist ein erstes Ziel dieser Arbeit die Entwicklung eines mathematischen Modells, das das gegebene Schichtplanungsproblem für Zugbegleiter mit Zugbegleitquoten darstellt. Um zunächst die Auswirkungen der neuen Restriktionen für die Zugbegleitquoten zu analysieren, können weitere in der Praxis notwendige Anforderungen (z.B. Personalkapazität an den Einsatzstellen) weggelassen und der Planungshorizont auf einen Tag begrenzt werden. Nach der Modellierung des Problems mit weiteren Restriktionen soll in dieser Arbeit ein geeigneter Lösungsansatz entwickelt werden, der vor allem die Lösbarkeit großer realer Instanzen gewährleistet. Die generierten Schichtpläne müssen den gesetzlichen, vertraglichen und betrieblichen Anforderungen genügen und die dadurch entstehenden Kosten minimieren. Da in der Praxis ein Planungszeitraum von einem Tag weder betriebswirtschaftlich sinnvoll noch kosteneffizient ist, wird als nächstes Ziel die Ausdehnung des Planungszeitraums auf mehrere Tage angestrebt. Diese Ausdehnung sollte sich sowohl auf das Modell als auch auf den entwickelten Lösungsansatz auswirken. So können weitere mehrtägige Restriktionen integriert werden, wie z.B. die gleichmäßige Verteilung der von einem Zugbegleiter besetzten Fahrten. In der Forschung ist es wichtig, eine Vergleichbarkeit bzw. eine Bewertung der Qualität des Modells oder des Lösungsansatzes herzustellen. Aus diesem Grund sollte eine Arc-Flow-Formulierung des Schichtplanungsproblems für Zugbegleiter mit Zugbegleitquoten formuliert werden, um kleine Instanzen optimal zu lösen und untere Schranken für reale Instanzen zu setzen. Um die Lösung der Arc-Flow-Formulierung zu beschleunigen und zu verbessern, wird die Anwendung von gültigen Ungleichungen validiert. Der Zweck dieser Arbeit, der sich aus den oben genannten Zielen ableitet, lässt sich in fünf Forschungsfragen zur Schichtplanung für Zugbegleiter mit Zugbegleitquoten zusammenfassen: Q1 Wie ist der aktuelle Forschungsstand zu Schichtplanungsproblemen für das Bahnpersonal und welche Forschungslücken können identifiziert werden? F2 Wie können Schichtplanungsprobleme für Zugbegleiter mit Zugbegleitquoten modelliert werden? F3 Wie können Instanzen von Schichtplanungsprobleme für Zugbegleiter mit Zugbegleitquoten im Hinblick auf die Anforderungen der Praxis gelöst werden? F4 Wie kann das entwickelte mathematische Modell und der hybride Lösungsansatz auf einen mehrtägigen Zeitraum ausgedehnt werden? Was ist das Potenzial eines integrierten Ansatzes im Gegensatz zum sequenziellen, tageweisen Ansatz? F5 Kann eine Arc-Flow-Formulierung des Schichtplanungsproblems für Zugbegleiter mit Zugbegleitquoten verwendet werden, um die Lösungsqualität des bisherigen Ansatzes zu bewerten oder sogar zu verbessern? Können gültige Ungleichungen das Verhalten der Arc-Flow-Formulierung in Bezug auf Rechenzeiten und untere Schranken verbessern?:List of Figures IV List of Tables V List of Algorithms VII List of Abbreviations VIII List of Symbols X 1 Introduction 1 1.1 Motivation 1 1.2 Basics of railway crew scheduling 3 1.3 Purpose and research questions 5 1.4 Structure of this work 6 1.5 Research design 10 2 Large-scale optimization techniques 16 2.1 Column generation 16 2.2 Dantzig-Wolfe decomposition for linear programs 18 3 Railway crew scheduling: models, methods and applications 22 3.1 Introduction 23 3.2 Crew planning in railway operations 25 3.2.1 Crew management in strategic and tactical planning 25 3.2.2 Crew scheduling in operational planning 25 3.2.3 Real-time crew re-scheduling in disruption management 27 3.2.4 Technical terms of crew scheduling 28 3.2.5 Special characteristics of transportation modes 29 3.3 Overview of RCSP literature 32 3.3.1 Planning stage 32 3.3.2 Mode 33 3.3.3 Crew type 33 3.3.4 Model 34 3.3.5 Objective 34 3.3.6 Solution method 34 3.3.7 Country 35 3.4 Model formulations, objectives and constraints of RCSP 40 3.4.1 Model formulations 40 3.4.2 Objectives 44 3.4.3 Constraints 48 3.5 Solution methods 50 3.5.1 Integer programming methods 51 3.5.2 Heuristics 54 3.5.3 Column generation 56 3.5.4 Meta-heuristics 64 3.6 Conclusion and further research opportunities 67 3.7 Decision support tools and railway crew scheduling in practice 69 4 Schichtplanung von Zugbegleitpersonal unter Berücksichtigung von Prüfquoten 74 4.1 Einleitung 75 4.2 Planungsprozesse im Schienenpersonennahverkehr 76 4.3 Problembeschreibung 78 4.3.1 Klassifikation 79 4.3.2 Betriebliche und rechtliche Rahmenbedingungen 80 4.4 Modellierung als Set-Covering-Problem 81 4.5 Modellierung der Schichtplanung der Zugbegleiter mit Prüfquoten 83 4.6 Beispiel 84 4.7 Zusammenfassung und Ausblick 88 5 A hybrid solution approach for railway crew scheduling problems with attendance rates 89 5.1 Introduction 90 5.2 Crew scheduling problem with attendance rates 90 5.3 Hybrid solution approach 92 5.4 Computational results 94 5.5 Conclusions and further research 95 6 Solving practical railway crew scheduling problems with attendance rates 97 6.1 Introduction 98 6.2 Related work 100 6.3 The crew scheduling problem with attendance rates 102 6.3.1 Analytics-based design 102 6.3.2 Problem description and practical requirements 103 6.3.3 Problem formulation 104 6.4 Solution approaches for the MCSPAR 107 6.4.1 A multi-period column generation algorithm 107 6.4.2 Solving the pricing problem 109 6.5 Artifact evaluation 112 6.5.1 Considered transport networks and experimental design 112 6.5.2 Evaluation and comparison of algorithms 114 6.6 Conclusions and further research 116 7 Valid inequalities for the arc flow formulation of the railway crew scheduling problem with attendance rates 118 7.1 Introduction 119 7.2 Related work 121 7.3 Problem description and practical requirements 122 7.4 Arc flow formulation 124 7.5 Valid inequalities 130 7.5.1 Model specic valid inequalities 130 7.5.2 Symmetry breaking constraints 131 7.5.3 Parallel arcs 132 7.5.4 Fixed arcs 132 7.6 Computational results 133 7.6.1 Small-sized instances 134 7.6.2 Bounds for real-world instances 138 7.6.3 Improve heuristic solution 139 7.7 Conclusion 140 8 Conclusion 144 8.1 Summary 144 8.2 Future research 148 A Declarations of authorship 151 Bibliography 155<br>In Germany, the number of passengers and the transport performance in regional and long-distance rail passenger transport increase constantly over the last decades. For example, the number of passengers carried in regional rail passenger transport rose from 1.96 billion in 2004 to 2.72 billion in 2018. This represents an increase of almost 39%. However, it is becoming increasingly difficult for railway companies to cover the required transport services by drivers and conductors due to the shortage of skilled workers. This implies that a greater transport performance must be achieved with fewer resources, thus resource-saving and at the same time cost-efficient planning of personnel is essential. This work aims to develop a solution concept for optimized and automated railway crew scheduling, especially ensuring attendance rates for conductors in regional trains. Since there already exists a variety of publications concerning modeling approaches and solution methods related to railway crew scheduling, the first step is to identify and classify relevant literature. This is necessary to determine suitable mathematical formulations and solution approaches which can also be used or further modified for the special case of railway crew scheduling problems with attendance rates for conductors. By systematizing the reviewed articles according to model formulations, objectives, constraints and solution methods, research gaps can easily be identified and opportunities for further research can be revealed. After an analysis of the given legal requirements, regulations from labor contracts, operating conditions and claims under transportation contracts, a first goal of this work is the development of a mathematical model which represents the given problem with attendance rates for conductors. In order to first analyze the effect of the new constraints on attendance rates, further requirements necessary in practice can be omitted (e.g. personnel capacity at crew bases) and the planning horizon can be limited to one day. After modeling the problem with further requirements, this work aims to develop a suitable solution approach which, above all, guarantees the solvability of large real-world instances. The generated shift schedules have to meet legal, contractual and operational requirements and thereby minimize the resulting costs. Since in practice a planning period of one day is neither operationally reasonable nor cost-efficient, the next goal is to extend the planning period to several days. This extension should affect both the model and the developed solution approach. This allows further restrictions concerning several days to be integrated, such as the uniform distribution of attended trips. In research, it is important to establish comparability or an assessment of the quality of the model or solution method. For this reason, an arc-flow formulation of the crew scheduling problem with attendance rates should be formulated to solve small-sized instances optimally and provide lower bounds for real-world instances. To accelerate and improve the arc-flow formulation solution, the application of valid inequalities will be validated. The purpose of this work derived from the above mentioned objectives can be summarized into five research questions on railway crew scheduling with and without attendance rates for conductors: Q1 What is the current state of research for railway crew scheduling problems and which research gaps can be identified? Q2 How can railway crew scheduling problems with attendance rates for conductors be modeled? Q3 How can instances of railway crew scheduling problems with attendance rates be solved with regard to real-world requirements? Q4 How can the developed mathematical model and hybrid solution approach be extended to a multiple day period? What is the potential of an integrated approach in contrast to the sequential day-by-day approach? Q5 Can an arc-flow formulation of the railway crew scheduling problem with attendance rates be used to evaluate or even enhance the solution quality of the previous approach? Can valid inequalities improve the performance of the arc-flow formulation concerning computing times and lower bounds?:List of Figures IV List of Tables V List of Algorithms VII List of Abbreviations VIII List of Symbols X 1 Introduction 1 1.1 Motivation 1 1.2 Basics of railway crew scheduling 3 1.3 Purpose and research questions 5 1.4 Structure of this work 6 1.5 Research design 10 2 Large-scale optimization techniques 16 2.1 Column generation 16 2.2 Dantzig-Wolfe decomposition for linear programs 18 3 Railway crew scheduling: models, methods and applications 22 3.1 Introduction 23 3.2 Crew planning in railway operations 25 3.2.1 Crew management in strategic and tactical planning 25 3.2.2 Crew scheduling in operational planning 25 3.2.3 Real-time crew re-scheduling in disruption management 27 3.2.4 Technical terms of crew scheduling 28 3.2.5 Special characteristics of transportation modes 29 3.3 Overview of RCSP literature 32 3.3.1 Planning stage 32 3.3.2 Mode 33 3.3.3 Crew type 33 3.3.4 Model 34 3.3.5 Objective 34 3.3.6 Solution method 34 3.3.7 Country 35 3.4 Model formulations, objectives and constraints of RCSP 40 3.4.1 Model formulations 40 3.4.2 Objectives 44 3.4.3 Constraints 48 3.5 Solution methods 50 3.5.1 Integer programming methods 51 3.5.2 Heuristics 54 3.5.3 Column generation 56 3.5.4 Meta-heuristics 64 3.6 Conclusion and further research opportunities 67 3.7 Decision support tools and railway crew scheduling in practice 69 4 Schichtplanung von Zugbegleitpersonal unter Berücksichtigung von Prüfquoten 74 4.1 Einleitung 75 4.2 Planungsprozesse im Schienenpersonennahverkehr 76 4.3 Problembeschreibung 78 4.3.1 Klassifikation 79 4.3.2 Betriebliche und rechtliche Rahmenbedingungen 80 4.4 Modellierung als Set-Covering-Problem 81 4.5 Modellierung der Schichtplanung der Zugbegleiter mit Prüfquoten 83 4.6 Beispiel 84 4.7 Zusammenfassung und Ausblick 88 5 A hybrid solution approach for railway crew scheduling problems with attendance rates 89 5.1 Introduction 90 5.2 Crew scheduling problem with attendance rates 90 5.3 Hybrid solution approach 92 5.4 Computational results 94 5.5 Conclusions and further research 95 6 Solving practical railway crew scheduling problems with attendance rates 97 6.1 Introduction 98 6.2 Related work 100 6.3 The crew scheduling problem with attendance rates 102 6.3.1 Analytics-based design 102 6.3.2 Problem description and practical requirements 103 6.3.3 Problem formulation 104 6.4 Solution approaches for the MCSPAR 107 6.4.1 A multi-period column generation algorithm 107 6.4.2 Solving the pricing problem 109 6.5 Artifact evaluation 112 6.5.1 Considered transport networks and experimental design 112 6.5.2 Evaluation and comparison of algorithms 114 6.6 Conclusions and further research 116 7 Valid inequalities for the arc flow formulation of the railway crew scheduling problem with attendance rates 118 7.1 Introduction 119 7.2 Related work 121 7.3 Problem description and practical requirements 122 7.4 Arc flow formulation 124 7.5 Valid inequalities 130 7.5.1 Model specic valid inequalities 130 7.5.2 Symmetry breaking constraints 131 7.5.3 Parallel arcs 132 7.5.4 Fixed arcs 132 7.6 Computational results 133 7.6.1 Small-sized instances 134 7.6.2 Bounds for real-world instances 138 7.6.3 Improve heuristic solution 139 7.7 Conclusion 140 8 Conclusion 144 8.1 Summary 144 8.2 Future research 148 A Declarations of authorship 151 Bibliography 155

碩士<br>國立海洋大學<br>河海工程學系碩士在職專班<br>91<br>Railway near bridge abutment, at both entering and leaving ends of the bridge, if not handled properly, will encounter some special localized problems. These problems include local overstress and buckling of the steel rails. Local overstress is due to the distinct difference of structural behavior in railway on both sides of the bridge abutment. Buckling of steel rails usually results from ambient temperature rise. If special care is not taken, these problems can result in derailing of the moving train and human disaster. The purpose of this article is to examine these problems. Conclusions and suggestions are also included.

The railway line haul is the terminal-to-terminal segment of a door-to-door intermodal transportation system. This research concentrates on the routing and scheduling of the railway line haul. Routing and scheduling is the most important portions of the planning activities performed by railway companies. In this research, we developed an integer programming model to determine optimal operations in minimizing the most significant cost figures involved in such operations. Although the intermodal transportation system combines several transportation modes, our model concentrates on rail segment operations because improving the on-time performance of the rail segment can increase the timeliness of the entire intermodal route. Given container demands differentiated by origin, destination, arrival date at origin, and due date, the objective is to determine a train schedule and container routing scheme to minimize operational costs while meeting on-time delivery requirements of the shipments. The model was extensively tested by example problems of practical backgrounds, derived from those available in literature.

碩士<br>國立東華大學<br>電機工程學系<br>94<br>Abstract Taiwan High Speed Rail will become operational at the end of this year, and the maximum operating speed of the train can reach up to 300 kilometers per hour. Therefore, there is no doubt to be a serious challenge for mobile wireless communications industry to maintain a reliable communication quality under high speed ambiance for commuter of the bullet train. Global System for Mobile (GSM) has been widely adopted since 1992 and offers voicemail, instant message and GPRS functions. Although the vigorous construction of third generation mobile systems (3G) and its base stations are setting out like wildfire amongst the telecommunication corporation in nowadays Taiwan, according to studies, 70% of cellular phone users still use GSM systems since 3G has not been widely accepted because of higher fare rate and less-popularized network. The 3G network is still not prevalent on the island; people mainly use the voice service through GSM service because the rates are less expensive. Moreover, GSM has already set up a compact network on the island and it is therefore still the mainstream of nowadays mobile telecommunication system. This thesis will test the DCS-1800(GSM-1800) under high speed conditions and to overcome the problems of the DCS-1800 in the Taiwan High Speed Rail ambiance. Foremost among these solutions is that the base station should be located on the train. We will connect BTS and BSC via the satellite communication under the Abis interface to solve the problems of connection under high speed rail conditions. At the same time, we must consider that using a geostationary satellite and the feasibilities to estimate the analysis. We have concluded the argument put forth in this thesis will demonstrate a framework that will provide the better system solution, if the satellite have no shielding, no inter-symbol interference and under the ideal weather conditions. The Abis interface overall Eb/No is about 13 dB and analysis results of the receiver signal bit error rate is less than which exhibits that transmission from BTS to BSC via GEO satellite is feasible on this framework.

碩士<br>國立成功大學<br>交通管理科學系<br>103<br>Since the railway system plays an important role in transporting passengers around Taiwan, increasing the line capacity is a major issue. For instance, there are many bottlenecks on the Taitung Line, because of 19 single-track sections. The railway line capacity can be increased by upgrading the single-track sections to double-track lines. Increasing transport volumes means that the rail operators should schedule more services. However, services are limited by the railway line capacity and such line capacity is affected by several factors, including train-type heterogeneity, speed and schedule effects. This study has evaluated services for railway line capacity, and has investigated the influence of track design (single-track or double-track) on the number of services and travel times, and has identified the bottlenecks. To solve the problem and find the optimal solution, we have designed Genetic Algorithm by combining the heuristic proposed by Lee and Chen (2009) with regression analysis. When tested with real-world examples from the Taitung Line, the results showed that there are significant differences between single-track and double-track lines. To ensure the quality of the problem solving, we have also used Lee and Chen’s (2009) scheduling timetable algorithm to enumerate the solution. The results prove that our algorithms are able to provide an optimal solution that is both accurate and rapid computationally. This research can provide the Taiwan Railways Administration (TRA) with suggestions for the best locations to upgrade their lines from single-track to double-track under conditions of limited resources.

碩士<br>國立成功大學<br>交通管理學系碩博士班<br>93<br>Taiwan high-speed rail corporation (THSRC) is a operating corporation of build-transfer-operate (BOT) contract of passenger railway transportation, and this corporation must be responsible for its profit even it is minus. The intention of the research is that to develop a model of railway seat allocation would find the best seat allocation, and this seat allocation makes the revenue be maximum of all. 　Because the operator wants to have the maximum revenue and the passengers wants to pay the minimum traveling cost, the research develops bi-level mathematical programming model to solve this problem. The lower level model is the model of passenger demand and the higher lower level model is the model of railway seat allocation. 　The research takes simulating annealing method to develop the solving algorithm of the railway seat allocation model. The process of this simulating annealing algorithm would find a crop of solutions, and the crop of solutions is the best crop of booking limits. Under this crop of booking limits, the revenue of sold railway tickets will be the maximum. 　In a numerical case study, the research present the results of the railway seat allocation model. By this results, the model is proved useful and correct.

碩士<br>國立成功大學<br>工業與資訊管理學系碩博士班<br>98<br>The Cyclic Crew Rostering Problem (CCRP) aims at ordering a set of duties to determine a roster of shortest cycle time. Previous solution methods usually treat CCRP as a Specific Travelling Salesman Problem (STSP). Although the STSP model can schedule all the duties, it cannot deal with some difficult operational regulations that restrict the schedules of off-duty periods in a rolling base. To this end, we design a Multi-level Rostering Network (MRN) to illustrate the CCRP and then solve it by a Full Integer Programming model (FIP). Since FIP usually consumes too much computational time to determine an optimal roster, we develop the Fix-and-Search Algorithm (FSA) that calculates a suitable roster in very short time. Starting with a lower bound on the length of a roster cycle, FSA tries to connect a feasible roster path by three major steps: First, it determines a feasible setting for two classes of duties by solving a subproblem of PIP so that the operational regulations can be easily satisfied; Second, the schedules for the key duties are fixed; Third, a modified Depth First Search (DFS) algorithm is used to find a feasible roster path. If no feasible roster path can be connected, FSA then increases the lower bound by one and repeats the steps until a feasible roster path is connected. The results of our computational experiments indicate FSA usually gives an optimal roster and is much more efficient than the STSP model in literature. If some crew members cannot be on duty, the Cyclic Crew Rerostering Problem (CCRSP) to rebuild a new roster starting from a given date (usually the first date of absence) has to be solved to the end of the current roster such that the interference is minimized. In a sense, CCRSP can be viewed as seeking another optimal roster to the original CCRP, and these two rosters should be identical before a given date of interference and as similar to each other as possible after that interference. To this end,we propose the Integer Programming (IP) model based on a Multi-commodity Network Flow (MNF) network.

碩士<br>國立成功大學<br>交通管理學系碩博士班<br>97<br>The research aims to use mathematical programming to establish a railway seat allocation model with different overbooking compensation strategies, under random passengers’ show-ups. The model focuses on using different overbooking compensation strategies to allocate optimal booking limit and to maximize the revenue. Besides, the research analyze the effects of passenger’s seat bumping to the operation of next trains, and attempt to build a real-time analyses allocation model. The research model uses GAMS to solve the model with the solver CoinBonmin. The outcome of analyzes shows that overbooking strategies actually decrease the number of empty seat, and increase the total revenue of trains about 5-7%. And the implement the strategies on long distance sections with main demands enhance the benefits of overbooking. However, non-linear compensation strategy limits the model to oversell too many tickets, and keep off losing the compensation cost. The operation could set up the breaking even between seat bumping and overbooking. Finally, the real-time analyses allocation model is only suitable for non-overbooking model.

碩士<br>國立成功大學<br>土木工程學系<br>103<br>Railway is a heavily planned system. The usage of all of the major resources, including crew, train, rolling stock, railway and station need to be planned carefully in order to achieve efficient operation. This work focuses on the optimization of rolling stock circulation. We first identify the key problems and requirements, then we propose a heuristic that is able to yield very good results. The Taiwan Railways Administration (TRA) offers approximately 950 services daily. All of its rolling stock needs to depart from a depot, and return to the same depot after serving a number of services. Feasible circulation plans for rolling stocks have to cover every service exactly once, and observe a number of regulations, including maximum mileage between regular maintenance, minimum connection time between services, depot capacity, and others. The optimization objective is to minimize the number of train sets needed, and to minimize dead mileage. In this study, we propose a two-stage heuristic to solve the rolling stock circulation problem. The first stage uses a time-space network to generate candidate train routes. The second stage selects part of the candidate train routes, then we uses an integer program to select the best combination. Numerical testing results indicate that the heuristic is able to produce rolling circulation plans that are very close to those used in reality.

Cette thèse étudie le problème du routage des locomotives qui se pose à la Compagnie des chemins de fer nationaux du Canada (CN) - le plus grand chemin de fer au Canada en termes de revenus et de taille physique de son réseau ferroviaire. Le problème vise à déterminer la séquence des activités de chaque locomotive sur un horizon de planification donné. Dans ce contexte, il faut prendre des décisions liées à l'affectation de locomotives aux trains planifiés en tenant compte des besoins d'entretien des locomotives. D’autres décisions traitant l'envoi de locomotives aux gares par mouvements à vide, les déplacements légers (sans tirer des wagons) et la location de locomotives tierces doivent également être prises en compte. Sur la base d'une formulation de programmation en nombres entiers et d'un réseau espace-temps présentés dans la littérature, nous introduisons une approche par horizon roulant pour trouver des solutions sous-optimales de ce problème dans un temps de calcul acceptable. Une formulation mathématique et un réseau espace-temps issus de la littérature sont adaptés à notre problème. Nous introduisons un nouveau type d'arcs pour le réseau et de nouvelles contraintes pour le modèle pour faire face aux problèmes qui se posent lors de la division de l'horizon de planification en plus petits morceaux. Les expériences numériques sur des instances réelles montrent les avantages et les inconvénients de notre algorithme par rapport à une approche exacte.<br>This thesis addresses the locomotive routing problem arising at the Canadian National Railway Company (CN) - the largest railway in Canada in terms of both revenue and the physical size of its rail network. The problem aims to determine the sequence of activities for each locomotive over the planning horizon. Besides assigning locomotives to scheduled trains and considering scheduled locomotive maintenance requirements, the problem also includes other decisions, such as sending locomotives to stations by deadheading, light traveling, and leasing of third-party locomotives. Based on an Integer Programming formulation and a Time-Expanded Network presented in the literature, we introduce a Rolling Horizon Approach (RHA) as a method to find near-optimal solutions of this problem in acceptable computing time. We adapt a mathematical formulation and a space-time network from the literature. We introduce a new type of arcs for the network and new constraints for the model to cope with issues arising when dividing the planning horizon into smaller ones. Computational experiments on real-life instances show the pros and cons of our algorithm when compared to an exact solution approach.

"The Cane Railway Scheduling Problem (CRSP) is to design a set of locomotive runs that supply the sugar factory with cane to crush, and the harvesting contractors with empty bins to fill with cane. Cane transport is the link between the harvesting and processing sectors of the sugar industry and its impact on both sectors must be considered. CRSP is significant problem for the sugar industry ... This research develops a real-time dynamic scheduling system (RTSS) that removes many of the assumptions and handles uncertainty, and produces schedules that are suitable for everyday, operational use"--Abstract.