Titolo della tesi: Integer Linear Programming and Learning Methods for Block Planning and Train Dispatching in Railways
Railway freight transportation entails a complex decision-making process both from the building of trains point of view and the dispatching of trains in the network. In this work we will analyze both these important aspects in railway context. The activity of building trains is called service design and it can be divided in two problems: the railroad blocking problem and the aggregation of blocks in trains. We will analyze the first phase.
In the railroad blocking problem a block is a set of commodities that travel between two nodes of the rail network as a logical unit. A commodity is a set of rail-cars (empty or loaded with goods) that have to go from an origin to a destination. Blocks are built in classification yards where commodities are grouped or separated. Grouping commodities into blocks allows the freight-hauling company to increase efficiency in shipments. However, this means that along their journey commodities may need to be "reclassified", i.e. separated and grouped into new blocks. This is a costly and time-consuming activity, hence the railroad blocking problem consists in finding a blocking plan that minimizes both transportation and intermediate handling costs.
A suitable blocking plan must satisfy capacity constraints at each classification yard, such as a bound on the number of outgoing blocks and a bound on the amount of cars grouped in each block.
Real-life instances of the railroad blocking problem typically comprise hundreds of classification yards and thousands of individual commodities, which means that this kind of optimization problems usually involves an extremely high number of variables.
The railway network can be represented like a graphs where the nodes are yards while arcs are the candidate blocks on which commodities can "travel". The path of each commodity will have to be find along these candidate blocks.
We propose two different approaches to tackle this problem. Both use an integer linear programming formulation. The first one uses a flow formulation to represent the flow of commodities on the candidate blocks. Moreover an iterative rounding routine is implemented to reduce the number of variables. The iterative rounding makes decisions supported by the solution of the linear relaxation.
However on bigger instance the number of variables increase and the formulation with the whole variables becomes intractable. So we decide to make some improvement. We introduce a column generation in the iterative rounding routine because when the number of variables increase the solver takes lots of time to find the optimal solution even for the LP. Moreover we decide to use the column generation after the iterative rounding to select a pool of variables that will be given to the ILP. To generate an adequate number of variables we strengthen the LP (after the iterative rounding) adding with the help of row generation some cuts. In this approach we use a path formulation both for the iterative rounding and pool generation while the flow one for the solution of the ILP.
We test these techniques on data provided by a real rail transportation company, consistently finding good quality solutions (compared to the value of the linear relaxation) within a computational time of a few hours.
From the point of view of dispatching, it is a very important activity in railway context in fact delays occur daily, leading to a mismatch between scheduled arrival time and actual arrival time. When the delay of one train is propagated to others, a loss in service quality arises, increasing costs and decreasing the quality of the service. Dispatchers monitor the traffic minute by minute, taking re-scheduling and re-routing decisions in near real-time. This is the train dispatching problem. Many exact algorithms are presented in the literature, but the computational effort often exceeds the time window available to solve them. In this paper, we propose a deep Reinforcement learning framework able to solve the problem in a time compatible with the application, while handling railway rules which could otherwise be hard to model. The approach belongs to the family of actor-critic methods, characterized by two operators: the actor, which gives a measurement (in terms of the probability distribution) on how good an action is, and the critic, which estimates the value associated with each state. For both actor and critic, we choose to exploit the graph structure of the railway network by adopting graph convolutional neural networks as estimate models.
Results show that the algorithm performs better than other learning-based approaches, like matrix-based Q-learning and deep Q-learning.