Dynamic Programming Algorithm Based on ARIMA Model and K-Means Clustering Analysis

doi:10.3969/j.issn.1674-0696.2022.07.02

Journal of Chongqing Jiaotong University(Natural Science) ›› 2022, Vol. 41 ›› Issue (07): 9-13.DOI: 10.3969/j.issn.1674-0696.2022.07.02

• Transportation+Big Data & Artificial Intelligence • Previous Articles Next Articles

Dynamic Programming Algorithm Based on ARIMA Model and K-Means Clustering Analysis

XU Jianmin1, ZANG Peng1, SHOU Yanfang2

(1. School of Civil Engineering and Transportation, South China University of Technology, Guangzhou 510640, Guangdong, China; 2. Guangzhou Institute of Modern Industrial Technology, South China University of Technology, Guangzhou 510640, Guangdong, China)

Received:2021-03-17 Revised:2021-07-15 Published:2022-07-25

基于ARIMA模型和K-means聚类分析的动态规划算法

徐建闽1，臧鹏1，首艳芳2

(1. 华南理工大学土木与交通学院，广东广州 510640； 2. 华南理工大学广州现代产业技术研究院, 广东广州 510640)

作者简介:徐建闽(1960—)，男，山东招远人，教授，博士，主要从事智能交通控制方面的研究。E-mail：aujmxu@scut.edu.cn
基金资助:
国家自然科学基金项目（61873098）; 广东省科技计划项目（2016A030305001）; 中央高校基本科研业务费专项资金项目（2018KZ17）

Abstract

Abstract: Finding the shortest path is one of the important steps to optimize the transportation system. In order to find the shortest path, a dynamic programming algorithm based on ARIMA model and K-means clustering analysis was established by using historical and real-time floating-car data. The algorithm was tested in the second ring road area of Chengdu using Didi travel data. The results show that the newly proposed algorithm provides high-quality time solutions with low computation. The operation time is less than 2.010 minutes, the mean absolute percentage error is less than 6.5% and the invalid value ratio is less than 20%.

Key words: traffic engineering; dynamic programming algorithm; K-means clustering analysis; ARIMA model; the shortest path

摘要： 寻找最短路径是实现交通系统最优化的重要步骤之一。为寻找最短路径，利用历史和实时的浮动车数据，建立基于ARIMA模型和K-means聚类分析的动态规划算法。算法使用滴滴出行数据并在成都市二环区域内进行了测试。研究表明:新的算法以较低的计算量提供了高质量的时间解，运算时间均低于2.010 min，平均绝对百分误差低于6.5%，无效值比率小于20%。

关键词: 交通工程；动态规划算法；K-means聚类分析；ARIMA模型；最短路径

CLC Number:

U491.1+4

XU Jianmin1, ZANG Peng1, SHOU Yanfang2. Dynamic Programming Algorithm Based on ARIMA Model and K-Means Clustering Analysis[J]. Journal of Chongqing Jiaotong University(Natural Science), 2022, 41(07): 9-13.

徐建闽1，臧鹏1，首艳芳2. 基于ARIMA模型和K-means聚类分析的动态规划算法[J]. 重庆交通大学学报（自然科学版）, 2022, 41(07): 9-13.

References

