考虑时间窗口的电动出租车路径规划研究

贾永基+郭文娟+郑瑶

摘 要：首先分析了电动出租车路径规划问题与传统燃油车路径规划问题的不同，根据电动汽车的特性以及出租车运营模式的特点，建立了考虑时间窗口的电动出租车路径规划问题的混合整数规划模型；然后采用遗传算法求解该模型，仿真测试结果表明，遗传算法是求解此类问题的有效方法。

关键词：电动出租车；时间窗口；车辆路径问题；遗传算法

Abstract： Firstly， the paper analyzes the difference between electric taxi routing problem and traditional fuel vehicle routing problem. Based on the characteristics of electric vehicles and taxi operating mode， a hybrid integer programming model of electric taxi routing problem with time windows is established. Then， the genetic algorithm is used to solve the model. The simulation results show that the genetic algorithm is an effective method to solve the problem.

Key words： electric taxi； time window； vehicle routing problem； genetic algorithm

引 言

随着汽车工业的迅速发展，其在造福人类的同时也带来了很大的弊端，燃油汽车造成的能源紧缺、环境污染、城市交通等问题日益严重。为了缓解能源危机和环境污染的压力，在政府的大力支持下，很多出租车公司将电动汽车引入到出租车运营中。然而，电动出租车续航里程短、充电时间长的缺点，影响了电动出租车的广泛使用。考虑到电动出租车的规模效应，出租车公司往往采用换电模式而不是充电模式。换电模式虽然初期投资巨大，但是换电时间相比充电时间要短得多，一方面有利于提高电动出租车的使用率，另一方面可以采用夜晚的低峰时段对电池进行充电，从而延长电池寿命、降低电动出租车的使用成本。由于电动出租车路径规划问题需要考虑电动汽车的换电站位置和换电时间等因素，对传统车辆路径规划理论有很大的冲击[1]，不能直接将传统车辆路径规划理论应用到电动出租车路径规划中。为保证服务质量，提高客户满意度，需要对电动出租车行驶路径进行有效规划。

当前，越来越多的国内外学者开始研究电动汽车路径规划问题。文献[2]有关电动汽车路径规划问题给出两个模型——能源最优化路径模型及距离最优化模型，分析了这两个模型的优缺点：能源最优化模型考虑了电动汽车制动时可以将动能转化为电能的特点，但该模型的数据较难收集，实际应用范围比较窄；距离最优化模型简化了电动汽车路径规划问题，并将该问题描述为带时间窗口的，目标函数为最小化旅途时间的装卸货问题。文献[3]将电动汽车应用在城市零担物流中，将电动汽车路径规划问题简化为带能力约束与时间窗口约束的问题。文献[4]研究了电动汽车在城市交通网络中的应用，构建了总行驶距离最短的优化模型，并采用遗传算法求解此问题，仿真测试表明遗传算法可以求解出该问题的最佳配置网络。文献[5]提出了采用电动汽车作为最后一英里的运输，考虑了电动汽车充电站位置以及客户时间窗口，建立了电动汽车路径规划问题的混合整数规划模型，提出了一种变领域搜索算法来解决此类问题。文献[6]将准时化生产的思想应用到电动汽车城市物流配送中，并将电动汽车在城市物流的配送问题简化为带软时间窗口的装卸货问题。文献[7]研究了考虑电动汽车充电时间以及客户时间窗口的电动汽车路径规划问题，建立了数学模型，并提出了一种基于变邻域搜索和禁忌搜索相结合的混合启发式算法。

电动出租车路径规划问题属于非确定性多项式组合难题，很难用精确式算法进行大规模求解，多采用启发式算法求得满意解。遗传算法是一种借鉴生物界的进化规律演化而来的随机搜索方法，具有计算时间短、鲁棒性好、精度高等优点[8]，故本文采用遗传算法来求解电动出租车路径规划问题。

1 电动出租车路径规划问题的混合整数规划模型

1.1 问题描述与基本假设

