1. 引言
随着汽车行业的高速发展，全球汽车的保有量不断增加，燃油汽车带来的能源紧缺、环境污染、城市交通等问题日益凸显。为了缓解城市交通压力、保护环境，很多公司会在早晚派送班车接送员工上下班，公司员工可以选择在合适的班车站点等待班车。但经常出现班车抵达不及时、某一时刻班次人员过多或过少的状况，不仅会造成员工等待时间过长、不能按时抵达公司等问题，在一定程度上也会导致班车利用率过低。因此，对公司班车行驶路线进行优化，可以在较大程度上解决此问题。
在政策的支持和引领下，很多公司把电动汽车引入到班车运营中，以进一步降低能耗、保护环境。电动汽车因其清洁、节能等显著优势，逐渐成为重要的交通工具 [1] 。在北京、上海、广州等城市的公共交通中，以电动汽车为代表的新能源公交车都得到了大规模示范运营。然而，电动汽车由于续航里程短，在服务一部分客户后需要到充电设施进行充电，传统的车辆路径规划理论不再适用于电动汽车路径规划问题。
目前，一些学者已经开始对电动汽车路径规划问题展开研究。Samanta S等 [2] 提出了带时间窗口的电动汽车和传统燃油车的混合车队的车辆路径规划模型，但并没有真正在模型中加入充电设施。Schneider M等 [3] 研究了成本最优的电动汽车路径问题，考虑了容量限制、客户时间窗口和充电时间，并采用禁忌搜索和变邻域相结合的混合启发式算法进行求解。Geoke D [4] 提出了求解大规模混合车队带时间窗口路径规划问题的邻域搜索算法，比较了不同目标函数下解的变化以及电动车辆的调度成本。Wang H等 [5] 研究了电动公交车辆的调度问题，通过对以往公交车的行驶路径进行分析，提出了总空闲时间最小的目标函数，给出了电动公交车出发时刻表及优化后的行驶路径。Li J Q [6] 研究了可更换电池或快速充电的电动公交车调度问题，提出了分支定价算法和基于列生成和局部搜索的启发式算法来求解该问题。刘华旭 [7] 研究了基于电动汽车技术的共同配送调度优化问题，考虑电动汽车续驶时间有限和充电时间约束，并采用蚁群算法求解。杨珺等 [8] 研究了带容量限制的电动汽车电池换电站选址与路径优化问题，同时确定电池交换站的选址策略和电动汽车的最优行驶路径，并设计了求解该问题的禁忌搜索算法，与CPLEX求解结果的比较结果表明该算法更加有效。
本文对带充电设施的电动班车路径规划问题展开研究，首先在第二节提出了该问题的混合整数规划模型，以优化电动班车的行驶路径，然后在第三节提出了求解该模型的遗传算法，在第四节对一个算例进行了仿真测试和分析，最后一节是结论。
2. 电动班车路径规划模型
2.1. 问题描述与基本假设
电动班车路径规划问题的典型描述如下：
电动汽车从停车场出发，将各个客户点的员工送至公司。班车到达客户点的时间需满足客户时间窗口，提前到达需等待并承担等待成本，延迟到达需承担惩罚成本。班车在运行过程中由于电池容量有限，当出现剩余电量不足以支撑车辆到达下一个客户点时，需要立即到充电设施充电，然后继续服务下一个客户，直至服务完所有客户，最后返回停车场。
电动汽车路径规划问题的基本假设如下：
1) 车辆从停车场出发或到充电设施充电之后，电池都拥有最大电量；
2) 电动班车车辆类型相同，拥有相同的载客能力和电池容量；
3) 车辆耗电系数固定，耗电量与行驶距离成正比；
4) 充电系数固定，车辆在充电设施处的充电时间与到达充电设施时的剩余电量线性相关；
5) 车辆行驶速度恒定。
2.2. 决策变量与参数定义
假设0为停车场；
为每个服务点乘客数量集合；
为服务点集合；
为各服务点要求送达的时间集合；
为公司；
为充电设施；
表示单个服务点，
，
代表出发点；
为车辆集合，
；
表示服务点
到
的距离，其中
；
表示车辆从服务点
到
的时间；
为车辆的最大载客量；
为车辆最大行驶里程(对应电池最大容量)；
表示车辆续驶里程(对应电池剩余电量)；
表示点
允许的最早服务时刻；
表示点
要求的最晚服务时刻；
表示车辆
到达服务点
的时刻，其中
；
为各点乘客要求的服务时间；
表示完成点
员工接送服务所需的时间；
为0-1决策变量，当车辆
从服务点
到
时取值为1(
)，否则为0；
为0-1决策变量，经过充电设施
时取值为1，否则为0。
2.3. 目标函数与约束条件
电动班车路径规划模型的目标函数与约束条件如下：
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
其中，式(1)表示行驶总路程最小，为目标函数；式(2)表示从停车场出发的车辆数不超过
；式(3)和(4)表示访问的唯一性约束，即一个预约服务点只能被一辆车服务一次且仅一次；式(5)表示每辆车从停车场出发，并在结束所有任务后返回停车场；式(6)表示每辆车载客总数量不超过其最大载客量；式(7)到(8)表示电动班车的时间窗约束，式(7)表示班车抵达某点的时刻要不大于该点的最早服务时刻，式(8)表示整个服务的结束时刻应早于最晚服务时刻，否则需要增加惩罚因子；式(9)表示车辆的剩余电量与行驶路程的关系，即如果车辆从点
驶入点
，那么车辆到达节点
时剩余电量等于离开节点
时剩余电量减去从节点
行驶到节点
消耗的电量；式(10)和(11)分别表示车辆在离开停车场和经过充电设施充电后其电量为满电；式(12)表示车辆在任意节点电量非负；式(13)表示0-1决策变量。
3. 基于遗传算法的模型求解算法
遗传算法是一类借鉴生物界的进化规律演化而来的随机搜索方法，通过对种群重复不断地进行选择、交叉、变异等基本遗传操作，以进化过程中得到的最大适应度个体作为最优解输出 [9] 。其中，遗传算法通过不断迭代搜索，最终得到了整个种群中最优的染色体相对应的车辆行驶路径，该车辆行驶路径即为整个问题的相对最优解，从而完成了带时间窗和容量限制的电动班车路径规划问题的路径寻优过程。
3.1. 染色体编码
假设k辆车用于服务n个客户点，染色体编码为(
)，其中0代表停车场，两个0之间的自然数序列表示一条子路径。
例如，使用3辆车服务8个客户点，9表示公司，得到的遗传编码为027390516904890，即表示第一辆车从停车场出发，依次到达客户点2,7,3后到达公司9，形成子路径1；同理，第二辆车从出发点出发后，依次到达客户点5,1,6后集中到达公司9，最后又回到出发点，形成子路径2；而第三辆车从出发点出发，依次到达客户点4,8之后集中到达公司9，最后同样回到出发点，形成子路径3。因此，对应的三辆子路径为：
子路径1：0→2→7→3→9→0
子路径2：0→5→1→6→9→0
子路径3：0→4→8→9→0
本文问题中所需派出的车辆的数量事先并未确定，因此在编码中的路径分隔符0可以直观地将各个路径分隔开来，从而判断派出的车辆的数量。
3.2. 适用度函数和选择操作
电动班车路径规划问题的优化目标是要找到总行驶距离最小的行驶路线，因此，本文将目标函数作为遗传算法的适用度函数
(14)
选择操作采用遗传算法的标准选择方法，即轮盘赌法，选择生命力强的个体繁殖后代产生新的种群，这是一种基于适应度比例的选择策略，假设
为种群数目，
为某个个体
的适应度值，则该个体被选择的概率为
(15)
3.3. 交叉操作和变异操作
本文研究的基于电动班车路径规划问题采用了客户点排列的自然数编码方式，所以交叉算法采用实数编码交叉方法。从种群中选出适用度强的个体，即行驶路程最短的个体，交叉后产生2个新的个体。根据算法设置的交叉概率
决定是否进行交叉，在
范围内产生随机数
，如果随机数
的值小于交叉概率
，则进行交叉操作。第
个染色体
和第
个染色体
在第
个位置的交叉方法 [10] 为
(16)
其中
是
之间的随机数。
同样，按照设置的变异概率
决定个体是否进行变异操作，在
范围内产生随机数，如果随机数小于变异概率，选择个体中的一个染色体进行变异，以产生更加优秀的个体。第
个个体的第
个染色体
进行变异操作的方法 [10] 为
(17)
(18)
其中，
是基因
的上界，
是基因
的下界；
为一个随机数；
是当前迭代次数；
是最大迭代次数；
为
之间的随机数。
4. 测试与分析
4.1. 测试实例
本文中的实验数据选用Solomon设计的车辆路径规划问题标准测试库 [11] ，对测试实例做以下假设：客户要求“最早服务时间 + 要求服务时间 
最晚到达时间”，同时应当满足每个服务点的预约员工数量应小于电动班车的总载客量。设停车场有4辆电动班车从停车场出发，需要服务17个客户点，这些客户点的最早服务时间、最晚到达公司时间及服务时间都不同，电动班车的终点为公司，电动班车完成任务后返回停车场，区域内有一个充电站。
假设电动班车载客量为20人，车辆的最大行驶里程为60 km，同时设定了车辆超过时间窗到达服务点的单位时间惩罚成本为30，单位距离成本为1，单位时间等待成本为20。停车场、充电站和客户点信息的具体数据如表1所示。
4.2. 测试结果分析
利用matlab 2014a编写本文提出的求解电动班车路径规划实例的基于遗传算法的模型求解算法，设置交叉概率为0.7，变异概率为0.6。为了使测试实例得到的路径规划结果更具科学性和有效性，对遗传算法中迭代次数和种群规模设置不同的参数。当迭代次数为500次时，设置种群规模为1000；当迭代次数150次时，设置种群规模为500。
对于上述两种情况分别进行20次测试后的求解结果如图1和图2所示。从中可以看出，当迭代次数为500、种群规模为1000时，测试得到平均最低总成本为292.0759 (波动非常小)；而迭代次数为150次，种群规模为500时，测试得到平均最低总成本超过300 (波动非常大)。
综合上述情况，在求解过程中，尽管迭代次数500次、种群规模为1000时求解过程花费的时间稍长，
Figure 1. Curve: cost of change after 500 times evolution
图1. 进化500次成本变化曲线
但其20次试验中得到的结果非常稳定，波动极小，其求解效果优于迭代次数为150、种群规模为500的情况。
最优实验结果如图3所示，最佳方案是使用4辆电动班车进行服务。其中，停车场为4辆电动班车的出发点和完成所有服务后返回的终点；1~17为客户需求点，18为公司。客户需求点分配及电动班车服务客户点顺序的描述如下：
路径1：停车场→需求点9→需求点8→需求点16→需求点13→需求点14→公司→停车场，抵达公
Figure 2. Curve: cost of change after 150 times evolution
图2. 进化150次成本变化曲线
Figure 3. Chart: electric shuttle bus routing
图3. 电动班车路径规划图
司时载客量为18人，在需求点14处需充电；
路径2：停车场→需求点15→需求点1→需求点17→需求点7→需求点12→公司→停车场，抵达公司时载客量为20人；
路径3：停车场→需求点2→需求点4→需求点11→公司→停车场，抵达公司时载客量为16人；
路径4：停车场→需求点6→需求点5→需求点10→需求点3→公司→停车场，抵达公司时车辆载客量为19人。
5. 结论
针对公共交通中较为普遍的公司班车服务中遇到的一些问题，将电动汽车引入班车服务以替代传统燃油班车，以缓解城市交通压力，并节约能源。考虑到电动汽车续驶里程有限，需要在服务中到充电设施充电的特点，如何规划班车行驶路线、确定班车充电策略，就成为电动班车路径规划中的关键。
本文首先提出了带充电设施的电动班车路径规划问题的混合整数规划数学模型，既考虑了电动班车的最大载客量、客户时间窗口等传统约束，又考虑了电动班车续航里程、充电策略等电动汽车特有的约束。该模型能有效提高电动班车的使用效率。然后，提出了求解该模型的遗传算法，并进行了仿真测试。测试结果表明，本文提出的遗传算法是求解此类电动班车路径规划问题的有效算法。
基金项目
中央高校基本科研业务费专项资金(16D110815)。