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

摘要

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.