电动出租车路径规划问题描述如下：当客户信息到达出租车调度中心后，调度中心进行调度，安排出租车为这些客户提供服务。每个客户信息有一个上车点位置、一个下车点位置以及时间窗口要求。电动出租车从车库出发，根据调度中心的安排，依次服务所分配的客户。当出租车在客户指定的上车点拉上客户之后，必须立即駛向该客户指定的下车点，而不能驶向其它位置。出租车到达上车点的时间需满足客户所指定的时间窗口，若提前到达则需等待并承担等待成本，若延迟到达则需承担惩罚成本。当服务完一个客户之后，调度中心要求电动出租车进行电池电量检查，并把检查结果反馈给调度中心。若该电动出租车服务完某个新客户后，剩余电量能保证该车辆到达车库进行电池更换，则把该新客户分配给该出租车；否则，出租车立即返回车库进行电池更换，然后继续服务客户。当电动出租车完成一天的工作之后，返回车库。

该问题的混合整数规划模型的基本假设如下：

（1）出租车开始服务客户时，电池都拥有最大电量；

（2）出租车到车库进行电池更换后，电池都拥有最大电量；

（3）电池耗电量与行驶距离成正比；

（4）电动出租车行驶速度恒定，不考虑交通拥堵等突发状况；

（5）出租车服务不允许拼车；

（6）忽略客户上下车时间。

1.2 决策变量与参数定义

假设o为车库；G为客户点集合，|G|为客户数量；K为车辆集合，|K|为车辆个数；i、j、k表示节点；S为客户点i的上车点位置，D为客户点i的下车点位置；N为所有节点集合N=G∪o∪S∪D；d表示节点i到j的距离；E为电动出租车满电状态时的最大行驶里程，E为电动出租车到达节点j时剩余电量所能行驶的里程；E为电动出租车离开节点i时的剩余电量所能行驶的里程；e表示客户点i的最早服务时刻；l表示客户点i的最晚服务时刻；t表示车辆k到达客户点i的时刻；ft为惩罚值函数；α为出租车行驶过程中的单位成本；β为更换电池的成本；p为出租车早到的单位时间惩罚值；q为出租车晚到的单位时间惩罚值；v表示电动出租车平均速度；X为0-1决策变量，当车辆k从客户点i到j时取值为1i≠j，否则为0；Y为0-1决策变量，当车辆k到车库o更换电池时取值为1，否则为0。

1.3 目标函数与约束条件

电动出租车路径规划模型的目标函数与约束条件如下：

其中：式（1）是目标函数，最小化电动出租车总运营成本，包括车辆行驶成本、电池更换成本和服务客户的时间惩罚成本；式（2）表示从车库出发的车辆数不超过|K|；式（3）表示车辆到达客户的上车点后，下一节点必定是该客户的下车点；式（4）表示车辆在离开车库后其电池为满电状态；式（5）表示电动出租车的里程约束；式（6）表示服务完客户后，电动出租车剩余电量所能行驶的里程要大于返回车库的行驶里程；式（7）表示时间约束，当X为1时，电动出租车抵达j的时间等于电动出租车到达i的时间加上从i行驶到j所花费的时间；当X为0时，不等式自然满足；式（8）表示违反客户时间窗口的惩罚成本。

2 基于遗传算法的模型求解算法

遗传算法是一种模拟自然界生物进化过程的一种随机搜索启发式算法，它不一定能找到最优解，却可以不断地寻找更优的解。遗传算法本身所具有的并行搜索能力、鲁棒性强、实现简单等诸多优点，使其在求解大规模组合优化问题时显示出了优越的性能。因此，本文使用遗传算法来求解上文提出的电动出租车路径规划问题。典型的遗传算法的基本流程如图1所示。

2.1 染色体编码与适应度函数

本文采用序数编码方式，即用序数1到n表示n个客户，0表示车库，则电动出租车路径规划问题的一个可行解可编码成长度为n+m的染色体：

其中δ表示第k辆车服务的第i个客户。这样的染色体结构可以理解为第k辆车从车库0出发，经过客户δ，δ，…，δ后回到车库0，形成1条子路径，总共形成包括m条子路径的完整路径。

本文选取模型的目标函数作为遗传算法的适用度函数。

2.2 遗传算子

（1）选择算子

本文采用轮盘赌选择方法进行染色体的选择。

（2）交叉算子

本文采用部分匹配交叉算子，首先从第一个父代染色体中随机选一个基因段作为待交叉基因段，然后将该基因段复制到子代染色体的相应位置，产生一个原始子代，接着删除第二个父代染色体中原始子代中已有的客户，得到原始子代所需要的其它客户的顺序，并按这个顺序将客户依次定位到原始子代的空缺位置上。

