曹卓 王鑫鑫 徐仟 马云峰

摘  要：考虑到电动车在当今物流配送环节中扮演着愈发重要的角色，电动车物流配送过程中充电站位置选择、充电时机选择以及相应路径规划越来越成为行业内备受关注的问题。文章基于车联网对电动车物流配送路径优化进行研究。首先，借助车联网技术获取实时交通路况以及充电站相关信息，提出车联网情境下基于排队论的充电排队等待时间预测模型。其次，考虑时间、路径选择、电量及载重约束，构建以参与配送车辆的配送时间成本、耗电成本以及时间窗惩罚成本之和最优为目标的电动车物流配送路径优化模型。最后通过算例验证模型的可行性以及算法的有效性。实验结果表明相较于最迟充电策略下的电动车物流配送路径优化模型，基于车联网的电动车物流配送路径优化模型具有显著优势。

关键词：车联网;物流配送;路径优化;充电选择

中图分类号：F253    文献标志码：A    DOI：10.13714/j.cnki.1002-3100.2023.15.006

Abstract： Considering that electric vehicles play an increasingly important role in today's logistics distribution， the selection of charging station location， charging timing and the corresponding path planning in the logistics distribution of electric vehicles has become an increasingly concerned issue in the industry. Based on the internet of vehicles， this paper studies the optimization of logistics distribution route for electric vehicles. Firstly， the real-time traffic conditions and related information of charging stations were obtained by means of the internet of vehicles technology， and a charging queue waiting time prediction model based on the queuing theory was proposed under the internet of vehicles technology scenario. Secondly， considering the constraints of time， path selection， electric quantity and load， an optimization model of logistics distribution route for electric vehicles was established with the goal of optimizing the sum of distribution time cost， power consumption cost and time window penalty cost of participating vehicles. Finally， an example is given to verify the feasibility of the model and the effectiveness of the algorithm. The experimental results show that compared with the logistics distribution path optimization model of EV based on the latest charging strategy， the logistics distribution path optimization model of EV based on the internet of vehicles has significant advantages.

Key words： internet of vehicles; logistics distribution; path optimization; charging options

0  引  言

随着我国经济社会的高速发展，城市交通问题、环境污染问题日益凸显。近年来，末端配送需求的增长让绿色、可持續的城市物流配送受到高度重视，电动车物流配送所占比重越来越大。EVRP问题是传统车辆路径问题的延伸，需要运用电动车进行物流配送，因而需要额外考虑电动车补电、充电站选址、考虑时间窗的约束等问题[1-2]。

电动车物流配送正处于迅速发展阶段，现阶段充电装置的供给并不能完全满足电动车的充电需求，由此产生排队过程，间接增加了物流企业的运营成本，于是考虑电动车排队过程，能够更好地量化配送总时长和企业配送成本问题。Dudin等提出了具有等级评价机制的竞争性排队系统[3]。Keskin等考虑充电站车辆排队时间的动态变化性以建立模型，对比了排队时间对路径选择的影响[4]。Mark等人以成本最小和服务水平最高为目标，通过鲁棒优化模型研究了电动汽车换电站的选址定容问题[5]。可见，目前学者研究考虑排队论的EVRP问题多停留在传统站内排队阶段，目标主要是针对充电桩选址定容和优化。

随着车联网技术的发展，对探讨实时数据和预测数据对电动车充电位置和时机选择的影响成为可能，车联网情境下的车辆路径问题已经引起部分学者关注。5G车联网和边缘计算技术的出现，车联网和传感器的快速发展为车车协同、车路协同系统提供了保障[6]。邓友均等利用群智感知技术实时获得车流与充电站信息，建立电动车路径优化和充电导航模型[7]。Malikopoulos等建立了智能网联车辆速度协调优化控制算法，相较人类驾驶能够降低26%～30%的行程时间[8]。刘智萍等提出基于免疫遗传优化的实时交通路径诱导方法。根据期望行驶速度，设定出行预期速率临界值，利用路网节点间的动态连通性优化路网架构，构建了实时交通局部路网模型[9]。赵建峰等提出了一种新型实用的基于车联网及云计算平台的电动车物流的多目标优化调度算法[10]。曾志等通过分析影响路径阻抗因素，构建路段阻抗函数，提出基于改进型的Logit模型的路径分配方法。基于5G通信平台和数据传输系统，收集各路径的数据信息，将结果发送给车辆[11]。

