考虑绕行特征的电动汽车快速充电站选址问题及自适应遗传算法

doi:10.12005/orms.2017.0002

运筹与管理 ›› 2017, Vol. 26 ›› Issue (1): 8-17.DOI: 10.12005/orms.2017.0002

考虑绕行特征的电动汽车快速充电站选址问题及自适应遗传算法

陆坚毅, 杨超, 揭婉晨

华中科技大学管理学院,湖北武汉430074

收稿日期:2015-06-02 出版日期:2017-01-20
作者简介:陆坚毅(1986-),男,浙江温州人,博士研究生,研究方向为网络优化与决策。
基金资助:
国家自然科学基金国际交流重大项目资助(71320107001);中央高校基本科研业务专项资金资助(HUST:2013QN101,2013ZZGH028)

An Adaptive-self Genetic Algorithm for Solving Electric Vehicle FastRecharging Location Problem with Detour Characteristic

LU Jian-yi, YANG Chao, JIE Wan-chen

School of Management, Huazhong University of Science and Technology, Wuhan 430074, China

Received:2015-06-02 Online:2017-01-20

摘要/Abstract

摘要： 快速充电站选址是电动汽车运营的重要内容之一。本文考虑电动汽车用户会通过绕行一定距离对车辆进行充电这一特征,建立了一个以电动汽车快速充电站建站成本和旅客整体绕行成本之和最小的双层整数规划模型。本文首先给出了用于生成绕行路径集合的A^*算法,然后设计了一种包含局部迭代搜索的自适应遗传算法对该模型进行求解。为了测试算法性能,通过两个不同规模的算例图与已有求解FPLM问题的遗传算法进行了比较,数值试验部分证明了算法的正确性和有效性。最后引入浙江省的高速路网图,从建站成本和截流量两方面对电池续航里程带来的影响进行了相关的灵敏度分析。

关键词: 电动汽车, 快速充电站选址问题, 绕行成本, 自适应遗传算法, A^*算法

Abstract: Fast recharging station location is one of the most important aspects in electric vehicle operations management. Considering the fact that the electric vehicle users will detour from their shortest paths to refuel the vehicles, this paper studies a battery fast recharging stations location problem and builds a bilevel integer programming model to minimize the sum of building cost and deviation cost. Firstly, an A-Star algorithm is presented to generate the path sets of all OD pairs, and then an adaptive-self genetic algorithm(AGA)including local iterative search is proposed to solve this problem.Compared with genetic algorithm(GA)in two networks with different size, simulation results indicate that AGA is effective especially in the large network. Furthermore, using the ZheJiang Province as the network, this paper also analyzes the impact of battery’s driving range on building cost and intercepting value.

Key words: electric vehicle, fast recharging station location problem, detour cost, adaptive-self genetic algorithm, A-star algorithm

中图分类号:

F542

陆坚毅, 杨超, 揭婉晨. 考虑绕行特征的电动汽车快速充电站选址问题及自适应遗传算法[J]. 运筹与管理, 2017, 26(1): 8-17.

LU Jian-yi, YANG Chao, JIE Wan-chen. An Adaptive-self Genetic Algorithm for Solving Electric Vehicle FastRecharging Location Problem with Detour Characteristic[J]. Operations Research and Management Science, 2017, 26(1): 8-17.

参考文献

