基于两阶段算法的带时间窗车辆路径研究

2020-07-01郭明顺

沈阳工业大学学报(社会科学版) 2020年3期

宿恺，赵洁，郭明顺

(沈阳工业大学管理学院，沈阳 110870)

物流作为电商的重要要素之一，在时间上制约了电商行业的发展。如何优化车辆路径、提高运输效率，是电商行业在物流环节急需解决的问题[1]。现阶段，许多车辆路径规划缺乏高效的线路设计，也未将时间延迟等情况考虑在内。能够针对顾客的要求进行特定时间段的配送，对于降低企业运输成本、改进客户服务质量具有重要意义。对企业而言，如何进行合理的路径规划是降低生产成本的合理方式之一[2]。

在实际配送过程中，顾客分布点不均匀，许多智能优化算法[3-7]被提出用来解决配送实际问题。遗传算法因极强的鲁棒性及收敛速度快，能够避免出现局部最优解；聚类算法在前期对客户点进行聚类则可以大大提高配送效率。因此，本文对遗传算法和聚类分析进行改进[8]，将二者结合起来建立数学模型，并运用算例分析验证其合理性和可行性。

一、数学模型建立

由于在实际情况中需求点分布失衡，导致在制定车辆路径方案时若仅根据以往工作人员经验会出现浪费时间和车辆的情况，尤其是在客户对于配送时间段要求比较高的时候，如何将货物准时送达是降低运输时间成本、提高顾客满意度所面临的重要挑战[9]。

本文建立的带软时间窗的车辆路径优化模型主要出于以下几方面考虑[10-11]：一是在顾客的规定时间进行货物配送可以提高配送环节的服务质量，提高顾客满意度；二是合理安排配送可以降低配送成本、提高配送效率从而带来更大的效益，在定量的时间内合理分配时间；三是使得车辆得到合理利用，用最大的负载率完成特定的任务，减少车辆空间冗余情况，同时缓解城市交通拥堵状况。

据此本文的VRPTW问题可以描述为：在软时间窗的条件下，针对不同客户定制不同的配送方案，使得满足车辆负载限制、交通情况等约束条件时总运输成本最低。

1. 基本假设及符号定义

基本假设：

(1) 配送为单向，即在商品运输过程中只进行配送，不提供其他服务。

(2) 每次配送要求从固定配送中心出发，开始和结束位置相同，所有车辆在完成若干客户的服务后必须返回相应的配送中心。

(3) 所有车辆的载重不超过负载能力。

(4) 所有车辆车种相同，且容量可知。

(5) 每个客户仅被服务一次。

(6) 每个客户都有一个指定服务时间[Ei，Li]，客户可接受在规定时间外服务，企业接受在规定时间外服务产生的惩罚成本。

(7) 客户需求量已知，该点货运只能由一辆车完成，且所有客户都获得该服务。

(8) 假定车辆配送成本即为车辆配送距离。

(9) 所有服务均不考虑服务时间。

(10) 假设路况均为顺畅，对车辆行驶不造成影响。

上述参数的符号定义如表1所示。

表1 参数符号及含义

如果车辆在客户要求时间Ei之前到达，则会产生等待成本；如果在Li之后到达，则需要支付一定罚金。惩罚函数Pi(Si)表示惩罚成本的高低，定义如下[12]：

(1)

式中，ai、bi表示惩罚系数。

2. 模型建立

本文模型目标是在配送过程中使运输成本最低，根据以上假设建立模型：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(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]。