﻿ 带充电设施的电动班车路径规划问题研究 Research on Electric Shuttle Bus Routing Problem with Recharging Station

Management Science and Engineering
Vol.05 No.04(2016), Article ID:19245,8 pages
10.12677/MSE.2016.54016

Research on Electric Shuttle Bus Routing Problem with Recharging Station

Fangfang Xing, Yongji Jia, Qi Jiang, Yao Zheng

Glorious Sun School of Business and Management, Donghua University, Shanghai

Received: Nov. 25th, 2016; accepted: Dec. 9th, 2016; published: Dec. 15th, 2016

ABSTRACT

According to the actual situation of company shuttle bus, considering the limited range of electric shuttle bus and the different customers’ reservation time windows, a mixed integer programming model for the electric shuttle bus routing problem with recharging station is constructed. By this model, the operation time and the utilization efficiency of the electric shuttle bus are improved. Then, a genetic algorithm is proposed to solve this model, and test results demonstrate that the algorithm proposed in this paper is efficient.

Keywords:Recharging Station, Electric Vehicle, Vehicle Routing Problem, Genetic Algorithm

1. 引言

2. 电动班车路径规划模型

2.1. 问题描述与基本假设

1) 车辆从停车场出发或到充电设施充电之后，电池都拥有最大电量；

2) 电动班车车辆类型相同，拥有相同的载客能力和电池容量；

3) 车辆耗电系数固定，耗电量与行驶距离成正比；

4) 充电系数固定，车辆在充电设施处的充电时间与到达充电设施时的剩余电量线性相关；

5) 车辆行驶速度恒定。

2.2. 决策变量与参数定义

2.3. 目标函数与约束条件

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

3. 基于遗传算法的模型求解算法

3.1. 染色体编码

3.2. 适用度函数和选择操作

(14)

(15)

3.3. 交叉操作和变异操作

(16)

(17)

(18)

4. 测试与分析

4.1. 测试实例

4.2. 测试结果分析

Table 1. Data of test instance

Figure 1. Curve: cost of change after 500 times evolution

Figure 2. Curve: cost of change after 150 times evolution

Figure 3. Chart: electric shuttle bus routing

5. 结论

Research on Electric Shuttle Bus Routing Problem with Recharging Station[J]. 管理科学与工程, 2016, 05(04): 149-156. http://dx.doi.org/10.12677/MSE.2016.54016

1. 1. 欧雯要, 叶瑞克, 鲍健强. 电动汽车的节能减碳价值研究[J]. 未来与发展, 2012, 2(5): 36-40.

2. 2. Samanta, S. and Jha, M.K. (2011) Multi Depot Probabilistic Vehicle Routing Problems with a Time Window: Theory, Solution and Application. International Journal of Operations Research & Information Systems, 2, 40-64. https://doi.org/10.4018/joris.2011040103

3. 3. Schneiderm, M., Stengera, A. and Goeke, D. (2014) The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations. Transportation Science, 48, 500-520. https://doi.org/10.1287/trsc.2013.0490

4. 4. Goeke, D. and Schneider, M. (2015) Routing a Mixed Fleet of Electric and Conventional Vehicles. European Journal of Operational Research, 245, 81-99. https://doi.org/10.1016/j.ejor.2015.01.049

5. 5. Wang, H. and Shen, J. (2007) Heuristic Approaches for Solving Transit Vehicle Scheduling Problem with Route and Fueling Time Constraints. Applied Mathematics & Computation, 190, 1237-1249. https://doi.org/10.1016/j.amc.2007.02.141

6. 6. Li, J.Q. (2014) Transit Bus Scheduling with Limited Energy. Transportation Science, 48, 521-539. https://doi.org/10.1287/trsc.2013.0468

7. 7. 刘华旭. 基于电动汽车技术特征的共同配送调度优化研究[D]: [硕士学位论文]. 北京: 北京交通大学, 2012.

8. 8. 杨珺, 冯鹏祥, 孙昊, 等. 电动汽车物流配送系统的换电站选址与路径优化问题研究[J]. 中国管理科学, 2015, 23(9): 87-96.

9. 9. 玄光男, 程润伟. 遗传算法与工程优化[M]. 北京: 清华大学出版社, 2004.

10. 10. 郁磊, 史峰, 王辉, 胡斐, 等. MATLAB 智能算法30个案例分析[M]. 北京: 北京航空航天大学出版社, 2015.

11. 11. VRPTW Benchmark Problems. http://w.cba.neu.edu/~msolomon/problems.htm