无容量限制的混合轴辐式零担运营网络优化

方晓平，何开先，陈维亚，倪玲霖

(1．中南大学交通运输工程学院，湖南长沙410075;2．浙江财经大学东方学院，浙江 杭州310018)

物流企业的运营网络可分为直通运输网络，轴辐式运输网络和混合轴辐式运输网络。其中，轴辐式网络还可以从不同方向进行细分，比如可分为非枢纽节点单分配网络和多分配网络，枢纽有能力约束的运输网络和枢纽无容量约束的运输网络，有运量折扣和无运量折扣的运输网络。另外，还有不同折扣方式的运输网络，货物流量可以分割的运输网络和不可以分割的运输网络，货物允许混装的运输网络和不允许混装的运输网络。很多学者针对不同的细分类型对轴辐式网络进行了优化研究。

各种分类的不同组合均能构成一个不同的问题。大类来讲，可先从轴辐式网络和混合轴辐式网络细分。关于轴辐式网络，李有梅等［1］研究了P－中位问题的启发式算法，段生虎［2］建立了针对云南地区的轴辐式网络优化模型，张世翔等［3］对长三角地区城市群建立了P－中位选址模型，并进行优化。还有学者从其他方面对轴辐式网络问题再进行细分，如文献［4］考虑了机场定价环境费用，建立了轴辐式网络优化模型，李红启等［5］研究了允许沿途停靠的货物运输网络枢纽选址问题，文献［6］将规模效应加入轴辐式网络优化模型并求解，文献［7］也在优化模型中加入了规模效应，并使用了非线性的折扣函数，这使他们的研究更接近实际。关于混合轴辐式网络的研究相对较少，具有代表性的有:文献［8］对货物允许混装的混合轴辐式网络进行了研究，得出了允许混装的运输网络成本比不允许混装的更低的结论，文献［9］建立了竞争下的混合轴辐式网络的选择构建优化模型，Lin等将规模效应应用到航空混合轴辐式网络中［10］。此外，还有学者综合考虑选址和路线，将两者一并优化，文献［11］和［12］分别建立了基于轴辐式和混合轴辐式网络的选址和线路优化模型。Zäpfel等［13］在考虑运输费用和分拣费用最小化，自由选择枢纽站的情况下，其中运输车分为配带1个或2个集装箱2种，建立了混合轴辐式的数学模型，并阐述了混合轴辐式网络与轴辐式相比可以节约成本。Barcos等［14］研究在保证一定服务水平，考虑运输费用和中转处理费用最小情况下，设计了可不经过枢纽，并带有沿途停靠点的零担货物运营网络。上述文献说明了混合轴辐式网络可以比轴辐式网络节约成本，但均没有考虑实体网络的新建与改造问题。翁克瑞［15］指出轴辐式网络产生了“绕道运输”，而混合轴辐式网络可以避免该问题，又提出以往轴辐式网络模型中的枢纽间折扣函数不合理。在函数断点处，细微的流量变化导致巨大的成本差异，为此，将折扣函数改成折扣率函数的拓展形式，虽然效果得到改善，但总运量与总运费倒挂问题依然存在。

本文研究在实体运营网络的限制下，考虑累进式折扣价格策略的中转枢纽选址和路线优化问题，旨在针对确定的OD需求，设计混合轴辐式运营网络，即:在轴辐式网络的基础上允许部分非枢纽节点之间直通运输和只经过1次枢纽中转的运输来设计货物运输路线。运输路段上的运输单价采用累进式折扣函数，考虑运输费用和枢纽节点中转费用，使得总成本最小。

1 模型的建立

很多物流企业已建成实体网络，即节点设施。在现有的实体网络下，如何选择最优运输路线是运营决策的核心问题。现针对国内1家已经完成实体网络布局的全国性零担货物运输服务商，其具有完善的2级枢纽。其中1级枢纽是中转枢纽，2级枢纽作为最低节点，不考虑2级枢纽以下的营业站。模型中的枢纽必须取自现有的1级枢纽集合中，并作如下假设:(1)任何OD对之间的流量都是确定的，车型固定，发车频率根据路段流量确定，且满足服务商承诺的服务水平。(2)允许所有的OD流直通运输，单点中转运输和两点中转运输。(3)OD流可分，即一对OD点间的货物可以分开采取不同路线。(4)总的成本费用包含运输成本和中转成本。

运输成本是和路段上流量相关的函数，有学者在此只针对枢纽之间使用固定折扣［16］。为了避免费用倒挂现象，本文针对全路段的分段累进式折扣函数f(·)。中转成本一般分为固定成本和变动成本。而文中所要研究的是在有形网络布局基础上，对运营网络，即无形网络进行优化。所以枢纽的固定成本就不是本问题的决策成本，故中转成本均是与通过枢纽节点流量成正比的费用g(·)。

所涉及的符号说明如下:

本模型是以运输成本和中转成本之和作为目标函数的。即

累进折扣定义如下:

式中:lr为每个区间的左端点;ur为每个区间的右端点;αr为对应区间的折扣值;l1=0，u1=l2，…，uR－1=lR，则平均折扣为

只有变动中转费用是决策成本，设其与流量成正比，枢纽节点k的中转成本定义如下:

式中:λk为枢纽节点k的单位流量处理费用。由此，目标函数可以写成:

当m=k时，i－k－k－j路线被计算2次，故而减去1项。约束条件如下:

经过k－m的全部流量，式(6)中的i≠k∪j≠m是为了避免k－m－k－m中路段k－m被计算2次。

2 模型的求解与结果

2．1 数据来源及初步处理

