考虑回路因素的电动汽车最短路问题研究

交通运输系统工程与信息 ›› 2020, Vol. 20 ›› Issue (2): 181-187.

考虑回路因素的电动汽车最短路问题研究

何方^1a，罗志雄^1a，杨艳妮²，李萌^{* 1b}

1. 清华大学a. 工业工程系，b. 土木工程系，北京 100084；2. 首都经济贸易大学管理工程学院，北京 100070

收稿日期:2019-11-26 修回日期:2020-02-08 出版日期:2020-04-25 发布日期:2020-04-30
作者简介:何方(1987-)，男，山东人，副教授，博士.
基金资助:
国家自然科学基金/National Natural Science Foundation of China(71871126，71801161，51622807).

Finding Shortest Path for Battery Electric Vehicles Considering Loops

HE Fang^1a, LUO Zhi-xiong^1a, YANGYan-ni², LI Meng^1b

1a. Department of Industrial Engineering, 1b. Department of Civil Engineering, Tsinghua University, Beijing 100084, China; 2. School of Management and Engineering, Capital University of Economics and Business, Beijing 100070, China

Received:2019-11-26 Revised:2020-02-08 Online:2020-04-25 Published:2020-04-30

摘要/Abstract

摘要：

电动汽车保有量迅速增长，但仍存在里程焦虑、充电设施缺乏等问题，导致驾驶员有时必须绕路才能给电动汽车充电. 基于电动汽车在长途出行过程中绕路充电产生的回路现象，对电动汽车最短路径问题进行深入探索. 对路网进行重构，考虑驾驶员在不同充电速度和排队情况下的充电站选择行为，构造寻求电动汽车最短路径的混合整数规划模型，使用成熟的商业规划软件求解. 为提高大型路网下的模型求解速度，基于动态规划的思想提出一种改进的标签设置算法，高效求解路网中存在回路时的电动汽车最短路径问题. 通过算例验证所提模型和算法的合理性及高效性.

关键词: 城市交通, 电动汽车最短路, 混合整数规划, 回路, 改进的标签设置算法

Abstract:

Battery electric vehicles enjoy fast- growing adoption in recent years. However, there are still some problems including limited driving range, insufficient charging infrastructure and long battery charging time that cannot be ignored and result in electric vehicle drivers detouring to recharge. In this situation, there exist loops on the traveling paths between an OD pair. To address this problem, the road network was reconstructed. Then considering the driver's queuing and choice behaviors with different level of charging stations, a mixed integer programming model for finding the shortest path of EV was put forward, which can be solved by mature programming software. In order to improve the solving efficiency under large- scale road network, an improved label-setting algorithm based on dynamic programming was proposed, which can be employed to efficiently solve the shortest path problem of electric vehicles with loops. Finally, a numerical example was illustrated to verify the rationality and effectiveness of the proposed model and algorithm.

Key words: urban traffic, shortest path of EV, mixed integer programming, loops, improved label-setting algorithm

中图分类号:

U491.3

何方，罗志雄，杨艳妮，李萌. 考虑回路因素的电动汽车最短路问题研究[J]. 交通运输系统工程与信息, 2020, 20(2): 181-187.

