面向全自动控制交通系统的车辆调度算法

上海交通大学学报（自然版） ›› 2017, Vol. 51 ›› Issue (2): 174-.

面向全自动控制交通系统的车辆调度算法

李爽a，杨明b，王春香a，王冰b

上海交通大学 a. 机器人研究所；b. 自动化系，上海市北斗导航与位置服务重点实验室，上海 200240

出版日期:2017-02-28 发布日期:2017-02-28
基金资助:
国家自然基金重大研究计划（91420101），国家自然科学基金项目（61174178/51178268）资助

Scheduling Algorithm for Vehicles in Cybernetic Transportation System

LI Shuanga,YANG Mingb,WANG Chunxianga,WANG Bingb

a. Research Institute of Robotics; b. Department of Automation, Shanghai Key Laboratory of
Navigation and Location Services, Shanghai Jiao Tong University, Shanghai 200240, China

Online:2017-02-28 Published:2017-02-28

摘要/Abstract

摘要：

结合遗传算法和贪婪算法的优点，提出了聚类贪婪遗传算法，构建了一个全自动控制交通系统的仿真系统；针对遗传算法、贪婪算法和聚类贪婪遗传算法分别进行实验，并比较其实验结果.结果表明：当系统趋于稳定时，聚类贪婪遗传算法能够提高叫车请求的平均响应时间，从而避免叫车请求饿死的情况；聚类贪婪遗传算法可用于全自动控制交通系统车辆的调度.

关键词: 车辆, 调度, 全自动控制交通系统, 聚类贪婪遗传算法, 仿真系统

Abstract:

Combining the advantage of greedy algorithm with that of genetic algorithm, this paper presents a new algorithm named proximity cluster greedy and genetic algorithm. This paper also designs a simulation system for cybernetic transportation system to test all the three algorithms and collect the experiment results. The results show that when the system tends to be steady, the proximity cluster greedy and genetic algorithm can efficiently decrease the response time and avoid the requests’ starving, so this algorithm is a good choice for the cybernetic transportation system.

Key words: vehicles, scheduling, cybernetic transportation system (CTS), proximity cluster reedy and genetic algorithm, simulation system

中图分类号:

TP 273

李爽a，杨明b，王春香a，王冰b. 面向全自动控制交通系统的车辆调度算法[J]. 上海交通大学学报（自然版）, 2017, 51(2): 174-.

LI Shuanga,YANG Mingb,WANG Chunxianga,WANG Bingb. Scheduling Algorithm for Vehicles in Cybernetic Transportation System[J]. Journal of Shanghai Jiaotong University, 2017, 51(2): 174-.

参考文献

［1］DANTZIG G, RAMER J. The trunk dispatching probem ［J］. Management Science, 1959, 10(6): 80-91.
［2］TARANTILIS C D, IOANNOU G, KIRANOUDIS C T, et al. Solving the open vehicle routing problem via a single parameter metaheuristic algorithm ［J］. Journal of the Operational Research Society, 2005, 56(5): 588-596.
［3］WILSON G V, PAWLEY G S. On the stability of the TSP algorithm of Hopfield and Tank ［J］. Boil Cybem, 1988, 58: 63-70.
［4］ESCOBAR J W, LINFATI R, TOTH P, et al. A hybrid granular tabu search algorithm for the multidepot vehicle routing problem ［J］. Journal of Heuristics, 2014, 20(5): 483-509.
［5］LIN C, CHOY K L, HO G T S, et al. Survey of green vehicle routing problem: Past and future trends ［J］. Expert Systems with Applications, 2014, 41(4): 1118-1138.
［6］BOISS S, BENENSON R, BOURAOUI L, et al. Cybernetic transportation systems design and development: Simulation software cybercars［C］∥IEEE International Conference on Robotics and AutomationICRA’2007. Roma, Italy: ICRA, 2007.
［7］LI T Y, YANG M, DENG L Y, et al. An extended probabilistic selflocalization algorithm using hybrid maps［C］∥17th International IEEE Conference on Intelligent Transportation Systems (ITSC). New York, USA: IEEE, 2014: 81-86.
［8］DOI S. Proposal and evaluation of a pheromonebased algorithm for the patrolling problem in dynamic environments［C］∥IEEE Symposium on Swarm Intelligence (SIS). Istanbul, Turkey: IEEE, 2013: 48-55.
［9］SARAYDARYAN J, JUMEL F, SIMONIN O. Robots delivering services to moving people: Individual vs. group patrolling strategies［C］∥2015 IEEE International Workshop on Advanced Robotics and Its Social Impacts (ARSO). Lyon, France: IEEE, 2015: 1-8.
［10］YANOVSKI V, WAGNER I A, BRUCKSTEIN A M. A distributed ant algorithm for protect efficiently patrolling a network ［J］. Algorithmica, 2003, 37(3): 165-186.
［11］HEYDON A, NAJORK M. Mercator: A scalable, extensible web crawler ［J］. World Wide Web, 1999, 2(4): 219-229.
［12］LOHSE M, NAGEL A, HERTER T, et al. Mercator: A fast and simple web server for genome scale functional annotation of plant sequence data ［J］. Plant, Cell and Environment, 2014, 37(5): 1250-1258.
［13］PASQUALETTI F, FRANCHI A, BULLO F. On optimal cooperative patrolling［C］∥49th IEEE Conference on Decision and Control (CDC). Atlanta, Georgia, USA: IEEE, 2010: 7153-7158.
［14］POULET C, CORRUBLE V, SEGHROUCHNI A E F. Working as a team: using social criteria in the timed patrolling problem［C］∥IEEE 24th International Conference on Tools with Artificial Intelligence. Athens, Greece: IEEE, 2012: 933-938.
［15］POLI R, KOZA J. Genetic programming［M］. USA: Springer, 2014: 143-185.
［16］PHAM D T, DIMOV S S, NGUYEN C D. Selection of K in Kmeans clustering ［J］. Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science, 2005, 219(1): 103-119.