总而言之，现有文献大多只关注电动车充电方式、充电桩选址以及车联网下的路网优化，较少考虑续航能力、换电站布局和客户时间窗等约束条件下，通过实时数据和预测数据来选择电动车充电位置和充电时机。而在车联网情境下，电动车充电实时数据的获取成为可能，进一步探讨实时数据和预测数据对电动车充电位置及时机的选择也变得可能和必要。因此本文基于路径规划理论和排队论建立基于车联网的电动车物流配送路径优化模型，并以时间窗、续航里程、载重、电量做为约束条件，采用遗传算法进行求解。

1  问题与模型

1.1  问题描述及假设。基于车联网的电动车物流配送路径优化问题描述为：单配送中心向多个客户点进行物流配送，各个客户点的需求量、地理位置、服务时间以及时间窗要求均已知。配送区域内存在r个充电站，充电车辆满足先到先充、充完即走的充电策略，且车辆到达服从参数为λ的泊松分布，目标是实现配送总成本最小。为了使本研究更贴近实际问题，现对该数学模型作出以下假设：（1）参与物流配送的电动车均为同一车型，最大装载量、额定电池容量、单位里程电池电量消耗均一致;（2）配送车辆均从配送中心出发，完成配送任务后返回至物流中心;（3）各个客户点均只被一辆电动车服務;（4）配送车辆早于或晚于时间窗范围到达，需接受惩罚成本;（5）配送车辆在充完电后为满电状态，且只在配送路径上耗电，到达客户点服务时间不耗电，默认熄火状态;（6）每辆车辆充电速率均为常量，不考虑电池老化导致充电速率的变化;（7）不考虑车辆因实时载重差异导致车辆耗电不同;（8）每个客户点的服务时间为定值。

1.2  参数和变量。数学模型中参数、变量及其含义如表1所示。

1.3  目标函数。本文模型以配送总时间成本C、耗电成本C和时间窗成本C之和作为优化目标，三部分成本之和达到最小即为所追求的目标。其中行驶时间成本、客户点服务时间成本、排队时间成本和充电时间成本之和为配送时间成本，目标函数即：

MinC=MinC

+C

+C

（1）

（1）配送时间成本

C=C

T

+T

+T

+T                                           （2）

式中：T、T、T和T分别表示行驶时间、客户点服务时间、排队时间和充电时间，C表示单位时间配送人员的劳动成本。各部分时间求法如下：

T=∑∑

x                                        （3）

v=                                              （4）

式（3）中，v表示在车联网情境下，t时刻路径ij上车辆k的速度。由决策中心通过WiFi、RFID等无线传感技术，收集正在配送电动车辆上传的定位信息，从而计算出该速度。式（4）中，dist为计算复杂路网的欧几里得距离，l和l分别表示路径ij上电动车辆k在t和t+1时刻的坐标。

T=∑∑1

-z

·T                                        （5）

T=                                              （6）

T=                                  （7）

综上，配送总时间成本表达式为：

C=C

∑

∑

x+

∑

∑1-

z·

T

++C   （8）

（2）耗电成本

车辆配送过程中，车身驱动用电以及车载设备用电等方面均会耗费电量，现假设车辆耗电成本与车辆行驶距离呈正相关，其中β表示单位时间充电电价，可得耗电成本公式如下：

C=β·

∑

∑

·

d

x                                      （9）

（3）时间窗成本

城市配送可能遇到一些不可控因素，导致到达客户点时间与客户预期时间不符，从而引发时间窗惩罚成本。设定令客户满意的时间窗区间为

T，

T，如果车辆提早到达惩罚成本为γ，延迟到达则惩罚成本为γ。因此，本文时间窗惩罚成本见式（10）。

F

T=

（10）

由此可得，时间窗成本为：

C=∑∑F

T                                         （11）

1.4  约束条件。在所建的基于车联网的电动车物流配送优化模型中，需要满足以下四方面约束，即时间约束、路径选择约束、电量约束和载重约束。

（1）时间约束

对于被访问的任意客户点j，电动车k到达该客户点的时刻可以表示如下：

T=x

T+1-

z

T

+z

T

+， ?k∈K; ?s∈S; ?i， j∈V; i≠j                        （12）

式中，当z=1时，车辆前往充电站充电，当z=0时，车辆前往下一客户点或者返回配送中心。

（2）路径选择约束

∑x=∑x， ?i∈V， k∈K                                    （13）

∑∑x=1， ?j∈C                                        （14）

∑x=∑x， ?k∈K                                        （15）

x=

（16）

x=

（17）

