基于多目标迭代局部优化算法的成本

韦鹏飞 张建军

文章编号：1005-9679（2022）03-0091-08

摘要：电动车凭借低碳、环保的优势越来越多地被企业接受用于物流场景，但续航里程和充电限制仍制约着电动车的应用。以往文献极少在电动车背景下同时考虑运行成本和路径平衡。因此，将总运营成本和路径平衡两个目标纳入问题，构建了数学模型，结合迭代局部搜索算法和变领域搜索算法的特性，采用五种领域算子，设计了多目标优化算法求解问题。研究构造了九组算例，对比了提出的算法与VNS算法、ILS算法的表现。数据实验验证了算法的可行性、有效性和稳定性。

关键词：电动车;路径规划;多目标优化;迭代局部搜索

中图分类号：F272

文献标志码：A

TheElectricVehicleRoutingProblemConsideringCostandRouteBalanceUsingaMulti-ObjectiveLteratedLocalSearchAlgorithm

WEIPengfeiZHANGJianjun

（SchoolofEconomicsandManagement，TongjiUniversity，Shanghai200092，China）

Abstract：Electricvehicles（EVs）areincreasinglyadoptedbycorporationsforlogisticsscenariosduetobeinglow-carbonandenvironmentallyfriendly，butrangeandcharginglimitationsstillconstraintheapplicationofelectricvehicles.PreviousliteraturerarelyconsidersbothoperatingcostandroutebalanceinthecontextofEVs.Therefore，thestudyconsiderstotaloperatingcostandroutebalanceintotheelectricvehiclesroutingproblemsimultaneously，anddesignsamulti-objectiveoptimizationalgorithmbycombiningiteratedlocalsearchalgorithmsandvariableneighborhoodsearchalgorithmsandusingfiveoperators.Thestudyprovidesninesetsofarithmeticcasestocomparetheperformanceoftheproposedalgorithmwiththevariableneighborhoodsearchalgorithmandtheiteratedlocalsearchalgorithm.Computationalexperimentsverifythefeasibility，effectivenessandstabilityoftheproposedalgorithm.

Keywords：electricvehicle;routingproblem;multi-objectiveoptimization;iteratedlocalsearch

目前世界氣候和能源问题严峻，国际社会一致寻求变革。我国于2020年9月明确提出2030年碳达峰与2060年碳中和的“双碳”目标，带动了新能源相关行业的发展。国际汽车市场上，奔驰、大众、通用等国际知名车企纷纷提出了全面电气化的新战略，新能源汽车逐渐取代传统燃油车已是未来趋势。

电商的进一步发展也带动物流业规模迅速扩大。《2021年12月中国快递发展指数报告》显示，我国年快递业务量突破1000亿件。在此背景下，企业向绿色物流转变对于成本效益和环境保护都有积极意义。

与燃油车相比，电动车有着不可忽视的特性，因此在对电动车进行路径规划时，必须充分考虑其特点。电动车在节能、环保等方面都较燃油车有显著优势，但在续航、充电速率方面有明显的短板。另外，电动车的配套公共设施还远不如燃油车完善，这也制约了电动车的推广。在这样的限制下，采用电动车的企业需要开发高效的车队管理方案，在充分考虑电动车自身限制的情况下扩大经济效益。

面对这个困难，众多学者对电动车路径规划问题（ElectricVehicleRoutingProblem，EVRP）进行了探索。EVRP的核心是在考虑电动车的里程、充电和载货量限制的情况下，合理配置路径，以最低成本满足客户需求。在此基础上，实际问题还需要考虑时间窗、可变能耗、充电站容量限制等因素。Conrad和Figliozzi首先介绍了途中充电的路径规划问题。Erdogan和Miller-Hooks第一次提出了充电站的路径规划问题。Schneider等介绍了一种带时间窗的电动车路径规划。

然而，目前极少有文献考虑里程限制和客户时间窗，并将成本和路径平衡作为目标。在电动车加速进入物流场景，物流企业比拼服务质量，劳动者权益越来越受重视的当下，同时将电动车特性、客户时间窗、路径平衡纳入考虑是非常必要的。因此，本文结合这些因素，提出了带时间窗的多目标电动车路径规划问题，设计了一种基于ILS算法、结合VNS算法领域搜索框架的多目标优化算法。

