大规模零担物流轴辐式网络决策优化

王雁凤， 黄有方

(1.上海海洋大学 经济管理学院， 上海 201306； 2.上海海事大学 物流研究中心， 上海 201306)



大规模零担物流轴辐式网络决策优化

王雁凤1,2*， 黄有方2

(1.上海海洋大学 经济管理学院， 上海 201306； 2.上海海事大学 物流研究中心， 上海 201306)

经济的发展和公路运输的畅通，使零担物流得到迅猛发展.本文针对大规模零担物流网络优化问题，构建了基于双层规划的大规模零担物流轴辐式网络模型，并基于进化博弈和多目标优化思想，设计分层遗传算法来求解模型，最后以算例进行模型及算法验证，得出大规模零担物流网络的枢纽选址、流量分配等决策.灵敏度分析表明节点间流量、单位运输成本等参数会对零担物流网络产生不同程度的影响，增量优化表明当货流量变化时，对建设成本权重较小的情景，决策者宜优先采取改变枢纽点数量来满足需求，而权重系数较大时则应当考虑改变原有枢纽点能级来应对变化.

零担物流； 轴辐式网络； 双层规划； 分层遗传算法； 决策优化

近年来，随着经济的发展和公路运输的畅通，零担物流得到了迅猛发展，全国数十万家零担物流运营商提供的服务网络遍及全国各地.零担物流是将多批次货物合并运输，以达到提高车辆满载率、降低空驶率和运输成本的集约化目标，轴辐式物流网络是零担物流网络的典型形式[1].轴辐式网络作为一种特殊结构的网络，最先指航空公司将一个或几个适当的机场作为中枢，中枢周边较小的城市间不直接通航，而是通过在中枢进行有效中转完成衔接的一种航线网络布局模式，这种网络最早由Goldman在1969 年首次提出[2]，之后O'Kelly在1987年研究美国航空网络时提出了轴辐式网络的数学模型[3]，后来该模式得到了诸多学者的广泛关注和深入研究.与传统的网络结构相比，轴辐式网络简化了网络结构，减少了网络成本，对货物的集中处理和分类使货物的运输实现了规模经济.目前在全国名列前茅的零担物流运营商有德邦、天地华宇、新时代等，它们的服务网络遍及全国各地，拥有如此大规模货流量的物流企业迫切需要构建有效合理的物流网络来降低总成本、提高车辆满载率，并保障货物及时有效到达目的地.

国外学者对轴辐式网络研究的一个重要视角是关于辐节点与枢纽点的指派问题，据此轴辐式网络问题一般分为单分配和多分配问题.单分配问题是指每个辐节点指派且仅指派给一个枢纽点，而多分配问题是指每个辐节点可以指派给多个枢纽点.国外学者分别针对单分配、多分配轴辐式网络问题进行了研究[4-7]，还有学者同时针对这两种指派方式进行了研究[8].此外，考虑到是否有容量约束，学者分别针对枢纽点容量以及节点间流量限制的轴辐式网络问题进行了研究[9-10].国内学者的研究主要集中在轴辐式网络的应用方面，分别针对公路货运系统、海运网络、民用航空等诸多物流领域进行了研究[11-15].然而，上述文献大多针对较小规模的轴辐式网络进行研究，对现实中规模庞大、布局复杂的大型物流企业构建轴辐式物流网络而言略显不足.

零担物流轴辐式网络的构建是一个长期战略决策过程，其决策结果将对未来发展产生持久的影响.面对规模庞大、网点布局复杂的大规模零担物流网络，本文针对问题特征构建了基于双层规划的大规模零担物流轴辐式网络，并设计了分层遗传算法来解决问题，最后运用算例进行模型算法验证和灵敏度分析，为零担物流企业构建大规模物流网络提供有效支持和决策依据.

1 模型构建

1.1问题描述

轴辐式网络结构包括节点和连线.节点通常包括枢纽点和辐节点(本文指需求点).连线是各节点之间的连接路线，承载节点之间的OD流.大部分OD流通过网络中的一个或多个枢纽点实现集货和散货，从而在枢纽点之间形成集中货流的规模效应，降低系统的总物流成本.轴辐式网络规划问题的核心任务是确定枢纽点，以及非枢纽点对枢纽点之间的分配关系.

