Simultaneous optimization of delay management decisions and passenger routes

The task of delay management is to decide whether connecting trains should wait for delayed feeder trains or depart on time in order to minimize the passengers' delay. To estimate the effect of the wait-depart decisions on the travel times, most delay management models assume that passengers' routes are predefined. However, in practice, passengers can adapt their routes to the wait-depart decisions and arising changes in the timetable. For this reason, in this paper the authors assume that passengers' demand is given in form of pairs of origins and destinations (OD-pairs) and take wait-depart decisions and decisions on passengers' routes simultaneously. This approach, called delay management with re-routing, was introduced in Dollevoet et al. (Transp. Sci. 46(1):74-89, 2012) and the authors build their research upon the results obtained there. They show that the delay management problem with re-routing is strongly NP-hard even if there is only one OD-pair. Furthermore, they prove that even if there are only two OD-pairs, the problem cannot be approximated with constant approximation ratio unless P=NP. However, for the case of only one OD-pair they propose a polynomial-time algorithm. They show that their algorithm finds an optimal solution if there is no reasonably short route from origin to destination which requires a passenger to enter the same train twice. Otherwise, the solution found by the algorithm is a 2-approximation of an optimal solution and the estimated travel time is a lower bound on the objective value.


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01496877
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Sep 26 2013 9:33AM