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

Sylvain M. R. Fournier (), Eduardo Otte Hülse () and Éder Vasco Pinheiro ()
Additional contact information
Sylvain M. R. Fournier: WPLEX Software Ltda.
Eduardo Otte Hülse: WPLEX Software Ltda.
Éder Vasco Pinheiro: WPLEX Software Ltda.

Public Transport, 2021, vol. 13, issue 3, No 6, 557-578

Abstract: 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.

Keywords: Trip Planning Problem; Pareto dominance; A* algorithm (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12469-019-00204-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:pubtra:v:13:y:2021:i:3:d:10.1007_s12469-019-00204-1

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12469

DOI: 10.1007/s12469-019-00204-1

Access Statistics for this article

Public Transport is currently edited by Stefan Voß

More articles in Public Transport from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().