本文研究的是单分配、有容量限制的大规模零担物流轴辐式网络问题，涉及到的成本主要考虑枢纽点的建设成本和节点之间的运输成本，而运输成本又包括需求点到枢纽点的收集成本、枢纽点到需求点的配送成本及枢纽点之间的中转成本.决策者需要综合考虑上述成本做出决策，从而在满足需求的情况下使网络总成本最小.此外，由于本文研究的是大规模零担物流网络优化，传统的计算方法很难在较短时间内得到全局最优解.因此，本文基于进化博弈和多目标优化思想，设计分层遗传算法来求解问题，并通过算例进行模型算法验证和分析，得出较为理想的大规模零担物流网络枢纽选址、流量分配等决策.最后通过灵敏度等分析研究参数变化对轴辐式网络产生的影响，得出结论和启示.

1.2参数和变量定义

1.3数学模型

综合考虑零担物流轴辐式网络的建设成本、运输成本(收集成本、中转成本及配送成本)，构建以总成本最小为目标的数学模型如下：

min f=λf1+θf2,

(1)

(2)

(3)

s.t

(4)

xikxkk,i,k∈N,

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

2 算法设计

近年来，多目标进化算法因具有较优的全局搜索能力以及对目标函数要求不高的优势，逐步被用于双层规划研究中，一些学者分别用多目标进化算法、混合遗传算法、层次混沌量子遗传算法解决了双层规划问题[16-18].本文基于进化博弈和多目标优化思想，设计分层遗传算法来求解基于双层规划的大规模零担物流轴辐式网络问题.求解思路是：上层规划中零担物流企业给出一些备选节点，下层规划的每个需求点依据自身利益选择各自运输成本最小的枢纽点，综合所有需求点的分配关系和需求量，可求得上层规划中需要建设的枢纽点数量、能级与位置，从而计算出物流企业构建零担物流网络的总成本；物流企业想要降低总成本，通过调整备选枢纽点个数、能级及位置，从而使需求点将货物送往较远的但对企业总体有利的枢纽点，这时建设成本有所下降，运输成本上升.如此反复迭代运算，不断调整网络节点和分配关系，直到满足一定的收敛条件，运算终止.

设计步骤包括：

1) 编码设计，本文采用分层编码方式，第一层表示hub选址决策，每条染色体有I个基因位，I代表备选的枢纽点个数，每个基因位采用0-1编码，1表示选择在该点建设枢纽点，0表示不建设；第二层表示枢纽点与需求点(辐节点)的分配关系，每条染色体有J个基因位，J是需求点的数量，每个基因位代表需求点对枢纽点的分配关系.以图1为例说明，一种可能的方案为：选择在1、3、5备选点建设枢纽点，且需求点1运到其它节点的货物需途径第3个枢纽点中转，需求点2运到其它节点的货物需经过第1个枢纽点中转，以此类推.

图1 分层编码设计Fig.1 Hierarchical coding design

2) 种群数量为N，设定最大进化代数、交叉率、变异率，随机生成一组染色体，构成初始种群F0，并设t=0,Ft=F0.

3)求解下层规划模型f2，每个需求点按自身运输成本最小化原则选择枢纽点，并将需求点的选择及需求量等信息反馈到上层模型中.

4)求解上层规划目标函数f1，并把总目标值f作为适应度函数，对种群Ft进行选择、交叉、变异、合并等操作得到新种群Pt.其中选择操作采用轮盘赌方式，变异操作采用随机变异方式，交叉操作的思路是：对于每一对父代染色体，在每条父代染色体中寻找为1的基因位，将父代染色体融合产生子代，判断子代染色体中为1的基因位个数，如大于K，则去掉距离太近的两个枢纽点中的一个，若小于K，则父代染色体出现错误，需重新选择.

5)对新种群Pt进行快速非劣排序[17]，得到Ft+1.

6)此时，t=t+1，判断是否满足终止条件，若不满足返回到步骤3，若满足则运算终止，得出结果.

3 算例分析

某零担物流企业配送网络中共有200个需求点，决策者拟从中选择个别节点作为枢纽点构建配送中心以满足子公司(需求点)之间的货运需求，这就构成了初始的大规模零担物流轴辐式网络.随机产生200个节点，各节点之间的货运需求量服从0-1的随机分布.假定每个配送中心均有4个能级，这4个能级的容量分别为：2 000、2 800、3 600、4 800，对应的固定成本分别为：22 000、32 000、40 000、46 000.取单位货物单位距离的收集成本、中转成本及配送成本分别为3、0.75、2，建设成本与运输成本的权重均为0.5.之后，随着外界环境的变化，节点间需求量、单位运输成本等参数会发生一定变化，决策者需要考虑这些参数的影响，并通过调整原有网络来满足需求并降低总成本.

