基于文献计量和知识图谱的电动车辆路径问题研究综述

doi:10.3778/j.issn.1002-8331.2306-0065

摘要/Abstract

摘要： 为揭示电动车辆路径问题领域的研究与发展现状，对CNKI和Web of Science数据库中电动车辆路径问题1994—2022年间的期刊文献进行知识挖掘与分析。基于文献计量学的量化分析与知识图谱的可视化，通过分析文献外部特征和共被引情况，梳理研究热点及热点演进趋势，归纳研究主题，总结出电动车辆路径问题的知识域包括研究主题和应用场景，其中，研究主题由变体研究、充电调度、求解方法三部分构成；对电动车辆路径问题在复杂实际问题、高效求解算法方面的未来发展进行展望，这将为电动车辆路径问题研究的深入化与国际化提供一定的推动作用。

关键词: 电动车辆路径问题, 绿色物流, 充电调度, 知识图谱, 可视化计量

Abstract: To reveal the research and development status in the field of electric vehicle routing problem, knowledge mining and analysis are conducted on the papers of electric vehicle routing problem in CNKI and Web of Science database from 1994 to 2022. The external characteristics and co-citation of the literature are analyzed based on the quantitative analysis of bibliometrics and the visualization of knowledge mapping. The research hotspots and hotspots evolution trend are sorted, and the research topics is summarized in the field. The knowledge domain of the electric vehicle routing problem is summarized, including research topics and application scenarios. The research topic consists of variant research, charging scheduling, and solution methods. The future development of electric vehicle routing problem in complex practical problems and efficient algorithms is prospected. This paper will provide a certain impetus for the deepening and internationalization of the research on the electric vehicle routing problem.

Key words: electric vehicle routing problem, green logistics, charging scheduling, knowledge mapping, visual measurement

王文豪, 殷旅江, 鄢曹政, 牟光远. 基于文献计量和知识图谱的电动车辆路径问题研究综述[J]. 计算机工程与应用, 2024, 60(2): 46-62.

WANG Wenhao, YIN Lyujiang, YAN Caozheng, MOU Guangyuan. Review of Research on Electric Vehicle Routing Problem Based on Bibliometrics and Knowledge Mapping[J]. Computer Engineering and Applications, 2024, 60(2): 46-62.

参考文献

