A matheuristic for passenger service optimization through timetabling with free passenger route choice

Sets

S

Set of all stops

L

Set of all directed lines

\(T=\{1,\dots ,n\}\)

Set of all timetabled trips

\(T_l \subseteq T\)

Subset of all trips in the directed line \(l \in L\)

\(T^1 \subseteq T\)

Set of all trips which are the first in their directed line

\(S_i \subseteq S\)

Set of all stops visited by trip \(i\in T\)

\(J_i \subseteq S_i\)

Set of all intermediate stops visited by trip \(i \in T\), i.e. \(J_i=S_i\setminus \{st_i, et_i\}\)

R

Set of all transfer opportunities, each defined by a triplet (i, l, s): passengers disembarking trip \(i \in T\) at stop \(s\in J_i\cup \{et_i\}\) with the intent of embarking a trip \(j\in T_l\) of line \(l\in L\) such that \(l\ne l_i\) and \(s\in J_j\cup \{st_j\}\)

K

Set of all depots

I

Set of all compatible trips, \(I=\{(i,j)|i,j \in T:i\ne j, Dist(et_i,st_j)\le u, a_{i,et_i}^{-}+q^{-}+b_{ij}\le d_{j,st_j}^{+},a_{i,et_i}^{+}+q^{+} + b_{ij}\ge d_{j,st_j}^{-} \}\)

\(V_k\)

Set of nodes, which contains a node for each trip \(i\in T\), as well as for depot \(k \in K\) which is denoted \(n+k\), thus \(V_k=T\cup \{n+k\}\)

\(A_k\)

Set of arcs, including deadhead trips, pull-out trips, and pull-in trips, thus \(A_k=I\cup (\{n+k\} \times T)\cup (T\times \{n+k\})\)

\(G_k=(V_k, A_k)\)

Graph associated with depot \(k \in K\)

\(Q^D\)

Set of all deadhead triplets \(Q^D=\{ (i,j,k) : k \in K, (i,j) \in I\}\)

\(Q^O\)

Set of all pull-out triplets \(Q^O=\{(n+k,j,k): k \in K, j \in T \}\)

\(Q^H\)

Set of all pull-in triplets \(Q^H=\{ (i,n+k,k) : i \in T, k \in K \}\)

Q

Set of all compatible triplets (i, j, k), representing a vehicle from depot \(k\in K\) covering the pair of trips \((i,j)\in A_k\). \(Q = Q^D \cup Q^O \cup Q^H\)

T(Q)

Set of all pairs of trips \(i,j\in T\) for which a triplet involving i and j exists, \(T(Q)=\{(i,j)|i,j\in T: \exists (i,j,k) \in Q\}\).

Parameters

\(l_i\)

Directed line of trip \(i\in T\)

\(t_i\)

Total travel time of trip \(i\in T\) in the initial timetable

\(st_i \in S_i\)

Start terminal of trip \(i\in T\)

\(et_i \in S_i\)

End terminal of trip \(i\in T\)

\(h_{is}^-, h_{is}^+\)

Minimum and maximum headways, respectively, in relation to the timetabled headways, for each trip \(i\in T\) at each stop \(s\in J_i\cup \{st_i\}\)

\(d_{i,st_i}^-, d_{i,st_i}^+\)

Minimum and maximum departure shift from the first station for trip \(i\in T\), defined in relation to its departure time in the initial timetable

\(w_{is}^-\)

Dwell time in the initial timetable of a trip \(i\in T\) at stop \(s\in J_i\)

\(w_{is}^+\)

Maximum allowed dwell time of a trip \(i\in T\) at stop \(s\in J_i\)

w

Upper bound on the total added dwell time to all stops of any trip

\(\Lambda _{is}\)

Number of passengers that are on board (and will continue on board) when trip \(i\in T\) arrives at stop \(s\in J_i\)

\(a_{is}^-,a_{is}^+\)

Earliest and latest arrival times of trip \(i\in T\) at stop \(s\in J_i\cup \{et_i\}\), determined by the possible timetable modifications

\(d_{is}^-,d_{is}^+\)

Earliest and latest departure times of trip \(i\in T\) from stop \(s\in J_i\cup \{st_i\}\), determined by the possible timetable modifications

\(f_r\)

Number of passengers requesting transfer \(r\in R\)

\(e_r\)

Minimum transfer time for transfer \(r\in R\)

\(q^-,q^+\)

Minimum and maximum turnaround times

\(b_{ij}\)

Driving time between \(et_i\) and \(st_j\)

\(v_k\)

Number of schedules that can be created departing from depot \(k \in K\)

Dist(i, j)

Distance between the end terminal of trip \(i \in T\), \(et_i\), and the start terminal of trip \(j\in T\), \(st_j\)

u

Maximum deadhead distance

\(c_{ijk}\)

Operating cost associated with servicing triplet \((i,j,k)\in Q\). The cost \(c_{ijk}\) of triplet \((i,j,k)\in Q\) is equal to the deadhead time \(b_{ij}\) multiplied by a driving cost per time unit; if \((i,j,k)\in Q^O\), \(c_{ijk}\) also includes a fixed cost for creating a new schedule, corresponding to the fixed cost for using a vehicle.

\(c^{DW}\)

Operating cost per minute of extra dwell time

\(c^{OB}\)

Cost per minute of extra dwell time per on-board passenger

\(c^{TR}\)

Cost per minute of excess transfer time at transfers per passenger

B

Budget value for the operating costs

M

Big M value. In this problem, it is sufficient to set a big M value higher than the number of minutes in the planning horizon

Decision variables

\(x_{ijk} \in \{0,1\}\)

1 if and only if a vehicle from depot k travels from node i directly to node j, 0 otherwise

\(\tau ^d_{is} \in {\mathbb {Z}}^+_0\)

Departure time of trip \(i \in T\) from stop \(s \in J_i\cup \{st_i\}\)

\(\tau ^a_{is} \in {\mathbb {Z}}^+_0\)

Arrival time of trip \(i \in T\) at stop \(s \in J_i\cup \{et_i\}\)

\(\gamma _r \in {\mathbb {R}}^+_0\)

Excess transfer time for passengers using transfer location \(r\in R\)

\(\alpha _{ijs} \in \{0,1\}\)

1 if and only if passengers of transfer location \(r=(i,l_j,s)\in R\) embark trip \(j\in T\), 0 otherwise

\(\delta _{is} \in {\mathbb {Z}}^+_0\)

Minutes of dwell time added to trip \(i\in T\) at stop \(s \in J_i\)