1文献综述

为了减少传统燃油车的负面影响，采用电动车作为城市物流的主要载具是一个有效的措施。由于电动车存在续航里程短和充电时间长等不可忽视的短板，许多学者将其特点纳入考虑，针对电动车路径规划问题展开了研究和探索。

电动车路径规划问题脱胎于路径规划问题（VehicleRoutingProblem，VRP）。Conrad和Figliozzi介绍了一种考虑途中充电的路径规划问题（RechargingVehicleRoutingProblem，RVRP），问题假设客户处可提供充电服务，车辆可在客户处服务的过程中充电。Erdogˇan和Miller-Hooks提出了绿色路径规划问题（GreenVehicleRoutingProblem，GVRP）的概念，并且第一次提出了考虑充电站的路径规划问题，但没有考虑时间窗和载货量限制。Schneider等介绍了一种带时间窗和充电站的电动车路径规划问题（ElectricVehicleRoutingProblemwithTimeWindowsandRechargingStations，EVRPTW），问题的主要目标是用最少的车辆和最短的总行驶里程满足需求。Hiermann等将EVRPTW进一步拓展，考虑了由在载货量、电池容量和采购价格方面有区别的不同车型组成的混合车队。揭婉晨等也研究了多车型的电动车路径规划问题，并提出了一种改进的分支定价算法。

为了使模型更贴近现实，一些研究人员考虑了更多细致的现实情况。为了更快地完成服务，电動车在有些情况下并不需要进行完全充电，只要将电量补充至所需值即可。Keskin和Catay构建了允许部分充电的EVRPTW模型并用实验证明部分充电可以减少交通成本、优化路径决策。葛显龙和竹自强研究了带软时间窗的电动车辆路径优化问题。Montoya等考虑了电动车充电速率的现实情况，构建了带非线性充电函数的EVRP模型并提出了一种混合元启发算法来求解。唐佩佩等考虑生鲜产品的特点，研究了生鲜同城配送的路径问题。Schiffer和Walther将充电站的位置也设为变量，同时研究了充电站的选址问题和车辆的路径规划问题。为了克服电动车充电时间长的缺点，以更换电池代替充电的方案吸引了一些学者的注意。王琪瑛等研究了带软时间窗的电动车换电站选址路径问题。李嘉等考虑到客户同时存在收货和寄件需求的情况，研究了装卸一体化的电动车路径问题。

现实的物流场景往往还涉及多种不同的目标，例如经济成本、服务时长、路径平衡等。一些学者将单目标EVRP问题拓展至包含多种目标的路径规划问题（Multi-objectiveVehicleRoutingProblem，MOVRP）。Lee和Ueng认为路径之间的不平衡会导致员工的不满意程度上升，提出了一种考虑路径平衡的VRP。Sessomboon等研究了带模糊时间窗的MOVRP，考虑了四种目标函数，并提出了一种混合遗传算法来求解问题。Ombuki等研究了以车辆数和总行程为目标的MOVRP并提出了一种改进的遗传算法求解问题。Jozefowiez等对MOVRP进行了归纳和回顾，他注意到多目标进化算法（Multi-objectiveEvolutionaryAlgorithms，MOEA）比较受研究者关注。Zhang等研究了一种带弹性时间窗的MOVRP，并提出了一种基于蚁群算法的求解策略和三种变异算子。

目前多目标电动车路径规划问题的研究较少，在电动车背景下同时考虑成本与路径平衡的研究更为稀少。在此背景下，本文对以成本和路径平衡为目标的带时间窗的电动车路径规划问题展开了研究。

2模型

2.1问题描述

本文研究的带时间窗的多目标电动车路径规划问题（Multi-objectiveElectricVehicleRoutingProblemwithTimeWindows，MOEVRPTW）可以具体描述为某物流配送中心采用一电动车车队向N位客户提供物流配送服务，车队中各车为相同车型。车辆从配送中心出发，服务若干名客户，但须在每个客户指定的时间窗内向其提供配送服务，且每个客户仅由一辆车服务一次。在服务过程中，车辆载货量不能超过最大限值，由于电动汽车的行驶里程有限，车辆在配送途中可前往充电站进行充电。

