Scheduling Algorithm for Vehicles in Cybernetic Transportation System

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

CLC Number:

TP 273

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-.

References

［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]	LIU Yahui, SHEN Xingwang, GU Xinghai, PENG Tao, BAO Jinsong, ZHANG Dan. A Dual-System Reinforcement Learning Method for Flexible Job Shop Dynamic Scheduling [J]. Journal of Shanghai Jiao Tong University, 2022, 56(9): 1262-1275.
[2]	LI Dechang, YANG Hualong, DUAN Jingru. A Joint Optimization of Vessel Scheduling and Refueling Strategy for Container Liner Shipping with Cooperative Agreements [J]. Journal of Shanghai Jiao Tong University, 2022, 56(7): 953-964.
[3]	LI Linyan, HAN Shuang, QIAO Yanhui, LI Li, LIU Yongqian, YAN Jie, LIU Haidong. A Wind-Solar-Electric Vehicles Coordination Scheduling Method for High Proportion New Energy Grid-Connected Scenarios [J]. Journal of Shanghai Jiao Tong University, 2022, 56(5): 554-563.
[4]	LI Jiaqi, XU Xiaoyuan, Yan Zheng. A Review of Coupled Electricity and Hydrogen Energy System with Transportation System Under the Background of Large-Scale New Energy Vehicles Access [J]. Journal of Shanghai Jiao Tong University, 2022, 56(3): 253-266.
[5]	BI Anyuana (毕安元), FENG Zhengpinga,b∗ (冯正平), ZHU Yuchena (朱昱琛), DENG Xua (邓旭). Two-Stage Scheme for Disturbance Rejection Hovering Control of Underwater Vehicles [J]. J Shanghai Jiaotong Univ Sci, 2022, 27(3): 375-382.
[6]	LIU Shuangxi, WANG Yichong, ZHU Mengjie, LI Yong, YAN Binbin. Research on Differential Game Guidance Law for Intercepting Hypersonic Vehicles with Small Missile-to-Target Speed Ratio [J]. Air & Space Defense, 2022, 5(2): 49-57.
[7]	WANG Zixiang, WU Zerui, LIU Ran. Weekly Physician Scheduling for Emergency Departments with Time-Varying Demands of Patients with Revisits [J]. Journal of Shanghai Jiao Tong University, 2022, 56(2): 242-252.
[8]	TANG Hongtao, WANG Dannan, SHAO Yiping, ZHAO Wenbin, JIANG Weiguang, CHEN Qingfeng. A Modified Migrating Birds Optimization for Multi-Objective Lot Streaming Hybrid Flowshop Scheduling [J]. Journal of Shanghai Jiao Tong University, 2022, 56(2): 201-213.
[9]	LU Qiuyu, YU Zhen, YANG Yinguo, LI Li. Two-Stage Optimal Schedule of Offshore Wind-Power-Integrated Multi-Microgrid Considering Uncertain Power of Sources and Loads [J]. Journal of Shanghai Jiao Tong University, 2022, 56(10): 1308-1316.
[10]	CHEN Chunhong, GU Cunfeng, HU Jun, YANG Jianchao, WU Wen. Research on Distributed ISAR Imaging Simulation Technology of Air Targets [J]. Air & Space Defense, 2022, 5(1): 12-19.
[11]	SHI Qiang (师强), ZHANG Jianlin (张建林), YANG Ming∗ (杨明). Curvature Adaptive Control Based Path Following for Automatic Driving Vehicles in Private Area [J]. J Shanghai Jiaotong Univ Sci, 2021, 26(5): 690-698.
[12]	SU Yimin (苏奕敏), WANG Lin∗ (王琳). Integrated Framework for Test and Evaluation of Autonomous Vehicles [J]. J Shanghai Jiaotong Univ Sci, 2021, 26(5): 699-712.
[13]	LÜ Xiangmei, LIU Tianqi, LIU Xuan, HE Chuan, NAN Lu, ZENG Hong. Low-Carbon Economic Dispatch of Multi-Energy Park Considering High Proportion of Renewable Energy [J]. Journal of Shanghai Jiao Tong University, 2021, 55(12): 1586-1597.
[14]	WANG Jinfeng, CHEN Lu, YANG Wenhui. A Single Machine Scheduling Problem Considering Machine Availability Constraints [J]. Journal of Shanghai Jiao Tong University, 2021, 55(1): 103-110.
[15]	WANG Haoning, TANG Shengjing, GUO Jie, HUANG Fan. Time-Constrained Reentry Guidance with Dynamic Angle of Attack Profile [J]. Air & Space Defense, 2021, 4(1): 71-76.