HE Fang, LUO Zhi-xiong, YANGYan-ni, LI Meng. Finding Shortest Path for Battery Electric Vehicles Considering Loops[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(2): 181-187.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract20028.shtml

http://www.tseit.org.cn/CN/Y2020/V20/I2/181

参考文献

[1] ZHENG H, PEETA S. Routing and charging locations for electric vehicles for intercity trips[J]. Transportation Planning and Technology, 2017, 40(4): 393-419.

[2] PENG C, RUI T, GUANGQUAN L, et al. The α-reliable path problem in stochastic road networks with link correlations: A moment- matching- based path finding algorithm[J]. Expert Systems with Applications, 2018, (110): 20-32.

[3] HE F, YIN Y, LAWPHONGPANICH S. Network equilibrium models with battery electric vehicles[J]. Transportation Research Part B: Methodological, 2014, (67): 306-319.

[4] HE F, YIN Y, ZHOU J. Deploying public charging stations for electric vehicles on urban road networks[J]. Transportation Research Part C: Emerging Technologies, 2015(60): 227-240.

[5] ZÜNDORF T. Electric vehicle routing with realistic recharging models[D]. Karlsruhe: Karlsruhe Institute of Technology, 2014.

[6] MONTOYA A, GUÉRET C, MENDOZA J E, et al. The electric vehicle routing problem with nonlinear charging function[J]. Transportation Research Part B: Methodological, 2017: S0191261516304556.

[7] STORANDT S. Cruising with a battery-powered vehicle and not getting stranded[C]//Aaai Conference on Artificial Intelligence, 2012.

[8] 张建寰, 南洋. 基于交通信息影响下的电动汽车充电路径规划[J]. 计算机应用, 2016, 36(S2): 282-285. [ZHANG J H, NAN Y. Electric car charging path planning under influence of traffic information[J]. Journal of Computer Applications, 2016, 36(S2): 282- 285.]

[9] 郭放, 杨珺, 杨超. 基于货物分类配送的电动汽车路径优化与换电策略研究[J]. 运筹与管理, 2018, 27(9): 37- 48. [GUO F, YANG J, YANG C. Study on the electric vehicle routing problem and pattery swapping strategy in the presence of cargo category[J]. Operations Research and Management Science, 2018, 27(9): 37- 48.]

[10] GITHUB. Transportation networks for research[OL]. (2016-6-20) [2019-3-21]. https://github.com/bstabler/ TransportationNetworks.

[1]	刘晓冰, 李奉孝, 田欣妹, 闫学东. 基于通勤模式的都市圈中心结构判别研究[J]. 交通运输系统工程与信息, 2022, 22(2): 17-28.
[2]	许奇, 陈越, 黄靖茹, 高顺祥, 张志健. 考虑出行费用的就业可达性分析[J]. 交通运输系统工程与信息, 2022, 22(2): 37-44.
[3]	刘春禹, 刘永红, 罗霞, 朱颖. 混合交通流环境下单交叉口自动驾驶车辆轨迹优化[J]. 交通运输系统工程与信息, 2022, 22(2): 154-162.
[4]	张小雨, 邵春福, 王博彬, 黄士琛. 新冠疫情影响下居民共享出行方式选择行为研究[J]. 交通运输系统工程与信息, 2022, 22(2): 186-196.
[5]	李欣, 戴章, 李怀悦, 胡笳. 基于连续近似模型的轨道交通与常规公交耦合优化设计[J]. 交通运输系统工程与信息, 2022, 22(2): 206-213.
[6]	郝妍熙, 刘戎阳, 胡华, 方勇, 刘志钢. 单向通道行人-自行车混合流建模及自组织现象研究[J]. 交通运输系统工程与信息, 2022, 22(2): 223-229.
[7]	赵传林, 贺少松, 孙淑敏, 王钰涵. 基于理性疏忽理论的交通疏散网络双层优化模型[J]. 交通运输系统工程与信息, 2022, 22(2): 239-246.
[8]	陈小红, 蓝秋雨. 不确定交通需求下交叉口信号配时区间优化模型[J]. 交通运输系统工程与信息, 2022, 22(2): 247-256.
[9]	李冰, 王正辉, 马铭炜, 杨鸿宇, 冯悦. 信号交叉口行人二次过街下右转车通行能力与延误估计模型[J]. 交通运输系统工程与信息, 2022, 22(2): 257-267.
[10]	朱彤, 秦丹, 董傲然, 杜雨萌, 魏雯. 公交驾驶员违规类型同交通事故间的关联分析[J]. 交通运输系统工程与信息, 2022, 22(2): 322-329.
[11]	毛保华, 王敏, 何天健, 陈海波. 城市公共交通服务水平研究回顾和展望[J]. 交通运输系统工程与信息, 2022, 22(1): 2-13.
[12]	王子甲, 贾慧慧, 朱亚迪, 陈峰. 基于智能卡数据的轨道与公交复合网络通勤方式选择行为研究[J]. 交通运输系统工程与信息, 2022, 22(1): 67-73.
[13]	贾斌, 朱凌, 李树凯, 刘家林. 城市轨道交通小交路计划与客流控制协同优化策略[J]. 交通运输系统工程与信息, 2022, 22(1): 124-132.
[14]	牟振华, 汪寒冰, 林本江, 陈逸群, 金程程, 陈艳艳. 基于演化博弈的违章停车动态罚金策略效用仿真评价[J]. 交通运输系统工程与信息, 2022, 22(1): 152-162.
[15]	贾富强, 李引珍, 杨信丰, 马昌喜, 代存杰. 基于演化博弈的政府鼓励条件下共享停车行为分析[J]. 交通运输系统工程与信息, 2022, 22(1): 163-170.