混合轴辐式零担快运网络车辆调度设计与实现

缪桂根

（湖南现代物流职业技术学院 物流管理学院，湖南 长沙 410131）

0 引言

零担运输是指货主一次托运的货量不足一车时，与其他货物拼装的运输方式，特别适用于货物批量较小、发货频次较高、发货范围较广等商业情境。在零担货运中，如何合理组织运输网络十分重要。零担运输网络以轴辐式网络为主。轴辐式网络又分为不允许网点直通的纯轴辐式和允许直通的混合轴辐式。混合轴辐式零担快运网络中既有直达线路又有转运线路，如何合理安排车辆路线及车型是混合轴辐式网络运营规划中极其重要的方面。车辆路线及车型安排问题属于物流运筹学中的经典问题车辆调度问题（Vehicle Routing Problem，VRP）。车辆调度是将车辆选择、路线规划问题结合起来考虑，以保证在达成服务承诺的前提下最大限度降低运营成本。相较于传统车辆调度问题，混合轴辐式网络下的车辆调度问题具有更多的约束条件，如表现出多时间窗、循环取货、直达与中转并存、轴辐节点功能不同等特点，模型更为复杂求解难度更大。混合轴辐式网络下的车辆调度问题研究细分领域较多，如网络末端的集配送车辆调度、不同指派关系不同枢纽数量网络车辆路线安排、涉及不同车型的网络车辆路线安排、考虑时间窗的车辆路线安排等。本文研究单一指派的多枢纽混合轴辐式网络中车辆安排问题，旨在针对节点间确定的运输需求，安排合理的运输路线及车型。以节点的操作处理成本、节点间的运输成本之和最低为目标，构建具有多重时效要求的车辆调度模型，设计遗传算法并在Matlab 中予以仿真实现。

1 模型构建

1.1 问题描述

网络中节点分为货运站和枢纽站，每个货运站与枢纽站的指派关系是确定的，且每个货运站只能指派给一个枢纽站。货运站与货运站之间允许直达运输，也可以通过枢纽站中转运输。货运站之间的运输最多经过两次中转即可到达。这是一个典型的单一指派多枢纽混合轴辐式网络，如图1 所示。

图1 单一指派多枢纽混合轴辐式网络结构图

1.2 数学模型

本文研究的单一指派多枢纽混合轴辐式网络的运输方式有两个大类：直达运输和中转运输，其中按照节点与指派枢纽的从属关系而形成的区域，可以进一步细分为四种运输类型，分别是区域内直达、区域间直达、区域内单枢纽中转、区域间双枢纽中转。考虑到问题中网络的节点已经建立，所以节点相关的固定成本属于沉没成本，在此不予考虑。总的运营成本主要考虑节点的操作处理成本、节点间的运输成本。中转运输方式相较直达运输方式，增加了枢纽的操作处理成本及起讫点间的运输时间，但由于可以将较为分散的货量集中起来转运，产生了一定的规模经济，枢纽的操作处理成本较货站处理成本要低，转运路段上通过使用更大车型也能够获得更低的单位运输成本。在货运站和枢纽站产生的成本主要包括装卸、搬运、分拣、保管等带来的费用。节点间的运输成本包括车辆折旧费、维修费、燃料费、路桥费、驾驶员工资、税金、管理费用等。以上运输成本可以进一步划分为与行驶距离相关的公里成本，如车辆折旧费、维修费、燃料费、路桥费等，以及与运输时间相关的小时成本如驾驶员工资、税金、管理费用等。不同车型的公里成本、小时成本不相同，相同车型在不同线路上的公里成本和小时成本也不相同。本文出于简化问题考虑，不考虑相同车型在不同线路上的成本差异，默认各车型成本是固定值。

货运站之间的日均货运量已知且是确定的，可用车型已知且固定，发车班次根据路段货量确定，且满足各货运站的时间窗要求。两个货运站之间的货量不可拆分。在这样一个货运站与枢纽站指派关系确定的多枢纽轴辐式网络中，如何合理安排各节点间线路上每日的车型及发车频次，以达成网络总运营成本最低的目标，就是本文拟解决的问题。综合考虑混合轴辐式零担网络运营的运输成本及节点处理成本，构建以总网络运营成本最小为目标的数学模型如下：

目标函数的第一部分表示货运站产生的处理成本，第二部分表示在第一转运枢纽产生的处理成本，第三部分表示在第二转运枢纽产生的处理成本，第四部分表示货运站间采用直达运输时的路段运输成本，第五部分表示货运站间采用中转运输时发生在支线上的运输成本，第六部分表示货运站间采用中转运输时发生在干线上的运输成本。

约束条件如下：

式（2）保证各枢纽站所属货运站数之和等于总货运站数量。式（3）限定了k 枢纽区域内运输时各节点的运输时效。式（4）限定了区域间运输时各节点间的运输时效；式（5）、式（6）、式（7）表示路段容量限制，限定了直达线路、支线、干线可用车型装载量及最大车型数量；式（6）表示决策变量的含义。

2 遗传算法设计

