基于遗传算法的物流车辆配送路径优化模型

Logistics Vehicle Routing Optimization Model Based on Genetic Algorithm

摘要: 物流车辆路径优化是提高配送效率和缩减运输开支的核心问题。针对传统方法在处理复杂约束时易陷入局部最优的不足，本研究提出一种基于遗传算法的单目标与多目标物流车辆路径优化模型。单目标模型以最小化参与配送车辆的最大运输距离为目标，多目标模型进一步引入碳排放约束，综合考虑运输成本与环保需求，通过加权求和法将双目标转化为单目标求解。采用整数编码与锦标赛选择策略设计遗传算法，结合贪心初始化与动态调整机制提升解的可行性。实验结果表明，单目标模型将最大运输距离优化至25.79 km，多目标模型在权重系数为0.6时实现总运输距离100.42 km与碳排放86.65 kg的均衡解。本研究为绿色物流提供了兼顾效率与环保的路径优化框架。

Abstract: Vehicle routing optimization is a core issue in improving logistics efficiency and reducing transportation costs. To address the limitations of traditional methods in handling complex constraints, this study proposes a single-objective and multi-objective vehicle routing optimization model based on genetic algorithms. The single-objective model minimizes the maximum transportation distance of delivery vehicles, while the multi-objective model introduces carbon emission constraints and balances transportation costs with environmental requirements through weighted summation. An integer encoding scheme and tournament selection strategy are designed, combined with greedy initialization and dynamic adjustment mechanisms to enhance solution feasibility. Experimental results show that the single-objective model reduces the maximum transportation distance to 25.79 km, and the multi-objective model achieves a balanced solution of 100.42 km total distance and 86.65 kg carbon emissions when the weight coefficient is 0.6. This study provides a framework for green logistics that integrates efficiency and environmental protection.

1. 引言

作为现代经济的重要支柱，物流配送效率的高低直接影响企业运营成本与服务质量。车辆路径问题(VRP)旨在合理规划车辆行驶路径以满足客户需求并优化资源分配，是物流领域的研究热点。传统方法在处理复杂约束时易陷入局部最优，而遗传算法(GA)凭借其全局搜索能力，成为解决VRP的有效工具。

现有研究多聚焦单一目标优化，忽视环境因素(如碳排放)。本文综合考虑运输成本与环保需求，提出多目标优化模型，为绿色物流提供理论支持。遗传算法的鲁棒性与自适应性为复杂约束下的路径规划提供了新解法[1]。

2. 问题描述与假设分析

2.1. 问题描述

某地区物流网络位置示意图如图1所示，该物流网络包含1个配送中心，8个需求点(坐标见表1)，在配送中心有3辆可供调配的车辆，每辆车的载重上限为20吨。8个需求点的需求量总和为31吨，需要合理安排车辆和路线。同时，我们的目标是使参与配送车辆的最大运输距离最小化，即平衡各车辆的配送负担，避免某辆车行驶过长的距离。规划配送车辆的最优行驶路径，使其以配送中心为起点出发，依次访问各客户，最后再回到配送中心，3辆载重20吨的车辆需满足各点需求量(见表2)，且每辆车仅出发一次。

Table 1. Coordinates of distribution centers and demand points (unit: km)

表1. 配送中心、需求点的坐标(单位：km)

i	0	1	2	3	4	5	61	7	8
x	8.3	3.1	11.8	16.4	11.6	9.2	2.6	1.4	7
y	9	2.5	1	7.1	11.3	17	15.8	10.3	5.2

注：其中i = 0表示配送中心，i = 1，2，……，8表示8个需求点。

Table 2. Daily demand of demand points (unit: t)

表2. 需求点每天的需求量(单位：t)

需求点	1	2	3	4	5	6	7	8
需求量	4	5	3	2	6	3	2	6

Figure 1. Schematic diagram of the locations of the distribution center and the demand points

图1. 配送中心与需求点的位置示意图

2.2. 假设分析

在配送车辆有限的前提下，做出适当的假设(见表3)并解决以下问题：

