Title: Methods for path and service planning under route constraints

Authors: Chao-Lin Liu, Tun-Wen Pai

Addresses: Department of Computer Science, National Chengchi University, Taipei 11605, Taiwan. ' Department of Computer Science, National Taiwan Ocean University, Keelung 20224, Taiwan

Abstract: We examine methods for a special class of path-planning problems in which the routes are constrained. The scenario could happen, for instance, in transit systems where passengers cannot order drivers to change the routes of public buses to meet individual travel needs. General search algorithms are applicable to this class of problems, but may not find the desired solution as efficiently as possible. This paper reports three different strategies that capture the route constraints for improving efficiency of path planning algorithms. The first strategy applies hierarchical planning, and the rest employs matrices for encoding route constraints. We propose and prove that the Q matrix is instrumental for capturing route constraints and measuring quality of service of the transportation network. Moreover, we discuss how we may apply the Q matrix in designing admissible heuristic functions that are crucial for applying the A* algorithm for best-path planning under route constraints.

Keywords: travel information systems; intelligent transportation systems; ITS; matrix applications; path planning; route constraints; search; transit applications; service planning; quality of service; transportation networks.

DOI: 10.1504/IJCAT.2006.008668

International Journal of Computer Applications in Technology, 2006 Vol.25 No.1, pp.40 - 49

Published online: 13 Jan 2006 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article