The identification of optimum itineraries in an urban public transport system constitutes an important journey planning decision faced by travelers. The objective of this paper is to present a new formulation and algorithmic solution of the optimum itinerary problem that takes into account: (1) the dynamic nature of the urban public transport travel time; (2) the multiple decision making criteria and the associated priorities reflecting the travelers objectives and preferences; and (3) the scheduling constraints of the problem expressing the preferences of the travelers on the departure and arrival times at the origin and destination points respectively. The proposed formulation includes a special case of a problem that a visit at an intermediate stop within a specified time window is taken into account as a binding constraint. An algorithm has been developed for solving the emerging optimization problem that aims to determine the lexicographically optimum itinerary for all possible departure times from the origin. The special case of the problem with a mandatory visit at an intermediate stop is analyzed as a two-stage optimum itinerary problem that is solved through the appropriate modification of the aforementioned algorithm. The proposed algorithms have been integrated in a travelers' information system enabling the capability of planning the journey of a traveler. The performance of the proposed algorithms has been assessed through a set of runs on problems defined on the entire Athens Urban Public Transport Network providing encouraging results.
Abstract