1) 以参与配送车辆的最大运输距离最小化为优化目标建立数学建模，并开发求解算法。

2) 考虑不同配送车辆在配送过程中排放CO₂等有害气体的不同，建立以总的有害气体排放最少、总的运输距离最小为目标的优化模型，并给出求解算法。

Table 3. Hypothetical contents

表3. 假设内容

假设方案	假设内容
1	车辆行驶速度不变，不计交通拥堵等因素对行驶时间的影响
2	车辆在装卸货工作中的耗时忽略不计
3	不同车辆的单位运输成本相同，忽略车辆类型差异对成本的影响
4	有害气体排放量与车辆行驶距离呈正比关系，且不同车辆的排放系数可根据其类型确定
5	每辆车一天最多只装一次货，每次装载量不超过20 t
6	每个客户一天仅由1辆车提供服务

3. 模型构建

3.1. 单目标优化模型

3.1.1. 参数定义

将配送中心设为编号0，用英文字母$m$ 表示配送车辆数量；$\text{n}$ 表示配送点数量(包括配送中心)；$i，j$ 来表示需求点($i，j=0,1,2，\cdot \cdot \cdot ，n$ )；$k$ 表示配送车辆($k=0,1,2,\cdot \cdot \cdot ,m$ )。模型参数及定义如表4所示。

Table 4. Parameter symbols and their definitions

表4. 参数符号及其定义

参数符号	定义
$d_{ij}$	需求点$i$ 到需求点$j$ 的欧式距离
$d_j$	需求点$j$ 的需求量
$q_k$	车辆$k$ 的装载量

3.1.2. 决策变量

对决策变量的规定如下：

$x_{ij}^k=\{\begin{array}{l}1,配送车k从需求点i行驶到需求点j\\ 0,配送车k不从需求点i行驶到需求点j\end{array}$

3.1.3. 目标函数建立

使参与配送车辆的最大运输距离最小的目标函数为：

$\min Z_1=\underset{1\le k\le m}{\max }\left({\displaystyle \sum }_{i=0}^n{\displaystyle \sum }_{j=0}^n{d}_{ij}\cdot x_{ij}^k\right)，\left(k=1,2,\cdot \cdot \cdot ,m\right)$ (1)

3.1.4. 约束条件设定

1) 客户需求约束——每个需求点有且仅有一辆车访问[2]；

2) 路径连续性约束——车辆以配送中心为起点并最终返回配送中心；

3) 车辆容量约束——车辆装载量限制。

3.2. 多目标优化模型

3.2.1. 参数、决策变量和约束条件

在保持上文单目标优化模型中定义的参数(3.1.1)、决策变量(3.1.2)和约束条件(3.1.4)不变的情况下，增加$e_k$ 作为车辆$k$ 的单位距离，$C{O}_2$ 排放量(kg/km)作为新参数。

3.2.2. 目标函数建立

1) 总的运输距离函数：

$Z_2={\displaystyle \sum }_{k=1}^m{\displaystyle \sum }_{i=0}^n{\displaystyle \sum }_{j=0}^n{d}_{ij}\cdot x_{ij}^k$ (2)

2) 总$C{O}_2$ 的排放量函数：

$Z_3={\displaystyle \sum }_{k=1}^m{\displaystyle \sum }_{i=0}^n{\displaystyle \sum }_{j=0}^n{d}_{ij}\cdot x_{ij}^k\cdot e_k$ (3)

3) 运用加权求和法将双目标转化为单目标问题即可实施单目标问题求解。引入权重系数$w_1$ 、$w_2$ 分别作为总的运输距离函数和总$C{O}_2$ 的排放量函数的权重系数($w_1+w_2=1$ )，则加权目标函数为：

$\max Z_4=w_1\cdot \frac{1}{Z_2}+w_2\cdot \frac{1}{Z_3}$ (4)

4. 遗传算法设计与实现

4.1. 算法设计

算法总体流程

1) 初始化：贪心策略生成可行解，确保载重约束；

2) 适应度计算：单目标评估最大距离，多目标计算加权值；

