陈其赛，倪 静

（上海理工大学 管理学院，上海 200093）

随着国务院办公厅《新能源汽车产业发展规划（2021—2035）》的印发，未来电动汽车代替燃油汽车已成为必然趋势。对于物流企业来说，如何降低成本一直是研究的重点。相比传统燃油汽车，电动汽车以极低的运输成本优势逐渐在短距离的市内配送中成为企业首选。此外，在现代物流中，配送方式随着客户群体的不同存在不同的运输模式。对于超市、便利店等这类每日既要进货又有未售罄生鲜需要回收的商户来说，同时送取货这一更贴近实际需求的物流配送模式逐渐成为学者的研究重点。

对同时送取货问题的研究更贴近于实际，考虑车辆在实际配送任务中不同客户的需求，国内外已有不少学者研究。徐小峰等[1]考虑了同时送取货需求带模糊容量限制的动态选址问题，通过改进五角模糊数隶属度函数来表示模糊容量约束，再通过禁忌搜索与自适应大规模领域搜索算法结合的混合算法来求得可行解；王超等[2]首次设计了回溯搜索优化算法来解决带时间窗同时送取货问题并证明有效性；Wang等[3]研究了多配送中心同时送取货的车辆路径问题并利用非支配排序遗传算法求解；周咏等[4]研究冷链物流同时送取货车辆路径优化问题；谭巍等[5]研究了车辆负载量不断变化情况下引入候选集合的策略，将启发因子设为目标函数值并利用蚁群系统与2-opt方法相结合的启发式算法求解模型；Golsefidi等[6]考虑到供应链管理中残缺产品库存的不确定性，通过适用于等式约束的鲁棒优化方法以及改进模拟退火算法、遗传算法求解模型并分析算法性能。

电动汽车凭借低成本、绿色环保逐渐在物流配送领域成为主流，但由于其存在着续航能力较弱、配套的充电设施布局不健全等问题。如何建立一套完整的电动汽车物流配送网络体系，对充电设施的选址以及配送路径的优化成为了当下急需解决的问题。杨磊等[7]考虑了电动汽车在充电和换电两种模式下电动车的充换电设施选址问题，分别建立了两种模式下的数学模型并通过改进遗传算法来求解路径规划和选址模型；陆坚毅等[8]考虑到电动汽车用户会绕行一段距离对车辆进行充电的特征建立了以充电站建设成本和绕行成本之和最小为目标的双层整数规划模型，通过包含局部迭代搜索的自适应遗传算法对模型求解；Zhang等[9]考虑了电动汽车的能耗问题，基于蚁群算法求解电动汽车的最小能耗并说明最小能耗作为目标函数而不是最小距离作为目标函数的好处；杨珺等[10]、敦放等[11]考虑到差异化因素对选址路径的影响，并分别用改进禁忌搜索算法和MCWGATS算法求解该模型，最后用多组算例证明了算法的有效性。

综上所述，学者们已对同时送取货问题的选址或者配送方法进行了研究，但针对电动汽车完成同时送取货选址路径优化问题的研究较少。电动汽车采用同时送取货模式进行配送可降低成本，本文综合考虑客户同时送取货需求、时间窗约束以及电动汽车电量与容量约束等因素，建立了带同时送取货和时间窗约束的电动车选址路径问题模型（ELRPSPDTW）[12-14]，并设计了改进的混合模拟退火-蚁群算法（SA-ACO）来求解该问题[15-16]。首先，进行问题描述并建立相应模型；其次，提出混合模拟退火-蚁群算法并介绍相关优化策略；接着，通过随机生成不同规模大小的算例进行仿真实验，并与蚁群（ACO）、禁忌搜索（TS）以及自适应大邻域搜索（ALNS）3种算法的解进行比较；此外，再和送取分离的配送模式进行对比，验证算法的稳定性与实用性；最后，证明本文提出的模型和算法在解决同时送取货问题时的可行性以及对未来的展望。

1 模 型

1.1 问题描述

构建电动汽车带时间窗和同时送取货的选址路径模型，具体问题描述如下：ELRPSPDTW组成的网络图为G=(N,A)，N=Nc∪S∪{0}，其中，Nc={1,2,···,n}，Nc为顾客点集合，S={1,2,···,s}，S为充电站集合，s∈S，{O}为中心仓库，A={(i,j)|i,j∈N,i≠j}，A为点i,j弧集合，每条边(i,j)∈N为两两节点的距离dij，满足距离关系式dik+dkj≥dij。该配送中心有m辆车型相同的电动汽车，其中，k∈K,K={1,2,···,m}，K为车辆集合。

