基于博弈论的内河港口作业车辆协同选路方法

doi:10.11772/j.issn.1001-9081.2019060988

计算机应用 ›› 2020, Vol. 40 ›› Issue (1): 50-55.DOI: 10.11772/j.issn.1001-9081.2019060988

基于博弈论的内河港口作业车辆协同选路方法

范家佳^1,2, 刘洪星^1,2, 李勇华^1,2, 杨丽金^1,2

1. 武汉理工大学计算机科学与技术学院, 武汉 430063;
2. 交通物联网技术湖北省重点实验室(武汉理工大学), 武汉 430070

收稿日期:2019-06-12 修回日期:2019-07-31 出版日期:2020-01-10 发布日期:2019-09-27
通讯作者: 李勇华
作者简介:范家佳(1994-),男,重庆人,硕士研究生,主要研究方向:智能交通、调度优化;刘洪星(1963-),男,湖北洪湖人,教授,博士,主要研究方向:智能交通、调度优化;李勇华(1977-),男,湖北武汉人,副教授,博士,主要研究方向:智能交通、调度优化;杨丽金(1994-),女,河北张家口人,硕士研究生,主要研究方向:智能交通、调度优化。
基金资助:
内河航运技术湖北省重点实验室基金资助项目（NHHY2017003）；交通物联网技术湖北省重点实验室基金资助项目（2017III028-002）。

Collaborative routing method for operation vehicle in inland port based on game theory

FAN Jiajia^1,2, LIU Hongxing^1,2, LI Yonghua^1,2, YANG Lijin^1,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

Received:2019-06-12 Revised:2019-07-31 Online:2020-01-10 Published:2019-09-27
Supported by:
This work is partially supported by the Fund of Hubei Key Laboratory of Inland Shipping Technology (NHHY2017003), the Fund of Hubei Key Laboratory of Transportation Internet of Things (2017III028-002).

摘要/Abstract

摘要： 针对以汽车运输为主且吞吐量较大的内河港口的交通拥堵问题，提出一种基于博弈论的内河港口作业车辆协同选路方法。首先，基于港口路网特征与车辆作业特点，将同时请求路径规划的作业车辆间的交互建模为不完全信息博弈，采用满足均衡（SE）的概念来分析该博弈。假设每个车辆对选路效用都有一个预期，当所有车辆都得到满足时博弈即达到均衡。然后，提出了一种车辆协同选路算法，算法中每个车辆首先按照贪心策略初始选路，之后将所有车辆按规则分组，组内车辆根据历史选路结果进行适应性学习并完成博弈。实验结果表明，当港区同时作业车辆数为286时，协同选路算法的车辆平均行驶时间分别比Dijkstra算法和自适应学习算法（SALA）少50.8%和16.3%，系统收益分别比Dijkstra算法和SALA提高51.7%和24.5%。所提算法能够有效减少车辆平均行驶时间，提高系统收益，更适用于内河港口车辆选路问题。

关键词: 交通拥堵, 车辆选路问题, 路径规划, 内河港口, 博弈论

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.

Key words: traffic congestion, vehicle routing problem, route planning, inland port, game theory

中图分类号:

TP311.5

范家佳, 刘洪星, 李勇华, 杨丽金. 基于博弈论的内河港口作业车辆协同选路方法[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[J]. 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.

基于博弈论的内河港口作业车辆协同选路方法

Collaborative routing method for operation vehicle in inland port based on game theory

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李开荣, 刘爽, 胡倩倩, 唐亦媛. 基于转角约束的改进蚁群优化算法路径规划[J]. 计算机应用, 2021, 41(9): 2560-2568.
[2]	王艺洁, 凡佳飞, 王陈宇. 云边环境下基于博弈论的两阶段任务迁移策略[J]. 计算机应用, 2021, 41(5): 1392-1398.
[3]	张舒瑶, 李勇华, 范家佳. 基于博弈论的散货港口堆场堆位分配算法[J]. 计算机应用, 2021, 41(3): 867-874.
[4]	毛莺池, 徐雪松, 刘鹏飞. 基于稳定匹配的多用户任务卸载策略[J]. 计算机应用, 2021, 41(3): 786-793.
[5]	魏博, 杨茸, 舒思豪, 万勇, 苗建国. 基于离子运动-人工蜂群算法的移动机器人路径规划[J]. 计算机应用, 2021, 41(2): 379-383.
[6]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[7]	王家亮, 李树华, 张海涛. 基于贝叶斯估计与区域划分遍历的四轴飞行器避障路径规划算法[J]. 计算机应用, 2021, 41(2): 384-389.
[8]	李伟, 金世俊. 基于人工势场法和启发式采样的最优路径收敛方法[J]. 计算机应用, 2021, 41(10): 2912-2918.
[9]	刘思嘉, 童向荣. 基于强化学习的城市交通路径规划[J]. 计算机应用, 2021, 41(1): 185-190.
[10]	徐晓强, 秦品乐, 曾建朝. 基于改进粒子群优化算法的牙齿正畸路径规划方法[J]. 计算机应用, 2020, 40(7): 1938-1943.
[11]	祁玄玄, 黄家骏, 曹建安. 基于改进A^*算法的无人车路径规划[J]. 计算机应用, 2020, 40(7): 2021-2027.
[12]	郑延斌, 樊文鑫, 韩梦云, 陶雪丽. 基于博弈论及Q学习的多Agent协作追捕算法[J]. 计算机应用, 2020, 40(6): 1613-1620.
[13]	韩雨涝, 房鼎益. 联合无线充电与数据收集的移动充电装置多目标路径规划算法[J]. 计算机应用, 2020, 40(6): 1745-1750.
[14]	徐小强, 王明勇, 冒燕. 基于改进人工势场法的移动机器人路径规划[J]. 计算机应用, 2020, 40(12): 3508-3512.
[15]	屈立成, 吕娇, 赵明, 王海飞, 屈艺华. 基于三维时空地图和运动分解的多机器人路径规划算法[J]. 计算机应用, 2020, 40(12): 3499-3507.