基于启发式智能算法的多层网络路径规划研究

Multilayer Network Pathway Planning Research Based on a Heuristic Intelligence Algorithm

摘要: 为了确保物流周转效率和质量，应当借助互联网以及大数据的发展实现物流管理的优化提升，针对物流配送过程中存在的仓储布局、物流路线优化等问题，构建面向物流配送的多品种物流配送的VRP模型，采用改进的遗传算法对其进行求解，并通过实例进行验证。本课题拟将物流配送系统中的智能调度问题建模，并将其转换为一类基于启发式智能算法的物流网络路径优化问题，以物流调度需求为输入变量，以物流系统中的物流调度为目标，设计物流调度系统中物流系统的物流调度优化方案。通过对全国公路、铁路、水路三大交通网络的优化设计，使车辆从生产基地先运至前置仓库，再运至4S门店。针对以上问题，本文将构建以仓储位置为对象的图聚类模型，在物流费用与时间最优相矛盾且不能兼顾的情况下，构建多目标优化模型，并利用GPU并行遗传算法求解。

Abstract: In order to ensure the efficiency and quality of logistics turnover, the optimization of logistics man-agement should be realized with the help of the Internet and the development of big data. Aiming at the problems existing in the process of logistics distribution, such as warehousing layout and lo-gistics route optimization, a multi-variety logistics distribution VRP model for logistics distribution is constructed, which is solved by improved genetic algorithm and verified by an example. This top-ic intends to model the intelligent scheduling problem in the logistics distribution system, and transform it into a kind of logistics network path optimization problem based on heuristic intelli-gent algorithm, taking the logistics scheduling demand as the input variable, taking the logistics scheduling in the logistics system as the goal, design the logistics scheduling optimization scheme of the logistics system in the logistics scheduling system. Through the optimization design of the na-tional highway, railway and waterway transportation networks, the vehicles are first transported from the production base to the front warehouse, and then to the 4S stores. In view of the above problems, this paper will build a graph clustering model based on warehousing location. Under the condition that logistics cost and time optimization are contradictory and can not be taken into ac-count, a multi-objective optimization model is constructed and solved by GPU parallel genetic algo-rithm.

1. 引言

随着经济的快速发展，我国的城市化进程也在持续地推进，城市人口也在快速地增加，因此，我国的物流总量也呈现出了指数式的增长。要想保证物流周转的效率和质量，应该利用互联网和大数据的发展，来实现对物流管理的优化升级 [1] 。建设智能物流可以使物流运作与网络 [2] 紧密结合，使我国的物流事业进入到一个新的高度。

物流运输已经开始向着智慧型发展，它不但可以有更高的运输效率，而且还具备了及时处理和自我调整的能力。因此，在传统仓储中，将物联网技术运用到智能物流仓储管理系统中，可以提高货物进出效率，扩大存储的容量，降低人工的劳动强度，降低人工的成本，还可以实时显示和监控货物进出情况。智慧物流能够促进城市之间的甩挂运输、城市内部的联合配送等方式的落地；其次，基于数据驱动的智慧物流供应链能够促进城市供给、消费和商业渠道 [3] 等要素的资源优化配置。当前，在国内外先进的智慧物流系统中，已经开始将最新的光、机、电、信息等技术应用到其中，比如红外探测技术、无线通信技术、编码认址技术、RFID识别技术等。这些新技术给物流产业注入了新的动力，极大地提升了物流系统的运作能力，使传统物流朝着大型化、节能化、标准化、系统化、智能化和高效化的方向发展。

目前，我们所要研究的内容，主要集中在仓库选址和最优的运输路线上，此外，还应考虑相关的货物转运模式。在进行仓储选址时，可采用解析法、仿真法、k-means聚类等多种算法。本文将结合实际地理环境，基于少数已知数据对某些数据进行分类，并对迭代函数进行优化。因此利用聚类方法建立了一个以仓库选址为对象的图聚类模型，对配送中心进行了合理的选择。在路径优化中，采用了捕食搜索、粒子群、蚁群 [4] 、启发式遗传算法。该方法采用了一种新的优化方法，该方法直接使用了目标函数，具有很大的灵活性和很少受参数影响的特点。因此，在配送过程中，采用了一种基于启发式的智能算法来解决配送中心的选址问题以及配送路线的优化问题。

2. 前置仓选址

2.1. 模型的建立

