基于承运人视角的运输线路组合问题及粒子群算法求解

郭俊

（重庆交通大学经济与管理学院，重庆400074）

0 引言

物流组合问题是指将物流领域内的单一问题或单一因素综合考虑，再设计适当的求解算法对组合问题求解。邱国庆等人[1]提出运输任务分配与路径选择的组合优化问题，并针对该问题建立了组合优化模型，设计了基于二维染色体结构的改进遗传求解算法。Mesa-Arango R 等人[2]在任务可搭载的基础上，将m-PDVRP 模型应用在零担物流车辆路径优化中，并且采用分支定界算法对模型进行解。而其他研究者使用了诸如禁忌搜索法[3]、粒子群算法[4]等智能算法求解可搭载问题。

综上所述，少有研究者关注运输线路组合问题，虽多基于承运人视角，但更关注任务执行阶段。因此，本文着重于任务选择，并根据任务选择情况规划车辆路径。

1 问题描述和建立模型

1.1 问题描述

本文研究问题如下：无向图G=（V，E）为运输网络，其中 V={0，1，2，…n}表示所有运输节点，0 表示车场。边集合E={（i，j）｜i，j∈V}，每个边上的单位成本为cij；∞1和∞2分别表示车辆空载和满载情况下单位距离的油耗成本，则cij=（Qij，k/Q）（∞1-∞2），其中 Q、Qij，k分别表示车辆最大载重和边（i，j）上的载重；各个节点的位置表示为（xi，yi），dij表示节点i，j 间的距离。假设某承运人的任务集合为C={1，2，3…n]，任务t 的运价用pt表示，需求量用qt表示。在时间窗[elt，ltt]上增加了最大容忍上限eett和最大容忍下限eltt；承运人同型车辆集合 K={1，2，3…m]，k 表示任意车辆，Lk表示车辆的最大行驶里程，v 表示速度。承运人在运力范围内选择f 个任务，当承运人选择承运任务t 时，Yt=1，否则Yt=0。当车辆 k 经过边（i，j），决策变量 Xij，k=1；否则，Xij，k=0。当任务 t 分配给车辆 k，决策变量 Zt，k=1；否则，Zt，k=0。

1.2 建立模型

基于上述分析和变量的设置，建立以承运人收益最大化为目标的数学模型：

目标函数（1）表示承运人收益最大化；式（2）表示承运人的运力限制；式（3）表示物流流量的平衡；式（4）表示车辆的最大里程限制；式（5）表示车辆最大运量限制；式（6）～式（8）表示决策变量取值范围。

2 算法设计

众所周知，任务组合问题是NP-hard 问题，而对该类问题的求解是较为困难的。因此本文采用标准的PSO 算法[5]构架对模型求解。

2.1 粒子群算法

粒子群算法也称粒子群优化算法，是由J. Kennedy 和R. C. Eberhart 等开发的一种进化算法。算法通过改变粒子的速度来控制粒子的飞行方向和距离，不断产生由优化的函数决定的适应值，具体公式如下：

上式中，vi表示粒子 i 的速度，w 表示惯性权重；c1、c2表示两个为常量的学习因子；pbesti和gbest 分别表示粒子群体中个体局部最优和全局最优位置；r1、r2为两个0、1 之间的随机数。

2.2 任务选择

Step1：初始化，生成 n×N 随机数矩阵，n、N 分别表示任务个数和粒子个数。

Step2：将随机数进行四舍五入处理，0 代表不选择，1代表选择。

2.3 路径规划

Step1：计算单独运输任务t 的开始服务时刻Tt。

Step2：计算每个任务的初始时间执行权重φt，若Tt＜eett，则 φt=0；若 Tt＞eltt，则 φt=1；若 eett≤Tt≤eltt，则 φt=Tteett/eltt-eett。

Step3：将执行权重降序排列，确定首个任务点。

Step4：判断是否为多任务起点，若是，则在不拆分的情况下尽可能多的装载任务。

Step5：判断车辆剩余运力，若运力不足，则完成已装载任务的运输后进入step6；若运量充足，则进入下一步。

Step6：更新执行权重，寻找下一节点。

Step7：判断节点性质，若是pickup 点则返回step4；若是delivery 点，则卸载对应的任务。

Step8：判断任务是否运输完成，若完成进入下一步；若未完成则返回step6。

Step9：根据车辆行驶里程约束，拆分线路。

Step10：结束。

3 算例分析

该章节根据上述算法思想设计了数值算例，物流网络节点距离信息和托运人任务信息分别如表1 和表2 所示。

表1 节点间距离表

表2 任务信息表

表3 车辆信息表

粒子群参数设置为：种群规模为20，迭代次数为100，学习因子 c1=1.5，c2=0.3，ωmax= 0.4，通过 PSO 计算结果如图1。

图1 收益迭代图

根据算法计算结果，承运人选择承运任务1、2、3 和任务4 时，收益最大为4609.5 元。在设定承运人最大运力为13t 的情况下，算法选择承运的总任务量为12.8t。而为了在车辆的行驶里程内完成任务的运输，最少需要2 辆车。具体的车辆运输信息表如表4 所示。

表4 车辆运输信息表

4 结论

本文从承运人的视角对运输线路组合问题展开研究，建立了承运人收益最大的数学模型。结果显示，在承运能力允许范围内，承运任务1、2、3 和4，承运人收益最大。因此，本文所以提出的算法对求解运输线路组合问题具有一定的理论和应用价值，有利于承运人充分运用其运输能力，避免造成资源闲置。同时，本文还存在些许不足之处。本文所研究的问题，是在运量不允许的拆分的情况下进行的。然而，就实际情况来看，适当的将需求进行拆分是可以降低承运人的运输成本，达到增加承运人收益的效果。