两级车辆路径问题的离散差分进化算法

彭鹏+李彬哲+付雪薇+汪恭书

A Discrete Differential Evolution Algorithm for Two-echelon Vehicle Routing Problem

PENG Peng， LI Bin-zhe， FU Xue-wei， WANG Gong-shu

摘 要：针对广泛存在于现代物流配送过程中的两级车辆路径问题，在考虑配送服务耦合性特征的基础上建立了以总成本最小为目标函数的整数规划模型，并提出了求解问题的离散差分进化算法。在离散差分进化算法框架中，采用贪婪算法产生初始解，对一级和二级网络分别进行编码，然后进行变异和交叉操作，并在二级网络求解的基础上求解一级网络。文章采用随机产生的算例对算法求解效果进行验证。结果显示，所建的模型和算法正确有效，在求解大规模问题时也能够获得相对较好的优化结果。

关键词：两级车辆路径问题；混合整数规划；离散差分进化

中图分类号：U116.2 文献标识码：A

Abstract： This paper studies a two-echelon vehicle routing problem that is widely existed in the distribution process of the modern logistics system. By considering the coupling characteristics of distribution service， the problem is formulated as an integer programming model with the objective of minimizing total distribution cost， and a discrete differential evolution algorithm is proposed to solve the model. In the framework of discrete differential evolution algorithm， we encode the first and second network individually， then use greedy algorithm to get the initial solution. The next step is variation and cross. The solution to the first network is based on the second. The proposed algorithm is tested by a random example. The results show that the proposed model and algorithm are correct， and can obtain high-quality solutions.

Key words： two-echelon vehicle routing problem； integer programming； discrete differential evolution algorithm

0 引 言

经典的车辆路径问题大多假设单级配送，即由配送中心直接向顾客配送物资。但是由于政府部门对大型车辆的管制，从配送中心必须先到达各个中转站，然后再送给各个顾客，这样就形成了两级车辆路径问题（2E—VRP）。在文献[1]中首次提出了2E-VRP问题的数学模型，应用分支—割平面算法求解；文献[2]采用特殊的分支—割平面算法求解2E—VRP，取得了较好成果；文献[3]采用了自适应大规模邻域搜索算法改进了初始解，平衡了结果的质量和求解时间。本文采用离散差分进化算法对此问题进行求解，实验结果表明，该算法能够获得高质量的解。

1 问题描述和数学模型

两级车辆路径问题结构如图1所示，在两级配送网络中，第一级为从配送中心运送货物至中转站，然后再从中转站运送到顾客。因此，在车辆路径问题中，已知配送中心、中转站的位置和容量、顾客的位置和需要的货物，需要确定各个顾客分别由哪个中转站服务、每个中转站由哪个配送中心供货，并设计相应的车辆行驶路径，使车辆行驶成本之和为最低。

下面我们给出两级车辆路径问题参数和变量的定义[4]：配送中心集合N■，中转站集合N■，顾客集合N■，顾客i的需求量q■i∈N■，m■j∈N■表示配送中心j拥有的车辆数量，m■k∈N■表示中转站k拥有的车辆数量，B■表示中转站k的容量，M■表示经过配送中心j的一级路径集合，R■表示经过中转站k的二级路径集合，c■表示二级路径l的费用，c■表示一级路径l的花费。定义x■和y■为0-1决策变量，对l∈R■， k∈N■，x■=1表示二級路径l被选择，否则x■=0，对l∈M■， j∈N■，y■=1表示一级路径l被选择，否则y■=0。基于上述定义，两级车辆路径问题可以表示为以下整数规划模型：

minz=■■c■x■+■■c■x■ （1）

s.t.

■■x■=1， i∈N■ （2）

■x■≤m■， k∈N■ （3）

■■q■x■≤B■， k∈N■ （4）

■y■≤m■， j∈N■ （5）

■q■=■■q■x■， j∈N■， k∈N■ （6）

