新能源移动充电车路径优化问题研究

doi:10.12005/orms.2020.0029

运筹与管理 ›› 2020, Vol. 29 ›› Issue (2): 12-18.DOI: 10.12005/orms.2020.0029

新能源移动充电车路径优化问题研究

陈萍¹, 董文哲², 于信尧¹

1. 南开大学商学院,天津 300071;
2. 伦敦大学巴特莱特学院,伦敦 WC1E 6BT

收稿日期:2018-08-21 出版日期:2020-02-25
作者简介:陈萍(1981-), 女, 山东人, 博士, 讲师, 研究方向:城市物流, 车辆优化调度;董文哲(1996-), 女, 河北人, 硕士生, 研究方向:城市物流, 车辆优化调度;于信尧(1996-), 男, 辽宁人, 硕士生, 研究方向:车辆优化调度, 信息系统。
基金资助:
国家自然科学基金青年科学基金项目(71701107);教育部人文社会科学青年基金项目(13YJC630010)

Studyon Routing Problemfor New Energy Mobile Charging Vehicles

CHEN Ping¹, DONGWen-zhe², YU Xin-yao¹

1. Business School, Nankai Univeristy, Tianjin 300071, China;
2. Bartlett School, University College London, London WC1E 6BT, UK

Received:2018-08-21 Online:2020-02-25

摘要/Abstract

摘要： 在绿色城市背景下,新能源汽车的数量快速增长,现有公共充电设施的不完善使得移动充电服务应运而生。投入运营成本较高而利润低成为阻碍移动充电业务运营的瓶颈之一,如何通过科学合理的调度提高平台利润成为重要问题。本文研究了移动充电车队的调度和路径优化问题,以平台最大收益为目标,综合考虑顾客软时间窗、移动电池容量以及充电车续航里程等约束,建立数学规划模型;设计了一种最大最小蚁群算法,并通过数值实验验证了模型的合理性和算法的有效性,为移动充电企业运营提供决策参考。

关键词: 新能源车, 路径优化, 软时间窗, 电池最大容量, 续航里程, 最大最小蚁群算法

Abstract: Against the background of green city, the number of electricvehicles has increased sharply. However, the charging infrastructure is notsufficient, and thus mobile charging industryappears.However, these companies are not profitableas expected. The main problem they are facing is the conflict between high operating cost and low profits. Optimizing the decision making of mobile charging vehicle routing becomes a critical issue. This study focuses on mobile charging vehicle routing problem, which aims to maximize the total profit under the constraints of soft time windows, battery capacity and endurance mileage. We formulate this problem. In addition, to solve this problem, a max-min ant colony algorithm is presented. Computational results demonstrate the effectiveness and efficiency of the model and algorithm. This paper also provides some managerial insights for mobile charging companies operation.

Key words: new energy vehicle, routing, Soft time windows, battery capacity, endurance mileage, max-min ant system

中图分类号:

O224

陈萍, 董文哲, 于信尧. 新能源移动充电车路径优化问题研究[J]. 运筹与管理, 2020, 29(2): 12-18.

CHEN Ping, DONGWen-zhe, YU Xin-yao. Studyon Routing Problemfor New Energy Mobile Charging Vehicles[J]. Operations Research and Management Science, 2020, 29(2): 12-18.

参考文献

