摘要
随着我国经济的迅速发展,如何对快运系统进行优化已成为制约快运企业发展的重要问题。此优化涉及到两方面的内容,一是快运系统的结构优化,涉及到配送中心选址的优化问题、运输网络的结构优化问题等;另一方面是快运运营管理的优化,典型的有快运车辆装载问题和车辆路径安排问题。围绕上述本文主要做了以下工作：
(1)构建了国际快运运输网络基本模式,基于快运业时间阈值的特点以及干线和支线运输的运价折扣因素,建立了快运网络优化的混合整数规划模型,设计了基于LINGO的求解算法。通过数值实验,分析揭示了时间和成本这对快运业的永恒矛盾,有助于量化权衡快运业的广义成本,进而为快运网络优化提供决策支持。
(2)基于快运的多方式、多目标、以及多维度等特征,对快运网络进行超网络建模,提出了两种基于多种运输方式的成本与效率阈值的多目标超网络模型的优化策略,算例分析显示了快运网络的运输方式与快运效率、快运成本之间的优化关系。
(3)通过引入剩余空间及其相关作业,建立了基于剩余空间的厢式货车配载与配送联合优化的混合整数规划模型,提出了一种由C-W节约算法与基于剩余空间的装箱算法有机结合的交互式算法,仿真实验结果证实,联合优化优于配载优先与配送优先的单独优化。
(4)考虑了货物的易损性、装载的稳定性等配载约束,构建了车辆配载与配送联合优化的混合整数规划模型,基于问题自身的特点开发了由配载启发式算法和基于节约值的蚁群算法有机结合的混合算法,采用基准实验问题进行了一系列对比试验,结果显示了所提出的模型及算法的有效性与实用性。
With the rapid development of economy in our country, how to optimize the express transportation system has become an important problem restricting the progress of express enterprises. The optimization mainly involves two aspects, one is the structure optimization of the express system, such as the selection optimization of distribution center location, and the structure optimization of the transportation network, etc.; the other is the management optimization of express operation, especially the typical vehicle filling problem and vehicle routing problem.The main work in this dissertation about the above problems is as follows:
(1) A basic model of regional transportation network of international express is built. Then, based on the feature of the time threshold in express delivery industry and the freight transport discount factor of link and extension, a mixed integer programming model of regional express network optimization is established, an solver algorithm based on LINGO is designed. The analysis for example reveals the eternal contradiction between time and cost in express delivery industry, which could help to quantify the generalized cost of express delivery industry, and thus provide decision support for regional express network optimization.
(2) A super network model for express transportation network is put forward, and two methods of optimization based on the cost and the efficiency of multiple transportation modes and the multiple objectives are proposed. A numerical experimental example shows the optimal relationship between transportation modes and express efficiency and cost in ETN.
(3) By means of introducing the residual space and its correlative operations, an integrated optimized mixed integer programming model on both vehicle filling problem (VFP) and vehicle routing problem (VRP) for van truck transportation, based on residual space, is proposed. Then, a new interactive algorithm, suitable for the above model, is designed. The simulation experiments demonstrate that the total objective function of the integrated optimization increases by comparing with two kinds of separate sub-problem optimization instances, which preferentially consider VRP and VFP.
(4) With the consideration of vehicle loading constraints, such as cargo destructibleness, loading stability, unwarrantable upside down, vehicle balance, and last-in-first-ou unloading rule, an integrated optimized mixed integer programming model is proposed. Then, a hybrid interactive algorithm, consisting of a series of heuristic loading rules for VFP and an ant colony optimization algorithm based on the C-W saving heuristic rule for VRP, has been developed suitable for the above model. The simulation experiments, from the benchmark problems, are conducted, and the results with comparison to those in the current literatures demonstrate the effectiveness and practicality of both the model and algorithm.
引文
[1]程晓玲.城市物流节点选址方法研究[硕十学位论文].长安大学,2008.
[2]日通综合研究所物流手册.北京：中国物资出版社,1986.
[3]Kuehn A A, Hamburger M. A heuristic program for locating warehouses. Management Science,1963,9(6):643-666.
[4]蔡希贤,夏十智.物理化的数量方法.武汉：华中理工大学出版社,1985.
[5]Barcelo J, Casanovas J. A heuristic lagrangian algorithm for capacitated plant location problem. European Journal of Operational Research,1984,15(2):212-226.
[6]Geoffrion A M, Graves G W. Multicommodity distribution system design by benders decomposition. Management Science,1974,20(5):822-844.
[7]Chestler L. Overnight air express:spatial pattern, competition and the future in small package delivery services. Transportation Quarterly,1985,39(1):59-71.
[8]Wesolowsky G 0, Truscott W G. The multiperiod location-allocation problem with relocation of facilities. Management Science,1976,22 (1):57-65.
[9]Pirkul H, Jayaraman V. A multi commodity, multi-plant, capacitated facility location problem:formulation and efficient heuristic solution. Computers and Operations Research,1998(25):69-78.
[10]Brimberg 0, Revelle C. A bi-objective plant Location problem:cost vs. demand served. Location Science,1998,6(1):121-135.
[11]Vaidy N, Jayaraman. A multi-objective logistics model for a capacitated service facility problem. International Journal of Physical Distribution & Logistics Management,1999,29 (1):69-70.
[12]刘海燕,李宗平, 叶怀珍.物流配送中心选址模型.西南交通大学学报,2000,35(3)：311-314.
[13]Oded B, Zvi D, George 0 W. Satisfying partial demand in facilities location. HE Transactions,2002,34:971-978.
[14]李延晖,马士华,刘黎明.基于时间约束的配送系统模型及一种启发式算法.系统工程,2003,21(04)：23-28.
[15]李延晖,马士华,刘黎明.基于时间约束的供应链配送系统随机模型.预测,2004,23(04)：45-47.
[16]Emanuel M, Hokey M. Redesigning a warehouse network. European Journal of Operational Research,2007,176(1):210-229.
[17]Daskin M S, Coullard C R, Shen Z M. An inventory-location model:formulation, solution algorithm and computational results. Annals of Operations Research, 2002,110(1-4):83-106.
[18]王勇,邓哲锋,徐鹏.基于多折扣价格报价的库存与运输整合优化模型.工业工程,2009(06)：85-89.
[19]陈大伟,徐中,李旭宏.区域综合货运枢纽布局优化模型.华南理工大学学报(自然科学版),2009(11)：31-36.
[20]Armacost A P, Barnhart C, Ware K A, et al. UPS optimizes its air network. Interfaces, 2004,34(1):15-25.
[21]Hendricks K, Piccione M, Tan G F. Entry and exit in hub-spoke networks. Rand Journal of Economics,1997,28(8):291-303.
[22]Pels E, Nijkamp P, Rietveld P. A note on the optimality of airline networks. Economics Letters,2000,69:429-434.
[23]倪玲霖,史峰,方晓平,等.全连通快递网络与轴辐快递网络的比较.系统工程,2009(12)：45-50.
[24]Kuby M J, Gray R G. The hub network design problem with stopovers and feeders: the case of federal express. Transportation Research Part A,1993,27(1):1-12.
[25]Wasner M, Czunther Z. An integrated Multi-depot hub-location vehicle routing model for network planning of parcel service. International Journal of Production Economics,2004,90(3):403-419.
[26]Barnhart C, Schneur R. Air network design for express shipment service. Operations Research,1996,44(6):852-863.
[27]刘沛.轴辐式快速货运网络规划研究[硕士学位论文].山东大学,2007.
[28]张健,吴耀华,刘沛,等.公路快速货运复合轴辐式网络规划分析.山东大学学报(工学版),2008(05)：6-9.
[29]杨华,聂玉超,张洪斌,等.基于复杂网络的快递网络性质分析.北京师范大学学报(自然科学版),2009(01)：101-103.
[30]Girvan M, Newman M E J. Community structure in social and biological networks. Proc.Nat1. Acad. Sci. USA,2002,99(12):7821-7826.
[31]Fisher M L. Optimal solution of vehicle routing problems using minimum k-trees. Operations Researeh,1994,42(4):141-153.
[32]Padberg M, Rinaldi G. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review,1991,33(1):60-100.
[33]Kohl N, Madsen 0 B G. An optimization algorithm for the vehicle routing problem with time windows based on lagrangian relaxation. OperationsResearch, 1997,45(3):395-406.
[34]Tan K C, Chew Y H, Lee L H. A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems. European Journal of Operational Research,2006,172(3):855-885.
[35]李志威,张旭梅.基于动态扫描和蚂蚁算法的物流配送网络优化研究.管理工程学报,2006(04)：9-12.
[36]Wen H Y. Genetic algorithm based computation of shortest path in discrete-time networks. Journal of South China University of Technology,2008,36(2):13-16.
[37]张丽霞,赵又群,潘福全.Hopfield神经网络算法求解路网最优路径.哈尔滨工业大学学报,2009(09)：222-224.
[38]李宁,邹彤,孙德宝.车辆路径问题的粒子群算法研究.系统工程学报,2004(06)：596-600.
[39]Zhang H. Immune optimization algorithm for constrained nonlinear multiobjective optimization problems. Applied Soft Computing Journal,2007,7(3):840-857.
[40]蒋忠中,汪定伟.物流配送车辆路径优化的模糊规划模型与算法.系统仿真学报,2006(11)：3301-3304.
[41]何波,杨超,张华.废弃物回收的多层逆向物流网络优化设计问题研究.中国管理科学,2007(03)：61-67.
[42]何波,杨超,杨堪.废弃物逆向物流网络设计的模糊多目标优化模型.工业工程与管理,2007,5：43-46.
[43]Dyckhoff H. A typology of cutting and packing problems. European Journal of Operational Research,1990,44(2):145-159.
[44]王金敏,马丰宁,刘黎.模拟退火算法在布局求解中的应用.机械设计,2000(02)：6-9.
[45]George J A, Robinson D F. A heuristic for packing boxes into a container. Computers & Operations Research,1980,7(3):147-156.
[46]Bischoff E E, Marriott M D. A comparative evaluation of heuristics for container loading. European Journal of Operational Research,1990,44(2):267-276.
[47]姜义东,查建中,何大勇.集装箱装载矩形货物的布局研究.铁道学报,2000(06)：13-18.
[48]樊建华,黄有群,刘嘉敏.集装箱装入算法的研究.沈阳工业大学学报,2002(04)：306-308.
[49]靳志宏,朴惠淑,杨华龙.集装箱多式联运系统装卸与运输一体化优化问题.系统工程,2005(11)：1-6.
[50]Jin Z, Ohno K, Du J. An efficient approach for the three-dimensional container packing problem with practical considerations. Asia-Pacific Journal of Operational Research,2004,21(3):279-298.
[51]Jin Z, Ito T, Ohno K. A sub-volume based simulated annealing algorithm for the three-dimensional container packing problem. Journal of Japan Industrial Management Association,2002,53(3):220-227.
[52]卜雷,袁新江,蒲云,等.基于遗传算法的集装箱单箱三维装载优化问题.中国铁道科学,2004(04)：109-112.
[53]Burke E, Kendall G, Whitwell G. A new placemen heuristic for the orthogonal stock-cutting problem. Operations Research,2004,52(4):655-671.
[54]Lodi A, Martello S, Vigo D. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS Journal on Computing, 1999,11 (4):345-357.
[55]何琨,黄文奇.求解三维矩形布局的最大穴度算法.华中科技大学学报(自然科学版),2008(03)：92-94.
[56]Wilson N H M, Colvin N J. Computer control of the Rochester dial-a-ride system[M]. Massachusetts Institute of Technology, Center for Transportation Studies,1977.
[57]Psaraftis H N. A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem. Transportation Science,1980,14(2):130-154.
[58]Psaraftis H N. Dynamic vehicle routing problems. Vehicle routing:Methods and Studies,1988,16:223-248.
[59]Psaraftis H N. Dynamic vehicle routing:status and prospects. Annals of Operations Research,1995,61(1):143-164.
[60]Lund K, Madsen 0 B G, Rygaard J M. [M]. I MM Institute of Mathematical Modelling, 1996.
[61]Larsen A, Madsen 0 B G. The dynamic vehicle routing problem[D]. Technical University of DenmarkDanmarks Tekniske Universitet, Department of Transportlnstitut for Transport, Logistics & ITSLogistik & ITS,2000.
[62]Larsen A, Madsen 0, Solomon M. Partially dynamic vehicle routing-models and algorithms. Journal of the Operational Research Society,2002:637-646.
[63]Pavone M, Bisnik N, Frazzoli E, et al. A stochastic and dynamic vehicle routing problem with time windows and customer impatience. Mobile Networks and Applications, 2009,14(3):350-364.
[64]Attanasio A, Cordeau J F, Ghiani G, et al. Parallel Computing,2004,30(3):377-387.
[65]Fagerholt K, Foss B A, Horgen 0 J. A decision support model for establishing an air taxi service:a case study. Journal of the Operational Research Society, 2008,60(9):1173-1182.
[66]Moretti B R, Amaral A V, L(?)kketangen A. Adaptive granular local search heuristic for a dynamic vehicle routing problem. Computers & Operations Research,2009,36(11): 2955-2968.
[67]Ghiani G, Manni E, Quaranta A, et al. Anticipatory algorithms for same-day courier dispatching. Transportation Research Part E:Logistics and Transportation Review, 2009,45(1):96-106.
[68]Gendreau M, Laporte G, Semet F. A dynamic model and parallel tabu search heuristic for real-time ambulance relocation. Parallel computing,2001,27(12):1641-1653.
[69]Pureza V, Laporte G. Waiting and buffering strategies for the dynamic pickup and delivery problem with time windows. INFOR:Information Systems and Operational Research,2008,46 (3):165-176.
[70]Yang J, Jaillet P, Mahmassani H. Real-time multivehicle truckload pickup and delivery problems. Transportation Science,2004,38(2):135-148.
[71]Mitrovi6-Mini6 S, Laporte G. Waiting strategies for the dynamic pickup and delivery problem with time windows. Transportation Research Part B:Methodological, 2004,38 (7):635-655.
[72]Branke J, Middendorf M, Noeth G, et al. Waiting strategies for dynamic vehicle routing. Transportation science,2005,39(3):298-312.
[73]Haghani A, Jung S. A dynamic vehicle routing problem with time-dependent travel times. Computers & operations research,2005,32(11):2959-2986.
[74]Du T C, Li E Y, Chou D. Dynamic vehicle routing for online B2C delivery. Omega, 2005,33(1):33-45.
[75]Potvin J Y, Xu Y, Benyahia I. Vehicle routing and scheduling with dynamic travel times. Computers & Operations Research,2006,33(4):1129-1137.
[76]Ichoua S, Gendreau M, Potvin J Y. Exploiting knowledge about future demands for real-time vehicle dispatching. Transportation Science,2006,40(2):211-225.
[77]Xiang Z, Chu C, Chen H. The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments. European Journal of Operational Research, 2008,185(2):534-551.
[78]Guner A R, Murat A, Chinnam R B. Dynamic routing under recurrent and non-recurrent congestion using real-time ITS information. Computers & Operations Research, 2012,39(2):358-373.
[79]Gendreau M, Guertin F, Potvin J Y, et al. Parallel tabu search for real-time vehicle routing and dispatching. Transportation science,1999,33(4):381-390.
[80]Ichoua S, Gendreau M, Potvin J Y. Diversion issues in real-time vehicle dispatching. Transportation Science,2000,34(4):426-438.
[81]Kergosien Y, Lente C, Piton D, et al. A tabu search heuristic for the dynamic transportation of patients between care units. European Journal of Operational Research,2011,214(2):442-452.
[82]Liao T Y, Hu T Y. An object-oriented evaluation framework for dynamic vehicle routing problems under real-time information. Expert Systems with Applications, 2011,38(10):12548-12558.
[83]Ichoua S, Gendreau M, Potvin J Y. Vehicle dispatching with time-dependent travel times. European journal of operational research,2003,144(2):379-396.
[84]Beaudry A, Laporte G, Melo T, et al. Dynamic transportation of patients in hospitals. OR spectrum,2010,32(1):77-107.
[85]Montemanni R, Gambardella L M, Rizzoli A E, et al. Ant colony system for a dynamic vehicle routing problem. Journal of Combinatorial Optimization,2005,10(4):327-343.
[86]Kim S, Lewis M E, White I C C. Optimal vehicle routing with real-time traffic information. Intelligent Transportation Systems, IEEE Transactions on,2005,6(2): 178-188.
[87]Gendreau M, Guertin F, Potvin J Y, et al. Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries. Transportation Research Part C:Emerging Technologies,2006,14(3):157-174.
[88]Huisman D, Freling R, Wagelmans A P M. A robust solution approach to the dynamic vehicle scheduling problem. Transportation Science,2004,38(4):447-458.
[89]Bent R W, Van H P. Scenario-based planning for partially dynamic vehicle routing with stochastic customers. Operations Research,2004,52 (6):977-987.
[90]Chen Z L, Xu H. Dynamic column generation for dynamic vehicle routing with time windows. Transportation Science,2006,40(1):74-88.
[91]Mes M, Van der Heijden M, Van Harten A. Comparison of agent-based scheduling to look-ahead heuristics for real-time transportation problems. European Journal of Operational Research,2007,181 (1):59-75.
[92]Ganshar F T, Ombuki-Berman B M. Dynamic vehicle rout ing using genetic algorithms. Applied Intelligence,2007,27(1):89-99.
[93]Du T, Wang F K, Lu P Y. A real-time vehicle-dispatching system for consolidating milk runs. Transportation Research Part E:Logistics and Transportation Review, 2007,43(5):565-577.
[94]Jaillet P, Wagner M R. Generalized online routing:new competitive ratios, resource augmentation, and asymptotic analyses. Operations research,2008,56(3): 745-757.
[95]Dorigo M. Swarm Intelligence:7th International Conference, ANTS 2010, Brussels, Belgium, September 8-10,2010 Proceedings [M]. Springer-Verlag New York Incorporated, 2010.
[96]Li J Q, Mirchandani P B, Borenstein D. A Lagrangian heuristic for the real-time vehicle rescheduling problem. Transportation Research Part E:Logistics and Transportation Review,2009,45(3):419-433.
[97]Hong L. An improved LNS algorithm for real-time vehicle routing problem with time windows. Computers & Operations Research,2012,39(2):151-163.
[98]Tagmouti M, Gendreau M, Potvin J Y. A dynamic capacitated arc routing problem with time-dependent service costs. Transportation Research Part C:Emerging Technologies,2011,19(1):20-28.
[99]Larsen A, Madsen 0 B G, Solomon M M. Recent developments in dynamic vehicle routing systems[M]. The Vehicle Routing Problem:Latest Advances and New Challenges. Springer US,2008.
[100]Berbeglia G, Cordeau J F, Laporte G. Dynamic pickup and delivery problems. European Journal of Operational Research,2010,202(1):8-15.
[101]谢秉磊,郭耀煌,郭强.动态车辆路径问题：现状与展望.系统工程理论方法应用,2002(02)：116-120.
[102]郭耀煌,谢秉磊.一类随机动态车辆路径问题的策略分析.管理工程学报,2003(04)：114-115.
[103]郭耀煌,钟小鹏.动态车辆路径问题排队模型分析.管理科学学报,2006(01)：33-37.
[104]张建勇,李军,郭耀煌.带模糊预约时间的动态VRP的插入启发式算法.西南交通大学学报,2008(01)：107-113.
[105]吴兆福,董文永.求解动态车辆路径问题的演化蚁群算法.武汉大学学报(理学版),2007(05)：571-575.
[106]王江晴,康立山.动态车辆路径问题中的实时最短路径算法研究.武汉理工大学学报(交通科学与工程版),2007(01)：46-49.
[107]王江晴,康立山.动态车辆路径问题中实时信息生成算法.计算机与数字工程,2007(04)：16-18.
[108]王江晴,康立山.动态车辆路径问题仿真器的设计与实现.核电子学与探测技术,2007(05)：991-994.
[109]刘霞,齐欢.带时间窗的动态车辆路径问题的局部搜索算法.交通运输工程学报,2008(05)：114-120.
[110]刘士新,冯海兰.动态车辆路径问题的优化方法.东北大学学报(自然科学版),2008(04)：484-487.
[111]熊浩,胡列格.多车型动态车辆调度及其遗传算法.系统工程,2009(10)：21-24.
[112]王训斌,陆慧娟,陈五涛.带时间窗动态车辆路径问题的改进蚁群算法.工业控制计算机,2009(01)：41-43.
[113]陈晓眯,孟志青,徐杰.基于混合禁忌搜索算法的动态车辆路径研究.浙江工业大学 学报,2009(05)：580-585.
[114]王江晴,张潇.复杂环境下动态车辆路径问题的建模与求解.武汉大学学报(理学版),2010(04)：462-466.
[115]钱艳婷,王鹏涛,魏国利.动态车辆路径问题的算法研究.天津理工大学学报,2010(06)：72-74.
[116]胡明伟,唐浩.动态车辆路径问题的多目标优化模型与算法.深圳大学学报(理工版),2010(02)：230-235.
[117]王旭,葛显龙,代应.基于两阶段求解算法的动态车辆调度问题研究.控制与决策,2012(02)：175-181.
[118]洪联系.带时间窗口动态车辆路径规划模型及其求解算法.计算机工程与应用,2012(04)：244-248.
[119]胡祥培,丁秋雷,张漪,等.干扰管理研究评述.管理科学,2007(02)：2-8.
[120]王旭坪,吴绪,马超,等.运力受扰的多车场车辆调度干扰管理问题研究.中国管理科学,2010(06)：82-88.
[121]王旭坪,许传磊,胡祥培.有顾客时间窗和发货量变化的车辆调度干扰管理研究.管理科学,2008(05)：111-120.
[122]王旭坪,杨德礼,许传磊.有顾客需求变动的车辆调度干扰管理研究.运筹与管理,2009(04)：16-24.
[123]许顺斗,宋学君,涂奉生.复合结构快件网的成本模型及邮政快件网的结构优化设计.邮政研究,1998(06)：29-31.
[124]胡安康,连漪.轴辐式网络模型在现代物流配送优化中的应用.商场现代化,2009(09)：158-159.
[125]杨长春.国际货物运输方式的选择与应用[M].北京：对外经济贸易大学出版社,2006.
[126]Yang H, Nie Y C, Zhang H B, et al. Insight to the express transport network. Computer Physics Communications,2009,180:1511-1515.
[127]靳志宏,计明军.物流实用优化技术[G].北京：中国物资出版社,2008.
[128]靳志宏,兰辉,郭贝贝.基于现实约束的集装箱配载优化及可视化.系统工程理论与实践,2010(09)：1722-1728.
[129]Gendreau M, Iori M, Laporte G, et al. A tabu search algorithm for a routing and container loading problem. Transportation Science,2006,40(3):342-350.
[130]靳志宏,于波,侯丽晓.厢式货车配载与配送的联合优化.交通运输工程学报, 2010(03)：95-100.
[131]郭贝贝.复杂集装箱装载问题研究及可视化实现[硕士学位论文].大连海事大学,2009.
[132]程满中.蚂蚁算法在车辆路径问题中的研究[硕士学位论文].中南民族大学,2007.