多层图结构的弧集为 $A_f=A_1\cup A_2\cup A_3$ ，其中 $A_1$ 表示公路构成的弧集， $A_2$ 表示铁路构成的弧集， $A_3$ 表示水路构成的弧集，见图1 (只显示一线和新一线共十九个城市)所示。

Figure 1. Schematic diagram of multilayer diagram structure

图1. 多层图结构示意图

以下需要解决的问题可以描述为运输工具从三个前置仓出发向其所处类中的4S店运输所需车辆。为确定具体的前置仓以及其所负责的4S店，建立的聚类模型可表示如下：

1) 只考虑了一个生产厂(还兼做前置仓)，两个前置仓的情况。

2) 仅考虑了前置仓库对所属类别内的4S店供应的情况。

3) 最佳化指标与费用组成：由前置仓至车4S店的路程长平均运费单价与前置仓租金。

4) 只考虑了公路运输，没有考虑到各区域之间的费用差别。

5) 各前置仓库的仓储成本为一种固定的经营成本，与运输工具的数量没有任何关系。

以上约束条件，使得

$J_{\min }=\min {\displaystyle \underset{j\in C_{48}^2}{\sum }\left(\frac{{\displaystyle \underset{i=1}{\overset{a}{\sum }}{d}_{1i}^{A_{1j}}}}{a-1}+\frac{{\displaystyle \underset{i=1}{\overset{b}{\sum }}{d}_{1i}^{B_{1j}}}}{b-1}+\frac{{\displaystyle \underset{i=1}{\overset{c}{\sum }}{d}_{1i}^{C_{1j}}}}{c-1}\right)}$ (2-1)

$d_{1k}=\min \left\{d_{1k},d_{2k},d_{3k}\right\}$ (2-2)

$d_{i1}={\displaystyle \underset{m=1}{\overset{a}{\sum }}{l}_{i1}^1{p}_1}+{\displaystyle \underset{i=1}{\overset{b}{\sum }}{M}^i{S}^i}$ (2-3)

选择得分最低时的聚类情况作为最终的聚类结果。

2.2. 前置仓库选址的k-Means聚类算法的实现步骤

依据关于k-means [5] 的计算逻辑，并结合对于4S店智慧配送的实际情况，对全国主要城市(共49个)的4S店进行聚类分析。具体步骤为：

1) 确定数据 [6] 。本文的数据选取根据2023年最新数据，选择一线城市(4个)、新一线城市(15个)以及二线城市(30个)，共49个城市的4S店作为初始数据。

2) 选取初始聚类中心。为方便计算，初始聚类中心选取个数为3，将温州设置为生产仓库(作为其中一固定的聚类中心，可将其记为 $A_1$ )，即在聚类过程中只有两个聚类中心是变化的，这两个聚类中心在剩下的48个主要城市中任意选取。

3) 根据选取初始聚类中心，以各4S店之间的实际公路距离为聚类属性，将4S店按照距离的远近进行聚类。具体过程为：

① 将所选取的4S店依次编号 $A_1,\cdots ,A_n\left(1\le n\le 49\right)$ ，将i、j两地的实际公路距离记为 $s_{ij}^1$ (其中上角标1表示公路运输)，假定第一次选择 $A_1$ 、 $A_2$ 、 $A_3$ 分别为四个聚类的初始聚类中心，四个聚类分别记为 $G_1$ 、 $G_2$ 、 $G_3$ ，以 $A_1$ 作为第一个聚类(即 $G_1$ )的初始聚类中心为例，进行以下操作：

Step 1：通过实际最短公路距离 $l_{i1}^1$ 描述点 $A_i$ 与 $A_1$ 之间的路径关系，其中定义 $l_{ij}^1=0$ (当 $i=j$ 时)

Step 2：将各地之间的两两直接公路路径关系用矩阵进行表示，记为

${\left(s_{ij}^1\right)}_{49\times 49}$ $1\le i\le n,1\le j\le n$

Step 3：记 $l_{ij}^f$ 表示在第f种运输方式下从销售点i到销售点j的实际最短公路距离，在这里仅考虑 $l_{ij}^1$ (即公路运输下从销售点i到销售点j的最短距离)；记 $p_f$ 为第f种运输工具运输时的平均单价，在这里仅考虑 $p_1$ (即通过公路运输时的平均单价)；记 $m_i$ 为每个仓库(包括生产仓库和前置仓库)的租金单价(单位：元/m²)；记 $S^i$ 为每个仓库(包括生产仓库和前置仓库)的占地面积(单位：m²)。