3) 选择：锦标赛选择保留前30%个体；

4) 交叉与变异：两点交叉与随机变异；

5) 更新：更新种群基因；

6) 迭代优化：多次迭代进化，记录最优解；

7) 参数调整：调整交叉率和变异率，比较得出适合的值。

(算法流程图见图2)

Figure 2. Overall flowchart of the algorithm

图2. 算法总体流程图

4.2. 编码与解码方法

4.2.1. 编码方式选择

本文针对物流车辆路径优化问题，采用整数编码方式，具体设计如下所示[3]：

编码规则：个体表示为一个长度是需求点数量(8个)的整数列表，每个元素对应车辆编号−1，元素索引对应需求点编号−1。

例如，个体染色体[2, 0, 1, 0, 2, 1, 1, 0]表示：

需求点1分配给车辆3；

需求点2分配给车辆1；

……

依此类推至需求点8。

4.2.2. 解码方法设计

解码过程将编码后的个体染色体转化为具体的车辆行驶路径，并确保解的可行性。具体步骤如下：

1) 需求点分配

根据个体编码，将各需求点分配到对应车辆的任务列表中。例如，下图3由个体染色体生成车辆1、2、3的二维列表。

Figure 3. Sample distribution result

图3. 示例分配结果

2) 路径生成

采用最近邻算法(Nearest Neighbor Algorithm)为每辆车规划访问顺序，以最小化行驶距离：从配送中心(节点0)出发，依次访问距离当前节点最近的未访问需求点，最后返回配送中心。例如，车辆0的路径为0→7→8→2→0。

3. 可行性验证

载重约束：计算每辆车分配的需求点总需求量，若超过20吨，则通过惩罚函数(如适应度值赋极大值)淘汰该个体。

单次服务约束：编码设计天然保证每个需求点仅由一辆车服务[4]。

4.2.3. 解码优化策略

为提升解码效率与路径质量，引入以下策略：

1) 贪心初始化(Greedy Initialization)：在生成初始种群时，优先将高需求量客户分配给载重较小的车辆，避免初始解违反载重约束(代码见create_individual_feasible函数)。

2) 动态调整：在变异操作中，若某车辆载重超限，则随机调整部分需求点至其他车辆，增强解的可行性 (代码见mutate函数)。

4.3. 选择操作

4.3.1. 选择策略的选择

本文采用锦标赛[5]选择(Tournament Selection)策略，其核心思想是通过局部竞争筛选优质个体。相较于轮盘赌选择(Roulette Wheel Selection)，锦标赛选择具有以下优势：

1) 避免过早收敛：轮盘赌选择依赖适应度值的比例分配选择概率，易导致高适应度个体快速占据种群，引发早熟收敛；锦标赛选择通过小规模竞争保留多样性，平衡探索与开发。

2) 参数可控性：锦标赛规模(即每次竞争的个体数)可灵活调整，规模较小时偏向探索，较大时偏向开发。

3) 计算高效：无需全局适应度排序，适合大规模种群场景[6]。

4.3.2. 选择操作的实现

锦标赛流程：

1) 从种群中随机选取若干个体；

2) 比较这些个体的适应度值，选择适应度最优(单目标下最小化的最大距离，多目标下最大化的加权适应度)的个体加入下一代种群；

3) 重复上述过程直至新种群规模达到设定值；

对算法收敛性的影响：

1) 锦标赛规模：实验表明，当种群规模设为5时，算法在全局搜索与局部开发间取得平衡；若规模过大，可能导致种群多样性下降，进而陷入局部最优；

2) 适应度压力：锦标赛选择通过竞争机制间接施加选择压力，适应度较差的个体仍有概率参与进化，避免种群同质化。

4.4. 交叉与变异操作

4.4.1. 交叉操作设计

交叉操作用于组合父代基因信息以生成子代，两点交叉相较于单点交叉能保留更多父代基因块的结构信息，增强全局搜索能力。本文采用两点交叉(Two-Point Crossover)策略：

操作流程：

1) 随机选择一对父代染色体[7]；