式中：約束（13）表示车辆访问节点后立即离开，保持进入和离开任意节点的车辆数量相等。约束（14）表示配送过程中一个客户点只能被访问一次。约束（15）表示每辆电动车配送的起点和终点均为配送中心。约束（16）为0～1约束，比较两段时间耗费情况从而选择更优路径，前者为从客户点i出发先前往r充电站再前往下一客户点j ，计算i-r-j行驶时间以及在充电站r排队与充电的时间之和;后者为从客户点i出发先前往客户点j再前往充电站r排队与充电，计算i-j-r行驶时间以及在充电站r排队与充电时间之和。如果前者总时间长，则选择先前往下一客户点j;反之，则选择先前往r充电站充电。由于各客户点的服务时间相等，因此，在此约束中无需考虑服务时间的差异。约束（17）也为0～1约束，表示车辆行驶到下一客户点时不足以保证再行驶至任意充电站，则立即前往充电站，否则可以前往下一客户点。

（3）电量约束

EQ=EQz， ?i∈S， ?k∈K                                      （18）

10%EQ≤EQ≤EQ， ?k∈K， ?i∈V                                 （19）

EQ=EQ-edx， ?i， j∈V， i≠j， ?k∈K                                 （20）

EQ=EQ， ?j∈C， ?k∈K                                       （21）

式中：約束（18）表示访问充电站后电动车剩余电量为100%。约束（19）表示电动车剩余电量最低不得低于10%。约束（20）表示车辆到达客户点j时的剩余电量，其中e表示单位里程消耗电量。约束（21）表示在客户点服务时，车辆不消耗电量。

（4）载重约束

由于路径分配后，每辆电动车均会沿指定路线对各客户点进行配送直至配送任务结束返回配送中心，配送中途不得返回配送中心装卸货，因此，需要约束路径上各个客户点需求总量不得大于电动车最大载重量。

∑∑xq≤W， ?k∈K                                     （22）

2  算法与设计

本文采用遗传算法求解车辆充电时的路径规划模型。利用遗传演变原理，模仿生物的生存进化，通过选择（Selection）、交叉（Crossover）与变异（Mutation）等基本操作因子，使种群中个体的适应度（Fitness）不断提高。

本文的遗传算法流程如下：

Step1  选择适合本文模型的自然数编码方法，基于成本最小化，设计充电情境下的电动车配送路径;

Step2  根据本文提出的约束子函数，考虑车辆载重约束、客户时间窗约束、成本约束等设置算法参数;

Step3  初始种群定义为500，为了使初始种群在区域内呈线性分布，采用randi函数随机生成初始种群;

Step4  适应度计算，将目标函数C的倒数作为适应度，即f=;

Step5  采用轮盘赌法，将适应度值大小靠后的染色体复制进入下一代，进行选择;

Step6  标记初始变量i=0，采用改进型交叉方法，对父代个体进行配对，以父代目标函数值排序，目标函数值大的与大的配对，小的与小的配对，然后利用混沌序列确定交叉点，最后进行交叉处理，该改进型交叉方法能有效提高算法收敛精度;

Step7  根据本文给定的变异率0.05，采用互换变异，随机选取染色体上两个等位基因，交换基因值，得到新的染色体;

Step8  将上一步得到的父代带入下一轮循环中;

Step9  计算适应度值，不断地进行运算直到得到的结果满足停止条件，此时可以停止运行，输出结果，否则，转至Step5。

3  算例仿真

3.1  实验设置。引入适用于本文模型的随机生成客户点算例进行仿真实验。该算例的客户点数量为30个，表示为节点1～30;充电站节点数量为3个，坐标表示为节点3161.7，43.6、3224.1，21.4、3331.7，56.6;配送中心的坐标为43.0，44.0，服务时间为960min;车辆额定载重量为7.5t;为方便计算，将配送途中所有车辆的平均行驶速度定为40km/h，续航里程为300km，车辆早于的客户规定的时间窗到达的惩罚权重为15元/小时，晚到的单位惩罚权重为35元/小时。客户点信息如表2所示。

3.2  实验结果分析。程序采用python3.9.2编程实现，在Intel（R）Core（TM）i7CPU2.60GHz，内存4GB的微机上运行。遗传算法参数设定如下：种群规模取100，最大迭代次数取500，变异概率取0.05。导入算例数据，可以看出，在代码迭代计算200次后，迭代曲线收敛，此刻所得值可视为该模型最优解。迭代收敛曲线如图1所示。

表3为本文算法求出的算例结果，配送中心将会派遣3辆电动车进行配送，均未出现电量耗尽情形，其中配送成本为1 102.3元，耗电成本为757.9元，时间窗成本为436.3元，总成本为2 296.5元。

3.3  对比分析。将最迟充电策略下的电动车物流配送路径优化模型M2与本文模型M1进行对比实验。最迟充电策略指车辆在电量到达阈值时前往充电站充电，本文阈值取10%EQ。模型M2的其他约束条件与模型M1一致，对比实验结果如表4所示。