② 查询并计算每个4S店分别到3个聚类中心的实际距离 $d_{ij}$ ，生成距离矩阵，两点之间的实际距离定义为：

$d_{i1}={\displaystyle \underset{m=1}{\overset{a}{\sum }}{l}_{i1}^1{p}_1}+{\displaystyle \underset{i=1}{\overset{b}{\sum }}{m}_i{S}^i}$ $\left(i=1,\cdots ,n\right)$

其中a表示车型数量，b表示仓库数量(包括生产仓库和前置仓库)。

③ 然后根据距各点到各初始聚类中心距离的远近进行排序，形成初始聚类。在每一类中，计算未分类的点分别到三个聚类中心的距离，记某一未参与分类的点为 $A_k$ ，比较 $d_{1k}$ 、 $d_{2k}$ 、 $d_{3k}$ 之间的大小关系，若

$d_{1k}=\min \left\{d_{1k},d_{2k},d_{3k}\right\}$

则 $A_k\in G_1$ 。

④ 重复①、②、③，直到所有城市全部聚类完成，对聚类后的点重新编号：

$G_1=\left\{A_1,A_2,\cdots ,A_a\right\}$

$G_2=\left\{B_1,B_2,\cdots ,B_b\right\}$

$G_3=\left\{C_1,C_2,\cdots ,C_c\right\}$

其中 $A_1$ 、 $B_1$ 、 $C_1$ 、 $D_4$ 为聚类中心计算本轮聚类情况的得分。定义聚类得分

$score\_j={\displaystyle \underset{i=1}{\overset{3}{\sum }}averageDistance\_ij}$

其中

$averageDistance\_1j=\frac{{\displaystyle \underset{i=1}{\overset{a}{\sum }}{d}_{1i}^{A_{1j}}}}{a-1}$

$averageDistance\_2j=\frac{{\displaystyle \underset{i=1}{\overset{b}{\sum }}{d}_{1i}^{B_{1j}}}}{b-1}$

$averageDistance\_3j=\frac{{\displaystyle \underset{i=1}{\overset{c}{\sum }}{d}_{1i}^{C_{1j}}}}{c-1}$

⑤ 将④重复 $C_{48}^2$ 次。

⑥ 比较score_j之间的大小关系，当 $score=\text{min}\left\{score\_j\right\}$ 时，将此时四个聚类中心作为最终的输出结果。

注意：当

$averageDistance\_ij=0$

(即本类中只有一个城市)时，舍弃第j种情况。

3. 车辆配送路径

3.1. 配送过程模型构建

用N表示4S店 $D_d$ 、前置仓库 $O_o$ 和生产基地 $Q_q$ 构成的点集；汽运、铁运、水运的交通运输线路构成图的弧集 $A_f$ ；f表示运输工具的种类(f取值为1，2，3分别代表公路、铁路和水路)；用 $m_{o_o}$ 表示前置仓库一个周期(月)的运营成本(单位：元)，用 $C^f$ 表示第f种运输工具的运载能力；用 $w_i$ 表示每个节点的总需求量， $w_i={\displaystyle \underset{k=1}{\overset{K}{\sum }}{w}_i^k}$ 。

忽略在配送过程中运输工具遇到的拥挤排队等不利于生产进行的外界因素，整个装配运送过程正常运行。

多层图结构的弧集为 $A_f=A_1\cup A_2\cup A_3$ ，其中 $A_1$ 表示公路构成的弧集， $A_2$ 表示铁路构成的弧集， $A_3$ 表示水路构成的弧集。 $l_{ij}^f$ 表示在第f种运输方式下从销售点i到销售点j的实际最短距离，货物从出发点到运输到目的路径由多段弧 $\left(i,j\right)$ 构成， $p_f^m$ 为第f种运输工具运输第m种车型的单价。

在多层有向图 $G=\left(N,A_f\right)$ 上考虑多车型配送问题 [7] ，配送方案须满足配送需求的情况下，使配送费用达到最小。

在配送过程中

1) 只考虑了1个生产仓(还兼做前置仓)、3个前置仓的情况。

2) 最佳化之目的与成本组成：从生产地至前置仓库之运费、从前置仓库至4S商店之运费、及前置仓库之房租。