式（1）为目标函数，目标为两级物流网络成本最小，式（2）表示顾客i能且只能被访问一次，式（3）表示中转站k使用的车辆不能超过其所拥有的数量，式（4）表示中转站k运输的货物总量不能超过其容量，式（5）表示配送中心j使用的车辆不能超过其所拥有的数量，式（6）表示中转站运入的货物总量等于其运出的货物总量。

2 差分进化算法

本文提出了离散差分进化算法对两级车辆—路径问题进行求解。差分进化算法（DE）是一种用于最佳化问题的后设启发式算法。本质上说，它是一种基于实数编码的具有保优思想的贪婪遗传算法。

离散差分进化算法采用自下向上的求解过程，在每一次迭代过程中首先对二级配送网络中配送路径进行求解，然后根据二级配送网络求解结果，求解一级配送网络的配送路径。

2.1 编 码

由于2E—VRP包含多个子问题，并且本文提出的离散差分进化算法采用自下向上的求解过程，因此在解编码方式选择上，本文将一级配送网络与二级配送网络分别用相同的方式进行编码来表示解向量。

本文采用的是实数编码方式，以二级配送网络为例。对每一个中转站分别进行编码，该编码包含有编号为1，2，…，c的c个需求点以及若干个0表示路径分割。图2为某一中转站的编码示意图。

该网络编码可转换为3条路径：

路径1：某中转站→22→8→7→27→该中转站

路径2：某中转站→16→19→6→24→14→该中转站

路径3：某中转站→20→28→该中转站

2.2 算法步骤

初始化：

在初始化过程中需要生成两级配送网络初始解，本文采用贪婪算法生成初始解。

第一阶段利用贪婪算法搜索构造第二级配送网络解向量，第二阶段根据上一阶段生成的第二级配送网络解向量，采用相同的方法构造第一级配送网络解方案。

以二级配送网络为例，贪婪随机初始化具体步骤如下。

步骤1：将需求点分配给距离其最近的备选中转站。

步骤2：根据需求点分配结果，检查所有中转站服务的需求点是否超过该中转站的容量。

步骤3：若有中转站服务的需求点超过其容量，将最后一个分配到该中转站的需求点分配到距离其次近的中转站。

步骤4：根据需求点分配结果，检查所有中转站的服务的需求点是否超过该中转站的容量。如果都没有超过，则初始化结束。否则返回步骤3。

变异：

利用随机数产生变异的位置，例如对图3进行变异操作，假设随机产生的交换的两个位置是3和4，变异过程如图3所示。

交叉：

步骤1：随机选择切点c■，c■。

步骤2：交换中间部分。

步骤3：从第二个切点c■后，第一个基因起列出原顺序，去掉已有基因（注意0的个数）。

步骤4：从第二个切点c■后，第一个位置起，将获得的无重复顺序填入。

我们将上面的原个体和变异个体进行交叉操作，假设我们随机产生的c■、c■为4和6，交叉操作如图4所示。

3 实验分析

本文采用随机生成的2E—VRP算例来对离散差分进化算法进行求解验证。算法在Intel（R）Core（TM）i7—4720HQ CPU、4GB RAM、Windows10操作系统环境下，使用MATLAB编译运行。该算例需求点数量为50，需求量为1，中转站10个，容量10，每个拥有的车数量3辆，车的容量为5，配送中心3个，容量为30，每个拥有的车数量3辆，车的容量为10。离散差分进化算法框架部分所含参数包括：最大进化代数，变异概率，交叉概率，种群规模，在这里分别设置为100，0.5，0.9，200。求解结果如图5所示。

4 结 论

针对两级车辆路径问题，建立了以一级、二级配送网络总成本最小为目标函数的混合整数规划数学模型，考虑了一级配送中心、二级中转站容量约束，一级、二级配送车辆容量約束。并提出了离散差分进（下转第13页）