电动汽车充满电后从配送中心匀速出发为多个顾客提供配送服务，而每个顾客有且仅能接受一辆电动汽车的服务，电动汽车在完成配送任务之后需要返回配送中心。每辆电动汽车有配送容量限制，每个顾客除了具有送货需求之外也存在取货需求且送取货需求量均已知，每个顾客都有一定量的货物需要电动汽车送回配送中心，因此，在电动汽车服务过程中，运载量不能超过其车身最大装载量。每个顾客既存在软时间窗限制又存在硬时间窗限制，软时间窗为[ei,li]，硬时间窗为[Ei,Li],[Ei,Li]⊆[ei,li]，车辆到达时间在硬时间窗范围内、软时间窗范围外时存在时间窗惩罚成本。

在本文中，只有电动汽车经过配送中心或者充电站才能换上充满电量的电池，充电站的位置在网络中随机产生。本文考虑到长期使用以及各种未知因素，采用自建充电站的形式，每一个充电站的建设都会产生固定费用。为尽可能减小充电过程中带来的损失，采用更换电池的充电方式，更换一个电池所需时间固定。

1.2 符号与决策变量

为了能更好地描述ELRPSPDTW的数学模型，对本文使用的符号作如下说明：G表示一个配送网络，G=(N,A)；N表示节点集，N=Nc∪S∪{0}，Nc为顾客集，S为充电站集，0为配送中心；A表示边集；dij为节点i到节点j的距离；K为车辆集合；C为单位距离耗电成本；W1为车辆早到等待时的单位时间机会成本；W2为车辆晚到时的单位时间惩罚成本；为车辆k到达i点时的时间；为车辆k离开i点时的时间；tsi为车在i点的服务时间；v为车速；ei为客户点i满意的时间下限；li为客户点i满意的时间上限；Ei为允许车辆到达客户点i的最早时间；Li为允许车辆到达客户点i的最晚时间；f为单位充电站的建造成本；Ck为电动汽车k的发车成本；pi为i点的送货量；qi为i点的取货量；Q为车的最大容量；Qijk为k车在弧(i,j)段时的负载量；Bk为电动车k电池的最大容量；为电动车k到达节点i时的剩余电量；为电动车k离开节点i时的剩余电量；r为电动车单位距离耗电量；h为电动车在充电站更换电池所需时间。决策变量：xijk为k车经过弧(i,j)从节点i到节点j时则为1；yi为建造第s个充电站时则为1；为k车从i点前往j点过程中需要先经过充电站s时则为1。

1.3 模型

建立数学模型：

约束条件：

其中：目标函数式（1）表示电动汽车车辆运输成本、时间窗惩罚成本和充电站服务设施建设成本这3项物流成本最小化；约束式（2）表示每个顾客被服务仅被服务一次；约束式（3）表示车辆进出流量平衡，即每辆车进入某个点的次数和离开某个点的次数相等；约束式（4）表示电动汽车从配送中心出发最后返回配送中心；约束式（5）表示每一条路线只有一辆车行驶；约束式（6）为消除子回路；约束式（7）和式（8）表示每条路径上任意节点车辆的装载量不会超过车辆的装载能力；约束式（9）表示任意节点货物量的送取平衡；约束式（10）表示电动汽车从配送中心出发时开始计时；约束式（11）和式（12）表示车辆k在离开i点和到达j点时的时间；约束式（13）为硬时间窗约束；约束式（14），（15），（16）表示车辆离开配送中心、离开充电站和离开客户点时的电量水平；约束式（17）定义决策变量是0-1变量。

2 算法设计