3) 将一个月作为一个时间单元，并将生产基地的车辆出货周期(每月)与4S商店的需求周期(每月)相一致，根据产量和需求，对此期间的分配计划进行优化。

4) 前置仓库先进，后出，也就是从生产基地运来的商品先到前置仓库，然后才从前置仓库运出去。

5) 关于货物(车辆)约束，每个节点(需求站点)和运输车工具的流平衡关系，即对于节点i，所有运输工具运进该节点的货物(车辆)数量减去从该节点运出货物(车辆)的数量等于该节点的需求量。

6) 容量约束，限制每条运输路径(弧)上总流量不能超过所有运输工具所提供的总容量。

7) 每条配送路径上都只有同一种运输工具进行货物(车辆)配送，不能使用其他运输工具进行配送。

8) 货物出厂补货恒等约束，各个生产基地每种车型出厂数之和等于前置仓库每种车型补货数之和。

多层图结构的弧集为 $A_f=A_1\cup A_2\cup A_3$ ，其中 $A_1$ 表示公路构成的弧集， $A_2$ 表示铁路构成的弧集， $A_3$ 表示水路构成的弧集。 $l_{ij}^f$ 表示在第f种运输方式下从销售点i到销售点j的实际最短距离，货物从出发点到运输到目的路径由多段弧 $\left(i,j\right)$ 构成， $p_f^m$ 为第f种运输工具运输第m种车型的单价。

在多层有向图 $G=\left(N,A_f\right)$ 上考虑多车型配送问题，配送方案须满足配送需求的情况下，使配送费用达到最小 [8] 。

对于在弧 $\left(i,j\right)$ 上定义指示变量 ${\delta }_{ij}^f$ ：在弧 $\left(i,j\right)$ 上若选择了第f种运输方式，则 ${\delta }_{ij}^f=1$ ，否则 ${\delta }_{ij}^f=0$ 。定义 $N_i^{+}=\left\{j=N|\left(i,j\right)=A\right\}$ ， $N_i^{-}=\left\{j=N|\left(j,i\right)=A\right\}$ 智慧配送策略数学模型 [9] 为：

${\displaystyle \underset{j\in N_i^{-}}{\sum }{x}_{ij}^k-}{\displaystyle \underset{j\in N_i^{+}}{\sum }{x}_{ij}^k}=w_i^k\forall i\in D_d,\forall k\in K$ (3-1)

在实际计算中只考虑每个节点的总需求量 $w_i={\displaystyle \underset{k=1}{\overset{K}{\sum }}{w}_i^k}$

目标函数为最小化运输费用

$F\left(i\right)=\min {\displaystyle \underset{\left(i,j\right)\in A_f}{\sum }{\displaystyle \underset{k\in K}{\sum }{\displaystyle \underset{f\in F}{\sum }{l}_{ij}{x}_{ij}^k{p}_f^k}}}{\delta }_{ij}^f+{\displaystyle \underset{i\in O_o}{\sum }{m}_i}$ (3-2)

s.t.

${\displaystyle \underset{k\in K}{\sum }{x}_{ij}^k}\le {\displaystyle \underset{f\in F}{\sum }{u}_{ij}^f},\forall \left(i,j\right)\in A_f$ (3-3)

${\displaystyle \underset{f\in F}{\sum }{\delta }_{ij}^f}=1,\forall \left(i,j\right)\in A_f,{\delta }_{ij}^f\in \left\{0,1\right\}$ (3-4)

$x_{ij}^k\le {\displaystyle \underset{i\in O_o}{\sum }\left(s_i^k+r_i^k\right)},\forall k\in K,\left(i,j\right)\in A^f$ (3-5)

$d_i^k\le {\displaystyle \underset{i\in O_o}{\sum }\left(s_i^k+r_i^k\right)},i\in D_d,\forall k\in K$ (3-6)

$x_{ij}^k\ge 0,\forall \left(i,j\right)\in A_f,\forall k\in K$ (3-7)

3.2. 运费最低车辆路径问题遗传算法求解

通过以下方式解决多层图结构下的路径选择问题 [10] ：

Step 1：分别将公路运输、铁路运输、水路运输的路网数据进行矩阵表示，得到距离矩阵，记为A、B、C；

Step 2：根据运费=路径长度×运费单价计算得到公路运输、铁路运输、水路运输的运费矩阵，记为A'、B'、C'；

