多枢纽轴辐式协同物流网络任务-路径优化匹配研究

徐小峰，孙玉萍

(中国石油大学(华东)经济管理学院，山东 青岛 266580)

1 引言

近年来，我国物流业产业规模扩展迅速，粗犷发展模式下的物流业暴露出网络运行成本高、效率低等问题，网络内部协同运作水平亟待提高[1]。作为一种科学有效的复杂系统网络组织结构，轴辐式网络(Hub and Spoke Network)在物流业的应用受到越来越广泛的关注。与全联通的网络结构相比，轴辐式网络在服务空间分散的小批量物流需求、整合物流资源、产生规模效益等方面更具应用潜力[2]，但也存在物理路径延长、绕道时效损失等弊端。同时，为灵活地应对差异化物流需求，轴辐式物流网络不再局限于单枢纽-单分配-纯轴辐式结构形式，而是更趋近于采用多枢纽-多分配-混合轴辐式网络结构形式[3]，即网络中布局多个枢纽、允许单个辐点分配到多个枢纽且辐点间存在直达线路的情况，这也使得物流节点的协同运作和物流网络的运营管理更加复杂。因此，如何权衡多任务整体利益和单个任务满意度，实现多个空间分散的物流任务-执行路径的有效匹配，成为提升物流集成服务商竞争力的关键。

1987年，O’Kelly以航线网络优化为切入点，首次提出轴辐式网络p-中位优化设计模型[4]，引发学术界对轴辐式结构的广泛关注。按照规划内容适用周期的不同，将近年轴辐式网络规划相关研究分为长期规划研究(Hub and Spoke NetworkLong-term Planning，HSNLP)和短期规划研究(Hub and Spoke Network Short-term Planning，HSNSP)。HSNLP是指以节点城市物流服务能力、城市间物流往来流量结构数据为基础，进行轴辐式网络枢纽选址和轴线分配等研究，大致有两类研究方法：一类是通过建立指标评价体系，利用主成分分析等方法对节点的服务能力进行分级以此确定枢纽节点的数量和位置[5-8]，这类方法侧重对物流节点服务能力的评价，对网络本身的运营成本及效率考虑不足；另一类则更多地考虑节点间已知物流往来流量结构，通过数学建模和智能算法求解来优化网络结构[9-12]，不少研究还针对单分配[13-15]、多分配[16-17]、含直达线路[18]以及存在多式联运[19-20]的情况进行改进设计，大大提高了轴辐式网络在实际运营中的适用性和灵活性。然而，上述HSNLP研究内容仅仅完成了网络建设工作，在网络实际运行中，由于流量状态存在不确定性，与HSNLP设定状态存在差距，物流任务集的最佳走形线路将发生变化。为此，一些学者针对网络运营过程中物流任务-路径匹配等HSNSP问题进行了研究，如Karlaftis等[21]提出枢纽港口与众多喂给港口间货物往来存在季节性变化，因此对轴辐式子网络集装箱船舶线路重新规划，建立了带时间窗的整数规划模型，但未考虑中转时间和等待时间；杨立乾[22]考虑枢纽容量和货物时间约束，对轴辐式支线集装箱运输多船型船舶调度问题进行建模研究，并设计粒子群算法进行模型求解；黄丽霞等[23]综合考虑客户送达时间、服务等级需求和运输能力限制等因素，对轴辐式网络下的干线货物运输路径、服务班列及运行数量进行优化设计。

综上，尽管轴辐式网络规划已经有较丰富的研究内容[24-27]，但多是集中于轴点选址等HSNLP方面[28]，而较少关注在轴辐式物流资源服务体系确定条件下的物流任务-路径优化匹配等HSNSP问题，且已有HSNSP研究多是将轴辐式网络作为问题产生的背景，仅仅将单个层级(支线或干线)作为资源调度对象，未能从系统整体角度考虑调度过程，忽视了网络层级间的相互影响。因此，本文将多任务集成调度问题扩展到HSNSP研究领域，以多枢纽-多分配-混合轴辐式多式联运协同物流网络(双层)为基础，综合考虑干线资源发车时刻限制和费用折扣系数动态变化条件，针对一特定时段内网络内部多起始点-多目的地的物流任务集，构建轴辐式协同物流网络任务-路径优化匹配模型并采用遗传算法进行模型求解，以满足客户服务时间要求并使得总物流成本最小。

2 问题描述

在轴辐式物流网络资源服务体系确立的条件下，本文从物流集成服务商的角度出发，研究一个调度周期内多起止点多个需求不同的物流任务的任务-路径优化匹配过程，通过物流任务的有效聚合，实现物流资源的整合，从而最大限度地发挥网络系统协同规模效益。

图1 多枢纽-多分配-混合轴辐式多式联运协同物流网络形态示意图

