基于遗传算法的配送中心路径优化问题分析

Optimization of Distribution Center Path Based on Genetic Algorithm

摘要: 配送路径的选择在物流成本中占据着很大的比例，本文针对配送中心满足客户需求时所选取路径，基于遗传算法进行深度优化，加入各个需求点的需求量及时间窗，在降低成本的同时最大程度提高客户满意度，结果表明该算法在解决需求点无序排列且带有时间窗问题的车辆路径方面问题有较高的精确性，具有一定的实用价值。

Abstract: The choice of distribution path occupies a large proportion in logistics cost. In this paper, the route selected by the distribution center to meet customer needs is deeply optimized based on genetic algorithm, and the demand and time window of each demand point are added to reduce costs, and maximize customer satisfaction. The results show that the algorithm has higher accuracy in solving the problem of disordered arrangement of demand points and vehicle path with time window problem, and has certain practical value.

1. 引言

VRP问题指车辆路线优化问题，一般而言，有一个或多个供应点，多个需求点有不同的货物需求，分析如何组织货车在这些需求点中进行配送从而达到总里程最小、配送时间最短、总成本最低等目标。VRP问题普遍被认为是NP问题(多难问题)，目前有许多关于该问题的研究，并衍生出了更多的相关问题，比如VRPTW问题(带时间窗的车辆路线问题)、CVRP (简单的车辆路线问题)、VRPDP问题(追求最佳服务时间的车辆路线问题)等等。

关于VRPTW问题最早提出的是Solomon [1] 的启发式算法研究，随后有更多学者对该问题进行了深入的研究，Paessens [2] 为了降低该问题的复杂度，使用了更加简单的结构体系，Wee-Kit [3] 通过对启发式算法进行深入研究，利用多种启发式算法的进行组合寻求近似最优解。Ombuki [4] 分别将最短时间和最少车辆定为优化目标，使用遗传算法和禁忌搜索算法对该目标进行了求解，并发现该组合算法的求解结果优于各种单一算法的运算结果。谢秉磊 [5] 通过设立不同的约束条件设计出了能够同时解决软时间窗约束和硬时间窗约束的遗传算法。张丽萍 [6] 等人通过交叉算子，提出了改进遗传算法，在某种程度上能够有效避免局部最优的现象出现。张海刚 [7] 使用改进免疫遗传算法，实现了带硬时间窗的车辆调度问题的优化改进。杨宇栋 [8] 引入客户直接排列的解的表示方式，改进了模拟退火算法，提高了求解VRPTW问题的效率。吴勇民将我国现行的生鲜农产品网络配送网络与其他国家进行比较，找出缺点，提出问题，并提出了一种新的物流模式。高斌、张仁顾 [9] 在针对物流中心选址问题上提出了更加全面的选址方式，更加贴合实际，加入了更多的影响决策的因素，并建立出了非线性规划模型，将多种方法进行了混合，从性质和数量上都进行了考虑，建立了更加完善的选址方式。索志林、王栋 [10] 在针对生鲜农产品在配送过程中的表现性质，提出了腐烂函数这个概念，并通过大量的实践，提出了生鲜农产品在相同条件下时间对生鲜农产品自身价值的数学模型，并进行了证明。史晓原 [11] 根据生鲜农产品的固有特性，并参照相关腐烂函数，对其与时间的关系进行了分析，发现了他们之间的规律，并建立了数学模型，以最低成本，降低货损率为目标，进行了分析，并使用遗传算法进行了相关计算，并得出了相关的优化方案。李明泽 [12] 针对城市内农产品车辆路径问题进行了探讨，根据运输货物的特性对配送路线进行优化研究。姜大立 [13] 构造了车辆路径问题的染色体表达，并以此建立了相关模型证明遗传算法是求解该问题的较好方案。钟惟钰 [14] 通过对传统遗传算法求解过程进行分析后，发现收敛速度较慢，尝试采用新的双层编码方式对种群进行优化，提高了遗传算法运行时的收敛速度。周艳聪 [15] 同样是针对车辆路径问题的遗传算法的收敛速度进行改善，通过对交叉算子引入局部竞争择优机制保证种群的多样性，减少相似个体的出现。金仙力 [16] 利用遗传算法对多目标路径优化问题进行探索，有效解决了服务点有序且带时间窗约束条件的车辆路径问题。

本文以某市配送中心为例，将所需要满足的各个需求点抽象为一个点，假定每个需求点的需求量可一次配送满足，每个需求点对应不同的需求重量以及对应的体积和时间窗约束，加入时间窗惩罚机制，并将惩罚成本加入到配送成本，同时考虑每个配送车辆的固定费用，以最小成本为最终优化目标，探究基于遗传算法的带有时间窗约束的车辆路线问题。

