A*-guided heuristic for a multi-objective bus passenger Trip Planning Problem
Document Type
Journal Article
Publication Date
2021
Subject Area
mode - bus, place - south america, place - urban, planning - methods, planning - signage/information
Keywords
Trip Planning Problem, Pareto dominance, A* algorithm
Abstract
The Bus Passenger Trip Planning Problem is the decision problem the bus passenger faces when he has to move around the city using the bus network: how and when can he reach his destination? Or possibly: given a fixed time to get to the destination, what should be his departure time? We show that both questions are computationally equivalent and can be answered using an A*-guided and Pareto dominance-based heuristic. The A* procedure drives the search estimating the arrival time at the target node, even in intermediate nodes. Dominance is triggered each time a new label is generated, in order to prune out labels defining subpaths with high values for the objectives we focus on: arrival time at destination, number of transfers and total walking distance. We discuss the tradeoff between processing time and solution quality through a parameter called A* speed. The tool is available for transit users on a day-to-day basis in Brazilian cities of up to 800,000 inhabitants and returns a variety of solutions within a couple of seconds.
Rights
Permission to publish the abstract has been given by SpringerLink, copyright remains with them.
Recommended Citation
Fournier, S.M.R., Hülse, E.O. & Pinheiro, É.V. (2021). A*-guided heuristic for a multi-objective bus passenger Trip Planning Problem. Public Transport, Vol. 13, pp. 557–578.