给定轴辐式协同物流网络G=(N,E)(如图1)，N=H∪S表示网络中的两层物流节点，上层为轴点H={h1,h2…hk,hm…hh}，具有货物中转功能，下层为辐点S={s1,s2,…si,sj…ss}，为轴点提供物流任务喂给服务；E为网络中关联边集合，表示服务商在该路段可提供的物流资源，带有运输时间、运输能力、可变费用折扣等属性。网络中轴点间完全联通，辐点间的联络主要借助轴点实现。考虑到物流网络的稳定性和货物运输选择的灵活性，该网络允许辐点与多个轴点存在指派关系，xik是表示si和hk之间是否存在指派关系的0-1变量；同时部分辐点间可选择直达线路，yik是表示si,sj间是否有直达线路的0-1变量。轴点hk,hm间存在多种运输工具供选择，运输能力及发车时刻存在一定要求。

图2 多任务多起止点物流服务示意图

1)匹配执行模式：调度过程存在直达和转运两类执行模式，转运模式下的干线运输成本远低于直达模式，但前者由于存在绕道以及中转耗时使得总体运输时间大于后者；

2)匹配转运枢纽：不同枢纽对应干线不同，中转成本、中转耗时及等待时间也不同；

3)调度运输资源：干线间运输资源的开始服务时间取决于其待执行物流任务集中最晚到达任务的最早开始时间。

3 模型构建

3.1 条件假设

为方便模型构建和计算分析，作如下假设：

(1)轴辐式网络中物流资源均为系统原有资源，模型中不再考虑建设成本等固定成本；

(2)轴点中转无容量限制，且针对不同运输资源的中转时间和成本相同；

(3)干线存在多种运输资源，支线和直达线路只有公路运输一种；

(4)干线运输资源存在发出时刻限制；

(5)仅考虑干线规模效益，用费用折扣系数表示，折扣大小随调度周期内该条干线承担总物流量动态变化；

(6)物流任务不可拆分，即单个物流任务只能匹配一条路径；

(7)物流任务发出和接收地均为辐点，运输过程最多允许转运两次；

(8)物流任务的执行仅考虑从发出方到接收方的过程，即任务性质为纯送货任务。

3.2 变量定义

表1 模型参数含义说明

3.3 目标函数

(1)

(2)

其中：式(1)为模型的服务成本目标函数，由四个部分组成：第一部分是转运路径成本，分别为轴点间规模运输成本、辐点与轴点间支线集散运输成本和轴点转运成本；第二部分为辐点间的直接运输成本；第三部分为超时惩罚成本；第四部分轴点等待成本。式(2)是模型的服务时间目标函数，包括运输时间、转运时间和等待时间。

3.4 约束条件

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

式(3)表示每个物流任务只能匹配一种运输方式，即基于轴点转运运输或者直接运输；若选择转运，干线运输只能匹配公路或者铁路一种运输工具。式(4)表示轴点选择条件，即只有当任务发出点/接收点与轴点存在指派关系时，才能选择相应轴点作为转运点。式(5)表示选择直线运输的条件是任务起讫点间存在直达线路。式(6)表示运输路径能力限制。式(7)表示干线资源发车时间，即作为紧后活动，其开始时间取决于紧前子任务集的最晚完成时间。式(8)表示物流任务r的实际总服务时间。式(9)表示物流任务超时惩罚函数。式(10)表示费用折扣系数变化依据，αmin为给定最低费用折扣值。

4 模型求解

多枢纽轴辐式协同物流网络任务-路径优化匹配问题属于NP问题，其时间复杂度会随着问题规模增大而急剧上升，传统的精确计算方法难以解决。遗传算法是一类借鉴生物界自然选择和遗传机制的随机搜索算法，非常适应于处理复杂的非线性规划问题。本文利用遗传算法对上述模型进行求解，具体实现过程如下：

(1)编码

根据轴辐式网络任务-路径优化匹配过程的特点，在对所有物流节点及干线运输方式编号的基础上，本文设计了三层整数编码来表示任务执行路径，如图3所示。每层编码基因数目与任务数r相等，即染色体总长度为3r。对于任务r，若一二层基因恰好等于其起止点，则表示该任务匹配直达线路。若两个任务三层编码完全一致，则表示两个任务在相应路段发生集并。

图3 编码示意图

(2)种群初始化

设置种群规模为m，按照编码规则随机生成m个满足路径约束、资源能力约束的染色体，以此为初始种群进行遗传操作。

(3)适应度函数

适应度是评估染色体优劣的标准。本文通过赋权的方式将模型中成本和时间两个目标函数转化为单目标形式，同时进行归一化处理，得到适应度函数如下：

F=ηminC/Cmax+(1-η)minT/Tmax

(12)