［1］王迎, 赵建军, 李兴菊, 等. 基于交通大数据的车辆行驶路径规划综述［J］.软件导刊, 2020,19(10):50-54.
WANG Ying, ZHAO Jianjun, LI Xingju, et al. Review of vehicle route planning based on traffic big data ［J］. Software Guide, 2020, 19(10): 50-54.
［2］ PEREZ G F, CANDIA V A, MACULAV G, et al. Improved robust sho-rtest paths by penalized investments ［J］. Rairo-Operations Research, 2021,55(3):1865-1883.
［3］雒应, 何强. 考虑转向延误的最短路径的节点标号算法［J］.重庆交通大学学报(自然科学版), 2021, 40(4):48-53.
LUO Ying, HE Qiang. Node labeling algorithm of shortest path considering turn delay ［J］.Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(4): 48-53.
［4］ PEREZ G F, CANDIA V A, MACULAN G, et al. Improved robust shortest paths by penalized investments ［J］. Rairo-Operations Research, 2021, 55(3): 1865-1883.
［5］陈展, 公建宁, 刘媛媛, 等. 基于禁忌搜索的多AGV系统路径优化算法［J］. 计算机工程与应用, 2021, 57(10): 273-278.
CHEN Zhan, GONG Jianning, LIU Yuanyuan, et al. Multi-AGV system path optimization algorithm based on tabu search ［J］. Computer Engineering and Applications,
2021, 57(10): 273-278.
［6］刘智萍, 王芳, 彭吉琼, 等. 基于免疫遗传优化的智慧交通路径诱导算法［J］. 计算机仿真, 2020, 37(11): 134-137.
LIU Zhiping, WANG Fang, PENG Jiqiong,et al. Intelligent traffic path guidance algorithm based on immune genetic optimization short-term ［J］. Computer Simulation,
2020, 37(11): 134-137.
［7］李建伏, 王思博, 宋国平. 基于出行偏好和路径长度的路径规划方法［J］. 吉林大学学报(理学版), 2021, 59(1):107-114.
LI Jianfu, WANG Sibo, SONG Guoping. Path planning method based on routing preference and path length ［J］. Journal of Jilin University (Science Edition) , 2021, 59(1):
107-114.
［8］ XIA J, CHEN M, HUANG W. A multistep corridor travel-time predict- ion method using presence-type vehicle detector data ［J］. Journal of Intelligent
Transportation Systems, 2011, 15(2), 104-113.
［9］李瑞敏, 张威威, 刘志勇,等. 组合短路段的长路段旅行时间短时预测［J］.公路工程, 2018, 43(3):1-5.
LI Ruimin, ZHANG Weiwei, LIU Zhiyong, et al. Short-term travel time forecasting of long link combined short links ［J］. Highway Engineering, 2018, 43(3):1-5.
［10］ THOMAS B W, WHITE C C. The dynamic shortest path problem with anti- cipation ［ J］. European Journal of Operational Research，2007, 176（1）： 836-854.
［11］ GUNNER A R, MURAT A, CHINNAM R B. Dynamic routing under recurrent and non-recurrent congestion using real-time ITS informaion ［J］. Computers &
Operations Research, 2012, 39(2): 358-373.
［12］ SHUAI H, FANG J, AI X, et al. Stochastic optimization of economic dispatch for microgrid based on approximate dynamic programming ［J］. IEEE Transactions on
Smart Grid, 2019, 10(3): 2440-2452.
［13］张玉芳, 毛嘉莉, 熊忠阳. 一种改进的K—means算法［J］. 计算机应用, 2003(8): 31-33.
ZHANG Yufang, MAO Jiali, XIONG Zhongyang. An improved K-means algorithm［J］. Computer Applications, 2003(8): 31-33.

[1]	WENG Xiaoxiong, QIN Zhenlin, ZHANG Pengfei. Individual Metro Travel Prediction Based on Graph Convolution Gated Recurrent Network [J]. Journal of Chongqing Jiaotong University(Natural Science), 2022, 41(09): 1-6.
[2]	PEI Tongsong1, PEI Yu2. Prediction of Highway Traffic Volume Based on Markov Chain-BP Neural Network Model [J]. Journal of Chongqing Jiaotong University(Natural Science), 2021, 40(02): 35-41.
[3]	WU Lan, WANG Tongwei, LI Pengju, ZHAI Wei. Lane Reduction Method Based on Narrow Road Concept [J]. Journal of Chongqing Jiaotong University(Natural Science), 2020, 39(11): 26-32.
[4]	CHEN Yanyi, CAO Ying, ZHANG Jianan, FENG Rui. Evaluation of the Development Efficiency of Shenzhen Ecological Transportation Based on DEMATEL-BCC Model [J]. Journal of Chongqing Jiaotong University(Natural Science), 2020, 39(07): 27-32.
[5]	ZHANG Lanyi, HU Xisheng, CHEN Qingyao, QIU Rongzu. Prediction of Car Ownership Based on Principal Component Analysis and Logistic Regression [J]. Journal of Chongqing Jiaotong University(Natural Science), 2017, 36(5): 104-109.
[6]	ZHU Shun-ying，WANG Hong，LI Guan-shou. The ARIMA model used in forecasting of traffic volume in short interval on the link [J]. Journal of Chongqing Jiaotong University(Natural Science), 2003, 22(1): 76-77.
[7]	WENG Xiaoxiong1, REN Jie1, QIN Zhenlin1, LUO Ruifa2. Multi-step Prediction of Individual Travel Based on Deep Attention Model [J]. Journal of Chongqing Jiaotong University(Natural Science), 2022, 41(10): 35-40.

Dynamic Programming Algorithm Based on ARIMA Model and K-Means Clustering Analysis

基于ARIMA模型和K-means聚类分析的动态规划算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 7

Recommended Articles

Metrics