Step 3：用 $l_{ij}^f,f=1,2,3$ 表示在第f种运输方式下节点 $A_i$ 与 $A_j$ 之间的实际最短公路(铁路、水路)距离；

Step 4：

① 当从前置仓库向其所处类中的4S店运输时，仅考虑公路运输。在运输过程中运输媒介对被运输物品只关注其数量而不关注其类别与型号，只考虑每个节点的总需求量 $w_i={\displaystyle \underset{k=1}{\overset{K}{\sum }}{w}_i^k}$ ，通过不同运输方式运输(每种运输方式下只包含一种运输工具)时运输工具的容量记为 $C^f$ ，节点的最大需求量记为M，总的类别需求量记为 $M^G=\max \left\{M^{G_1},M^{G_2},M^{G_3}\right\}$ ，要求 $M\le C^1\le \frac{M_G}{2}$ ，同时假设 $C^2$ 、 $C^3\gg M^G$ 。

② 运输车辆的数量约束：(以 $G_1$ 为例)

根据聚类结果可知，最终得到的四个类的节点的集合分别为：

$G_1$ 、 $G_2$ 、 $G_3$

四个类中的每个节点的需求量分别记为 $w_{i_1}$ 、 $w_{j_2}$ 、 $w_{k_3}$ ， $i=1,2,\cdots ,a$ ， $j=1,2,\cdots ,b$ ， $k=1,2,\cdots ,c$

$A_1$ 是前置仓库，当运输车辆在某一路径上行驶时，不妨设该车辆负责并途径的4S店依次为 $A_2,\cdots ,A_k\left(k=2,3,\cdots ,a\right)$ ，这些4S店的需求量分别为 $w_{2_1},\cdots ,w_{k_1}\left(k=2,3,\cdots ,a\right)$ ，当 ${\displaystyle \underset{k=2}{\overset{k_1}{\sum }}{w}_{k_{1}1}}\le C^1<{\displaystyle \underset{k=2}{\overset{k_1}{\sum }}{w}_{k_{1}1}}+w_{k_1+1,1}$ 时，该车辆由 $A_{k_1}$ 沿 $A_{k_1}$ 与 $A_1$ 之间的最短路径直接返回 $A_1$ ，由新的运输车辆从 $A_1$ 开始沿第二条路径开始运输。故可同时有 $u_1$ 辆车从 $A_1$ 出发，最多可以有一辆车使得其满足一个节点的需求后所能容纳的货物量 $\ge \min \left\{w_{k_1}\right\},\left(k=2,3,\cdots ,a\right)$ 。 $G_2$ 、 $G_3$ 同理。

③ 从生产仓库向前置仓库运输时，仅比较生产仓库与前置仓库之间的公路运输和水路运输的运费矩阵B'、C'，选择运费较小的运输方式进行运输。

算法流程

遗传算法的流程包括：编码、种群初始化、适应度函数、遗传算子、交叉算子、变异算子等基本步骤。本节设计遗传算法 [11] 运算流程见图2所示。

Figure 2. Genetic algorithm flow chart

图2. 遗传算法流程图

1) 编码和解码

编码的过程就是通过设计基因将所研究问题中的决策内容转换为计算机可识别符号的过程，本文决策内容主要包括前置仓选择、顾客分配以及配送路径设计。在遗传算法中常见的编码方式有实数编码、二进制编码以及符号编码等，本文采用二进制和实数混合编码 [12] 。本文的车辆路径问题适合采用自然数编码来构造染色体，用数字“1”、“2”、“3”分别表示三个聚类中心，用“ $1,2,\cdots ,N$ ”来表示4S店，用“0”来分隔每辆车的配送路径，染色体中“0”的个数应为“车辆数 + 1”，用 $\left|X\right|$ 表示车辆数。

该模型编码情景可描述为：模型中有 $\left|I\right|$ 个前置仓可供选择、 $\left|J\right|$ 个顾客需要服务，所选前置仓需确保自己的配送服务能覆盖所有顾客群，因此整个编码过程涉及顾客分配以及配送路径设计 [13] 两个决策内容，算法对应两部分决策内容。模型中有 $\left|J\right|$ 个顾客需要服务，根据k-means聚类的结果可知所确定的前置仓分别为合肥、温州和中山，要求每个前置仓只负责其自己所处类中的4S店，故所选前置仓需确保自己的配送服务能覆盖所有顾客群。