本文研究的多目标问题包含两个目标，分别为成本目标和路径平衡目标。车辆的成本分为两部分：固定的采购成本和与行驶里程线性相关的运输成本。另外，在现实企业运营中，若车辆之间的任务量差距较大，会引起司机的不满，影响企业的运营。因此，本文研究的MOEVRPTW决策问题为在满足电动车续航和运力约束、时间窗约束的情况下，确定车辆数和路径安排，并取得总成本与路径平衡的均衡最优。

3.2数学模型

其中，式（1）、（2）分别为总成本目标函数和路径平衡目标函数;式（3）、（4）对路径平衡目标函数进行补充定义;式（5）为决策变量;式（6）确保每个客户仅被一辆车服务且只服务一次;式（7）表示一个虚拟充电站最多只能接待一辆车;式（8）确保流量平衡，除了场站点，车辆到达某点后必须从该点离开;式（9）表示车辆最多只能执行一条路线的任务;式（10）、（11）分别保证了从场站点和客户处、充电站处离开的路线的时间可行性;式（12）表示时间窗约束;式（10）～（12）防止子路径的产生;式（13）确保路径上的客户的货物需求得到满足;式（14）为车辆载货量约束;式（15）、（16）分别保证了从客户处、从场站点和充电站处离开的路线的电量可行性。

3算法设计

3.1迭代局部搜索（ILS）算法

迭代局部搜索算法是一种简洁而高效的启发式算法，它结合了迭代方法和局部搜索，并将方法作为一种多样性机制来搜索更广范围。

在迭代局部搜索算法中，先对初始解S0进行局部搜索，找到局部最优并作为当前最优解S*，然后开始迭代。在每一轮迭代中，对S*进行扰动得到中间解S′，再对S′实施局部搜索得到S′*，若S′*满足设定的接受准则，则接受它作为新的S*，若不满足，则保留原来的S*。

迭代局部搜索算法的核心在于专注于对局部最优解而非全部可行域的搜索，算法的扰动机制使得新的搜索起点可以继承原有局部最优的部分片段，提高全局搜索效率。已有相当多的研究应用了该算法并证明了其有效性。另外，迭代局部搜索算法拥有很好的适应性，算法的扰动、接受准则部分可以灵活地根据具体情况进行调整，以满足不同问题的优化需求。

3.2多目标迭代局部搜索算法（MOILS）

3.2.1解的编码

本研究运用整数编码方式，以一个含有10位客户、2个充电站的案例为例。0表示场站点，1～10表示客户，11、12表示终点站，解的编码如下：

以上编码表示在一条路径中，车辆从场站点出发，依顺序服务了1、3、4号客户，前往12号充电站充电后又服务了9、2号客户，然后经过11号充电站充电并回到场站点。

3.2.2初始解的构造

本文运用一种贪心构造法构造初始解，在描述初始解的构造方法之前，先定义“可到达客户”，即以当前电量，从当前位置可以直接到达或途经充电站充电后可以到达的客户。

构造初始解的步骤如下：

（1）当存在未服务的客户时，开启一条新路径。车辆从场站点出发，寻找所有未服务的可到达客户，从中选择最近的客户前往提供服务。

（2）在客户处，寻找当前状态的所有未服务的可到达客户，若存在未服务的可到达客户，则从中選择最近的客户前往提供服务;若不存在未服务的可到达客户，则返回场站点并回到步骤（1）。

（3）重复步骤（1）、（2）直至所有客户均接受到服务，即完成了初始解的构造。

3.2.3算法迭代机制

本文设计的多目标迭代局部搜索（MOILS）算法以迭代局部搜索（ILS）为基础，步骤如下：

（1）构造初始解S0并初始化目标函数权重参数α、β，接受初始解作为当前最优解S*。

（2）用原目标函数和权重参数构造新的目标函数，初始化迭代参数i。

（3）扰动S*得到中间解S′，并初始化领域搜索参数k。

（4）在S′的k领域内搜索得到S″，若S″优于S′，接受S″作为新的中间解并重置领域搜索参数k，否则保留S′并使k增加1。

（5）若k≤5，回到步骤（4），否则进行下一步。

（6）若S′通过接受准则，则接受S′作为新的当前最优解，否则保留原当前最优解，无论是否接受，都使迭代参数i增加1;若i不超过终止迭代次数It，退回步骤（3），否则进行下一步。