其中，Cmax、Tmax取种群进化过程遍历的可行解中对应的最大执行成本和最大执行时间。

(4)遗传操作

1)选择

依据适应度值选择优良个体作为父代进行繁殖，形成新的子代。本文采用轮盘赌选择策略。

2)交叉

随机选择两个染色体，以设定概率Pc进行交叉操作。由于本文采用三层编码表示任务执行路径，经典的单点交叉算子极易破坏解的可行性，导致大量无效操作。因此，本文设计了多点位交叉方式，如图4所示，若随机选中第r+2个基因进行交叉，则第2和第2r+2个基因也随之进行交叉，即任务r2的三层编码同时交叉，保证了交叉的有效性。

图4 交叉过程示意图

3)变异

随机选择两个染色体，以设定概率Pm进行变异操作，同交叉方式类似，本文的变异方式遵循同一任务的三层编码同时变异的原则。

4)终止

当进化次数达到预设的迭代次数时，终止遗传操作，输出结果。

5 算例仿真

5.1 算例设计

某物流集成服务商承接了我国中西部一制造业企业在全国范围内的物流任务，其可调配的物流资源组成图5所示的轴辐式协同物流网络，主要资源参数见表2。取两点间直线距离作为两物流节点间的运输距离，并假定干线和支线公路运输时速分别为80公里/时和70公里/时，干线铁路运输时速为100公里/时，以此得到网络运输时间矩阵。干线规模效益取决于该线路承担的货运量(式(10))，货运量越大，规模效益越显著，设定αmin=0.3，即当该线路满载时，成本折扣系数达到最小0.3。

根据全国各销售商订单需求和兰州、西安及重庆三处分制造厂的供货情况，物流集成服务商需要在一个调度周期内完成表3所示的8个物流任务。为实现规模效益最大化，集成商会尽可能使任务集并运输，但如果任务对交货期要求严，集并可能会大大降低单个任务满意度。因此，集成商需根据各任务的具体需求及任务各执行阶段可匹配的资源情况(图6)，综合制定任务-路径匹配方案。

图5 轴辐式协同物流网络形态示意图

表2-a 轴辐式网络物流资源条件——干线资源

hk⇌hm公路铁路dijvcijukmvdijvcijukmv成都⇌北京19.03102015.223030成都⇌杭州19.38102015.53030杭州⇌北京14.13102011.33030

表2-b 轴辐式网络物流资源条件——支线及枢纽资源

表3 物流任务表

图6 多任务物流服务示意图

5.2 结果分析

设置种群规模为30，迭代次数为250，交叉概率为0.8，变异概率为0.1，编写遗传算法利用Matlab2014a进行求解。

为便于比较分析，令成本目标函数权重系数η分别等于0.5和1，同时令后者惩罚成本为0，得到收敛曲线如图7所示，对应的路径匹配方案如表4所示。

图7 遗传算法收敛曲线

可以发现，当集成商只关注自身成本时，尽管实现了更低的成本支出，却忽略了单个任务的满意度，使得对服务时间要求高的任务发生延迟；而当集成商兼顾整体与单个任务效益时，尽管成本有所上升(+1.4%)，却大幅度节省了执行时间(-14.9%)，从而大大提升了客户满意度。由图8可以看到，优化方案中，对于延迟成本高的任务2和任务7，集成商放弃使用转运路径直接匹配直达线路，保证了其交货时间；对于延迟成本低的任务，普遍采用转运运输，以达到更大的规模效益，且当多个任务最优路径相同而路径能力有限时，为保证整体利益，损失更小的任务将匹配次优线路。

表4 轴辐式协同物流网络任务-路径匹配方案

注：①-分别代表成都、北京、杭州、兰州、重庆、西安、石家庄、天津、济南、郑州、南京、武汉；I代表干线公路运输，II代表干线铁路运输。

图8 轴辐式协同物流网络甘特图

6 结语

本文研究HSNSP问题，在多枢纽-多分配-混合轴辐式多式联运协同物流网络建立的条件下，对一个调度周期内多个多起点-多目的地的物流任务进行路径优化匹配。从物流集成服务商角度出发，综合考虑干线资源的发车时刻和能力约束，设计了随物流量动态变化的成本折扣系数来表示规模效益，建立了带软时间窗的任务-路径优化匹配模型，优化目标为集成商物流成本和服务时间最小。针对模型特点，在利用遗传算法求解过程中，设计了三层编码来表示任务路径，并采用多点位交叉、变异机制来保证遗传操作的有效性。最后利用具体算例验证了本文模型和算法的有效性。

研究结果表明，本文模型通过对单个任务设置延时惩罚，兼顾物流服务集成商的利润需求和客户服务质量，实现了整体效益最优。带资源回程的轴辐式协同物流网络任务-路径优化匹配将是下一步研究工作的重点。