基于DFS-回溯算法的公交网络限时免费换乘优化模型求解

基于青岛市“限时免费换乘”政策理念,建立费用与时间、换乘次数的关系模型,采用深度优先遍历与回溯相结合的算法,寻找限定时间内最短时间与超限时条件下最低费用路径,给出起讫点间的最优路径方案,结合车站智能诱导发布平台对算法进行验证。运行结果表明,DFS-回溯算法在数据规模较大的情况下,比蚁群等全局搜索算法效率高,可既快又准的找到最优路线;基于该算法的最佳路径模型方案,可准确的为乘客提供最大选择便利性,实现公共交通资源利用最大化。

Solution of the optimization model of bus network time-limited free transfer based on DFS-Backtracking algorithm

Based on the Qingdao policy of "Time-limited Free Transfer", the relational model of cost, time and the number of transfer is established, adopting Depth-First Search combined with backtracking algorithm, looking for path of the shortest time within limited-time and path of the lowest cost under the condition of overrun, the optimal path of any OD is obtained. Combined with the station intelligent induction publishing platform to verify this algorithm. the running results show that the DFS-backtracking algorithm have higher efficiency than the global search algorithms such as ant colony algorithm, under the condition of larger data size, can be quickly and accurately find the optimal route; The best route model based on the algorithm, can accurately provide maximum choice convenience for passengers, maximize public transport resource utilization.