因此，根据备选前置仓与顾客信息确定其对应的唯一数字ID码分别为1- $\left|I\right|$ 和1- $\left|J\right|$ ，并根据决策需求设计两部分基因序列，共 $\left(2\times \left|J\right|+\left|X\right|+1\right)$ 个基因。其中第一部分由 $\left|J\right|$ 个基因组成，表示各顾客被分配的前置仓，基因位置表示对应ID的顾客，基因值表示服务该顾客的前置仓ID，该部分采用自然数编码，取值范围为1- $\left|I\right|$ ；第二部分表示配送路径设计，每个基因表示一个顾客，基因值为顾客的数字ID，由于配送路径中不允许出现两个相同的顾客，因此采用排列编码，将2个数字“0”分别作为第三部分染色体的头部和尾部，剩余的“0”插入客户点数字排列“ $1,2,\cdots ,N$ ”之间，形成形如“ $0,1,2,0,3,4,5,0,6,\cdots ,N,0$ ”这样的染色体编码结构，通过每两个“0”之间的基因排列顺序来表示不同的设计路径。

2) 种群初始化

种群初始化是指由一种算法产生一个初始化问题的过程。该算法既能保证群体的多样性，又能保持算法的计算性能。对初始群体进行了随机排序，得到了一组随机染色体，然后用遗传算法对其进行了筛选。以随机产生的方法，尽可能保证种群内部的多样性，并避免种群中的“早熟”现象。一般情况下，种群的 NP值从10到200不等，在进行了多次的预试验后，我们把NP值设定为100。

3) 适应度函数

在种群进化的过程中，每一条染色体都对应可行解的编码。为了判定某一条染色体所代表的方案是否为最优解，必须建立一种适应度函数，并根据该函数对每条染色体的适应度值进行评估。本文中的目标函数为总成本最低，即总成本越低的染色体适应度越高，二者成负相关关系，所以，下面的适应性函数被设计出来：

$F_{fit}\left(i\right)=\frac{1}{F(\; i\; )}$

以上公式中， $F_{fit}$ 表示第i个染色体的适应度函数， $C\left(i\right)$ 表示第i个染色体通过计算得到的总成本值。根据反比例函数可知，方案的总成本越高，染色体的适应度越低。

4) 选择算子

在群体演化中，个体对其所处环境的适应值是有差异的，较高的适应值有利于其生存，也有利于其遗传信息的传递。在遗传算法中，通过对个体的适应值进行筛选，使其能够被遗传给下一代的个体被称为选择。

在选择运算开始前，为了避免最佳个体在代际间被淘汰，提出了一种“精英主义”的思想，在群体中设置多个不做任何变化的精英，并将其加入到子代中，从而使最佳个体不会在代际间被淘汰。尽管不能进行杂交，但是他们还是被选择作为对方的双亲，这样他们的基因信息就可以与群体内的其它个体共享。在此基础上，提出了一种新的优化方法，该方法将优化后的最优个体数量设为2，使整个群体的适应值按照一定的顺序从高到低，从中选出最优个体。

该算法以种群中的非精英个体为父代a，使用锦标赛选择方法来决定要进行交叉的父代b，也就是从种群中随机地选出几个个体参加锦标赛，并以最大适应性值的个体作为要进行交叉的父代b。这个演算法将参赛选手的数目设定为10个。

5) 交叉算子

在自然界中，一对染色体是由一对同源染色体交叉重组组成的。在遗传算法中，以一定的方法将某些基因进行交换，从而得到一个新的个体，这一过程被称为交叉。在算法的设计过程中，对不同的区域内的基因采取了不同的交叉方法。对第一部分的基因，采取单交的方法，也就是后代遗传父代a或父代b的基因概率相同；对于第二部分基因，也采取了单点交叉的方式。为了确保客户所分配到的前置仓是存在的，第一部分基因值需要以第二部分基因交叉的结果为依据来更新；第三部分的基因使用了多点交叉的方法，可以随机地产生两个不同的断点1和2，子代会直接继承父代a两个断点之间的基因，而子代的其他基因则会从断点2起，依次被父代b的基因填补，以确保不会有重复的基因。通常，交叉概率被设定在0.25~1.00之间，高的交叉概率可以扩展搜索范围，但也会提高已有解被打破的几率，而低的交叉概率则会降低算法的效率。交叉概率 $P_c$ 一般设置在0.25至1.00之间，高交叉概率可以扩大搜索区域，但是也会增加其破坏现有解的概率，而低交叉概率会使得算法的效率不高，通过预实验多次尝试，本文设定交叉概率 $P_c=0.9$ 。