[1] 新浪汽车.公安部:17年底新能源汽车保有量达153万辆. http://auto.sina.com.cn/news/2018-01-16/detail-ifyqqieu6778118.shtml. 2018-01-16.
[2] Chao I, Golden B, Wasil E. The team orienteering problem[J]. European Journal Operational Research, 1996, 88: 464-474.
[3] Tang H, Miller-Hooks E. A tabu search heuristic for the team orienteering problem[J]. Computer and Operations Research, 2005, 32: 1379-1407.
[4] Vansteenwegena P, Souffriaua W. Iterated local search for the team orienteering problem with time windows[J]. Computers &Operations Research, 2009(36): 3281-3290.
[5] Archetti C, Hertz A, Speranza M. Metaheuristics for the team orienteering problem[J]. Journal of Heuristics, 2007, 13: 49-76.
[6] 柯良军,尚可,冯祖仁.动态团队定向问题的模型及其优化算法[J].西安交通大学学报,2011,45(6):1-7.
[7] Archetti C, Feillet D, Hertz A, Speranza M. The capacitated team orienteering and profitable tour problem[J]. Jounal of the Operational Research Society, 2008, 60 (6): 831-842.
[8] Luo Z, Cheang B, Lim A, Zhu W B. An adaptive ejection pool with toggle-rule diversification approach[J]. European Journal of Operational Research, 2013(229): 673-682.
[9] Vidal T, Maculan N, et al. Large neighborhoods with implicit customer selection for vehicle routing problem with profits[J]. Transportation Science, 2016(50): 720-734.
[10] Righini G, Salani M. Dynamic programming for the orienteering problem with time windows[R]. Crema, Italy: University degli Study Milano, 2006. 91-93.
[11] Montemanni R, Gambardella L. Ant colony system for team orienteering problems with time windows[J]. Foundations of computing and Decision Sciences, 2009, 34 (4): 287-306.
[12] Ke L, Archetti C, Feng Z. Ants can solve the team orienteering problem[J]. Computers and Industrial Engineering, 2008, 54 (3): 648-665.
[13] Souffriau W, Vansteenwegen P, Berghe G V, Van Oudheusden D. The multi constraint team orienteering problem with multiple time windows[J]. Transportation Science, 2013, 47(1): 53-63.
[14] Tricoire F, Romauch M, Doerner K, Hartl R. Heuristics for the multi-period orienteering problem with multiple time windows[J]. Computers and Operations Research, 2010, 37(2): 351-367.
[15] Mei Y, Salim F D, Li X. Efficient meta-heuristics for the multi-objective time-dependent orienteering problem[J]. European Journal of Operational Research, 2016, 254(2): 443-457.
[16] Sun P, Veelenturf L P, Dabia S, et al. The time-dependent capacitated profitable tour problem with time windows and precedence constraints[J]. European Journal of Operational Research, 2017, 264(3): 1058-1073.
[17] Golden B, Levy L, Vohra R. The orienteering problem[J]. Naval Research Logistics, 1987, 34: 307-318.
[18] 陈萍,黄厚宽,董兴业.求解卸装一体化车辆路径问题的混合启发式算法[J].计算机学报,2008,31(4):1-9.
[19] 张鹏威,李英.考虑充电设施重入的电动汽车旅行商问题研究[J].运筹与管理,2018,27(2):54-64.
[20] 王道平,徐展,杨岑.基于两阶段启发式算法的物流配送选址-路径问题研究[J].运筹与管理,2017,26(4):70-75.
[21] 王书勤,黄茜.军事定向越野路径优化问题建模及混合蚁群算法求解[J].运筹与管理,2018,27(4):105-111.

新能源移动充电车路径优化问题研究

Studyon Routing Problemfor New Energy Mobile Charging Vehicles

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics

[1]	丁肇炜, 杨建华, 王艾, 王欣. 面向突发事件的安保巡逻选址-路径优化研究[J]. 运筹与管理, 2021, 30(8): 1-6.
[2]	陈伟, 张玉林. “仓店一体化”模式下订单拣选与配送集成调度优化[J]. 运筹与管理, 2021, 30(7): 16-22.
[3]	原逸超, 石岿然. 考虑策略型消费者和退货的零售商降价促销决策研究[J]. 运筹与管理, 2020, 29(7): 58-63.
[4]	林婉妮, 王诺, 沈铭棋, 宋云婷. 基于海空协同的群岛救援方案优化模型及算法[J]. 运筹与管理, 2020, 29(5): 1-8.
[5]	任剑锋, 叶春明, 杨枫. 带时间窗的车间搬运机器人路径优化建模及算法研究[J]. 运筹与管理, 2020, 29(5): 52-60.
[6]	张建同, 丁烨. 变邻域模拟退火算法求解速度时变的VRPTW问题[J]. 运筹与管理, 2019, 28(11): 77-84.
[7]	刘艳秋,徐世达,蔡超. 部分联合运输策略下的物流车辆路径优化问题研究[J]. 运筹与管理, 2018, 27(8): 10-19.
[8]	张梦颖, 秦进, 梁樑. 包含随机客户的选择性旅行商问题建模及求解[J]. 运筹与管理, 2018, 27(5): 8-14.
[9]	王书勤, 黄茜. 军事定向越野路径优化问题建模及混合蚁群算法求解[J]. 运筹与管理, 2018, 27(4): 105-111.
[10]	王道平, 徐展, 杨岑. 基于两阶段启发式算法的物流配送选址-路径问题研究[J]. 运筹与管理, 2017, 26(4): 70-75.
[11]	王晶, 曲冲冲, 易显强. 道路修复条件下灾后应急资源配送LRP研究[J]. 运筹与管理, 2017, 26(12): 77-82.
[12]	史丽萍, 刘强, 贾亚男, 于心齐. 基于Projection Pursuit-RAGA-NK-GERT的质量绩效提升路径优化——以组织质量特异性免疫和产品生命周期为主导逻辑的解释框架[J]. 运筹与管理, 2015, 24(4): 188-197.
[13]	罗耀波, 孙延明, 廖鹏. 带退货和软时间窗的多仓库选址-路径问题研究[J]. 运筹与管理, 2014, 23(5): 78-85.
[14]	胡少龙, 胡志华, 曹杨. 基于多候选储位的存取路径优化问题研究[J]. 运筹与管理, 2013, 22(5): 111-116.