（7）缩小α并增大β，调整步长为δ。若调整后α>0，回到步骤（2），否则停止算法。

具体流程如图1所示：

3.2.4邻域算子

在局部搜索阶段，本文应用五种算子构造邻域。

（1）交换算子

随机选择任意两个节点，交换其位置。

（2）逆序算子

随机选择一条路径中的两个节点并反转两个节点及其之间的顺序。

（3）插入算子

随机选择解中的一个节点，将其移动到原路径或其他路径的另一个随机位置。

（4）移除算子

随机选择解中的一个充电站节点将其移除。

（5）合并算子

随机选择两条路径，将其合并。

3.2.5扰动与接受准则

（1）扰动方式

在对当前最优解进行扰动时，本文选用经典的double-bridgemove扰动策略，其扰动方式如图2所示。

在double-bridgemove扰动策略中，依序随机选择四个节点i、j、k、l，并如图2中点虚线所示切断（i，i+1），（j，j+1），（k，k+1），（l，l+1）四个路段，然后将路径按图中短划虚线所示方式连接（i，k+1），（k，i+1），（j，l+1），（l，j+1）四个路段，构成新路径。

（2）接收准则

对局部搜索得到的中间解S^'，本文采用模拟退火算法中的解接受准则。每次进行判断时，取随机数ε∈[0，1]，若ε<e-OF（S′）-OF（S*）T·ρi，则接受S′，否则保留S*。

4实验

4.1实验设置

本文采用Java编写算法，并在处理器为Intel（R）Core（TM）i5-5257UCPU@2.70GHz、内存为8G的计算机平台上进行实验。

在参数设置方面，本文做如下假设：

由于本文研究的多目标电动车路径规划问题目前缺少可横向比较的研究算例，本文构造了九组算例来验证算法的有效性。九组算例的顾客数和充电站数如表5所示。

为了对比算法的表现，除了用本文提出的算法，研究还应用VNS算法和ILS算法求解了九组算例，其求解结果也在实验结果中展示。

4.2实验结果

用本文提出的MOILS算法求解九组算例，每组运行5次。由于多目标问题的解为帕累托解，以下以α-0.7，β-0.3为参数设置展示多目标算法的求解结果，结果如表4所示。

在上述求解结果表中，单目标MOILS表示将算法中的成本函数权重参数固定为1，并将路径平衡函数权重参数设为0，以达到求解单目标的效果。

表4为对成本函数求解的结果，每种算法分别展示了算法运行5次的最优结果和平均结果。由表4可知，本文提出的MOILS在求解EVRP问题时可以得到较好的结果。与经典VNS算法和ILS算法相比，MOILS在仅求解成本目标时明显优于VNS和ILS，在九组算例中求得的最优解成本比VNS平均低9.41%，比ILS平均低17.72%。

表5展示了每种算法所求的最优成本及最优成本对应的路径平衡结果。表6展示了各种算法求得的最优成本对应的路径平衡结果以及多目标MOILS求得的路径平衡结果相较于VNS和ILS的改善程度。由表5和表6可以看出，在考虑双目标的情况下，本文提出的MOILS同样有较好的表现。与VNS和ILS相比，在不显著提升成本的情况下，MOILS也可以使路径之间的平衡得到大幅度改善，例如在算例R03中，MOILS的成本只比VNS和ILS的成本分别增加了0.58%和3.37%，但路径平衡却分别改善了68.63%和64.49%。

表7展示了VNS、单目标MOILS和多目标MOILS求解各算例5次所得解的路径平衡的均值和标准差。表7中数据表明MOILS在求解单目标问题和多目标问题时，都体现出比VNS更好的稳定性。在九个算例中，VNS、单目标MOILS和多目标MOILS求得的路径平衡的平均方差分别为7.7%、6.3%和2.8%。

实验数据表明，本文提出的算法能够在求解多目标电动车路径规划问题时取得较好的结果。

5结论

本文以成本和路径平衡为目标，研究了多目标电动车路径规划问题，考虑了电动车行驶里程、载货容量、充电速率以及顾客时间窗等限制因素，提出了相应的数学模型，并设计了一种多目标优化算法。