对比分析结果表明，在考虑车联网情境下，相比最迟充电策略下的电动车物流配送路径优化模型，在排队与充电时间上节省了30.4%，体现出车联网在物流配送中节省排队与充电时间具有显著优势，能减少无效时耗，减少配送人员工资开支，也在一定程度上减缓配送人员疲劳度，避免安全隐患。另外，在时间窗成本上节省了23.2%，体现出充电时机选择在时间窗成本减少上发挥的作用，合适的充电时机不仅能减少排队与充电环节的时间消耗，而且能从物流配送全局考虑，协调各环节，实现最优路径方案;而且时间窗满足率的提高能够有效提升客户满意度，客户对该物流企业的能力及信誉更加满意，利于企业的长远发展。总成本方面节省了24.6%，进一步证明该模型能有效节省物流配送成本。

总体来说，基于车联网的电动车路径优化模型能够有效减少配送过程中的充电排队时间，选择更加合适的充电时机，减少配送全过程中的成本，对于当今日渐流行的电动车配送更具优势。

4  结束语

电动车物流配送过程中电动车的充电行为选择，对成本控制造成较大影响，应引起物流企业的高度重视。本文借助车联网技术获取实时交通路况以及充电站相关信息，对电动车物流配送路径优化进行研究，考虑时间、路径选择、电量及载重约束，构建了以参与配送车辆的配送时间总成本、耗电成本以及时间窗惩罚成本之和最优为目标的电动车物流配送路径优化模型，并运用遗传算法进行求解。仿真实验结果表明该模型可以有效解决电动车物流配送中的排队时间以及充电时机的问题，为配送总成本的节省提供有效帮助。但本文未考虑实际配送过程中因车辆货物重量的改变所导致的耗电量的影响，后续的研究中会加以改进。

参考文献：

[1]  CORDEAU J F. VRP with time windows， the vehicle routing problem[J]. SIAM Monographs on Discreate Mathematics and Applications， 2002（9）：157-193.

[2] 邵赛，毕军，关伟. 基于电动汽车的动态需求车辆路径问题[J]. 吉林大学学报，2017，47（6）：1688-1695.

[3]  DUDIN A N， DUDIN S A， DUDINA O S， et al. Competitive queueing systems with comparative rating dependent arrivals[J]. Operations Research Perspectives， 2020（7）：100139.

[4]  KESKIN M， LAPORTE G， CATAY B. Electric vehicle routing problem with time-dependent waiting times at recharging stations[J]. Computers & Operations Research， 2019，107：77-94.

[5]  MARK H Y， RONG Y， SHEN Z J M. Infrastructure planning for electric vehicles wit battery swapping[J]. Management Science， 2013，59（7）：1557-1575.

[6] 李静林，刘志晗，杨放春. 车联网体系结构及其关键技术[J]. 北京邮电大学学报，2014，37（6）：95-100.

[7] 邓友均，李明，余千，等. 基于实时信息感知的电动汽车物流配送路径优化与充电导航[J]. 南方电网技术，2017，11（2）：41-49.

[8]  MALIKOPOULOSA A， HONG S， PARK B B， et al. Optimal control for speed harmonization of automated vehicles[J]. IEEE Transactions on Intelligent Transportation Systems， 2018，20（7）：2405-2417.

[9] 刘智萍，周清华，彭吉琼，等. 基于免疫遗传优化的实时交通路径诱导方法[J]. 计算机仿真，2022，39（2）：98-101，418.

[10] 赵建峰，袁细国，梁伯栋，等. 基于车联网及云计算的电动物流车智能调度算法[J]. 公路交通科技，2019，36（6）：112-124.

[11] 曾志，曾璐，肖松，等. 基于5G的路径选择协同优化研究[J]. 科技与创新，2022（2）：159-163，167.

收稿日期：2022-12-14

基金项目：湖北省高校哲社重大课题项目（19ZD015）;中国物流学会研究课题项目（2022CSLKT3-336）

作者简介：曹  卓（1999—），男，湖北荊州人，武汉科技大学管理学院硕士研究生，研究方向：物流系统调度优化;王鑫鑫（1980—），男，湖北十堰人，武汉科技大学管理学院，副教授，硕士生导师，研究方向：数字化转型与商业模式创新、智慧物流;徐  仟（1998—），女，河南信阳人，武汉科技大学管理学院硕士研究生，研究方向：物流系统调度优化;马云峰（1972—），男，吉林蛟河人，武汉科技大学管理学院，教授，硕士生导师，研究方向：物流系统规划、管理定量分析。

引文格式：曹卓，王鑫鑫，徐仟，等. 基于车联网的电动车物流配送路径优化研究[J]. 物流科技，2023，46（15）：26-30.