Optimal Spreading of Alternative Train Routes in order to Minimise Passenger Travel Time in Practice 

Keywords: Minimal Expected Passenger Time, Optimal Cyclic Timetabling, Mixed Integer Linear Programming

1. Introduction
Dewilde et al. (2013) conclude that expected passenger time in practice is the ideal objective when considering a timetable from the passenger perspective. In one of our earlier papers on timetabling (Sels et al., 2013a), we derived our stochastic objective function for this objective. This includes a degree of robustness against primary delays via a knock-on delay model (Sels et al., 2013b). In general, it is considered as a good service to passengers that the different alternatives to get from an origin to a destination are equally spread in time. Adding this concern when developing our ideal timetable and studying the effect on the objective of expected passenger time is the subject of this paper.
In section 2, we give a short overview of related research. Section 3 gives a description of how we introduce spreading by linear constraints and extra terms in our objective function. Section 4 gives some preliminary results.


2. Related Research Overview
Wardman (2014) mentions that when for some of the possible trips in a network, more than one line is available, it is obvious that customers are better off if the trains of these lines are scheduled at equidistant intervals over the period under consideration. Vansteenwegen and Van Oudheusden (2007) also study ways to decrease waiting time of different types but do not yet focus on the effects of spreading departure times of alternative routes.


3. Introducing the Spreading in our Timetable Model
We think it is reasonable to assume that the preferred departure times of all the passengers are spread uniformly over the cycle time. In that case, a perfect spreading would minimise the average waiting time between the preferred departure time and the planned or actual departure time. With a cycle time of one hour, the perfect spreading of three alternative routes would mean one train every 20 minutes. In practice, however, this ideal spreading will not always be feasible, due to capacity restrictions for instance, or desirable, due to the other objectives. The spreading is not the only factor influencing the travel time in practice, so this perfect spreading often cannot be achieved but a measure of striving for this ideal spreading can be included in the objective function. By considering the average waiting time between the time passengers arrive at their departure station and the actual train departure time as a part of the passenger travel time in practice, the spreading concern can be integrated with the earlier developed objective of passenger travel time in practice. This is explained in this section. (Note that the same argumentation could be made based on the arrival times.)
Suppose that, during a cyclic period T of our timetable, f passengers want to travel from O to D and that they can choose amongst N alternative routes from O to D. We assume that the preferred departure times are spread uniformly in time amongst these f passengers. Let I_N represent the index set {0, 1, .., N − 1} of these N routes.


3.1. The Core Formulas
While calculating a timetable with our MILP model (Sels et al., 2013a), the departure and arrival times of all trains in all stations are being calculated. This means that the order of departure of alternative trips is still being decided upon. To accommodate for this in our model, we implement a permutation matrix P that reorders a vector b containing the N variables representing the N alternative route begin times, so with elements in unknown order, into a vector b, with elements guaranteed to always be ordered non-decreasingly. So B = P · b. Thanks to this vector B, we possess of the positive inter-departure time variables: forall i in I_N: s_i = B_{i+1} − B_i and s_{N−1} = T − B_{N−1} + B_0, which occur in our objective function. Indeed, assuming uniformly distributed preferred departure times, we can prove that the total ‘waiting’ time for these passengers between their preferred departure times and their actual departure times equals
  f · (s_i) ^ 2 / 2 . (1)
Expression (1) is quadratic and will need a QMIP solver that can handle quadratic objective functions or we could linearise it first and do with a MIP solver. The resulting model then minimises expected passenger waiting time at departure together with the expected trip time that we already had in the objective function before. A timetable with optimal spreading of alternative routes results.

3.2. The Number of Alternative Routes is Low in Practice
Our route choice algorithm, as described in Sels et al. (2011), tries to mimic passenger route choice behaviour by considering only the shortest routes in time. Suppose that the shortest route has a duration d. We then also consider all routes up to a duration d(1 + a), where a = 20%. For the whole Belgian railway network, for 58% of OD pairs, we find only 1 route per cycle time, for 31% of OD pairs, we find 2 routes and for 7% of OD pairs, we find 3 routes. So for only 4% of OD pairs, we find 4 or more routes. This means that the number of variables and constraints added to our model to realise the striving for spreading will remain fairly limited.


4. Preliminary Results
The modelling method described in section 3.1 has been tested for individual OD pairs, with sets of randomly generated constant b_i’s, instead of variable b_i’s, with typical values for N. These models each determine a single P and corresponding B and are solved quickly. Note that the whole model for all passenger trains in Belgium, has about 19000 OD pairs, and so, about 19000 of this individual OD pair models have to be solved simultaneously. Also, in the whole model, all b_i’s are variables instead of constants and their values influence each other via the objective function and the constraints.
Detailed results about the integration of spreading in the objective function and the cost of striving for spreading will be presented in the full paper.


References
Dewilde, T., Sels, P., Cattrysse, D., Vansteenwegen, P., 2013. Robust Railway Station Planning: An Interaction Between Routing, Timetabling and Platforming. Journal of Railway Transport Planning & Management. 3, 68–77.  Young Railway Operations Research Award 2013 of IAROR.
Sels, P., Dewilde, T., Cattrysse, D., Vansteenwegen, P., Feb. 2011. Deriving all Passenger Flows in a Railway Network from Ticket Sales Data. Proceedings of 4th International Seminar on Railway Operations Modelling and Analysis (IAROR): RailRome2011, February 16-18, Rome, Italy.
URL http://4c4u.com/RR2011.pdf
Sels, P., Dewilde, T., Cattrysse, D., Vansteenwegen, P., May 2013a. Expected Passenger Travel Time as Objective Function for Train Schedule Optimization. Proceedings of 5th International Seminar on Railway Operations Modelling and Analysis (IAROR): RailCopenhagen2013, May 13-15, Copenhagen, Denmark.
URL http://4c4u.com/RC2013.pdf
Sels, P., Dewilde, T., Cattrysse, D., Vansteenwegen, P., 2013b. Knock-On Delay Modelling and Optimisation: The Passenger Perspective. In: Proceedings of the 3rd International Conference on Models and Technologies for Intelligent Transport Systems (MT-ITS 2013), December 2-4, Dresden, Germany. pp. 1–10.
URL http://4c4u.com/ITS2013.pdf
Vansteenwegen, P., Van Oudheusden, D., 2007. Decreasing the passenger waiting time for an intercity rail network. Transportation Research Part B 41(4) (4), 478–492.
Wardman, M., 2004. Public transport values of time. Transportation Policy 11 (4), 363–377.