2) 随机生成0~1的数比较交叉率判断是否进行交叉互换；

3) 随机在父代上选取两个交叉点；

4) 交换两父代在交叉点间的基因片段[8]，生成两个子代个体。

4.4.2. 变异操作设计

变异操作通过随机扰动基因值维持种群多样性[9]，本文采用单点随机变异策略：

操作流程：

1) 遍历个体染色体的每个基因位，根据变异率随机进行改变；

2) 若变异后车辆载重超限，后续解码阶段通过惩罚函数淘汰该个体。

4.4.3. 交叉与变异概率设置

交叉率(CROSSOVER_RATE)：设为0.8，即80%的个体参与交叉。较高概率促进基因重组，但可能破坏优质个体；实验表明，0.6~0.9为合理范围。

变异率(MUTATION_RATE)：设为0.1，即每个基因位有10%概率变异。较低概率避免过度随机扰动，维持种群稳定性。

对算法性能的影响：

1) 交叉概率过高(如>0.9)：导致种群快速同质化，降低搜索效率；

2) 变异概率过低(如<0.05)：种群多样性不足，易陷入局部最优；

3) 平衡策略：通过参数敏感性实验，确定交叉率0.8与变异率0.1的组合在单目标与多目标模型中均表现稳定。

4.5. 算法参数设置

4.5.1. 参数及设置依据表(表5)

Table 5. Parameter settings

表5. 参数设定

参数	设定值	依据
种群规模(POPULATION_SIZE)	500	文献推荐值，平衡计算效率与解质量；过小易遗漏最优解， 过大增加耗时
交换率(CROSSOVER_RATE)	0.8	单目标参数调优实验确定，兼顾全局搜索与收敛速度
变异率(MUTATION_RATE)	0.2	单目标参数调优实验确定，较低概率避免过度随机扰动， 维持种群稳定性
迭代次数(MAX_GENERATIONS)	50	收敛曲线分析显示20代后适应度趋于稳定，留有余量确保收敛
锦标赛规模(tournament_size)	5	实验表明，当规模设为5时，算法在全局搜索与局部开发间取得平衡

4.5.2. 参数调整策略

1) 单目标模型调参：

通过网格搜索法测试不同参数组合；

记录各组合下算法收敛速度与最终解质量，选择综合最优参数。

2) 多目标模型迁移：

沿用单目标调优参数，因多目标加权函数对搜索机制影响较小。

4.5.3. 参数敏感性分析示例

以变异率为例，其他参数按表5设定，对比不同设定对单目标模型的影响：

1) 变异率 = 0.05：种群多样性不足，容易陷入局部最优解，见图4。

Figure 4. Variation rate 0.05

图4. 变异率0.05

2) 变异率 = 0.1：收敛线较快收敛，20代后稳定，见图5。

Figure 5. Variation rate 0.1

图5. 变异率为0.1

3) 变异率 = 0.2：频繁扰动，最终解波动较大，见图6。

Figure 6. Variation rate 0.2

图6. 变异率0.2

4.6. 算法实现

4.6.1. 算法实现框架

本文基于Python语言实现遗传算法，核心模块包括种群初始化、适应度计算、选择、交叉、变异及迭代优化。代码结构如下：

1) 数据加载[10]：读取配送中心与需求点坐标、需求量及车辆排放系数；

2) 距离矩阵计算：预计算所有点间的欧氏距离，并存储；

3) 种群初始化：

• 单目标：模型采用贪心策略[11]生成可行解；

• 多目标：随机生成初始解。

4) 适应度函数：

• 单目标：最小化最大运输距离，对超载个体施加高惩罚；

• 多目标：加权总距离与碳排放。

5) 进化操作：锦标赛选择、两点交叉、单点变异；

6) 迭代优化：循环执行选择、交叉、变异，记录每代最优解。

4.6.2. 调试与优化

1) 可行性验证：

• 在适应度函数中检查车辆载重约束，若超限则返回极大惩罚值，确保不可行解被快速淘汰；

• 多目标模型中通过权重系数动态调整目标优先级，避免单一目标主导搜索过程。