6) 变异算子

变异是指生物的染色体上的基因发生了变异，可有效增加生物的多样性。在遗传算法中，交换操作虽然能够增加子代基因多样性，但其效果可能不明显，为进一步增加种群多样性，就需要进行变异操作。在算法设计中针对不同区域基因，采用不同方式进行变异操作。为保证顾客只能被分配给已建设的前置仓，第一部分基因值的变异方式为随机变异，即基因值随机变异成已建设的前置仓数字ID；对于第二部分基因采用随机交换的变异方式，即需要变异的基因随机与该部分其他基因进行交换完成变异。变异操作是向种群中添加新个体的一种重要方式，有利于增加种群中个体的多样性，防止出现种群早熟与陷入局部最优等情况的出现。交叉和变异两种方式本质上是从全局和局部对空间进行搜索。本算法中设置变异概率 $P_m=0.01$ 。

7) 终止条件

遗传算法是一种搜索算法，通过不断迭代，逐渐靠近最优解 [14] 。如果迭代次数太少，得到的解可能不是近似最优解；如果迭代次数太多，虽然能够在后期迭代过程中逐渐靠近最优解，但由于误差十分小，多次迭代对于解决实际问题意义不大，反而会造成运算时间过长和算力资源的浪费。设置终止条件的意义就是在迭代次数和解的优劣程度之间寻找平衡。本文在算法中设置最大迭代次数为1000次，终止条件为迭代次数已经达到设定的最大迭代次数。

4. 模型求解结果

4.1. 聚类结果说明

根据计算可知，中心城市组合总数为1128，在运行过程中，实际迭代次数为11次，每次的迭代结果见表1所示。

根据最终的运行结果，见图3所示可知。

(迭代中)最优得分：1129.8617407407407

(迭代中)最优中心：合肥，温州，中山

Table 1. Clustering results

表1. 聚类结果

Figure 3. Clustering visualization results

图3. 聚类可视化结果

即以温州为生产仓库(同时作为前置仓)，共选择三个聚类中心作为前置仓时的聚类中心分别为合肥、温州和中山。其中以合肥作为聚类中心时，该类所包括的城市有[“北京”、“成都”、“重庆”、“武汉”、“西安”、“郑州”、“长沙”、“天津”、“南京”、“合肥”、“无锡”、“哈尔滨”、“南昌”、“济南”、“宁波”、“大连”、“贵阳”、“石家庄”、“南宁”、“常州”、“珠海”、“南通”、“兰州”、“徐州”、“太原”、“烟台”、“廊坊”]；以温州作为聚类中心时，该类所包括的城市有[“上海”、“杭州”、“福州”、“厦门”、“长春”、“温州”、“泉州”、“金华”、“嘉兴”、“保定”、“台州”、“绍兴”]；以中山作为聚类中心时，该类所包括的城市有[“广州”、“深圳”、“青岛”、“苏州”、“东莞”、“沈阳”、“佛山”]。

4.2. 遗传算法计算结果与量化分析

49个城市中分别以温州为聚类中心进行聚类后每个类别的车辆路径可视化结果以及所需运费见下图4和图5所示，以中山为聚类中心进行聚类后每个类别的车辆路径可视化结果以及所需运费见下图6和图7所示，以合肥为聚类中心进行聚类后每个类别的车辆路径可视化结果以及所需运费见下图8和图9所示。

Figure 4. Freight under different iterations in Wenzhou

图4. 温州不同迭代次数下的运费

Figure 5. Visualization results of Wenzhou vehicle route

图5. 温州车辆路径可视化结果

Figure 6. Freight under different iterations in Zhongshan

图6. 中山不同迭代次数下的运费

Figure 7. Visualization results of vehicle path in Zhongshan

图7. 中山车辆路径可视化结果

Figure 8. Freight under different iterations in Hefei

图8. 合肥不同迭代次数下的运费

Figure 9. Visualization results of Hefei vehicle path

图9. 合肥车辆路径可视化结果

5. 结论

本文将遗传算法应用于求解多层网络下的车辆路径规划问题，实验结果表明，本文设计的遗传算法求解多层网络路径规划问题，解的质量很高，显示了良好的寻优功能，对解决类似的组合优化问题有一定的参考价值。