（3）变异算子

本文使用的变异算子，将随机选择的变异基因不是插入到一个随机产生的位置，而是将该基因插入到染色体的使得目标函数增加值最小的最优变异位置。

2.3 控制参数与停止条件

交叉算子与变异算子的作用效果受到交叉率和变异率的控制，要想得到遗传算法的最优性能，必须确定这些参数的最优设置，然而这些参数的具体选取往往与所求解的问题相关，只能根据经验或者实验来确定。

由于遗传算法具有较大的随机性，本文选择迭代次数作为算法的终止条件。

3 测试与分析

3.1 测试实例

本文选用的实验数据来自Solomon设计的VRPTW标准测试题库[9]，对测试实例做以下假设：仅有一个单一的车库，而且车辆类型都是一样的，每个客户都指定一个时间窗口，客户均匀分布于70×70的坐标平面上，车库位于坐标平面的中心位置（35，35）。有20个位于不同地点的客户，这些客户点的最早服务时间、最晚服务时间以及目的地均不相同。每位客户的上、下车点坐标以及时间窗口的数据如表1所示，其分布情况如图2所示，其中三角形表示车库位置，实心圆点表示客户上车点，菱形表示客户下车点。

3.2 测试结果分析

利用matlab 2012b编写遗传算法程序，设置出租车提前到达客户点的惩罚值p为0.5；延迟到达客户点的惩罚值q为1.5；出租车行驶过程中产生的成本α为8；更换电池产生的成本β为20；出租车最大电量所对应的最大行驶里程为60公里；交叉率为0.7，变异率为0.6，迭代次數为1 000，种群规模为500。

遗传算法优化结果与进化代数的关系如图3所示。从中可以看出，在迭代的初期，种群的适应度比较低，曲线处于陡峭的状态并且下降趋势明显；迭代达到500次以后，曲线下降趋势明显变慢，且波动非常不明显；迭代次数达到620次的时候，曲线已经几乎不再波动，说明已进化至最优解，此时的最优值为9 965.61，最优解为电动出租车需求数量为3，其最优行驶路线如表2所示。

4 结 论

本文主要针对城市当中的电动出租车预约接送客户的问题，进行合理的路径规划与建模研究。在电动出租车行驶过程中，需要考虑行驶路径是否最短，是否回车库进行电池更换，还需要考虑客户的时间需求，尽可能的不违背客户时间等因素。

本文首先建立了电动出租车路径规划问题的混合整数规划模型，目标函数为最小化出租车运营总成本。然后，编写了遗传算法程序用于求解该问题，并设计了仿真测试的实例。测试结果表明，遗传算法是求解此类电动出租车路径规划问题的有效算法。

參考文献：

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

[2] Touati-Moungla N， Jost V. Combinatorial optimization for electric vehicles management[J]. 能源与动力工程（英文版），2012（5）：738-743.

[3] Conrad RG， Figliozzi MA. The Recharging Vehicle Routing Problem[C] // Proceedings of the 2011 Industrial Engineering Research Conference， Reno， USA， 2011.

[4] Taniguchi E， Kawakatsu S， Tsuji H. New cooperative system using electric vans for urban freight transport[C] // International Conference on Urban Transport， Greenville， SC， USA， 2010.

[5] Schneider M， Stenger A， Goeke D. The Electric Vehicle Routing Problem with Time Windows and Recharging Stations[J]. Transportation Science， 2014，22（8）：1-22.

[6] Bhusiria N， Qureshia AG， Taniguchia E. Application of the Just-In-Time Concept in Urban Freight Transport[J]. Procedia-Social and Behavioral Sciences， 2014，125（3）：171-185.

[7] Eisner J， Funke S， Storandt S. Optimal route planning for electric vehicles in large networks[C] // The Twenty-Fifth AAAI Conference on Artificial Intelligence， Stuttgart， Germany， 2011.

[8] 马洪坤，杨伟. 基于遗传蚁群算法的带时间窗多车场车辆调度问题[J]. 西华大学学报（自然科学版），2016，35（3）：31-35.

[9] 佚名. VRPTW Benchmark Problems[EB/OL]. （2005-03-24）[2016-11-25]. http：//w.cba.neu.edu/～msolomon/problems.htm.