单一指派多枢纽混合轴辐式网络模型为非线性整数规划问题，随着问题规模增大其可行解空间也快速扩大，这类问题多采用启发式算法求解。遗传算法是一种经典的启发式算法，在车辆调度等非线性规划问题中得到较多应用。通过模拟自然界生物的自然选择、交叉、变异等机理来搜索最优解，通过反复迭代运算得到最优解。其主要流程有编码并生成初始种群、适应度评估、选择/交叉/变异遗传操作。

2.1 编码并生成初始种群

本文采取二进制染色体编码方式。当货运站i 到货运站j 之间的运输采用直达方式时，编码为0；当货运站i 到货运站j 之间的运输采用中转方式时，编码为1。由于本文构造的网络模型中各节点与枢纽之间的指派关系是单一且明确的，且以各枢纽为中心形成若干小型区域网络，区域内节点间运输仅直达和单点中转两种，区域间节点间的运输仅直达和两点中转两种。因此，区域内节点间编码为1 表示单点中转，区域间节点间编码为1 表示两点中转。由于网络中货运站节点总数为n，因此，染色体为n×n 规模的0～1 矩阵。

种群规模对遗传算法运行结果和效率有着直接重要影响，种群规模过大，算法运行时间受影响，种群规模过小问题易陷入局部最优。本文以0～1 随机数方式生成初始种群，种群规模根据问题规模通过算法试运行予以调整到较合理的状态。

2.2 评估适应度

种群中哪些个体能够遗传到下一代，需要借助适应度来进行评估。适应度用来表征种群里的个体在优化过程中达到或接近于或有助于找到最优目标值的优良程度，对应自然界的“适者生存法则”，适应度值越高的个体具有更大的概率被选中遗传到下一代。本文用目标函数的倒数作为适应度评估值。

2.3 选择、交叉、变异

（1）选择算子。采用最佳个体保存与轮盘赌选择相结合的选择策略。操作基本过程如下：对种群进行轮盘赌选择操作，找出适应度最高和最低的个体；如果当前种群中最佳个体适应度高于前面种群遗传下来的最佳个体的适应度，则以当前种群适应度最佳的个体替换原来种群中适应度最低的个体。选择概率P 计算式如下，其中npop 表示种群规模。

（2）交叉算子。通过父代染色体的交叉运算能够产生子代，子代通过交叉遗传父代的基本特征。设交叉概率为P。选择单点交叉方式。将种群一分为二，前后两个部分对应的个体进行交叉，随机确定行交叉或列交叉，随机确定交叉点，在交叉点后编码互换。

（3）变异算子。变异是指通过改变个体的某些基因片段值，以使遗传算法扩大局部的随机搜索能力，加速问题向最优解收敛，同时扩大群体的多样性，避免群体陷入早熟。随机选择个体中的行或列中的随机位置进行反向变异，即0 变为1，1 变为0，设变异概率为P。

通过上述遗传选择、交叉、变异等操作可以得到新的种群，新的种群经过运算迭代后得到最优解。

3 算例仿真

以一家小型零担货运企业的网络为例，依据上述算法，用Matlab 编写程序对该企业的零担运输网络车辆调度问题进行仿真模拟。该企业零担业务主要集中在4 个省份。共设置3 个转运枢纽、10 个货运站。各货运站之间的日平均货物量如表1 所示。货运站间及货运站与指派枢纽间、枢纽站间的距离、货运站和枢纽站的单位处理成本已知。各货站的时效分为区域内到达时效和区域外到达时效。直达线路和区域内转运线路可用车型为3 吨、8 吨、17 吨三种，区域间的干线运输可用车型为17 吨、25吨、30 吨三种。直达线路限定一辆车、转运线路限定两辆车。各车型成本信息如表2 所示。

表1 货运站间日均货运量 单位：吨

表2 车型成本信息

选取不同的算法参数进行模拟运行，当参数设置交叉概率为0.6，变异概率为0.08，种群数为300，进化迭代次数为500时，算法运行效果最好，此时的混合轴辐式网络最小总成本是72 330 元，目标函数运算结果如图2 所示，各路段车辆调度方案如表3 所示。

表3 路段车辆调度方案

图2 目标函数运算结果

经计算纯轴辐式网络的运营成本为75 072 元，相较纯轴辐式网络，混合轴辐式网络成本约节约3.65%，考虑到纯轴辐式网络部分路段容量超出现有阈值，网络服务水平有所下降，混合轴辐式网络相较纯轴辐式网络的成本节约实际将超过3.65%。因此，混合轴辐式网络可以降低网络运营成本、提高服务水平。

4 结束语

混合轴辐式零担快运网络是零担运输网络的发展趋势。车辆调度问题是混合轴辐式零担快运网络运营规划的一个分支，车辆调度方案的优劣对网络运营成本及服务水平有较大影响。分析单一指派多枢纽轴辐式零担快运网络运输方式特点的基础上，在车辆种类和路段容量一定且节点多时间窗的前提下，构建了网络车辆调度模型，并编写了遗传算法程序在Matlab 中予以实现，实现了快速制定车辆运输方案，从而达到降低网络运营成本、提高服务水平的效果。由于模型采用启发式的遗传算法进行求解，其中涉及若干模型参数，实际应用该模型及算法时，需要根据问题中节点规模反复多次模拟找到适合问题的最佳参数组合。