依据本文构建的轴辐式网络模型和分层遗传算法，设置参数包括：种群为200，进化代数为300代，交叉率为0.9，变异率为0.02，运用Matlab7.0编程计算求得最优解.图2中(a)～(d)分别表示不同场景下配送中心的选址以及需求点与配送中心之间货物分配关系情况，其中需求点用空心点表示，所选的配送中心用实心点表示，节点之间的分配关系用直线表示.当所选配送中心的个数依次为6、8、10、12时，所选配送中心的位置有所不同，且需求点与配送中心的分配关系也有相应变化，每个配送中心负责周边几个需求点货物的中转，这主要是由需求场景的不确定性和配送中心的容量能力共同决定的.此外，图3中(a)～(d)表示运用分层遗传算法计算大规模零担物流网络的运行过程，运行时间短，约1 min，且算法收敛性较好.

在上述初始网络结构基础上，考虑实际运营过程中，由于市场的不确定性，货流量、单位运输成本等因素会发生变化，因此决策者需要针对变化作相应调整.本文设计了如表1所示的3个实验，分别针对模型中变量对轴辐式网络的影响以及流量变化时的增量优化进行研究.

图2 不同场景下大规模零担物流网络枢纽选址及流量分配情况Fig.2 Hub location and flow allocation decisions for the large-scale LTL logistics network in different schemes

图3 运用分层遗传算法求解大规模零担物流网络运行情况Fig.3 Running status for solving the large-scale LTL logistics network using the hierarchical genetic algorithm

实验序号场景模型调整和分析过程1分析流量wij变化对网络的影响1)保持建设成本的权重λ和运输成本的权重θ为0．5不变；2)调节wij的大小，使wij∈0．2wij，2wij[]；3)实验结果见表2；4)分析实验结果．2分析单位运输成本变化对网络的影响1)保持建设成本的权重λ和运输成本的权重θ为0．5不变；2)按照-45%、-35%、-25%、25%、…、25%、35%、45%调节单位运输成本的大小；3)实验结果见表3；4)分析实验结果．3分析流量变化时建设成本权重对增量优化网络的影响1)调节建设成本权重λ=0．01，0．02，…，0．99，则θ=1-λ；2)对每一对λ、θ，在初始网络基础上，将流量按照1．15、1．25、1．35、1．45、1．55、1．65的倍数增加或减少；3)多次计算并分析实验结果．

表2 节点间流量wij变化对零担物流轴辐式网络的影响

表3 单位运输成本变化对零担物流轴辐式网络的影响

此外，实验3设计的零担物流网络增量优化显示，当节点间货流量发生变化时，建设成本权重系数较小情景下的轴辐式网络优化倾向于采用新建或关闭枢纽点数量策略来满足需求，原有枢纽点能级几乎不变，而对于权重系数较大的情景，网络增量优化则优先选择改变原有枢纽点能级，枢纽点数量变化不明显.究其原因，主要是建设成本对总成本的影响较大，赋予建设成本的权重越大，其对总成本的影响就越大.一般而言，改变原有枢纽能级的调整成本比新建枢纽点的固定成本要小很多，因此，为寻求总成本最低，建设成本权重系数较大的情景优先选择改变原有枢纽点能级，直到超出这些枢纽点最大容量时，才选择新建枢纽点.反之，当建设成本权重系数较小时，其对总成本的影响也较小，运输成本反而上升成为总成本的重要影响因素，此时仅仅改变原有枢纽点能级可能造成运输成本及总成本急剧增加，因此该情景下的网络增量优化优先选择新建或关闭枢纽点的决策.

4 结语

现实环境的多变性和需求的不确定性，使得零担物流网络更加复杂多变，零担物流运营商的服务网络遍及全国各地，构建合理的物流网络结构已经成为大型零担物流企业迫在眉睫的挑战.本文针对大规模零担物流网络优化问题，构建了基于双层规划的大规模零担物流轴辐式网络模型，并基于进化博弈和多目标优化思想，设计分层遗传算法来求解模型，最后以算例进行验证，得出大规模零担物流网络的枢纽选址、流量分配等决策.灵敏度分析表明节点间流量、单位运输成本等参数会对零担物流网络产生不同程度的影响；增量优化表明当货流量变化时，对建设成本权重较小的情景，决策者宜优先采取改变枢纽点数量来满足需求，而权重系数较大时则应当考虑改变原有枢纽点能级来应对变化.本文深化了对大规模零担物流网络问题的优化研究，为决策者解决大规模零担物流网络枢纽选址及流量分配问题提供了依据和参考，未来可以针对更加符合现实的动态复杂网络设计模型和算法，提高文章对现实的指导意义.

