Abstract: Taxi passenger search path planning is an important measure to reduce taxi emptying rates. To efficiently solve the taxi passenger search path planning problem, a taxi passenger search path optimization method was proposed by considering three indicators: the probability of carrying passengers, the empty travel time and the regional supply/demand ratio. On this basis, the improved DBSCAN clustering algorithm and the grey comprehensive evaluation method were used to mine the hotspot areas of DiDi Express\\Select Vehicles and determine the target points for seeking passengers. The taxi passenger search routes were obtained by introducing a new rule of permanent labeling and two-way search improved Dijkstras algorithm. Finally, Didi order data from the core urban area of Chengdu were used to validate the proposed algorithm as an example. The results show that the improved Dijkstra algorithm has a faster shortest path search speed than Best-First, Foyle and other algorithms. Meanwhile, compared with common passenger search paths, the passenger search distance obtained by the proposed method is reduced by about 21.33%, and the passenger search time is reduced by about 22.16%. The proposed method can effectively guide taxi drivers to choose a better route to search passengers and provide effective guidance for taxi dispatching and urban transportation construction.

Key words: traffic engineering; DBSCAN clustering; grey comprehensive evaluation; improved Dijkstras algorithm; trajectory data

摘要： 出租车寻客路径规划是降低出租车空载率的重要手段。为高效解决出租车寻客路径规划问题，综合考虑载客概率、空载行驶时间和区域供需比3个指标，提出一种出租车寻客路径优化方法。在此基础上，基于改进的DBSCAN聚类算法和灰色综合评价法挖掘滴滴快/专车载客热点区域并确定寻客目标点，通过引进标号永久化新规则和双向搜索改进的Dijkstra算法获取出租车寻客路径。最后，使用成都市核心城区的滴滴订单数据对算法进行实例验证。结果表明：改进的Dijkstra算法较Best-first、Foyld等算法相比具有更快的最短路径搜索速度；同时，通过该方法获取的寻客路径与常见寻客路径相比，寻客距离减少约21.33%，寻客时间减少约22.16%。该方法能有效指导出租车司机选取较优的寻客路径，为出租车调度和城市交通建设提供有效指导。

关键词: 交通工程；DBSCAN聚类；灰色综合评价；改进的Dijkstra算法；轨迹数据