物流作为电商的重要要素之一，在时间上制约了电商行业的发展。如何优化车辆路径、提高运输效率，是电商行业在物流环节急需解决的问题[1]。现阶段，许多车辆路径规划缺乏高效的线路设计，也未将时间延迟等情况考虑在内。能够针对顾客的要求进行特定时间段的配送，对于降低企业运输成本、改进客户服务质量具有重要意义。对企业而言，如何进行合理的路径规划是降低生产成本的合理方式之一[2]。
在实际配送过程中，顾客分布点不均匀，许多智能优化算法[3-7]被提出用来解决配送实际问题。遗传算法因极强的鲁棒性及收敛速度快，能够避免出现局部最优解；聚类算法在前期对客户点进行聚类则可以大大提高配送效率。因此，本文对遗传算法和聚类分析进行改进[8]，将二者结合起来建立数学模型，并运用算例分析验证其合理性和可行性。
一、数学模型建立
由于在实际情况中需求点分布失衡，导致在制定车辆路径方案时若仅根据以往工作人员经验会出现浪费时间和车辆的情况，尤其是在客户对于配送时间段要求比较高的时候，如何将货物准时送达是降低运输时间成本、提高顾客满意度所面临的重要挑战[9]。
本文建立的带软时间窗的车辆路径优化模型主要出于以下几方面考虑[10-11]：一是在顾客的规定时间进行货物配送可以提高配送环节的服务质量，提高顾客满意度；二是合理安排配送可以降低配送成本、提高配送效率从而带来更大的效益，在定量的时间内合理分配时间；三是使得车辆得到合理利用，用最大的负载率完成特定的任务，减少车辆空间冗余情况，同时缓解城市交通拥堵状况。
据此本文的VRPTW问题可以描述为：在软时间窗的条件下，针对不同客户定制不同的配送方案，使得满足车辆负载限制、交通情况等约束条件时总运输成本最低。
1. 基本假设及符号定义
基本假设：
(1) 配送为单向，即在商品运输过程中只进行配送，不提供其他服务。
(2) 每次配送要求从固定配送中心出发，开始和结束位置相同，所有车辆在完成若干客户的服务后必须返回相应的配送中心。
(3) 所有车辆的载重不超过负载能力。
(4) 所有车辆车种相同，且容量可知。
(5) 每个客户仅被服务一次。
(6) 每个客户都有一个指定服务时间[Ei，Li]，客户可接受在规定时间外服务，企业接受在规定时间外服务产生的惩罚成本。
(7) 客户需求量已知，该点货运只能由一辆车完成，且所有客户都获得该服务。
(8) 假定车辆配送成本即为车辆配送距离。
(9) 所有服务均不考虑服务时间。
(10) 假设路况均为顺畅，对车辆行驶不造成影响。
上述参数的符号定义如表1所示。
表1 参数符号及含义
符号含义K配送车辆,K=(1,2,…,k)c配送车辆单位距离运输成本n需要服务的顾客数量bk车辆K服务的顾客数量m实际用车数量qi客户i的配送量dij客户i与j之间的距离ti车辆从配送中心到客户点i的行驶时间tj车辆从配送中心到客户点j的行驶时间Q配送车辆的负载能力tij配送车辆在客户i与j之间的行驶时间Si配送车辆到达客户点vi的时间Ei、Li客户i的服务时间窗,Ei表示开始服务时间,Li表示结束服务时间Tk0车辆k的出发时间Tkr车辆k的要求返回时间M一个非常大的正常数Pi(Si)惩罚函数
如果车辆在客户要求时间Ei之前到达，则会产生等待成本；如果在Li之后到达，则需要支付一定罚金。惩罚函数Pi(Si)表示惩罚成本的高低，定义如下[12]：
(1)
式中，ai、bi表示惩罚系数。
2. 模型建立
本文模型目标是在配送过程中使运输成本最低，根据以上假设建立模型：
(2)
(3)
(4)
(5)
(6)
(7)
(8)
i∈j∈(1，2，…，n)，k∈(1，2，…，K)
(9)
ti+Si+tij-M(1-xijk)≤tj
∀i，j∈(1，2，…，n)，k∈(1，2，…，K)
(10)
(11)
(12)
(13)
式(2)为配送成本最小的目标函数；式(3)表示编号为k的车辆最大载重量不超过车辆的负荷；式(4)表示从配送中心一共出发了K辆车进行服务；式(5)表示每个客户只能由一辆车进行服务；式(6)表示车辆完成相应顾客服务后要返回配送中心；式(7)表示所有车辆配送的顾客之和等于有货物需求的客户总数；式(8)、(9)表示0～1决策变量x、y之间的关系；式(10)保证了车辆行驶路线的总耗时不超过预先设定范围，以满足客户对供货时间的要求；式(11)表示出发时间和返回时间均在设定时间范围内；式(12)表示VRPTW有向图的权重值，当编号为k的车辆途径客户i完成对客户j的服务时xijk=1，否则xijk=0；式(13)表示当客户i的服务由编号为k的车辆负责时变量yijk=1，否则yijk=0。
上述模型充分考虑了实际约束情况，接近实际问题，得到的解为全局解，对于解决具体问题有很好的借鉴作用。
二、相关算法概述
1. K均值算法概述
K均值算法是一种迭代求解的聚类分析算法，其优点是可以使数据形成类，从而快速对繁琐复杂的事物进行分类，使得相似度高的事物聚集到一起分为一类。本文使用的K均值算法是非系统聚类方法中常用的一种。
2. 遗传算法概述
遗传算法是启发式算法之一，与传统算法相比迭代速度更快，能避免时间上的浪费。遗传算法模拟自然环境中的物种进化过程来选择优良个体和保留部分变异，可以用于复杂问题的优化计算，具有实际应用价值[13-14]。在产生初始种群之后，根据优胜劣汰的原则使后代适应度越来越高。在每一代中，根据个体适应度的不同选择一些较为优良的个体，并在进化过程中参与交叉、变异，同时设定相应的交叉算子及变异算子来帮助产生下一代。待优化过程结束之后，可以产生新种群的最佳个体，这时得到的解作为实际问题的近似最优解。
三、算法实现操作
1. 聚类分析设计
聚类数目根据具体数据的车辆数确定。聚类完成以后，为了保证每个类中的需求总量不会超过每辆车的负载量，在每加入下一个客户时要检查货物总重量是否超过车辆负荷，若超过则将不满足条件的客户从此群中去除。此时被牺牲的客户为距离聚类中心最远的那个客户，对该客户继续采用聚类算法将其加入其他类中，直到没有客户被牺牲为止。具体步骤为[15-16]：
步骤1 在系统中导入原始数据文件，包含客户坐标、时间要求、车辆负荷等。
步骤2 计算需要的车辆数目，对客户进行分群，直到所有客户点都被分配。
步骤3 检查各群内的顾客总需求量是否超出车辆最大载重量。若超过则执行步骤4，否则执行步骤8。
步骤4 去除距离聚类中心最远且超过车辆负荷的客户，直到符合车辆负荷要求。
步骤5 检查其他客户群的车辆是否有剩余容量。如果有则执行步骤6，否则执行步骤7。
步骤6 将剔除的客户加入到距离最近且加入后不超过车辆最大容量的客户群，并执行步骤8。
步骤7 分配一辆车服务，回到步骤2。
步骤8 聚类完成，得到的编码即为遗传算法的配送中心点。
2. 遗传算法设计
(1) 编码设计。遗传算法通常使用二进制编码，但这种编码方式可能会在计算过程中出现无效解。因此本文采用自然数编码形式，这种编码方式对于路径优化来说能在很大程度上提高运算效率[17]。
当被服务客户数量为n，服务车辆数量为m时，整个染色体的长度为m+n+1，所有染色体表示为{0，…，S1，S2，0，S3，…，Sn，0}，其中Si表示第i个客户点，出现0的个数与配送货物所需车辆的数量有关。用0代表配送中心对各个路段进行划分，便于观察车辆的具体路径。
(2) 适应度函数设计。在遗传算法中，适应度函数值大小与染色体能否遗传到下一代具有重要关联[18]。本文所建立的模型以运输费用最低为目标，因此适应度函数为运输费用的倒数，运输费用越小，适应度函数值越大，可行性越高，其关系表达式为
ai=1/bi (i=1，2，…，g)
(14)
式中：ai表示个体适应度；bi表示第i个个体对应的运输费用；g表示种群规模。
(3) 选择设计。采用最佳个体保留策略和比例选择策略相结合的方法对选择算子进行设计[19]。选择方式如下：①根据适应度函数计算每个个体的适应度，然后根据数值降序排列，将排序后的个体平均分成3份[20]。②将处于排序前1/3的个体倍数增加。③处于中间1/3的个体直接复制。④处于排序后1/3的个体直接淘汰。当种群进化到后期阶段，直接采用最佳个体保留法，不再参加其余进化过程，提高种群优良性。
(4) 交叉。交叉操作的作用是在进化过程中通过染色体片段的交换来形成新的个体，降低对优良模式的破坏概率。本文采用顺序交叉法，确保前一代的优良个体能够顺利得到遗传，同时增加了个体多样性。例如：
A(136458792)→A′(1364|5879|2)→
A1(243158796)
B(279431865)→B′(2794|3186|5)→
B1(457931862)
(5) 变异。在遗传过程中会出现一定概率的基因突变。变异算子用来表示这种现象可能发生的概率，改变染色体中的基因片段，呈现出基因多样性[21]。本文采用逆转变异对染色体中的基因片段进行调整。该方法能够对种群中的变异进行适当调整，在一定程度上防止过早收敛的现象。例如：
A(136458792)→A′(13|645|8792)→
A1(135468792)
(6) 终止规则。作为一种随机搜索算法，遗传算法需要提前设定终止条件来保证在一定时间内结束迭代循环。本文设定为进化次数达到100则停止运算[22]。
四、仿真实验与性能分析
采用MATLAB2018a软件实现该算法对带时间窗的车辆路径优化问题的求解过程。为进一步验证两阶段算法的性能，与经典遗传算法的算法性能进行对比分析，使用Solomon数据集进行仿真测试。选取数据集r106，如表2所示。
表2 客户需求点
客户数X坐标Y坐标需求等待时间到期日服务时间035350023001414910020410235177020210355451301971045520191391691051530260199106253038911910720505019810…………………9920269731031010018181716519510
仿真过程中相关运算参数设定如表3所示。
表3 实验参数设置
实验参数意义实验数值c配送单位距离成本 2.00ai等待单位时间成本1.00bi延误单位时间成本1.50Q单位车载能力1000.00g种群大小400.00Pc交叉概率0.85Pm变异概率0.02
实验结果及相关对比如图1～3所示。图1表示实验数据在第一阶段聚类分析之后得到的初始聚类中心以及各分布点位置。
图1 客户位置分布
图2表示运用经典遗传算法运算得到的仿真路径。图3表示加入聚类分析并对遗传算法进行改进之后得到的仿真路径，从中可以看出改进的算法能够明显对需求点进行分类配送。
图2 经典遗传算法配送路线
图3 改进遗传算法配送路线
为验证两阶段算法在求解问题时的最优性，对两阶段算法求解结果与经典遗传算法进行对比，如表4、5所示。
表4 两阶段算法求得的最优解
序号客户数客户点访问顺序配送距离车辆载重等待时间延误时间1110-61-16-81-79-52-69-88-3-27-35-38-089.9318200260-71-67-93-62-31-25-076.2518400
表4(续)
序号客户数客户点访问顺序配送距离车辆载重等待时间延误时间3130-86-96-1-9-23-14-6-34-90-76-50-80-42-0113.4016800490-82-59-51-28-44-91-55-100-53-096.47182005110-74-72-95-97-15-30-64-47-99-2-68-0125.5218200680-38-18-36-41-85-10-63-78-075.3117800780-8-58-39-46-65-60-13-37-080.37193008100-75-49-5-94-92-40-22-87-56-17-068.09164009130-98-26-84-19-11-54-57-89-4-29-70-83-12-0109.801660010120-66-77-33-20-48-24-45-32-21-73-43-068.4318900合计100903.57178800
表5 经典遗传算法求得的最优解
序号客户数客户点访问顺序配送距离车辆载重等待时间延误时间1100-39-81-63-15-71-21-36-100-94-11-050.89168 0 02120-6-85-61-14-27-55-96-57-38-74-75-73-076.2518314303120-43-23-10-88-95-5-79-37-13-30-46-18-095.941790732.34110-31-20-60-68-32-35-44-58-89-4-92-056.1717600580-51-42-67-69-62-84-53-90-0137.781670242.5680-45-83-3-87-86-28-24-12-0109.26197007110-82-29-65-34-47-49-9-64-22-66-76-097.2316000890-16-77-70-99-48-80-97-40-17-076.071900784.6990-8-2-33-91-98-59-78-52-72-052.49188090.310100-54-93-25-26-19-1-50-7-56-41-0132.721802610合计100884.8017884041849.7
对比表4、5可以看出，本文采用两阶段算法求得的最优解相对于经典遗传算法在等待时间和延误时间上有明显优势，更符合带时间窗的车辆路径优化问题对时间窗的要求，提高了服务效率。
从Solomon数据集中另外选出4组数据进行仿真，得出实验数据如表6、7所示。对比可见改进算法可以明显优化计算结果。
表6 实验最优运行时间对比
参数运行时间1运行时间2运行时间3运行时间4运行时间5基本遗传算法18.5217.3217.7617.1118.03改进算法17.1017.2416.9417.2317.33
表7 实验最优运输成本对比
参数运输成本1运输成本2运输成本3运输成本4运输成本5基本遗传算法24632.3928153.2630141.2827843.2928561.87改进算法24080.6426967.8929681.5728031.7228403.62
五、结 语
为更好地解决物流配送中存在的顾客时间限制问题，本文提出将聚类分析和遗传算法相结合的两阶段算法并对其进行改进。使用Solomon数据集进行算例分析并进行对比，结果表明该算法在求解带软时间窗的车辆路径优化问题时具有良好的可行性，能够提供最优方案。
[1]徐剑，林国志.物流产业创新的途径与机制 [J].沈阳工业大学学报(社会科学版)，2016(6)：538-543.
[2]张春霞，彭东华.我国智慧物流发展对策 [J].中国流通经济，2013，10(6)：35-39.
[3]王晓东，薛明，齐兴敏.基于神经网络的配送路径优化算法 [J].物流技术，2015，34(18)：157-159.
[4]Chen S，Yang J，Li Y，et al.Multiple constraints network intensive vehicle routing adaptive ant colony algorithm in the context of neural network analysis [J].Complexity，2017(1)：1-9.
[5]陈果.改进遗传算法下的车辆路径问题研究 [J].电子测试，2016(3)：56-57.
[6]裴小兵，贾定芳.基于模拟退火算法的城市物流多目标配送车辆路径优化研究 [J].数学的实践与认识，2016，46(2)：105-113.
[7]Pu E L，Wang F.Hybrid differential evolution optimization for the vehicle routing problem with time windows and driver-specific times [J].Wireless Personal Communications，2017，95(3)：2345-2347.
[8]Yang Z W，Osta J P.Dynamic vehicle routing with time windows in theory and practice [J].Natural Computing，2017，16(1)：119-134.
[9]蒋洋，张星臣，周晓晔.考虑支线运输服务的多式联运网络优化 [J].沈阳工业大学学报(社会科学版)，2019(4)：338-343.
[10] 孟祥虎，胡蓉，钱斌.求解带时间窗车辆路径问题的有效混合PBIL算法 [J].系统工程理论与实践，2014(10)：2701-2709.
[11] 朱志勇，刁洪祥.基于改进遗传算法的车辆路径问题研究 [J].湘潭大学自然科学学报，2011(3)：115-118.
[12] 李军，郭耀煌.物流配送车辆调度理论与方法 [M].北京：中国物资出版社，2001：117-128.
[13] 高升.基于电动汽车的带时间窗的路径优化问题研究 [D].大连：大连海事大学，2015.
[14] 庞燕，罗华丽，邢立宁，等.车辆路径优化问题及求解方法研究综述 [J].控制理论与应用，2019，36(10)：1578-1583.
[15] 林郁丞.基于聚类分析和遗传算法的带时间窗车辆路径问题研究 [D].福州：福建农林大学，2009：33-34.
[16] 武秀佳.基于准时制的快速消费品物流配送研究 [D].北京：北京交通大学，2014：45-60.
[17] 黄敏芳，刘敬，郭琼.带时间窗的电动汽车物流配送车辆路径问题研究 [J].技术与方法，2019，38(5)：66-72.
[18] 任杰.车辆路径问题中的遗传算法设计 [J].东华大学学报(自然科学版)，2015(3)：89-90.
[19] 郭海湘，杨娟，马争艳，等.煤矿物资多车型配送的改进遗传算法求解 [J].运筹与管理，2011，20(2)：194-198.
[20] 高玉明，张仁津.一种GA-PSO算法优化BP网络的网络流量预测 [J].计算机应用与软件，2014，31(4)：106-110.
[21] 胡思继，郎茂祥.用混合遗传算法求解物流配送路径优化问题的研究 [J].中国管理科学，2012，10(5)：51-56.
[22] 李解，任魏翔，秦永彬.混合流水车间调度问题的IPSO算法 [J].计算机与数字工程，2016，6(6)：985-991.