Collaborative routing method for operation vehicle in inland port based on game theory
FAN Jiajia1,2, LIU Hongxing1,2, LI Yonghua1,2, YANG Lijin1,2
1. School of Computer Science and Technology, Wuhan University of Technology, Wuhan Hubei 430063, China; 2. Hubei Key Laboratory of Transportation Internet of Things(Wuhan University of Technology), Wuhan Hubei 430070, China
Abstract:Focusing on the traffic congestion problem in inland ports with vehicle transportation and large throughput, a collaborative routing method for operation vehicles in inland port based on game theory was proposed. Firstly, the interaction between the operation vehicles that simultaneously request route planning was modeled as a game with incomplete information and the idea of Satisfaction Equilibrium (SE) was applied to analyze the proposed game. It was assumed that every vehicle has an expected utility for routing result, when all vehicles were satisfied, the game achieved an equilibrium. Then, a collaborative routing algorithm was proposed. In this algorithm, firstly every vehicle selected the route according to greedy strategy, then all vehicles were divided into groups by the rule and vehicles in the group performed adaptive learning based on historical routing results to complete the game. The experimental results show that the collaborative routing algorithm reduces the average driving time of vehicles up to 50.8% and 16.3% respectively and improves the system profit up to 51.7% and 24.5% respectively compared with Dijkstra algorithm and Self-Adaptive Learning Algorithm (SALA) when the number of simultaneously working vehicles in port is 286. The proposed algorithm can effectively reduce the average driving time of vehicles, improve system profit, and is more suitable for the routing problem of vehicles in inland port.
范家佳, 刘洪星, 李勇华, 杨丽金. 基于博弈论的内河港口作业车辆协同选路方法[J]. 计算机应用, 2020, 40(1): 50-55.
FAN Jiajia, LIU Hongxing, LI Yonghua, YANG Lijin. Collaborative routing method for operation vehicle in inland port based on game theory. Journal of Computer Applications, 2020, 40(1): 50-55.
[1] CHAN H K, XU S. Intelligent port data management systems to improve capability[C]//Proceedings of the 2017 International Conference on Service Systems and Service Management. Piscataway:IEEE, 2017:1-3. [2] 张胜利.我国港口信息化发展趋势与对策构想[J].中国水运,2015,23(5):30-31.(ZHANG S L. Development trends and countermeasures of port informatization[J]. China Water Transport, 2015, 23(5):30-31.) [3] CUNHA F, MAIA G, RAMOS H S, et al. Vehicular networks to intelligent transportation systems[M]//ARYA K V, BHADORIA R S, CHAUDHARI N S. Emerging Wireless Communication and Network Technologies. Berlin:Springer, 2018:297-315. [4] PSARAFTIS H N, WEN M, KONTOVAS C A. Dynamic vehicle routing problems:three decades and counting[J]. Networks, 2016, 67(1):3-31. [5] 刘恒宇,汝宜红.考虑交通拥堵及工作量平衡性的一致性车辆路径问题[J].西南交通大学学报,2016,51(5):931-937.(LIU H Y, RU Y H. Consistent vehicle routing problem considering traffic congestion and workload balance[J]. Journal of Southwest Jiaotong University, 2016, 51(5):931-937.) [6] DE SOUZA A M, YOKOYAMA R S, MAIA G, et al. Real-time path planning to prevent traffic jam through an intelligent transportation system[C]//Proceedings of the 2016 IEEE Symposium on Computers and Communication. Piscataway:IEEE, 2016:726-731. [7] LIN K, LI C, FORTINO G, et al. Vehicle route selection based on game evolution in social Internet of vehicles[J]. IEEE Internet of Things Journal, 2018, 5(4):2423-2430. [8] 严丽平,胡文斌,王欢,等.城市路网多路口路径动态实时选择方法[J].软件学报,2016,27(9):2199-2217.(YAN L P, HU W B, WANG H, et al. Dynamic real-time algorithm for multi-intersection route selection in urban traffic networks[J]. Journal of Software, 2016, 27(9):2199-2217.) [9] 吴黎兵,范静,聂雷,等.一种车联网环境下的城市车辆协同选路方法[J].计算机学报,2017,40(7):1600-1613.(WU L B, FAN J, NIE L, et al. A collaborative routing method with Internet of vehicles for city cars[J]. Chinese Journal of Computers, 2017, 40(7):1600-1613.) [10] AMAR H M, BASIR O A. A bargaining-based solution to the team mobility planning game[J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 19(3):854-867. [11] 陈磊,赵宪花.散货码头智能化发展制约因素研究[J].中国水运,2016,16(1):62-63.(CHEN L, ZHAO X H. Research on the constraints of intelligent development of bulk terminals[J]. China Water Transport, 2016, 16(1):62-63.) [12] GOONEWARDENA M, PERLAZA S M, YADAV A, et al. Generalized satisfaction equilibrium for service-level provisioning in wireless networks[J]. IEEE Transactions on Communications, 2017, 65(6):2427-2437. [13] MA W. Random expected utility theory with a continuum of prizes[J]. Annals of Operations Research, 2018, 271(2):787-809. [14] 徐蕾,杨成,姜春晓,等.协同过滤推荐系统中的用户博弈[J].计算机学报,2016,39(6):1176-1189.(XU L, YANG C, JIANG C X, et al. Game analysis of user participation in collaborative filtering systems[J]. Chinese Journal of Computers, 2016, 39(6):1176-1189.) [15] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematic, 1959, 1(1):269-271.