In progress Robust timetable design based on passengers’ behaviour and dynamic pricing
- ERIM PhD 2017 ESE RD SSA
With the increasing demand for railway transportation there is a significant need to improve the robustness of railway timetables. Disruptions and disturbances happen daily and designing such timetables is crucial to guarantee the performance and efficiency of the whole network. In the literature, such problems are tackled mostly from operators point of view. However, users’ (passengers’) satisfaction is equally important to maintain the service level.
Time frame2017 - 2021
In this research, we aim at designing a robust timetable for railways while taking users' behaviour into account. In railway planning or any other service industry, most of times, either supply or demand is modelled.
In general, for modelling demand, supply side information of the problem is usually assumed to be given (e.g., price and capacity of different alternatives). Then, demand is modelled using statistical tools to estimate a model for predicting its future trends or more recently by using discrete choice models to estimate the market share.
On the other hand, from supply point of view, demand related information is considered as given to facilitate solving an optimization model (MILP). For example, demand could be considered as deterministic, stochastic or could be following a specific statistical distribution.
In this project, we want to consider both sides of the problem to have a more realistic mathematical model. However, the resulting mathematical model from integration of supply and demand is usually nonlinear and nonconvex.
The expected outputs of this research project are two folds. First, sources of uncertainty need to be defined. Second, the integrated optimization model (choice model and robust optimization problem) need to be expressed in a way that is solvable and tractable.
A train timetable is defined as a set of arrival and departure times of each train from each of its stopping stations and it is created by the Train Timetabling Problem (TTP). Typically, the TTP models use the simplifying assumption that the passengers always take their shortest paths (see Caprara et al. (2002) for instance) and omit the demand from the problem. Recent models relax this assumption and include the demand in the optimization (see Schmidt and Schöbel (2015) for instance). However, these models only increase the attractiveness of a timetable and cannot estimate the realized demand and the underlying revenue. To do so, a demand forecasting model is needed.
From modelling point of view, TTP consists in finding a train schedule on a railway network that satisfies some operational constraints and maximizes some profit function which counts for the efficiency of the infrastructure usage.
One of such models, integrating the train timetabling and the demand forecast, is presented by Cordone and Redaelli (2011). However, they omit the time dependency of the demand and consider the timetable only as a frequency of the service rather than the actual departure times. On the other hand, in the model of Espinosa-Aranda et al. (2015), the time dependency of the demand is modelled. But their application being to a single high speed railway line, it lacks in the network dimension.
In practical cases, the maximization of the objective function is not enough and one calls for a robust solution that is capable of absorbing as much as possible delays/disturbances on the network (Fischetti et al (2009). In this context, source of uncertainty must be identified to make the timetable robust against potential disruptions or disturbances. All the above-mentioned research has modeled the problem from operators’ point of view. However, we take a different approach to benefit from integration of demand side and supply side.
Supply and demand integration:
During the last decade, there has been an increasing trend to integrate user behaviour models in optimization. Several applications can be found in facility location problems (Haase and Müller (2014), Zhang et al. (2012), Benati and Hansen (2002)), and in revenue management networks in different contexts such as transportation (Haensel and Koole (2010)) and hotel management (van Ryzin and Vulcano (2014)). The main reason to combine the two is to provide a better understanding of the preferences of clients to policy makers while planning for their systems.
These preferences are formalized with predefined discrete choice models, which are the state-of-the-art for the mathematical modelling of demand. However, their complexity leads to mathematical formulations that are highly non-linear and non-convex in the variables of interest, and are therefore difficult to include in a discrete optimization model, where linearity is highly desirable, and convexity is necessary. As a result, in the literature discrete choice models are typically assumed to be given in order to simplify the optimization model.
The implicit understanding is that a complete prescription for decision problems will require fitting the right parametric choice model to data, so as to make accurate predictions. On the other hand, discrete optimization models create a platform where supply and demand closely interact, which is typically the case in transportation problems such railway scheduling.
Such models are associated with (mixed) integer optimization problems, whose discrete variables are used to design and configure the supply. There are only few instances in the literature that have integrated discrete choice models in mixed integer linear optimization, the most typical methodology framework in operations research. Furthermore, most of them are limited to the logit model (e.g., IIA assumption), where users are assumed to be homogeneous in their observable characteristics. Many techniques have been developed to linearize and convexify such models (Azadeh et al. (2015)).
Novelty, difficulties and expected outcomes:
For the first time in the literature, we want to tackle the problem of robust timetabling design taking the behavioral aspect of users. We would like to come up with a tractable mathematical model that can solve the problem in an exact way. Then, we want to introduce tailored heuristic techniques to solve the problem for large scale. The major difficulty however, is to come up with a linear representation of mathematical model. Choice models are the main source of nonlinearity and nonconvexity, especially when the decision variable of the optimization model appear in the users’ utility function. The expected outcome is double folded: 1- from practical point of view, we test the robustness of the model against several scenarios of interruptions. 2- from methodological point of view, we solve a relatively smaller problem in an exact way and propose heuristic methods to solve the larger cases.