数据来自1家在国内全境从事公路零担物流服务的公司2011年全年的营业数据，一共128 018条，包括全国11大运营区下属的49个专线(含每条专线下属的收发站点)之间的OD货物流。另外，假设每辆运输车载质量平均为28 t。数据初步处理时，因计算条件限制，选取该公司18个城市，得出这18个城市之间的OD矩阵(如表1所示)。

表1 需求量OD矩阵Table 1 OD matrix of demand kg

续表1

2．2 计算结果

该数学模型是1个线性规划模型。本文直接使用lingo11．0软件在型号为AMD Athlon(tm)64*2 Dual－Core Processor TK－53的CPU环境下求解。

本算例中的18个节点，除了5个枢纽站属于1级节点外，其他均为2级节点，如表2所示。

表2 网络节点构成Table 2 Hubs and nodes

Lingo软件求解此类混合整数规划的算法是指数算法，也就是计算时间随着枢纽数量或节点数量的增加而急剧增加。模型中不同枢纽数的计算结果与计算时间比较如表3所示。

比较含有5个节点的轴辐式网络和混合轴辐式网络，目标总费用分别为8 686 950元和7 994 138元，总派车次数分别为145 974次和123 601。混合轴辐式网络比轴辐式网络节约了8．0%的费用和15．3%的派车次数。模型求得的混合轴辐式网络图如图1所示。

表3 不同枢纽数时的计算结果比较Table 3 Comparison on total cost and computing time of different hub set

图1 混合轴辐式网络的线路图Fig．1 Operational network of mixed hub － and － spoke resulted from sample data

3 结论

(1)混合轴辐式模型较单纯轴辐式模型可以节省费用，并减少派车次数。

(2)累进折扣费率的运用可避免简单折扣点附近运量与运价倒挂现象。

(3)随着枢纽数量的增加，计算时间呈指数增长。

(4)模型对于网络内的枢纽数量与OD结构的变化的适应性，使得该模型可以支持企业的日常运营决策。

［1］李有梅，陈晔．一种新的求解约束P－中位问题的启发式算法［J］．计算机工程，2005，31(19):162－164．LI Youmei，CHEN Ye．A new heuristic algorithm for capacitated pmedian problem［J］．Computer Engineering，2005，31(19):162 －164．

［2］段生虎．云南枢纽辐射式航空网络的构建［J］．航空制造技术，2005(2):53－55．DUAN Shenghu．Build a hub－and－spoke airline network for Yunnan［J］．Aeronautical Manufacturing Technology，2005(2):53－55．

［3］张世翔，霍佳震．基于轴辐式网络模型的长三角地区城市群物流配送体系规划研究［J］．管理学报，2005，2(增Ⅱ):194－199．ZHANG Shixiang，HUO Jiazhen．Research of city group logistics distribution system planning in Changjiang River Delta based on hub － and － spoke network model［J］．Chinese Journal of Management，2005，2(Sup Ⅱ):194 －199．

［4］Nero G，Black J A．Hub－and－spoke networks and the inclusion of environmental costs on airport pricing［J］．Transportation Research Part D:Transport and Environment，1998，3(5):275 － 296．

［5］李红启，刘鲁．Hub－and－Spoke型运输网络改善方法及其应用［J］．运筹与管理，2007，16(6):63－68．LI Hongqi，LIU Lu．Improvement and application of the hub－and－spoke transportation network［J］．Operations Research and Management Science，2007，16(6):63 －68．

［6］O’Kelly M E，Bryan D L．Hub location with flow economies of scale［J］．Transportation Research Part B:Methodological，1998，32(8):605 －616．

［7］Horner M W，O’Kelly M E．Embedding economies of scale concepts for hub network design［J］．Journal of Transport Geography，2001，9(4):255 －265．

［8］Liu J，Li C L，Chan C Y．Mixed truck delivery systems with both hub － and － spoke and direct shipment［J］．Transportation Research Part E:Logistics and Transportation Review，2003，39(4):325 －339．

［9］Adler N．Hub－spoke network choice under competition with an application to Western Europe［J］．Transportation Science，2005，39(1):58 －72．

［10］Lin C C，Lin Y J，Lin D Y．The economic effects of center－to－center directs on hub－and－spoke networks for air express common carriers［J］．Journal of Air Transport Management，2003，9(4):255 －265．

［11］Aykin T．The hub location and routing problem［J］．European Journal of Operational Research，1995，83(1):200－219．

［12］Melkote S，Daskin M S．An integrated model of facility location and transportation network design［J］．Transportation Research Part A:Policy and Practice，2001，35(6):515－538．

［13］Zäpfel G，Wasner M．Planning and optimization of hub－and－spoke transportation networks of cooperative third － party logistics providers［J］．International Journal of Production Economics，2002，78(2):207 －220．

［14］Barcos L，Rodríguez V M，álvarez M J，et al．Routing design for less－than－truckload motor carriers using ant colony techniques［J］．Workings Paper．Business Economics，2004 －14，2004．

［15］翁克瑞．轴辐式物流网络设计的选址与路线优化研究［D］．武汉:华中科技大学，2007．WENG Kerui．Research on location and routing optimization for hub－and－spoke logistics network design［D］．Wuhan:Huazhong University of Science and Technology，2007．

［16］张得志，李双艳．无容量约束单分配轴－辐式物流网络设计［J］．铁道科学与工程学报，2011，8(5):96－100．ZHANG Dezhi，LI Shuangyan．Research on an optimization model for logistics nodes dynamic location and its solution algorithm［J］．Journal of Railway Science and Engineering，2010，8(5):96 －100．