本文的算法以迭代局部搜索算法为基础，采用了五种算子，结合VNS的领域搜索策略，通过调整目标函数权重参数迭代求解多目标问题的帕累托前沿。本文对九组算例进行了多次实验，并对比了经典的VNS和ILS算法，证明了本文中算法的可行性和有效性。

未来的研究可以考虑其他现实目标，也可以将软时间窗、随机需求或随机道路条件等不确定性因素纳入考量，以增加模型、算法的现实应用价值。

参考文献：

[1]CONRADR，FIGLIOZZIM.Therechargingvehicleroutingproblem[J].Procofthe61stAnnualIIEConference，2011.

[2]ERDOGˇANS，MILLER-HOOKSE.Agreenvehicleroutingproblem[J].TransportationResearchPartE：LogisticsandTransportationReview，2012，48（1）：100-14.

[3]SCHNEIDERM，STENGERA，GOEKED.Theelectricvehicle-routingproblemwithtimewindowsandrechargingstations[J].TransportationScience，2014，48（4）：500-20.

[4]HIERMANNG，PUCHINGERJ，ROPKES，etal.Theelectricfleetsizeandmixvehicleroutingproblemwithtimewindowsandrechargingstations[J].EuropeanJournalofOperationalResearch，2016，252（3）：995-1018.

[5]揭婉晨，杨珺，杨超.多车型电动汽车车辆路径问题的分支定价算法研究[J].系统工程理论与实践，2016，36（7）：1795-805.

[6]KESKINM，CATAYB.Partialrechargestrategiesfortheelectricvehicleroutingproblemwithtimewindows[J].TransportationResearchPartC-EmergingTechnologies，2016，65：111-27.

[7]葛显龙，竹自强.带软时间窗的电动车辆路径优化问题[J].工业工程与管理，2019，24（4）：96-104，12.

[8]MONTOYAA，GURETC，MENDOZAJE，etal.Theelectricvehicleroutingproblemwithnonlinearchargingfunction[J].TransportationResearchPartB：Methodological，2017，103（87-110.

[9]唐佩佩，馮晓威，宫英丽.基于遗传算法的生鲜同城配送路径优化研究[J].上海管理科学，2018，40（5）：90-96.

[10]SCHIFFERM，WALTHERG.Theelectriclocationroutingproblemwithtimewindowsandpartialrecharging[J].EuropeanJournalofOperationalResearch，2017，260（3）：995-1013.

[11]王琪瑛，李英，李惠.带软时间窗的电动车换电站选址路径问题研究[J].工业工程与管理，2019，24（3）：99-106.

[12]李嘉，杨东，贾永基，等.装卸一体化电动汽车路径问题建模与优化[J].工业工程与管理，2020，25（1）：29-37.

[13]LEETR，UENGJH.Astudyofvehicleroutingproblemswithload‐balancing[J].InternationalJournalofPhysicalDistribution&LogisticsManagement，1999，29（10）：646-57.

[14]SESSOMBOONW，WATANABEK，IROHARAT，etal.Astudyonmulti-objectivevehiclerountingproblemconsideringcustomersatisfactionwithdue-time（thecreationofparetooptimalsolutionsbyhybridgeneticalgorithm）[J].TransactionsoftheJapanSocietyofMechanicalEngineersSeriesC，1998，64（1108-15.

[15]OMBUKIB，ROSSBJ，HANSHARF.Multi-objectivegeneticalgorithmsforvehicleroutingproblemwithtimewindows[J].AppliedIntelligence，2006，24（1）：17-30.

[16]JOZEFOWIEZN，SEMETF，TALBIE-G.Multi-objectivevehicleroutingproblems[J].EuropeanJournalofOperationalResearch，2008，189（2）：293-309.

[17]ZHANGH，ZHANGQ，MAL，etal.Ahybridantcolonyoptimizationalgorithmforamulti-objectivevehicleroutingproblemwithflexibletimewindows[J].InformationSciences，2019，490（166-90.

收稿日期：2022-03-16

作者简介：韦鹏飞（1997—），男，江苏无锡人，硕士研究生，研究方向：物流管理、路径规划，E-mail：pfwei973@163.com;张建军（1978—），男，江西上饶人，博士，副教授，博士生导师，研究方向：物流与供应链管理，E-mail：Zhangjianjun@tongji.edu.cn。