2. 问题描述

本文采用石家庄某物流企业所急需解决的问题作为优化目标，将其企业提供的基础数据输入程序，由于该市物流企业当前物流成本过高，客户满意度极低，使企业进入亏损状态，该物流企业的配送中心共有2个，共有需求点18个，每个配送车辆的固定费用为150元，速度为40 km/h，每辆车每公里费用为15元，超过每个客户要求的时间窗后每个小时的系数为1000，每个客户的服务时间为15分钟，加入对每个配送车辆负重空余的惩罚系数以及配送车辆的体积限制。该企业的配送中心以及需求点如图1所示。

Figure 1. Distribution point and demand point location

图1. 配送点与需求点位置

并建立优化模型如下：

目标函数：

$\min f=50\ast \underset{i=1}{\overset{z}{{\displaystyle \sum }}}\left(\text{volume}-W_i\right)+15\ast \underset{i=1}{\overset{z}{{\displaystyle \sum }}}{D}_i+Z\ast 150+1000\ast \underset{r=1}{\overset{n}{{\displaystyle \sum }}}{T}_r$ (1)

约束条件：

${\displaystyle {\sum }_{i=1}^z{\displaystyle {\sum }_{r=1}^n{a}_{ir}}}=1$ (2)

$W_i=w_i\ast a_{ir}$ (3)

$D_i=di{s}_{oi}+{\displaystyle {\sum }_{i=1}^n{\displaystyle {\sum }_{p=1}^n{d}_{ip}}}+di{s}_{po}$ (4)

$t_r=\frac{di{s}_{oi}+a_{ir}\ast {\displaystyle {\sum }_{i=1}^n{\displaystyle {\sum }_{p=1}^n{d}_{ip}}}}{v}+0.25$ (5)

$T_r={\displaystyle {\sum }_{i=1}^r{b}_i\left(\text{timewindow}-t_r\right)}$ (6)

$W_i\le \text{volume}$ (7)

$a_{ir}\ast {\displaystyle {\sum }_{i=1}^n{v}_n}\le Vol$ (8)

$a_{ir}$ 表示第r个需求点是否在第i条配送路线中，等于1时表示在该条路线上，等于0时表示不在该条路线上；

$W_i$ 表示第i条配送路线上的需求点所需配送货物的重量之和；

$D_i$ 表示每条配送路线的距离；

$di{s}_1$ 表示从起点出发的距离；

$d_{ip}$ 表示同一条路线上各个需求点之间的距离；

$di{s}_{oi}$ 表示车辆从配送中心o到达第一个需求点i的距离；

$di{s}_{po}$ 表示从最后一个需求点返回配送中心o的距离；

$b_i$ 表示配送车辆到达需求点时是否满足客户要求的时间区间，等于1时不满足，等于0时满足客户要求的时间区间；

$t_r$ 表示每个需求点配送车辆的到达时间；

timewindow表示用户满意的达到时间的区间；

volume表示配送车辆最大货物负载；

$v_n$ 表示同一条配送路线上各个需求点所需货物体积的总和；

V表示配送车辆最大可容纳的货物体积。

(2)表示每个需求点都在配送路线中，且只由一辆配送车辆进行配送，(3)表示第i条配送路线上的需求点所需配送货物的重量之和，(4)每条配送路线的距离，(5)表示每个需求点配送车辆的到达时间，(6)通过将到达时间与用户要求到达时间进行对比，(7)表示该配送路线未超过车辆额定载重，(8)表示配送路线上个需求点的货物体积值之和未超过配送车辆最大可容纳的货物体积。

3. 遗传算法运算

遗传算法主要通过五个步骤对复杂问题进行运算，包括编码、适应度函数、选择、交叉、变异从而得到最接近最优解的近似解，能够对非线性目标问题进行优化，同时对多个个体进行计算，有效避免陷入局部最优的情况出现。

(一) 编码

通过将目标个体转化为染色体的形式并以字符串表示，将该染色体放置在约束条件所形成的解空间中进行运算。编码直接决定了后续步骤的实现方法，常用的编码方法包括Grey编码、实数编码、多级参数编码等等。本论文采用的是实数编码，不需要进行编码的转换。

(二) 适应度函数

适应度函数是评价群体中个体好坏的标准，是进行自然选择的唯一依据，一般是由目标函数加以变化得到，根据求解最大值还是最小值问题的不同，适应度的选择也不同。

如6，3，11点需求量分别为4，1，2吨，车辆负重为6吨。

当配送路线计算到11时，超过负重上限，此时得到第一条配送路线，对比第一个需求点与哪个配送中心的距离最接近后，以此为起点，同理寻找返回的配送中心点，并计算其里程，从点11开始计算第二条配送路线，重复上述过程。

