非轴辐式快递网络的航线规划研究

2010，46（5）1 背景近年来，随着经济的飞速发展，快递业务也得到了一个难得的发展契机 。国外的快递巨头，如 UPS， Fedex， DHL， TNT 等纷纷加大了在中国大陆的投入，分抢中国快递这块大蛋糕 。国内也涌现出一批颇具规模的快递公司，像传统的 EMS，以及民营的宅急送 、申通 、顺丰 、大田等等，能够在一定程度上 、一定范围内跟国外的快递巨头进行正面对话 。随着竞争的升级，单纯的价格优势已经不再构成竞争力，国内的快递公司们也越来越把眼光关注到如何高效配置与运作资源，提高客户服务水平上来 。而飞机运输一直是整个快递网络的重中之重，因此，如何合理规划航线对降低运作成本，提高客户服务水平起着举足轻重的作用 。在快递服务中，客户服务水平是由客户委托货物到该货物到达目的地的时间确定的，有当天到达，第 2 日到达， 35 日到达等等1。一般来说，当日到达只有在同城快递中实现，而在城际快递中，最为快速的服务是第 2 日到达 。第 2 日到达网络（ Next-Day Air Network）对快递公司的要求最高，是理论研究的热点，也是该文所研究的对象 。1.1 问题描述在经典的快递服务网络理论的描述中，一个轴辐式快递网络如图 1 所示2。整个网络包括网关（ Gateway）每个网关都是本区域的中心，它的功能是收发本区域各地面中心（ Ground center）的货物，其中地面中心到网关的运输一般由卡车或者火车完成 。网络都会包含一个或多个中心点（ Hub），中心点除了具有网关的非轴辐式快递网络的航线规划研究戴 韬1，霍佳震2DAI Tao1， HUO Jia-zhen21.东华大学 旭日工商管理学院 电子商务与物流系，上海 2000512.同济大学 经济与管理学院，上海 2000921.Glorious Sun School of Business and Management， Donghua University， Shanghai 200051， China2.School of Economics and Management， Tongji University， Shanghai 200092， ChinaDAI Tao， HUO Jia-zhen.Research on express shipment network design based on non-hub network.Computer Engineeringand Applications， 2010， 46（ 5）： 193-196.Abstract： Express shipment service requires that shipments should be picked up and delivered within specified time intervals（ e.g.，24 hours， 48 hours）， so usually it is the airplane that accomplishes the long-distance transportation.The classical models on network design are reviewed.Then， considering the possible restrictions， two kinds of solutions facing the multi-commodity networkwithout a hub are presented， which are solution based on NLP model and solution based on improved ESSND model.At last， theuse of these two kinds of solutions is clarified in details， and the conclusion is that the solution based on improved ESSND modelcan obtain a near optimization result.Key words： network design； non-hub network； multi-commodity； express shipment service摘 要：快递服务要求在一个时间限制内（ 24 小时 、48 小时等）将货物从起点运送到目的地，由于对时间的严格要求，长距离的运输一般由飞机完成 。回顾了快递航线网络规划的经典模型，并研究了多货物流的非轴辐式快递网络，建立数学模型，分别提出了基于 NLP 模型和改进的 ESSND 模型的两种求解方法 。最后，设计算例，详细说明了这两类方法的使用，并得出结论改进的 ESSND 模型能够获得接近最优的结果 。关键词：网络规划；非轴辐式网络；多货物流；快递DOI： 10.3778/j.issn.1002-8331.2010.05.059 文章编号： 10028331（ 2010） 05-0193-04 文献标识码： A 中图分类号： C931.1基金项目：国家自然科学基金重大项目（ the Grand National Natural Science Foundation of China under Grant No.70832005） 。作者简介：戴韬（ 1983-），博士研究生，研究方向为工业工程与供应链管理；霍佳震（ 1962-），博士生导师，研究方向为工业工程与供应链管理 。收稿日期： 2008-12-18 修回日期： 2009-02-16图 1 轴辐式快递网络c1c2c3c4c5c6c7c8c9c10c11c12c13c14c15c3c16c17c18c19c20c4c21c22c23c10c6c14c12c8c9c11c24c13c20c17c18c3c1c10c12c14c4网关（ Gateway）中心点（ Hub）地面中心（ Ground Center）集货路径（ Pickup Link）送货路径（ Delivery Link）地面集货（ Feeder Link）地面送货（ Ground Link）Computer Engineering and Applications 计算机工程与应用 193Computer Engineering and Applications 计算机工程与应用2010，46（5）图 2 非轴辐式快递网络c1c2c3c4c5c6c7c8c9c10c11c12c13c14c15c16c17c18c19c20c21GatewayGround CenterPackage FlowGround Link所有功能外，是唯一的具有分拣功能的点 。因此，所有的货物都必须要先运送到中心点，在中心点分拣配载后再分发到目的地 。在货物从起点网关运送到中心点（中心点分发到目的地）的飞机航线中，由于飞机的特性约束，中途最多只允许一次停靠 。一个非轴辐式快递网络如图 2 所示 。在非轴辐式网络中，地面中心与网关之间的关系于运作方式跟轴辐式网络完全相同 。两类网络最大的区别是在网关间的运输过程中，取消了专门设置的 hub 点，相应地，每个网关都有了原来 hub 点才具有的分拣等功能，这样各网关之间的货物可以不用通过 hub 直接进行流动 。无论是上述的哪一类型网络，航线规划问题的目标都是首先选择最经济的路径满足各网关的需求，然后将不同类型的飞机航班安排到网络中，最后把货物指派到各飞机航班上 。1.2 文献综述关于网络规划问题的文献综述在 Minoux3， Magnanti 等4，Balakrishnan 等5， Gendron 等6， Barnhart 等7， Kim 等8的文章中均有涉及 。把这些研究成果归纳如下：（ 1） Chestler9研究了快递行业的早期发展 。定量分析了网络的结构，竞争模式与 hub 选址 。（ 2） Chan 和 Ponder10回顾了跟 Fedex 公司相关的航空货递业的发展历程 。他们概述了该行业的特征并作了管理实践的调查 。（ 3） Kanafani 和 Ghobrial11分析了航线网络中的汇聚（ hubbing）现象 。他们研究了汇聚现象背后的经济本质，并得出结论，在一些网络里面，合理的汇聚可以得到可观的经济效益 。（ 4） Hall12分析了通宵运输的约束对航空货递业一些特性的影响 。（ 5） Barnhart 和 Schneur13针对快递服务网路建立了数学模型，并设计了一个算法 。他们的数学模型中只有一个 hub 点也只有一种类型的飞机，他们的结论是货物流完全由飞机路径决定 。（ 6） Kuby 和 Gray14研究了轴辐式网络中的中途停留与补给问题，并且以 Fedex 的实际数据为例作了案例分析 。（ 7） Kim15针对复杂运输服务网络规划问题建立了一系列的模型和算法，并举例说明了该方法在快递业的使用 。（ 8） Magnanti16， Golden 和 Assad17， Desaulniers 等18， Desrosiers等19都研究了车辆路径选择的网络规划问题 。（ 9） Andrew P.Armacost20使用复合变量对快递服务网络进行建模和求解，解决了大型复杂网络因为变量规模过于庞大难以求解的问题 。1.3 研究内容从文献综述中，可以看到，几乎所有的研究都集中在轴辐式网络上，因为轴辐式快递网络运行稳定，易于管理，且在网关数量庞大时体现出了经济性，其在现实中更是得到了最广泛的应用，所有的大型快递公司都是按照这样的方式组织和规划网络 。但是在网关数量较少，特别是对国内的一些刚刚上一定规模的快递公司，轴辐式网络并不是一个最佳的选择，反而是非轴辐式网络更能够体现网络的优越性，然而理论上对于非轴辐式网络的模型和算法却是研究较少 。提出了两种解决非轴辐式快递网络的方法 。一种是基于 NLP（ Network Loading Problem）模型，另一种是基于改进的 ESSND（ Express Shipment Service Network Design）模型，在文章的最后还通过设计算例对提出的两种方法进行了详细说明 。2 经典轴辐式网络航线规划模型一般在文献中提到的 ESSND（ Express Shipment ServiceNetwork Design）网络都是指轴辐式网络 。它是在 NDP（ Network Design Problem）和 NLP（ Network Loading Problem）的基础上经过如下假设：（ 1）所有的货物都要经过 hub 点分拣；（ 2） hub 点的分拣 、起降能力有限；（ 3）集货与送货飞机数目均衡；（ 4）各 G 点进出飞机数目平衡 。一般的 ESSND 模型如下所示8：minfFrRfdfryfrkKxkijfFrRffrijufryfrfor all（ i， j） A （ 1）j：（ i， j） A xkij-j：（ j， i） A xkji=bkif i=O（ k），-bkif i=D（ k），0 Otherwise，iN， kK （ 2）rRfriyfr=0， iN， fF （ 3）rRfyfrnf， fF （ 4）fFrRfrhyfrah， hH （ 5）0xkij1， yfrZ+（ 6）目标函数表示飞机的运行成本和式（ 1）表示航线的容量约束，式（ 2）保证了货物流量的守恒，式（ 3）表示飞机数量平衡，式（ 4）表示飞机数量约束，式（ 5）表示 hub 点分拣 、起降能力约束 。为了对快递航线进行规划，首先应该确定每一个网关点的客户服务水平，即确定这些点的 EPT（ Earliest Pickup Time）和LDT（ Latest Delivery Time），以及 hub 点的 SET（ Sorting EndingTime）8；然后根据各 G 点的 EPT 和 LDT， hub 点的 SET 以及飞机的飞行时间与在各点的装卸时间，计算所有可能的飞行路径 。具体方法见文献 15。由于多货物流的快递网络规划是一个 NP 难问题，在 G 点个数上升时，问题的规模呈指数级增长，一般的解决整数规划的方法并不适用 。Andrew P.Armacost20引入了一个合成变量 c，重新定义 ESSND 模型，该变量由飞机的路径 、Gateway 的需求 、航线的容量三者合成，该模型最大特点是如果合成变量 c 取值为 “1”，所有该变量覆盖下的点的需求都能够满足，它把合成变1942010，46（5）图 3 基于 NLP 模型的非轴辐式网络航线规划流程图数据统计NLP 计算货物流安排Route客户服务水平确定图 4 由货物流构造飞机航线流程图更新货物流分配表添加航线是否陷入循环是否覆盖所有边产生路径图去掉最小量（由散航完成）是否是否有始发点否是是否G1G2G3G4G5G101 2001 6001 200880G22 00007002 3001 260G31 30060001 4001 450G41 4002 7001 70001 200G51 3001 4009901 4000表 1 网关货物流需求量分为 Single-Route、Multi-Route、Ramp-Transfer 三种，并证明了这样的变量 c 构造出来的新模型跟原模型是完全等价的 。该合成变量的引入，使得 ESSND 模型的规模得以大幅度减小，使得原来因为问题规模过于庞大无法求解的问题得到了解决 。3 基于 NLP 模型的非轴辐式网络航线规划NLP，全称为 Network Loading Problem，主要用来求解网络的最大负载问题，它的一般模型如下所示15：minfF（ i， j） Ahfijyfij+kK（ i， j） Ackijbkxkij（ 7）kKbkxkijfFufyfijfor all （ i， j） A （ 8）j：（ i， j） A xkij-j：（ j， i） A xkji=bkif i=O（ k），-bkif i=D（ k），0 Otherwise，iN， kK （ 9）jNyfij=jNyfji， iN， fF （ 10）0xkij1， yfijZ+（ 11）目标函数表示飞机的运行成本与货物流成本之和最小；由于货物流成本远小于飞机的运行成本且不同的路径选择下货物流成本变化幅度不大，在实际应用中经常将该项忽略不计 。式（ 8）表示航线的容量约束，式（ 9）保证了货物流守恒和所有 G点的需求得以实现，式（ 10）表示飞机进出数量平衡 。该模型有两类决策变量， xkij表示 k 类货物分配在边（ i， j）上的比例， yfij表示边（ i， j）被 f 类型飞机用到的次数 。基于 NLP 模型的非轴辐式网络航线规划方法如图 3 所示 。其中，数据统计是将各 G 点之间的货物流量进行统计； NLP计算货物流是将各 G 点的货物流满足约束地分配到网络中；然后，根据货物流分配安排航线；最后通过航线安排确定服务水平 。可见，这个方法是将航线资源当作最为稀缺的资源，追求航线资源的最大利用，以此来确定整个网络的客户服务水平 。通过研究 NLP 模型，可以发现，该模型只是将货物在满足航线容量约束与实现各点需求的条件下，以最小成本分配到网络中 。仍需要在此基础上将这些网络流构造成为可行的飞机路径，但是，由于可能货物流中存在着嵌套循环，并不是所有的网络流都可以毫无改动地构造出一套可行的飞机路径，可能里面有一些货物流需要通过其他途径完成（比如，外包给商业飞机做散航或是使用其他运输方式），这也符合我国的一些快递公司现实的操作方式的 。货物流构造飞机航线流程如图4 所示 。由 NLP 模型进行扩展的方法是一种启发式的方法，它的主要作用是对现有的资源条件及市场需求下，为如何确定客户服务水平提供一个参考，虽然由这个方法计算得到的飞机航班安排结果并不一定是最优的，但是由于 NLP 模型确定的货物流分配肯定是该网络运行的最理想状况（航线成本最省），可以为其他方法树立一个标杆 。4 基于改进的 ESSND模型解的非轴辐式网络航线规划经典的 ESSND 模型是针对轴辐式网络提出的，结合非轴辐式网络特征，对其进行了修正，修改后的 ESSND 模型如下所示：minfFrRfhfryfr+kKpPk（ ckpbk） xkp（ 12）kKppk（ pijbk） xkpfFrRufyfrrijfor all （ i， j） A （ 13）rRfriyfr=0 iN， fF （ 14）fFrRVyfr1 iN （ 15）ppkxkp=1 kK （ 16）oxkp1， yfrZ+（ 17）这个模型中目标函数及各约束的含义基本等同于 ESSND模型 。值得一提的是这里不再是用两点之间的边来表示货物流，而是把货物流分配到货物流路径（ path）中 。模型里有两类决策变量 xkp表示 k 类货物分配到 p 货物流路径上的比例， yfr表示由 f 类型的飞机完成 r 路径的次数 。这个模型清楚易懂，只要将所有 G 点的需求及所有被选的飞机路径 r 和货物流路径 f输入，模型即可求得最小运行成本的网络规划 。这种方法跟带轴辐式网络的计算方式类似，先计算所有可能的路径，然后选择成本最小的路径集合满足所有点的约束，最后确定所有点的客户服务水平 。比起上一种先货物流分配再路径的方法，这个方法保证求得的是给定路径下的最优解 。5 算例5.1 网络假设有一个非轴辐式网络包括 5 个网关（由于非轴辐式网络只有在网关点较少时才能体现出经济性，且从实际出发国内的快递公司的网络规模也较小，因此作了一个这样的假设） 。每个网关之间的货物流需求如表 1 所示 。戴 韬，霍佳震：非轴辐式快递网络的航线规划研究 195Computer Engineering and Applications 计算机工程与应用2010，46（5）（下转 223 页）图 8 基于改进 ESSND 模型的飞机路径图c1c2c3c1c4c5c1c6其中实线表示由 Fleet1完成，虚线由 Fleet2 完成 。这个航线网络的总运行成本是 865K。G5G4G1G3G2图 9 基于改进 ESSND 模型的飞机路径及各点客户服务水平19:30 21:00 22:00 23:00 0:00 1:004:000:302:002:0023:3024:001:0022:3023:000:0021:3021:3023:0020:3020:3021:3019:3019:30G3 G2 G4 G3G2G1G5G2G5 G4 G1 G5G1G2G4G1G1G2G3G4G5EPT19:0021:0019:0021:0019:00LDT2:304:301:3023:301:00Fleet1G1G2G3G4G5G102.02.51.01.0G22.002.01.51.5G32.52.001.52.0G41.01.51.502.0G51.01.52.02.00Fleet2G1G2G3G4G5G101.52.00.50.5G21.501.51.01.0G32.01.501.01.5G40.51.01.001.0G50.51.01.51.00表 2 两类飞机各点之间的运行时间图 5 基于 NLP 模型的货物流图其中实线表示由 Fleet1 完成，虚线由 Fleet2 完成 。这个货物流分配下的总运行成本是 800K。c1c2c3c1c4c5c1c6G5G4G3G2G1G1-G4（流量 3000）k2=1010 k3=590 k4=1400G1-G5（流量 3000）k2=990 k3=710 k5=1300G2-G4（流量 4850）k6=1200 k8=210 k9=2700 k24=750G2-G5（流量 2780）k8=390 k10=1400 k20=990G3-G4（流量 2850）k12=700 k14=1700 k24=450G3-G5（流量 3000）k11=1600 k15=990 k20=410G4-G1（流量 2400）k6=1200 k16=1200G4-G2（流量 5000）k2=1010 k12=700 k17=2300 k20=990G4-G3（流量 2610）k3=590 k8=210 k18=1400 k20=410G5-G1（流量 2400）k11=1600 k21=880G5-G2（流量 3000）k2=990 k22=1260 k24=750G5-G3（流量 3000）k3=710 k8=390 k23=1450 k24=450图 6 货物流分配图有两类飞机可供选择，其中类型 1（ Fleet1）的单架运输能力是 3 000 单位 。其单架运行成本由下式近似： c=20 000+30000x，其中 x 为运行时间 。类型 2（ Fleet2）的单架运输能力是 5000 单位 。其单架运行成本由下式近似： c=40 000+50 000x，其中x 为运行时间 。两类飞机在各点的飞行时间如表 2 所示 。5.2 基于 NLP 模型的求解模型求解由 ILOG 公司的 CPLEX9.0 组件完成，具体的编程及求解过程不在该文中讨论 。将货物流需求及飞机的假设建立模型，计算可以得到如图5 所示货物流图 。同时货物流分配图如图 6 所示 。图 6 中带下划线的货物及流量表示该货物不是始发，需要由其起始点转运过来，而 G1 点所有的货物均为始发，故可以从 G1 点开始构建飞机航线，按照图 4 所示的流程，最后可以得到构建的飞机航线与各点的客户需求水平如图 7 所示（其中，K8（ G2-G3）的部分（ 390 单位）需要由散航完成） 。5.3 基于改进 ESSND 模型的求解同样使用 CPLEX9.0 求解模型 。假设飞机最多只允许两次停靠，将该网络所有可能飞机路径（共 80 条） 、货物流路径（共80 条）输入模型，求解即可得到如下飞机路径图（如图 8） 。特别说明的是，这个航线的运行成本（ 865K）跟该网络的理想运行状况（ 800K）已经非常接近，说明这个方法能够获得接近最优的结果 。同时，各航线经过各点的起降时间及客户服务水平如图 9所示 。6 结论当前理论界对于快递航线规划问题基本上都是基于轴辐式网络展开的，对于非轴辐式网络研究较少，但是这种网络对于初具规模的国内的快递公司很有借鉴意义 。针对非轴辐式网络，提出了基于 NLP 和改进的 ESSND 模型的两种解法，并且编制算例对这两种方法进行验证 。结果表明，这两种方法都是可行的，且基于改进的 ESSND 的方法能够获得接近最优的航线网络规划 。参考文献：1 Barnhart C， Schneur R R.Air network design for express shipmentserviceJ.Operations Research， 1996， 44（ 6）： 852-863.2 Armacost A P， Barnhart C， Ware K A， et al.UPS optimizes its airnetworkJ.Interfaces， 2004， 34（ 1）： 15-25.3 Minoux M.Network synthesis and optimum network design problems：Models， solution methods and applicationsJ.Networks， 1989， 19.4 Magnanti T， Wong R.Network design and transportation planning：Models and algorithmsJ.Transportation Science， 1984， 18（ 1） .5 Balakrishnan A， Magnanti T L， Mirchandani P.Network designM/DellAmico M， Maffioli F， Martello S.Annotated Bibliographies inCombinatorial Optimization.New York： John Wiley and Sons.6 Gendron B， Crainic T G， Frangioni A.Multicommodity capacitatednetwork designM/Sanso B， Soriano P.Telecommunications NetworkPlanning， Dordrecht： Kluwer Academic Publisher.7 Barnhart C， Kim D.Transportation service network design： Modelsand algorithmsM/Wilson N H M.Lecture Notes in Economics andMathematical Systems 471： Computer -Aided Transit Scheduling.Berlin： Springer-Verlag， 1999： 259-283.8 Kim D， Barnhart C， Ware K， et al.Multimodal express package delivery： A service network design applicationJ.Transportation Science， 1999， 33（ 4）： 391-407.G1G2G3G4G5EPT19:0018:300:001:3020:30LDT9:004:304:002:307:30假设 G1 EPT=19： 00Fleet1G1（ 19:30） -G5（ 21:30） -G2（ 5:00） -G5（ 7:30） -G1（ 8:30）G5（ 21:30） -G3（ 0:30） -G4（ 3:00） -G1（ 4:00）G1（ 19:30） -G4（ 2:00） -G3（ 4:30） -G5（ 6:30）Fleet2G2（ 0:00） -G4（ 3:00） -G2（ 4:00）图 7 NLP 模型求得的客户服务时间及飞机航线1962010，46（5）（上接 196 页）9 Chestler L.Overnight air express： Spatial pattern， competition andthe future in small package delivery servicesJ.Transportation Quarterly， 1985， 39（ 1） .10 Chan Y， Ponder R J.The small package air freight industry inthe United States： A review of the federal express experienceJ.Transportation ResearchA， 1979， 13A.11 Kanafani A， Ghobrial A A.Airline hubbingSome implications forairport economicsJ.Transportation ResearchA， 1985， 19A.12 Hall R W.Configuration of an overnight package service networkJ.Transportation ResearchA， 1989， 23A（ 2） .13 Barnhart C， Schneur R.Air network design for express shipmentserviceJ.Operations Research， 1996， 44（ 6） .14 Kuby M J， Gray R G.The hub network design problem withstopovers and feeders： The case of federal expressJ.Transportation ResearchA， 1993， 27A（ 1） .15 Kim D.Large scale transportation service network design： Models，algorithms and applicationsD.Cambridge： MIT， 1997.16 Magnanti T.Combinatorial optimization and vehicle fleet planning：Perspectives and prospectsJ.Networks， 1981， 11.17 Golden B L， Assad A A.Vehicle routing： Methods and studiesM/Studies in Management Science and Systems.Amsterdam： North-Holland， 1988.18 Desaulniers G， Desrosiers J， Ioachim I， et al.A unified framework fordeterministic time constrained vehicle routing and crew scheduling problemsM/Crainic T G， Laporte G.Fleet Management and Logistics.Norwell， MA： Kluwer Academics Publisher， 1998： 57-93.19 Desrosiers J， Dumas Y， Solomon M， et al.Time constrained routingand schedulingC/Ball M O， Magnanti T L， Monma C L， et al.Handbooks in Operations Research and Management Science.Amsterdam： North Holland， 1995： 35-139.20 Armacost A P.Composite variable formulations for express shipment service netwo