Abstract: Clustering analysis on the time series of online car-hailing demand was made to identify the similarities and differences of demand variation rules on different dates, so as to rationally formulate operational scheduling plans and provide passengers with higher level transport services. Aiming at the problem that existing Euclidean distance agglomerative hierarchical clustering (Euc_AGNES) couldnt recognize time series migration and scaling, and the problem that dynamic time warping (DTW) distance had huge time consumption in calculation, an improved DTW_AGNES clustering method was proposed. The proposed method optimized the dynamic planning search range of DTW by adjusting the constraint range of matching path and used the improved DTW as the similarity measure method of agglomerative hierarchical clustering (AGNES). The experiment results show that the ordinary DTW_AGNES clustering and the improved DTW_AGNES clustering are more able to identify the time series of online car-hailing demand than the Euc_AGNES clustering does, which provides a reliable evidence for the operators to formulate online car-hailing scheduling. Furthermore, the operation efficiency of the improved DTW_AGNES clustering is 62.4% higher than that of the ordinary DTW_AGNES clustering, which saves computing time and resources, and proves the effectiveness of the proposed method.

Key words: traffic and transportation engineering, aggregation hierarchical clustering, dynamic time warping, time series, DTW_AGNES algorithm, online car-hailing

摘要： 对网约车需求量时间序列进行聚类分析，识别不同日期需求量变化规律的相似性和差异性，以合理制定运营调度计划，为乘客提供更高水平运输服务。针对现有的欧氏距离凝聚层次聚类(Euc_AGNES)不能识别时间序列偏移、伸缩等问题和针对动态时间弯曲(DTW)距离计算时间开销大的问题，提出一种改进DTW_AGNES聚类方法，通过调整匹配路径约束范围来优化DTW的动态规划搜索范围，并使用改进后的DTW作为凝聚层次聚类(AGNES)的相似性度量方法。实验结果表明：普通DTW_AGNES聚类和改进DTW_AGNES聚类均比Euc_AGNES聚类更能识别网约车需求量时间序列变化规律，为网约车运营商制定编排调度计划提供可靠依据，且改进后的DTW_AGNES聚类运行效率比普通DTW_AGNES聚类提高了62.4%，节省了计算时间和计算资源，证明了方法的有效性。

关键词: 交通运输工程, 凝聚层次聚类, 动态时间弯曲, 时间序列, DTW_AGNES算法, 网约车