2) 性能优化：

• 向量化计算：预计算距离矩阵，减少重复计算；

• 并行化处理：使用多线程加速种群适应度评估。

3) 参数调优：

• 通过网格搜索确定最佳交叉率与变异率，平衡收敛速度与解质量。

关键代码片段见图7。

Figure 7. Debugging and optimizing key code

图7. 调试与优化关键代码

5. 实验设计与结果分析

5.1. 实验设计

5.1.1. 实验数据

1) 配送中心坐标：(8.3, 9)，需求点坐标及需求量如表1、表2所示；

2) 车辆参数：3辆，载重上限20吨，根据文献[12]设定配送车的排放系数分别为[0.83, 0.86, 0.90] kg/km。

5.1.2. 实验场景

1) 单目标优化：最小化最大运输距离；

2) 多目标优化：同时最小化总运输距离与总碳排放量。

5.2. 实验结果

5.2.1. 单目标优化结果(图8)

1) 最优路径：最大运输距离25.79 km，车辆分配如下：

车辆1：0→3→2→0，载重8吨；

车辆2：0→4→5→6→0，载重11吨；

车辆3：0→8→1→7→0，载重12吨。

2) 收敛性：算法在20代后适应度稳定。

Figure 8. Results of minimizing the maximum transportation distance

图8. 最大运输距离最小化结果

5.2.2. 多目标优化结果

1) 权重敏感性：当权重系数$w_1 =0.6$ 时，总距离为100.42 km，碳排放为86.65 kg，达成均衡解(图9)；

Figure 9. Results with a weight coefficient of 0.6

图9. 权重系数$w_1 =0.6$ 结果

2) 帕累托前沿：图10展示不同权重下的目标值分布，体现距离与排放的权衡关系。

Figure 10. Distribution of target values under different weights

图10. 不同权重下的目标值分布

6. 模型评价

6.1. 模型的优点

1) 算法框架清晰

基于遗传算法构建优化模型，编码与解码逻辑简单直观，便于理解与实现，适合快速验证理论。

2) 多目标优化探索

将碳排放作为优化目标，结合运输距离进行加权分析，为绿色物流研究提供了初步框架。

3) 可行解生成能力

采用贪心策略初始化种群，有效提高了初始解的质量，减少了无效搜索迭代。

6.2. 模型的缺点

1) 假设过度简化

忽略交通拥堵、时间窗、动态需求等现实因素，模型与实际场景存在较大偏差。

2) 大规模问题表现差

需求点超过50个时，求解时间与解质量显著下降，算法复杂度未优化，难以应对实际物流中的超大规模场景。

3) 环境因素单一

仅考虑CO₂排放，未涉及噪音、能源类型等多维度环境影响，环保指标覆盖不全面。

7. 模型改进方向

7.1. 增强现实约束适配性

1) 引入时间窗约束(VRPTW)和动态交通数据，构建实时更新的距离矩阵，提升模型对复杂场景的适应性。

2) 考虑车辆类型差异(如电动车续航限制)，扩展多车型混合调度模型。

7.2. 优化算法效率与鲁棒性

1) 设计自适应参数调整机制(如根据种群多样性动态调整变异率)，减少人工调参依赖。

2) 采用并行计算或分布式框架(如Spark)加速大规模问题求解，提升工程实用性。

7.3. 完善环保评价体系

1) 增加噪声污染、能源消耗等环境指标，构建多维度绿色物流优化模型。

2) 结合生命周期评估(LCA)，量化车辆制造、维护等全链条环境影响。

7.4. 提升模型理论深度

1) 引入数学证明分析算法收敛性，从理论层面优化选择与变异策略。

2) 对比NSGA-III等先进多目标算法，改进帕累托解集的分布均匀性与覆盖率[13]。

7.5. 动态调度与实时优化

1) 开发在线优化模块，支持新增需求点的实时路径调整，避免全局重新计算。

2) 集成机器学习预测模型，预判交通流量与需求变化，增强动态决策能力。

NOTES

^*通讯作者。