Solving the multi-criteria time-dependent routing and scheduling problem in a multimodal fixed scheduled network

• Published in: European journal of operational research 2009, Vol.192 (1), p.18-28
• Main Authors: Androutsopoulos, Konstantinos N., Zografos, Konstantinos G.
• Format: Article
• Language: English
• Subjects: (B) Routing; (B) Routing Multi-objective programming Dynamic programming; Dynamic programming; Multi-objective programming; Multiple criteria decision making; Routing; Scheduling algorithms; Studies
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2007.09.004

Multi-criteria routing and scheduling in a multimodal fixed scheduled network with time-dependent travel times involves the determination of the non-dominated itineraries (i.e., paths enhanced with scheduled departures) under the following constraints: (i) visiting a given set of intermediate stops in a specified sequence, and (ii) strict time windows on the origin, the destination and the intermediate stops. The objective of this paper is to present the formulation and algorithmic solution for the multi-criteria itinerary planning problem that takes into account the aforementioned features. The algorithmic approach proposed is based on the decomposition of the problem to a sequence of elementary itinerary sub-problems, solved by a dynamic programming algorithm. The computational performance of the algorithms on a set of large scale test problems indicates non-prohibitive time requirements and encourages its integration into travel planning decision support systems.