[1]	刘亚辉, 申兴旺, 顾星海, 彭涛, 鲍劲松, 张丹. 面向柔性作业车间动态调度的双系统强化学习方法[J]. 上海交通大学学报, 2022, 56(9): 1262-1275.
[2]	李林晏, 韩爽, 乔延辉, 李莉, 刘永前, 阎洁, 刘海东. 面向高比例新能源并网场景的风光-电动车协同调度方法[J]. 上海交通大学学报, 2022, 56(5): 554-563.
[3]	黄鹤, 吴琨, 李昕芮, 王珺, 王会峰, 茹锋. 自适应插值飞蛾扑火优化的多特征粒子滤波车辆跟踪算法[J]. 上海交通大学学报, 2022, 56(2): 143-155.
[4]	汤洪涛, 王丹南, 邵益平, 赵文彬, 江伟光, 陈青丰. 基于改进候鸟迁徙优化的多目标批量流混合流水车间调度[J]. 上海交通大学学报, 2022, 56(2): 201-213.
[5]	王屹. 单点吊装作业视景仿真应用研究[J]. 海洋工程装备与技术, 2022, 9(2): 38-42.
[6]	陆秋瑜, 于珍, 杨银国, 李力. 考虑源荷功率不确定性的海上风力发电多微网两阶段优化调度[J]. 上海交通大学学报, 2022, 56(10): 1308-1316.
[7]	陈禹伊, 陈璐. 车辆路径规划问题的逆向优化方法[J]. 上海交通大学学报, 2022, 56(1): 81-88.
[8]	陈春红, 顾村锋, 胡俊, 杨建超, 吴文. 空中目标分布式ISAR成像仿真技术研究[J]. 空天防御, 2022, 5(1): 12-19.
[9]	王兴志, 翟海保, 严亚勤, 吴庆曦. 基于数字孪生和深度学习的新一代调控系统预调度方法[J]. 上海交通大学学报, 2021, 55(S2): 37-41.
[10]	许凌, 王兴志, 肖林朋. 基于语义特征抓取电网调度事件的检测技术[J]. 上海交通大学学报, 2021, 55(S2): 86-91.
[11]	胡益恺, 王春香, 杨明. 智能车辆决策方法研究综述[J]. 上海交通大学学报, 2021, 55(8): 1035-1048.
[12]	范厚明, 于佳琪, 马梦知, 蒋晓丹, 慈吉利, 翟志伟. 模糊时间窗下多船型不定期船调度与航速联合优化[J]. 上海交通大学学报, 2021, 55(3): 297-310.
[13]	吕祥梅, 刘天琪, 刘绚, 何川, 南璐, 曾红. 考虑高比例新能源消纳的多能源园区日前低碳经济调度[J]. 上海交通大学学报, 2021, 55(12): 1586-1597.
[14]	王金凤, 陈璐, 杨雯慧. 考虑设备可用性约束的单机调度问题[J]. 上海交通大学学报, 2021, 55(1): 103-110.
[15]	何德峰, 彭彬彬, 顾煜佳, 余世明. 基于高斯过程回归的车辆巡航系统学习预测控制[J]. 上海交通大学学报, 2020, 54(9): 904-909.