A*-guided heuristic for a multi-objective bus passenger Trip Planning Problem

Document Type

Journal Article

Publication Date


Subject Area

mode - bus, place - south america, place - urban, planning - methods, planning - signage/information


Trip Planning Problem, Pareto dominance, A* algorithm


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.


Permission to publish the abstract has been given by SpringerLink, copyright remains with them.