A new bidirectional search algorithm with shortened postprocessing.(Report) Pijls, Wim; Post, Henk

User activity

Share to:
View the summary of this work
Pijls, Wim ; Post, Henk
Appears In
European Journal of Operational Research
Algorithms; Business, general; Business, international
Academic; Trade
To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.09.032 Byline: Wim Pijls (a), Henk Post (b) Keywords: Shortest path; Road network search; Bidirectional search Abstract: For finding a shortest path in a network bidirectional A.sup.a is a widely known algorithm. This algorithm distinguishes between the main phase and the postprocessing phase. The version of bidirectional A.sup.a that is considered the most appropriate in literature hitherto, uses a so-called balanced heuristic estimate. This type of heuristic is chosen, as it accounts for a short postprocessing phase. In this paper, we do not restrict ourselves any longer to balanced heuristics. First, we introduce an algorithm containing a new method for the postprocessing phase, reducing this phase considerably for non-balanced heuristics. For a balanced heuristic the new algorithm is nearly equivalent to the existing versions of bidirectional A.sup.a. An obvious choice for a non-balanced heuristic turns out to be superior in terms of storage space and computation time. Second, we show that the main phase on its own, when using this non-balanced heuristic estimate, is a useful algorithm, which provides us quickly with a feasible approximation. Author Affiliation: (a) Erasmus University H10-20, Econometric Institute, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands (b) Connexxion Taxi Services, The Netherlands Article History: Received 12 June 2007; Accepted 16 September 2008 Article Note: (footnote) [star] This research is part of a Ph.D. project of the second author at Delft University of Technology, department of Electrical Engineering, Mathematics and Computer Science.
Work ID

2 editions of this work

Find a specific edition
Thumbnail [View as table] [View as grid] Title, Author, Edition Date Language Format Libraries

User activity

e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this work

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this work

Add a comment

Show comments and reviews from Amazon users