[1] 胡青蜜， 胡志华， 陶 莎. 二级轴辐式零担物流网络设计的资源均衡利用问题[J]. 公路交通科技，2013, 30(4):124-131.

[2] GOLDMAN A J. Optimal location for centers in a network[J]. Transportation Science, 1969, 3(4): 352-360.

[3] O’KELLY M E. A quadratic integer program for the location of interacting hub facilities[J]. European Journal of Operational Research, 1987, 32(3): 393-404.

[4] CAMARGO R S, MIRANDA G. Single allocation hub location problem under congestion: Network owner and user perspectives [J]. Expert Systems with Applications, 2012, 39(3):3385-3391.

[6] SENDER J, CLAUSEN U. Heuristics for solving a capacitated multiple allocation hub location problem with application in German wagonload traffic[J]. Electronic Notes in Discrete Mathematics, 2013(41):13-20.

[7] KRATICA J. An electromagnetism-like metaheuristic for the uncapacitated multiple allocation p- hub median problem[J]. Computers & Industrial Engineering, 2013, 66(4): 1015-1024.

[8] ALUMUR S A, NICKEL S, SALDANHA G F. Hub location under uncertainty[J]. Transportation Research Part B, 2012, 46(4):529-543.

[9] CORREIA I, NICKEL S, SALDANHA G F. Single-assignment hub location problems with multiple capacity levels[J]. Transportation Research Part B, 2010, 44(8) :1047-1066.

[10] ALUMUR S, KARA B Y. Network hub location problems: the state of the art[J]. European Journal of Operational Research, 2008, 190 (1):1-21.

[11] 张 健， 吴耀华， 刘 沛， 等. 公路快速货运复合轴辐式网络规划分析[J].山东大学学报(工学版)， 2008, 38(5):6-9.

[12] 汪传旭. 基于轴-辐运输系统的区域港口群二级物流运输网络优化[J]. 系统工程理论与实践, 2008(9): 152-158.

[13] 杨晗熠． 枢纽确定单连接轴—辐网络结构在中国民用航空网络中的应用[J].北京理工大学学报(社会科学版)， 2010, 12(2):27-30.

[14] 计明军， 陈 哲， 王清斌. 集装箱船舶支线运输航线优化算法[J].交通运输工程学报，2011, 11(4): 68-75.

[15] 吴旗韬， 张虹鸥， 叶玉瑶， 等. 基于轴辐网络模型的中欧集装箱航线优化[J].中山大学学报(自然科学版)，2012, 51(6): 131-138.

[16] 何 波， 孟卫东. 考虑顾客选择行为的逆向物流网络设计问题研究[J].中国管理科学, 2009, 17(6): 104-108.

[17] 李 砚， 杜 纲， 刘 波. 基于混合遗传算法的鲁棒双层规划求解[J].统计与决策, 2012(19): 44-47.

[18] 李昌兵， 杜茂康， 付德强. 求解双层规划问题的层次混沌量子遗传算法[J].系统工程学报, 2013, 28(2): 159-166.

Optimization for large-scale LTL logistics hub-and-spoke network

WANG Yanfeng1,2， HUANG Youfang2

(1. School of Economics and Management, Shanghai Ocean University, Shanghai 201306;2.Logistics Research Center, Shanghai Maritime University, Shanghai 201306)

The development of economy and smoothing of highway transportation make the less-than-truckload (LTL) logistics grow rapidly. In this paper, facing the large-scale LTL logistics network optimization problem, an optimization model is constructed based on bi-level programming for large-scale LTL logistics hub-and-spoke network. Based on the evolutionary game theory and multiple objective optimization, a hierarchical genetic algorithm is designed to solve the model. Then a numerical example is employed to validate the model and the algorithm. The hub location and flow allocation decisions for large-scale LTL logistics network are obtained. Sensitivity analysis shows that the flow and unit transportation cost have different influence on LTL logistics network. Incremental optimization suggests that changing hubs is the prior choice in the case of smallconstruction costs weigh, while greater weight requires adjustment on the capacities of hubs.

less-than-truckload logistics; hub-and-spoke network; bi-level programming; hierarchical genetic algorithm; optimization decision

2015-12-07.

教育部博士点基金项目(20123121110004)；上海海事大学研究生创新基金资助项目(2013ycx061)；上海海事大学优秀博士学位论文培育项目(2014bxlp002).

1000-1190(2016)04-0530-06

F252.21

A

*E-mail: guiyan_1234@163.com.