本文研究的ELRPSPDTW模型是以总成本最小为目标的选址路径问题，显然该问题属于典型的NP难题。针对选址路径（LRP）问题，目前国内外较为常见的方法主要是将LRP问题分解成选址分配问题（LAP）和车辆路径问题（VRP）分阶段求解。遗传算法、蚁群算法等启发式算法已被证明能很好地解决此类问题，其中，蚁群算法采用分布式并行计算机制，有自组织性、正反馈性与较强的鲁棒性，可以使问题在较短的时间内找到较为满意的解，同时通过引入高斯变异来改进对重点搜索区域的局部搜索性能。蚁群算法虽然可以在较短时间内得到较好的解，但是，当求解问题规模较大时，蚁群算法容易出现早熟、停滞现象。模拟退火算法是模拟固体退火过程的一种随机搜寻算法，具有结构简单且操作模块相对独立的特点，可以被广泛地应用于多约束耦合求解。由于在使用模拟退火的过程中加入了回火操作，增大了算法对非更优解的接受能力，有助于算法对局部较优解的跳出，这恰好能解决蚁群算法中容易陷入局部寻优的不足，因此，通过结合两种算法的优点设计该模拟退火-蚁群算法来解决本文问题，整体流程图如图1所示。

图1 算法流程图Fig.1 Algorithm flowchart

2.1 初始编码及编码规则

初始解操作的首要目的是生成一个满足问题约束的解，有利于后续目标优化的展开，本文采用均匀分布随机数产生特定范围内符合约束条件的初始编码。编码方式采用三层编码，第一层编码为充电站的选择优先度编码，编码长度为J，范围为1-J的不重复自然数；第二层编码为充电站的选择数量，编码长度为1，范围为1-J的整数；第三层编码为需求点的配送优先度，编码长度为K，范围为1-J的不重复自然数。如果J=5,K=6,C=[5,4,2,3,1,3,5,6,3,4,1,2]，则5, 4, 2, 3, 1为第一层编码，表示充电站是优先选择5，其次4，接着2，再选3，最后是1；3是第二层编码，表示选择3个充电站，按第一层编码的优先度进行选择，即依次选择5, 4, 2这3个充电站；5, 6, 3, 4, 1, 2为第三层编码，表示需求点的配送优先度，即配送顺序依次为5, 6, 3, 4, 1, 2。

2.2 高斯变异及信息素更新策略

高斯变异作为改进遗传算法对重点搜索区域的局部搜索性能的另外一种变异操作方法，在变异时用一个均值为μ、方差为 σ的正态分布的一个随机数来替换原有基因值，其过程与均匀变异类似，

信息素更新是蚁群算法的关键操作之一，若信息素更新过快，容易使算法过早陷入局部寻优，信息素更新过慢，则会影响算法的收敛速度。信息素挥发的公式为

式中：τi(gen+1)为第gen+1代第i个蚂蚁对应信息素；ρ为信息素挥发因子；τi(gen)为第gen代第i个蚂蚁对应信息素。

信息素增强的公式为

式中：Δτi(gen+1)为第gen+1代第i个蚂蚁的信息素增量；Qx为信息素增强因子；yi为第i个蚂蚁对应的目标函数值。

2.3 带回火操作的模拟退火算法求解步骤

带回火操作的模拟退火算法求解步骤：

a. 设置退火起始温度T0，退火终止温度Tz，退火系数th，回火系数hh，回火结束温度Th，退火温度T=T0，设置迭代次数Nh。

b. 每当退火迭代次数达到退火终止温度，则升高温度进行回火操作，在每次回火过程中，回火的最高温度随每次退火过程逐渐降低，最终达到回火结束温度时则停止运行算法。

3 数值仿真算例分析

3.1 参数设置

为了证明该算法的有效性，现利用数值仿真实验对算法进行实际应用。由于目前没有与本文问题相关的标准测试算例，本文的实验算例由1个中心仓库、8个待选充电站和30个客户组成，客户点的坐标由MATLAB 9.6.0软件的rand()函数在[0,150]区间随机生成，各个客户的送取货量在[0,360]区间随机生成。设置车的最大容量Q=1500，电池最大容量Bk=220，车速v=70。相关参数设置：Qx=1，ρ=0.01，T0=2 000，Tz=20，th=0.99，hh=0.75，Nh=200。

3.2 算法验证

算法通过MATLAB 9.6.0编程实现，计算机配置为Intel Core i7-9750H，2.60 GHz，32 GB RAM，在Windows10操作系统下运行。分别用SA-ACO，ACO，TS以及ALNS算法对随机生成的30个客户算例求解，求解得出的最优化路径如图2所示。其中，中心红点表示配送中心，C1-C8为随机生成的充电站，被选中使用的充电站点由紫色圆环标注，剩余点为待服务的客户点。

图2 不同算法路线求解结果Fig.2 Solution results of different algorithm routes