[1] DANTZING G, RAMSER J. The truck dispatching problem[J]. Management Science, 1959, 6(2): 80-91.
[2] CAO Q K, YANG K W, REN X Y. Vehicle routing optimization with multiple fuzzy time windows based on improved wolf pack algorithm[J]. Advances in Production Engineering and Management, 2017, 12(4): 401-411.
[3] BELHAIZA S. A game theoretic approach for the real-life multiple criterion vehicle routing problem with multiple time windows[J]. IEEE Systems Journal, 2018, 12(2): 1251-1262.
[4] GMIRAA M, GENDREAU M, LODI A, et al. Tabu search for the time-dependent vehicle routing problem with time windows on a road network[J]. European Journal of Operational Research, 2021, 288(1): 129-140.
[5] OSTERMEIER M, HUBNER A. Vehicle selection for a multi-compartment vehicle routing problem[J]. European Journal of Operational Research, 2018, 269(2): 682-694.
[6] ZHU W B, QIN H U, LI M, et al. A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP[J]. Computers and Operations Research, 2012, 39(9): 2178-2195.
[7] 杨华龙, 陆婷, 辛禹辰. 基于改进粒子群算法的异质车队二级IRP优化[J]. 计算机工程与应用, 2020, 56(22): 272-278.
YANG H L, LU T, XIN Y C. Improved particle swarm optimization for two-echelon IRP with heterogeneous fleet[J]. Computer Engineering and Applications, 2020, 56(22): 272-278.
[8] MACRINA G, PUGLIESE L, GUERRIERO F, et al. The green mixed fleet vehicle routing problem with partial battery recharging and time windows[J]. Computers and Operations Research, 2019, 101: 183-199.
[9] GAO S, WANG Y, CHENG J, et al. Ant colony optimization with clustering for solving the dynamic location routing problem[J]. Applied Mathematics and Computation, 2016, 285: 149-173.
[10] OKULEWICZ M, MANDZIUK J. The impact of particular components of the PSO-based algorithm solving the dynamic vehicle routing problem[J]. Applied Soft Computing, 2017, 58: 586-604.
[11] CHANG D J, MORLOK E K. Vehicle speed profiles to minimize work and fuel consumption[J]. Journal of Transportation Engineering, 2005, 131( 3): 173-182.
[12] ERICSSON E, LARSSON H, BRUNDELL-FREIJ K. Optimizing route choice for lowest fuel consumption-potential effects of a new driver support tool[J]. Transportation Research Part C: Emerging Technologies, 2006, 14(6): 369-383.
[13] KARA I, KARA B Y, YETIS M K. Energy minimizing vehicle routing problem[C]//International Conference on Combinatorial Optimization and Applications, 2007: 62-71.
[14] BEKTAS T, LAPORTE G. The pollution-routing problem[J]. Transportation Research Part B: Methodological, 2011, 45(8): 1232-1250.
[15] DEMIR E, BEKTAS T, LAPORTE G. A comparative analysis of several vehicle emission models for road freight transportation[J]. Transportation Research Part D: Transport and Environment, 2011, 16(5): 347-357.
[16] DEMIR E, BEKTAS T, LAPORTE G. An adaptive large neighborhood search heuristic for the pollution-routing problem[J]. European Journal of Operational Research, 2012, 223(2): 346-359.
[17] ERDOGAN S, MILLER-HOOKS E. A green vehicle routing problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2012, 48(1): 100-114.
[18] 周鲜成, 周开军, 王莉, 等. 物流配送中的绿色车辆路径模型与求解算法研究综述[J]. 系统工程理论与实践, 2021, 41(1): 213-230.
ZHOU X C, ZHOU K J, WANG L, et al. Review of green vehicle routing model and its algorithm in logistics distribution[J]. Systems Engineering—Theory & Practice, 2021, 41(1): 213-230.
[19] 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.
[20] KESKIN M, ?ATAY B. Partial recharge strategies for the electric vehicle routing problem with time windows[J]. Transportation Research Part C: Emerging Technologies, 2016, 65: 111-127.
[21] 郭放, 杨珺, 杨超. 考虑充电策略与电池损耗的电动汽车路径优化问题研究[J]. 中国管理科学, 2018, 26(9): 106-118.
GUO F, YANG J, YANG C. Study on the electric vehicle routing problem in the present of charging strategy and battery consumption[J]. Chinese Journal of Management Science, 2018, 26(9): 106-118.
[22] 黄建华, 刘方翔. 动态负载下电动汽车充电策略及路径优化问题[J]. 计算机集成制造系统, 2023(11): 3909-3921.
HUANG J H, LIU F X. Charging strategy and routing optimization of electric vehicles under dynamic load[J]. Computer Integrated Manufacturing Systems, 2023(11): 3909-3921.
[23] LEE C. An exact algorithm for the electric-vehicle routing problem with nonlinear charging time[J]. Journal of the Operational Research Society, 2021, 72(7): 1461-1485.
[24] BASSOA R, KULCSARB B, EGARDT B, et al. Energy consumption estimation integrated into the electric vehicle routing problem[J]. Transportation Research Part D: Transport and Environment, 2019, 69: 141-167.
[25] KANCHARLA S R, RAMADURAI G. An adaptive large neighborhood search approach for electric vehicle routing with load?dependent energy consumption[J]. Transportation in Developing Economies, 2018, 4: 10.
[26] YANG J, SUN H. Battery swap station location-routing problem with capacitated electric vehicles[J]. Computers and Operations Research, 2015, 55: 217-232.
[27] 陆坚毅, 杨超, 揭婉晨. 考虑绕行特征的电动汽车快速充电站选址问题及自适应遗传算法[J]. 运筹与管理, 2017, 26(1): 8-17.
LU J Y, YANG C, JIE W C. An adaptive-self genetic algorithm for solving electric vehicle fast recharging location problem with detour characteristic[J]. Operations Research and Management Science, 2017, 26(1): 8-17.
[28] KAKU I, DEWIL R, CATTRYSSE D. Hybrid simulated annealing and tabu search method for the electric travelling salesman problem with time windows and mixed charging rates[J]. Expert Systems with Applications, 2019, 134: 279-303.
[29] CESELLI A, FELIPE A, ORTUO M T, et al. A branch-and-cut-and-price algorithm for the electric vehicle routing problem with multiple technologies[J]. SN Operations Research Forum, 2021, 2: 8.
[30] 陈欣慰. 多模糊时间窗约束下基于纯电动汽车的城市配送车辆路径问题研究[D]. 成都, 西南交通大学, 2020.
CHEN X W. Research on vehicle routing problem based on pure electric vehicle with multiple fuzzy time windows constraints[D]. Chengdu, Southwest Jiaotong University, 2020.
[31] 王文豪, 殷旅江, 鄢曹政. 基于图谱量化的国内车辆路径问题研究发展分析[J]. 物流科技, 2023, 46(21): 65-69.
WANG W H, YIN L J, YAN C Z. Analysis of the development of domestic vehicle routing problem research based on mapping quantification[J]. Logistics Sci-Tech, 2023, 46(21): 65-69.
[32] CHEN C M, HU Z G, LIU S B, et al. Emerging trends in regenerative medicine: a scientometric analysis in CiteSpace[J]. Expert Opinion on Biological Therapy, 2012(5): 593-608.
[33] CHEN C M. Science mapping: a systematic review of the literature[J]. Journal of Data and Information Science, 2017(2): 1-40.
[34] 李英, 李惠, 成琪. 基于文献计量和知识图谱的国际绿色车辆路径问题研究发展分析[J]. 中国管理科学, 2016, 24: 206-216.
LI Y, LI H, CHENG Q. The development analysis of international green vehicle routing problem based on bibliometric and knowledge mapping[J]. Chinese Journal of Management Science, 2016, 24: 206-216.
[35] CHEN C M. CiteSpace II: detecting and visualizing emerging trends and transient patterns in scientific literature[J]. Journal of the American Society for Information Science and Technology, 2006(3): 359-377.
[36] SCHNEIDER M, STENGER A, GOEKE D. The electric vehicle-routing problem with time windows and recharging stations[J]. Transportation Science, 2014, 48(4): 500-520.
[37] 陈悦, 陈超美, 刘则渊, 等. CiteSpace知识图谱的方法论功能[J]. 科学学研究, 2015, 33(2): 242-253.
CHEN Y, CHEN C M, LIU Z Y, et al. The methodology function of CiteSpace mapping knowledge domains[J]. Studies in Science of Science, 2015, 33(2): 242-253.
[38] KESKIN M, LAPORTE G, ?ATAY B. Electric vehicle routing problem with time-dependent waiting times at recharging stations[J]. Computers and Operations Research, 2019, 107: 77-94.
[39] KESKIN M, ?ATAY B, LAPORTE G. A simulation-based heuristic for the electric vehicle routing problem with time windows and stochastic waiting times at recharging stations[J]. Computers and Operations Research, 2021, 125: 105060.
[40] ZHOU B H, ZHAO Z. Multi-objective optimization of electric vehicle routing problem with battery swap and mixed time windows[J]. Neural Computing and Applications, 2022, 34: 7325-7348.
[41] GOEKEA D, SCHNEIDER M. Routing a mixed fleet of electric and conventional vehicles[J]. European Journal of Operational Research, 2015, 245: 81-99.
[42] HE F, WU D, YIN Y, et al. Optimal deployment of public charging stations for plug-in hybrid electric vehicles[J]. Transportation Research Part B: Methodological, 2013, 47: 87-101.
[43] GOLI A, GOLMOHAMMADI A M, VERDEGAY J L. Two-echelon electric vehicle routing problem with a developed moth-flame meta-heuristic algorithm[J]. Operations Management Research, 2022, 15(3): 891-912.
[44] ROGGE M, EVELIEN V D, LARSEN A, et al. Electric bus fleet size and mix problem with optimization of charging infrastructure[J]. Applied Energy, 2018, 211: 282-295.
[45] ALVO M, ANGULO G, KLAPP M A. An exact solution approach for an electric bus dispatch problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2021, 156: 102528.
[46] 许美贤, 郑琰. 绿色车辆路径问题研究综述[J]. 昆明理工大学学报(自然科学版), 2021, 46(4): 158-170.
XU M X, ZHENG Y. Research review of green vehicle routing problem[J]. Journal of Kunming University of Science and Technology (Natural Science), 2021, 46(4): 158-170.
[47] MONTOYA A, CHRISTELLE G, JORGE E, et al. The electric vehicle routing problem with nonlinear charging function[J]. Transportation Research Part B: Methodological, 2017, 103: 87-110.
[48] HIERMANN G, PUCHINGER J, ROPKE S, et al. The electric fleet size and mix vehicle routing problem with time windows and recharging stations[J]. European Journal of Operational Research, 2016, 252(3): 995-1018.
[49] DESAULNIERS G, ERRICO F, IRNICH S, et al. Exact algorithms for electric vehicle-routing problems with time windows[J]. Operations Research, 2016, 64(6): 1388-1405.
[50] FELIPE A, ORTUO M T, RIGHINI G, et al. A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 71: 111-128.
[51] 李得成, 陈彦如, 张宗成. 基于分支定价算法的电动车与燃油车混合车辆路径问题研究[J]. 系统工程理论与实践, 2021, 41(4): 995-1009.
LI D C, CHEN Y R, ZHANG Z C. A branch-and-price algorithm for electric vehicle routing problem with time windows and mixed fleet[J]. Systems Engineering-Theory and Practice, 2021, 41(4): 995-1009.
[52] DOPPSTADT C, KOBERSTEIN A, VIGO D. The hybrid electric vehicle-traveling salesman problem with time windows[J]. European Journal of Operational Research, 2020, 284: 675-692.
[53] BREUNIGA U, BALDACCI R, HARTL R F, et al. The electric two-echelon vehicle routing problem[J]. Computers and Operations Research, 2019, 103: 198-210.
[54] ZHANG S, CHEN M Z, ZHANG W Y. A novel location-routing problem in electric vehicle transportation with stochastic demands[J]. Journal of Cleaner Production, 2019, 21: 567-581.
[55] BASSO R, KULCSAR B, SANCHEZ-DIAZ I, et al. Dynamic stochastic electric vehicle routing with safe reinforcement learning[J]. Transportation Research Part E: Logistics and Transportation Review, 2022, 157: 102496.
[56] MAO H, SHI J, ZHOU Y, et al. The electric vehicle routing problem with time windows and multiple recharging options[J]. IEEE Access, 2020, 8: 114864-114875.
[57] XIAO Y Y, ZHANG Y, KAKU I, et al. Electric vehicle routing problem: a systematic review and a new comprehensive model with nonlinear energy recharging and consumption[J]. Renewable and Sustainable Energy Reviews, 2021, 151: 111567.
[58] 魏冠元, 王冠群, 阮观梅, 等. 电动汽车充电站选址智能决策与优化研究综述[J]. 计算机工程与应用, 2023, 59(21): 52-65.
WEI G Y, WANG G Q, RUAN G M, et al. Review of intelligent decision optimization of electric vehicle charging stations location[J]. Computer Engineering and Applications, 2023, 59(21): 52-65.
[59] WORLEY O, KLABJAN D, SWEDA T M. Simultaneous vehicle routing and charging station siting for commercial electric vehicles[C]//2012 IEEE International Electric Vehicle Conference, Greenville, SC, USA, 4-8 March, 2012, 1-3.
[60] 王琪瑛, 李英, 李惠. 带软时间窗的电动车换电站选址路径问题研究[J]. 工业工程与管理, 2019, 24(3): 99-106.
WANG Q Y, LI Y, LI H. Battery swap station location-routing problem of electric vehicles with soft time windows[J]. Industrial Engineering and Management, 2019, 24(3): 99-106.
[61] AGHALARI A, SALAMAH D, KABLI M, et al. A two-stage stochastic location-routing problem for electric vehicles fast charging[J]. Computers and Operations Research, 2023, 158: 106286.
[62] KESKIN M, ?ATAY B. A matheuristic method for the electric vehicle routing problem with time windows and fast chargers[J]. Computers and Operations Research, 2018, 100: 172-188.
[63] GILMORE P C, GOMORY R E. A linear programming approach to the cutting-stock problem[J]. Operations Research, 1961, 9(6): 849-859.
[64] CLARKE G, WRIGHT J W. Scheduling of vehicles from a central depot to a number of delivery points[J]. Operations Research, 1964, 12(4): 568-581.
[65] PAZA J C, GRANADA-ECHEVERRIA M, ESCOBAR J W. The multi-depot electric vehicle location routing problem with time windows[J]. International Journal of Industrial Engineering Computations, 2018, 9: 123-136.
[66] FROGER A, MENDOZA J E, JABALI O, et al. Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions[J]. Computers and Operations Research, 2019, 104: 256-294.
[67] CUBIDES L C, LONDOO A A, ECHEVERRI M G. Electric vehicle routing problem with backhauls considering the location of charging stations and the operation of the electric power distribution system[J]. Tecno Lógicas, 2019, 22: 1-21.
[68] LIN B, GHADDAR B, NATHWANI J. Deep reinforcement learning for the electric vehicle routing problem with time windows[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(8): 11528-11538.
[69] 胡尚民, 沈惠璋. 基于强化学习的电动车路径优化研究[J]. 计算机应用研究, 2020, 37(11): 3232-3235.
HU S M, SHEN H Z. Research on electric vehicle routing problem based on reinforcement learning[J]. Application Research of Computers, 2020, 37(11): 3232-3235
[70] SOLOMON M M. Algorithms for the vehicle-routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2): 254-265.
[71] 项寅. 考虑产业布局和用户满意度的氢能源汽车加氢网络优化模型[J]. 中国管理科学, 2023, 31(5): 164-175.
XIANG Y. Hydrogenation infrastructure network optimization considering industrial layout and customer satisfaction[J]. Chinese Journal of Management Science, 2023, 31(5): 164-175.
[72] 杨笑笑, 柯琳, 陈智斌. 深度强化学习求解车辆路径问题的研究综述[J]. 计算机工程与应用, 2023, 59(5): 1-13.
YANG X X, KE L, CHEN Z B. Review of deep reinforcement learning model research on vehicle routing problems[J]. Computer Engineering and Applications, 2023, 59(5): 1-13.
[73] KUCUKOGLU I, DEWIL R, CATTRYSSE D. The electric vehicle routing problem and its variations: a literature review[J]. Computers and Industrial Engineering, 2021, 161: 107650.
[74] YE C, HE W, CHEN H. Electric vehicle routing models and solution algorithms in logistics distribution: a systematic review[J]. Environmental Science and Pollution Research, 2022, 29: 57067-57090.