(三) 选择操作

选择操作是从就群体中选择优良个体组成新的种群，得到下一代种群，个体的选择概率与适应度相关，个体适应度值越高，被选中的概率越大。遗传算法选择操作有轮赌盘法、锦标赛发等多种方法。

(四) 交叉操作

交叉操作指从种群个体中最近选择两个染色体，通过两个染色体的交换组合，把优秀的基因遗传给子代，从而产生新的优秀个体。因为个体采用实数编码，所以交叉操作采用实数交叉法，第K个染色体 $a_k$ 和第L个染色体 $a_l$ 在j位的交叉操作方法，b为[0,1]区间的随机数。

随机生成2个染色体如下：

4 12 6 7 2 5 10 14 13 19 3 8 11

3 12 13 9 5 4 14 6 11 10 78 1 2

随机生成[0,1]之间的数，当这个数字小于交叉概率Pc时，与临近的染色体进行交叉，例如为0.3，然后在[1,5]之间随机选取一个整数为1，就从染色体中位于第一位的基因进行交叉，将两者找到相同的基因进行交换得到：

|3|126 7 2 5 10 14 13 1 9 |4| 8 11

|4|12 13 9 5 |3|14 6 11 10 7 8 1 2

然后从第二位的基因继续进行交换，循环10次，从而得到交叉之后的染色体，并将产生的个体存储到子代的种群中，然后对产生的子代进行适应度计算，当子代的适应度比父代要差时，保留父代，保证不会出现退化解。

(五) 变异操作

变异操作的主要目的是保持种群多样性。变异操作从种群中随机选取一个个体，选择个体中的一点进行变异从而产生更加优秀的个体，统称下一代的群体为子代，上一代群体为父代。

将交叉后的子代进行变异操作，随机生成[0,1]之间的数，当其取值大于变异概率Pm时，对该染色体进行变异操作，随机生成一个数组，将该数组的第一位和第二位的数字所对应的交叉后产生的染色体的基因的位置进行调换。

(六) 终止条件

一般情况下，有以下几种情况发生时计算会停止：达到目标时，达到设置的时间，达到设置的迭代次数，在相同多代内没有任何变化时，系统自动停止。本文使用的方法是设置规定的迭代次数，当未达到最大次数时会重复上面的运算，然后选择适应度最好的个体进行输出。

4. 用遗传算法研究配送中心路径问题

其配送中心的坐标分别为(40,50)、(60,40)，其他需求点的具体情况如下图2、图3所示。其中需求点的时间约束条件如表1所示。

Figure 2. Demand of distribution points and distribution time requirements

图2. 配送点需求量及配送时间要求

Figure 3. Distribution of distribution point distance from demand point

图3. 配送点距需求点距离分布

Table 1. Demand point time constraint

表1. 需求点时间约束

各个需求点距离配送中心的距离如图3所示，如果与配送中心1的距离小于配送中心2的距离第三列为1，否则为2。

在求出各个配送点之间的距离之后，使用matlab进行计算，设定种群大小为150，迭代次数为200次，交叉概率为0.8，变异概率为0.3。

通过运算，迭代过程如图4所示。

Figure 4. Calculation process

图4. 迭代过程

得到优化后路线如表2，表3所示。

Table 2. Before optimization

表2. 优化前路线

Table 3. After optimization

表3. 优化后路线表

优化前、后路线如图5、图6所示。

Figure 5. Pre-optimization roadmap

图5. 优化前路线图

Figure 6. Optimized roadmap

图6. 优化后示意图

优化前该市配送中心一共需要8辆车，但很大程度上无法满足需求点的时间窗要求，加入惩罚成本后，总成本为64,124元，在通过是用遗传算法进行优化之后，不仅没有增加车辆的使用，而且能在很大程度上满足客户对于时间的要求，加上时间窗惩罚成本后总成本为24,541元，在配送成本上有显著的降低，达到了对配送中心配送路线优化的目的。

5. 结论

本文利用了遗传算法的全局性和自适应性对NP问题的最优解进行寻找，以石家庄市某物流企业所提供数据作为基础数据，着重考虑用户的满意度，在相同成本的基础上，尽可能的满足客户的需求，通过建立模型并进行求解，科学地规划配送路线，将优化前后的路线方案进行对比，结果表明获得了较好的优化方案。

本文目前只针对企业较突出的问题进行研究，未来会通过加入更多约束条件和优化算法完善内容，比如应用神经网络算法、数据分析模型进行需求预测，帮助提前安排用车，利用改进的遗传算法提高路径优化效率等。

基金项目

石家庄铁道大学青年项目(Z6612536)。