表1为30个客户在4种算法求解结果下所需车辆数、充电站数以及总成本。在本文所提出的算法求解结果中，配送中心需要3辆车并启用了2个充电站来完成该配送任务，总成本为1 977.85元。而ACO算法、TS算法以及ALNS算法结果的总成本分别为2 341.54元，2 748.77和2 276.91元。

表1 30个客户求解结果Tab.1 Solution results of 30 clients

3.3 混合算法有效性分析

为了进一步验证算法的有效性，除了生成30个客户的算例之外，再分别随机生成50，100以及150个客户的算例，继续进行实验分析，比较结果如表2所示，其中，GAP表示本文算法的求解结果优于对比算法的百分率。

从表2中可以看出，本文提出的算法比起传统蚁群算法的求解结果平均高出12.46%，说明在加入了模拟退火算法从而提高全局寻优能力之后确实能有效帮助蚁群算法得到更优解。在求解带时间窗和同时送取货约束的电动车选址路径问题中，改进的模拟退火-蚁群算法比起传统的启发式算法无论在中小规模算例中都能得到更好的总成本解，说明该算法具有良好的稳定性和有效性。另一方面，以150个客户的算例为例，用图3表示4种算法迭代200次的收敛情况。从图3可知，本文所提出的改进模拟退火-蚁群算法收敛效果最优，说明与蚁群算法相比，加入了模拟退火算法后不容易陷入局部寻优，在迭代160次左右后开始逐渐趋于最优解，通过综合对比后可知，本文算法在求解该类问题上具有一定优势。

图3 150个客户算法收敛对比图Fig. 3 Convergence comparison chart of 150 client algorithms

3.4 算法运行时间分析

模拟退火算法和蚁群算法在求解这类NP难题可以得出较优解，但是，计算效率都不高。为了从算法运行时间方面进一步分析本文算法，本文以150个客户的规模为标准，随机生成算例50次，分别用上述4种算法进行仿真求解并记录下4个算法的求解结果和所需时间，取平均值后结果如表3所示。从表3可以看出，由于加入了高斯变异和回火两种策略，尽管本文算法由两种效率较低的算法混合而成，与蚁群算法相比仍可更快跳出局部寻优，从而在更短时间内求得更优解。与TS算法以及ALNS算法相比，求解时间上还存在一定差距，但是，考虑实际环境，求解所需时间也还在可接受范围之内，具有可行性。

表3 算法运行时间对比Tab.3 Comparison of algorithm running time

3.5 送取货模式分析

为了进一步验证本文所提出的同时送取货模式以及模拟退火-蚁群算法的实用性，通过更改配送模式，将送货和取货分开来先统一进行送货，所有客户配送完毕后再进行取货工作。取同样的客户数据再一次进行仿真实验，结果如表4所示，其中，GAP表示各算法下同时送取货模式总成本优于送取货分离模式总成本的百分率。

表4 送取货结果对比Tab.4 Comparison of delivery and pickup results

从表4中可以看出，当采用送取分离模式进行配送之后，总成本平均上升9.38%，而另外3种算法平均上升均超过12%。说明本文所提出的模拟退火-蚁群算法实用性较好，且同时送取货的配送模式更贴近实际，有效解决了客户需求。

4 结束语

为了更加贴近实际物流的配送情景，考虑了在时间窗约束下进行同时送取货这一更贴近实际的物流运输行为。为更好求解带同时送取货和时间窗约束的电动汽车选址路径问题，提出了SAACO算法求解问题。在基础的SA算法与ACO算法中分别加入回火操作以及高斯变异，扩大搜寻更优解的能力，在整体与局部方面都提高了算法的性能，避免陷入局部寻优。但是，SA算法和ACO算法计算效率相对较低，比起其他算法所需的求解时间更长，这也是本文算法的一个缺陷，后续将尝试使用机器学习的方式改进算法或者使用更新的算法从而使得效率更高、求解效果更好。除了通过与不同规模、不同算法对比证明本文算法的优越性之外，本文还考虑了针对有送取需求的客户的两种不同配送模式，并最终证明与送取分离模式相比，同时送取货模式的合理性也更符合物流企业的实际需求。

基于同时送取货的电动车选址路径问题是物流配送领域未来值得深入研究的方向，在下一步问题的研究中还可以考虑客户送取货的不确定性需求以及考虑取得的货物的装载方式，根据配送的约束建立更加贴合实际的目标函数，从而为物流配送领域提供更好的理论支持。