Algorithm for the Optimal Riding Scheme Problem in Public traffic

摘要

A two-stage algorithm is proposed for the optimal riding scheme problem in public traffic querying system. The first stage is to find out the least transfer schemes, in which Bus Line Network model is presented to convert the least transfer scheme problem into the shortest path problem. The second stage is to search out the optimal riding scheme from the least transfer schemes, in which the transfer network is constructed to convert the optimal riding scheme problem into the constraint shortest path problem, and the algorithm for the constraint shortest path problem is also presented. Some examples are given to show the correctness and effectiveness of the proposed algorithm.