[1]国家发展改革委员会[Z].政府机关及公共机构购买新能源汽车实施方案,2014.
[2]北京市人民政府[Z].关于实施工作日高峰时段区域限行交通管理措施的通告,2015.
[3]Ogden J M. Developing an infrastructure for hydrogen vehicles: a southern california case study[J]. International Journal of Hydrogen Energy, 1999, 24(8): 709-730.
[4]Greene D L. Survey evidence on the importance of fuel availability to the choice of alternative fuels and vehicles[M]. DigitalCommons@ McMaster, 1998.
[5]Melendez M. Transitioning to a hydrogen future: learning from the alternative fuels experience[M]. National Renewable Energy Laboratory, 2006.
[6]Melaina M W. Initiating hydrogen infrastructures: preliminary analysis of a sufficient number of initial hydrogen stations in the US[J]. International Journal of Hydrogen Energy, 2003, 28(7): 743-755.
[7]Hodgson M J. A Flow-capturing location-allocation model[J]. Geographical Analysis, 1990, 22(3): 270-279.
[8]Berman O, Larson R C, Fouska N. Optimal location of discretionary service facilities[J]. Transportation Science, 1992, 26(3): 201-211.
[9]Averbakh I, Berman O. Locating flow-capturing units on a network with multi-counting and diminishing returns to scale[J]. European Journal of Operational Research, 1996, 91(3): 495-506.
[10]Berman O, Bertsimas D, Larson R C. Locating discretionary service facilities, II: maximizing market size, minimizing inconvenience[J]. Operations Research, 1995, 43(4): 623-632.
[11]Kuby M, Lim S. The flow-refueling location problem for alternative-fuel vehicles[J]. Socio-Economic Planning Sciences, 2005, 39(2): 125-145.
[12]Lim S, Kuby M. Heuristic algorithms for siting alternative-fuel stations using the flow-refueling location model[J]. European Journal of Operational Research, 2010, 204(1): 51-61.
[13]Kim J G, Kuby M. The deviation-flow refueling location model for optimizing a network of refueling stations[J]. International Journal of Hydrogen Energy, 2012, 37(6): 5406-5420.
[14]Upchurch C, Kuby M, Lim S. A model for location of capacitated alternative-fuel stations[J]. Geographical Analysis, 2009, 41(1): 85-106.
[15]Wang Y W, Lin C C. Locating multiple types of recharging stations for battery-powered electric vehicle transport[J]. Transportation Research Part E: Logistics and Transportation Review, 2013, 58(C): 76-87.
[16]Kuby M, Lim S. Location of alternative-fuel stations using the flow-refueling location model and dispersion of candidate sites on arcs[J]. Networks and Spatial Economics, 2007, 7(2): 129-152.
[17]Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths[J]. Systems Science and Cybernetics, IEEE Transactions on, 1968, 4(2): 100-107.
[18]Deb K, Agrawal S. Understanding interactions among genetic algorithm parameters[J]. Foundations of Genetic Algorithms, 1999: 265-286.
[19]Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. Systems, Man and Cybernetics, IEEE Transactions on, 1994, 24(4): 656-667.
[20]罗耀波,孙延明,廖鹏.带退货和软时间窗的多仓库选址-路径问题研究[J].运筹与管理,2014,(5).DOI:doi:10.3969/j.issn.1007-3221.2014.05.012.

考虑绕行特征的电动汽车快速充电站选址问题及自适应遗传算法

An Adaptive-self Genetic Algorithm for Solving Electric Vehicle FastRecharging Location Problem with Detour Characteristic

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

[1]	邓友均, 穆云飞, 贾宏杰, 张永熙. 计及客户满意度的电动汽车物流配送路径规划与充放电管理[J]. 运筹与管理, 2021, 30(7): 136-145.
[2]	刘国山, 王敏, 张转霞. 基于时间窗延迟的资源约束项目调度双层优化研究[J]. 运筹与管理, 2021, 30(12): 6-12.
[3]	何亚伟, 董沛武, 陈翔. 基于路网的电动汽车快速充电站布局决策研究[J]. 运筹与管理, 2020, 29(5): 125-134.
[4]	史乐峰, 吕通. 计及网络效应的共享电动汽车租赁网络扩张特征分析与布局算法构建[J]. 运筹与管理, 2019, 28(6): 166-174.
[5]	刘建胜, 张有功, 熊峰, 胡颖聪. Flying-V型仓储布局货位分配优化方法研究[J]. 运筹与管理, 2019, 28(11): 27-33.
[6]	郭放, 杨珺, 杨超. 基于货物分类配送的电动汽车路径优化与换电策略研究[J]. 运筹与管理, 2018, 27(9): 33-44.
[7]	张鹏威, 李英. 考虑充电设施重入的电动汽车旅行商问题研究[J]. 运筹与管理, 2018, 27(2): 54-64.
[8]	邵路路, 杨珺, 杨超. 电动汽车的市场需求和环境影响:功能更新与政府补贴[J]. 运筹与管理, 2018, 27(1): 103-111.
[9]	韩煜东, 任瑞丽, 许茂增. 目的地充电站电动汽车充电设施优化配置[J]. 运筹与管理, 2017, 26(8): 76-84.
[10]	邵路路, 杨珺, 杨超. 考虑产品环境质量和消费者惯性的电动汽车供应链策略分析[J]. 运筹与管理, 2017, 26(8): 99-108.