摘要
协同运输是近年发展并兴起的协同物流运作模式中的重要内容。协同运输要求相对独立的运输企业协同运作,共享物流资源和物流信息,共同承担客户需求,以达到减少车辆空载,降低整体物流成本,提高运行绩效和提高运输服务水平的目的。协同运输是一种新兴的运输模式和理念,面对此新型运输模式,产生诸多新问题有待研究。面向协同运输的车辆路径问题是其中一类基本而重要的问题。通过研究面向协同运输的车辆路径问题,可以确定运输企业在协同运输中最优车辆使用数目和车辆路径。同时,此问题也将为协同运输中的其他问题提供研究基础,对提高物流企业的生产经营管理水平和降低运作成本具有重要的理论意义和现实价值。
本文以面向协同运输的车辆路径问题为研究对象,提出面向协同运输的几类重要车辆路径问题,建立问题数学模型,综合运用组合优化、图论和启发式算法等方法和工具,设计求解问题的优化算法,并提出问题的有效不等式和紧凑下界,以定量评价所提出优化算法的求解精度。同时作为下一步研究的初步探讨,本文还以所研究的车辆路径问题作为基础,研究了面向协同运输的多企业利益分配问题。本文主要研究工作包括以下几点:
(1)综述了传统的车辆路径问题和面向协同运输的车辆路径问题。对车辆路径问题中两大基本问题,点路径问题和弧路径问题,以及面向协同运输特有的几类车辆路径问题,讨论分析了目前已经提出的数学模型、精确求解算法和启发式求解算法,分析了各种算法的求解性能。
(2)对基于任务选择的车辆路径问题进行研究。建立了此问题的混合整数规划数学模型。在分析问题数学模型特点的基础上,提出了问题的下界数学模型,采用数学规划软件Cplex实现分支定界算法求解下界数学模型,得到问题的下界。利用所研究问题的特性,基于简单启发式求解算法和最短路标签算法,设计了高效的现代现代启发式算法求解此问题。通过数值试验证明所提出启发式算法具有求解精度高,求解快速的特点,并验证了所提出的下界数学模型非常紧凑。
(3)首次提出开放-闭合混合式车辆路径问题。对此复杂问题建立精确数学模型,并设计现代启发式算法对此问题求解。启发式算法中嵌入利用了求解约束最短路问题的双标签算法,从而使得算法整体结构比较简单且易于实现。同时对此问题提出有效不等式,明显改进了分支定界算法求解问题的上界、下界效果和求解时间。数值试验证明,相对加入有效不等式提高后的Cplex求解结果,本文所提出的启发式算法在求解精度和求解时间两方面具有明显的优势。
(4)研究了两点间多次运输的多车场满载弧路径问题。针对目前精确算法求解此问题的不足,建立了该问题的全新数学规划模型和基于图论的模型,并设计了高效的两阶段启发式求解算法。第一阶段利用贪婪算法生成初始解,即形成完全覆盖运输任务弧的回路集;第二阶段组合和连接回路,构造起止于车场的闭通路。最后,利用局域搜索对求得的解改进,以得到最终解。同时,在分析问题特点性质基础上提出了新的下界数学规划模型。通过数值试验,定量分析了所提出启发式算法的求解效率和精度,同时分析对比了本文所提出的新下界模型和已有下界模型的效果。
(5)作为面向协同运输的车辆路径问题研究的扩展和进一步研究的探索,研究了面向协同运输的多企业利益分配问题。以面向协同运输的车辆路径问题优化结果为基础,同时采用Shapley值法对协同的利益在企业之间合理分配。对此问题研究深化了协同运输中利益分配问题的研究深度,为后续使用本论文的研究成果深入求解相关问题提供了借鉴和参考。
Collaborative transportation, as an emerging new mode, represents one of the major developing trends of transportation systems. Collaborative transportation brings together all participants to improve the overall performance of transportation planning and scheduling, share the information among the transportation companies, and reduce system-wide inefficiencies and cut down operational costs. Collaborative transportation was raised and adopted for only few years, thus there are many new problems that need to be studied. Among all these problems, vehicle routing problem, VRP, is an important and basic problem, which can help the companies in the collaborative transportation to utilize the vehicles and determine the optimal route scheme under some side constraints. Meanwhile, the VRPs are the basis of the collaborative transportation, since the results of the VRPs are necessary for other problems in the collaborative transportation. Therefore, in the collaborative transportation, developing solution algorithms with high quality and robustness for the VRPs is very necessary and significant to improve the management level and reduce the operation costs.
This dissertation focuses on some important variant problems of the VRP in the collaborative transportation. For these problems, this dissertation proposes mathematical models, develops sharp lower bounds and designs effective optimization algorithms. The major contributions are as follows:
(1) This dissertation shows a survey of the classical VRPs (i.e., the node routing problems and arc routing problems) and some special VRPs in the collaborative transportation. The mathematical models, exact algorithms and metaheuristics for these various problems are presented and discussed. Meanwhile, the implementation mechanisms and comparison of the different algorithms are given.
(2) The task selection and routing problem is introduced and studied in this dissertation, in which a truckload carrier receives tasks from shippers and other partners and makes a selection between a private vehicle and an external carrier to serve each task. The objective is to minimize the variable and fixed costs for operating the private fleet plus the total costs charged by the external carrier. Both the mathematical programming formulation and the lower bound are established. An effective memetic algorithm is developed to solve the problem. Computational experiments on a range of randomly generated instances are conducted. The results show that the proposed algorithm can produce high quality solutions within a reasonable computational time span.
(3) An optimization problem called the Closed-Open mixed vehicle routing problem is for the first time put forward, which can be used to assist in identifying routes when a carrier serves the customers through his private vehicles and vehicles hired from external carriers. The objective of the problem is to minimize the fixed and variable costs for operating the private vehicles and the hired vehicles. A mixed-integer programming model and an effective memetic algorithm are established for the problem. Computational experiments are conducted. The results show that the proposed algorithm is able to produce high reasonable solutions within an acceptable running time, and always outperforms the robust mixed-integer programming solver Cplex.
(4) A special optimization problem in the carrier collaboration system called the multi-depot capacitated arc routing problem with full truckloads is tackled in this dissertation. This dissertation proposes a mathematical programming model and its corresponding graph theory model, with the objective of minimizing empty vehicle movements. A two-phase greedy algorithm is given to solve practical large-scale problem instances. In the first phase, a set of directed cycles is created to fulfill the transportation orders. In the second phase, chains that are composed of cycles are generated. Furthermore, a set of local search strategies is put forward to improve the initial results. To evaluate the performance of the proposed algorithms, two lower bounds are developed. Finally, computational experiments on various randomly generated problems are conducted. The results show that the proposed methods are effective and the algorithms can provide reasonable solutions within an acceptable computational time.
(5) The profit sharing problem among transportation companies is also studied in this dissertation. This problem is studied on the basis of the optimization result of vehicle routing problems in the collaborative transportation. And, it is an extension of the vehicle routing problems in the collaborative transportation. In the first part, the profit margins resulting from cooperation among freight carriers are analyzed. In the second part, the possibilities of sharing these profit margins fairly among the partners are discussed. The Shapley value can be used to determine a fair allocation. Numerical results for test instances are presented. This study can promote the alliance of collaborative transportation. It can be absorbed and adapted by the future research about the related problems in the collaborative transportation.
引文
[1] Song, D.,Panayides, P. A conceptual application of cooperative game theory to liner shipping strategic alliances[J]. Maritime Policy and Management, 2002, 29 (3): 285-301.
[2] Engevall, S.,Gothe-Lundgren, M.,Varbrand, P. The Heterogeneous Vehicle-Routing Game[J]. Transportation Science, 2004, 38 (1): 71-85.
[3] Chen, X.,Simchi-Levi, D. Coordinating inventory control and pricing strategies: The continuous review model[J]. Operations Research Letters, 2006, 34 (3): 323-332.
[4] Ergun, O.,Kuyzu, G.,Savelsbergh, M. Reducing Truckload Transportation Costs Through Collaboration[J]. Transportation Science, 2007, 41 (2): 206-221.
[5] Agarwal, R.,Ergun. Mechanism design for a multicommodity flow game in service network alliances[J]. Operations Research Letters, 2008, 36 (5): 520-524.
[6] Zhang, A.,Zhang, Y. Issues on liberalization of air cargo services in international aviation[J]. Journal of Air Transport Management, 2002, 8 (5): 275-287.
[7] Ergun, ?.,Kuyzu, G.,Savelsbergh, M. Shipper collaboration[J]. Computers & Operations Research, 2007, 34 (6): 1551-1560.
[8]陈宁,刘会林,傅维新.多企业协同运输研究[J].武汉理工大学学报(交通科学与工程版), 2005, 29 (3): 440-443.
[9]刘冉,江志斌,陈峰,刘黎明,刘天堂.多车场满载协同运输问题模型与算法[J].上海交通大学学报, 2009, 43 (3): 455-459.
[10] Agarwal, R.,Ergun, ?.,Houghtalen, L.,Ozener, O. O. Collaboration in Cargo Transportation. In Optimization and Logistics Challenges in the Enterprise, 2009; 373-409.
[11] Liu, R.,Jiang, Z.,Fung, R. Y. K.,Chen, F.,Liu, X. Two-phase heuristic algorithms for full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration[J]. Computers & Operations Research, 2010, 37 (5): 950-959.
[12] Song, J.,Regan, A. Approximation algorithms for the bid construction problem in combinatorial auctions for the procurement of freight transportation contracts[J]. Transportation Research Part B: Methodological, 2005, 39 (10): 914-933.
[13] Lee, C.-G.,Kwon, R. H.,Ma, Z. A carrier's optimal bid generation problem in combinatorial auctions for transportation procurement[J]. Transportation Research Part E: Logistics and Transportation Review, 2007, 43 (2): 173-191.
[14] Houghtalen, L.,Ergun, O.,Sokol, J. Designing mechanisms for the management of carrier alliances[R]. Working paper, Georgia Institute of Technology, 2007.
[15] Dantzig, G. B.,Ramser, J. H. The Truck Dispatching Problem[J]. Management Science,1959, 6 (1): 80-91.
[16] Laporte, G. The vehicle routing problem: An overview of exact and approximate algorithms[J]. European Journal of Operational Research, 1992, 59 (3): 345-358.
[17] Bodin, L. Twenty years of routing and scheduling[J]. Operations Research, 1990, 38 (4): 571-579.
[18] Laporte, G. Fifty Years of Vehicle Routing[J]. Transportation Science, 2009, 43 (4): 408-416.
[19] Eiselt, H.,Gendreau, M.,Laporte, G. Arc Routing Problems, part I: The chinese postman problem[J]. Operations Research, 1995, 43 (2): 231-242.
[20] Eiselt, H.,Gendreau, M.,Laporte, G. Arc routing problems, part II: The rural postman problem[J]. Operations Research, 1995, 43 (3): 399-414.
[21] Chu, C. W. A heuristic algorithm for the truckload and less-than-truckload problem[J]. European Journal of Operational Research, 2005, 165 (3): 657-667.
[22] Bolduc, M. C.,Renaud, J.,Boctor, F.,Laporte, G. A perturbation metaheuristic for the vehicle routing problem with private fleet and common carriers[J]. Journal of the Operational Research Society, 2008, 59 (6): 776-787.
[23] Bolduc, M.,Renaud, J.,Boctor, F. A heuristic for the routing and carrier selection problem[J]. European Journal of Operational Research, 2007, 183 (2): 926-932.
[24] C?té, J.-F.,Potvin, J.-Y. A tabu search heuristic for the vehicle routing problem with private fleet and common carrier[J]. European Journal of Operational Research, 2009, 198 (2): 464-469.
[25] Laporte, G.,Mercure, H.,Nobert, Y. Exact algorithm for the asymmetrical capacitated vehicle routing problem[J]. Networks, 1986, 16 (1): 33-46.
[26] Christofides, N.,Eilon, S. An Algorithm for the Vehicle-Dispatching Problem[J]. Operational Research Quarterly, 1969, 20 (3): 309-318.
[27] Christofides, N.,Ningozzi, A.,Toth, P. Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations[J]. Mathematical Programming, 1981, 20 (3): 255-282.
[28] Eilon, S.,Watson-Gandy, C.,Christofides, N. Distribution management: mathematical modelling and practical analysis[M]. St. Martin's Griffin, 1971.
[29] Balinski, M. L.,Quandt, R. E. On an Integer Program for a Delivery Problem[J]. Operations Research, 1964, 12 (2): 300-304.
[30] R, R. M.,S, Z. Allocation of transportation units to alternative trips-A column generation scheme with out-of-kilter sub-problems[J]. Operations Research, 1968, 16 (1): 52-63
[31] Fisher, M. L.,Jaikumar, R. A generalized assignment heuristic for vehicle routing[J]. Networks, 1981, 11 (2): 109-124.
[32] Laporte, G.,Nobert, Y.,Desrochers, M. Optimal Routing under Capacity and Distance Restrictions[J]. Operations Research, 1985, 33 (5): 1050-1073.
[33] Clarke, G.,Wright, J. W. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points[J]. Operations Research, 1964, 12 (4): 568-581.
[34] Nelson, M. D.,Nygard, K. E.,Griffin, J. H.,Shreve, W. E. Implementation techniques for the vehicle routing problem[J]. Computers and Operations Research, 1985, 12 (3): 273-283.
[35] Paessens, H. The savings algorithm for the vehicle routing problem[J]. European Journal of Operational Research, 1988, 34 (3): 336-344.
[36] B. L. Golden, T. L. M., H. Q. Nguyen,. Implementing vehicle routing algorithms[J]. Networks, 1977, 7 (2): 113-148.
[37] Yellow, P. C. A Computational Modification to the Savings Method of Vehicle Scheduling[J]. Operational Research Quarterly 1970, 21 (2): 281-283.
[38] Gaskell, T. J. Bases for Vehicle Fleet Scheduling[J]. Operations Research, 1967, 18 (3): 281-295.
[39] Altinkemer, K.,Gavish, B. Parallel Savings Based Heuristics for the Delivery Problem[J]. Operations Research, 1991, 39 (3): 456-469.
[40] Wark, P.,Holt, J. A Repeated Matching Heuristic for the Vehicle Routeing Problem[J]. Journal of the Operational Research Society, 1994, 45 (10): 1156-1167.
[41] Mole, R. H.,Jameson, S. R. A Sequential Route-Building Algorithm Employing a Generalised Savings Criterion[J]. Operational Research Quarterly 1976, 27 (2): 503-511.
[42] Christofides, N.,Mingozz, i. A.,Toth, P. The vehicle routing problem. In Combinatorial Optimization, Christofides, N.,Mingozzi, A.,Toth, P., etc., Eds. Wiley: Chichester,UK, 1979; 315-338.
[43] Wren, A.,Holliday, A. Computer scheduling of vehicles from one or more depots to a number of delivery points[J]. Operational Research Quarterly, 1972, 23 (3): 333-344.
[44] Gillett, B.,Miller, L. A heuristic algorithm for the vehicle-dispatch problem[J]. Operations Research, 1974, 22 (2): 340-349.
[45] Foster, B. A.,Ryan, D. M. Integer programming approach to the vehicle scheduling problem[J]. Operational Research Quarterly, 1976, 27 (2): 367-384.
[46] Ryan, D. M.,Hjorring, C.,Glover, F. Extensions of the petal method for vehicle routeing[J]. Journal of the Operational Research Society, 1993, 44 (3): 289-296.
[47] Yogesh Agarwal, K. M., Harvey M. Salkin,. A set-partitioning-based exact algorithm for the vehicle routing problem[J]. Networks, 1989, 19 (7): 731-749.
[48] Renaud, J.,Boctor, F. F.,Laporte, G. An Improved Petal Heuristic for the Vehicle Routeing Problem[J]. Journal of the Operational Research Society, 1996, 47 (2): 329-336.
[49] Fisher, M. L.,Jaikumar, R.,Wassenhove, L. N. V. A Multiplier Adjustment Method for theGeneralized Assignment Problem[J]. Management Science, 1986, 32 (9): 1095-1103.
[50] Bramel, J.,Simchi-Levi, D. A Location Based Heuristic for General Routing Problems[J]. Operations Research, 1995, 43 (4): 649-660.
[51] Haimovich, M.,Rinnooy Kan, A. H. G. Bounds and Heuristics for Capacitated Routing Problems[J]. Mathematics of Operations Research, 1985, 10 (4): 527-542.
[52] Beasley, J. Route first-Cluster second methods for vehicle routing[J]. Omega, 1983, 11 (4): 403-408.
[53] Bertsimas, D. J.,Simchi-Levi, D. A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing Uncertainty[J]. Operations Research, 1996, 44 (2): 286-304.
[54] Prins, C. A simple and effective evolutionary algorithm for the vehicle routing problem[J]. Computers & Operations Research, 2004, 31 (12): 1985-2002.
[55] Lin, S. Computer solutions of the traveling salesman problem[J]. Bell System Technical Journal, 1965, 44 (10): 2245-2269.
[56] Lin, S.,Kernighan, B. An effective heuristic algorithm for the traveling-salesman problem[J]. Operations Research, 1973, 21 (2): 498-516.
[57] Renaud, J.,Boctor, F.,Laporte, G. A fast composite heuristic for the symmetric traveling salesman problem[J]. Informs Journal on Computing, 1996, 8 (2): 134-143.
[58] Thompson, P.,Psaraftis, H. Cyclic transfer algorithms for multivehicle routing and scheduling problems[J]. Operations Research, 1993, 41 (5): 935-946.
[59] Braysy, O.,Gendreau, M. Vehicle routing problem with time windows, Part I: Route construction and local search algorithms[J]. Transportation Science, 2005, 39 (1): 104-118.
[60] Braysy, O.,Gendreau, M. Vehicle routing problem with time windows, Part II: Metaheuristics[J]. Transportation Science, 2005, 39 (1): 119-139.
[61] Laporte, G. A concise guide to the Traveling Salesman Problem[J]. Journal of the Operational Research Society, 2010, 61 (1): 35-40.
[62] Kindervater, G.,Savelsbergh, M. Vehicle routing: Handling edge exchanges[J]. Local Search in Combinatorial Optimization, 1997, 337¨C360.
[63] Osman, I. H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem[J]. Annals of Operations Research, 1993, 41 (4): 421-451.
[64] Taillard,é. Parallel iterative search methods for vehicle routing problems[J]. Networks, 1993, 23 (8): 661-673.
[65] Gendreau, M.,Hertz, A.,Laporte, G. A Tabu Search Heuristic for the Vehicle Routing Problem[J]. Management Science, 1994, 40 (10): 1276-1290.
[66] Cordeau, J.,Gendreau, M.,Laporte, G. A tabu search heuristic for periodic and multi-depot vehicle routing problems[J]. Networks, 1997, 30 (2): 105-119.
[67] Cordeau, J. F.,Laporte, G.,Mercier, A. A unified tabu search heuristic for vehicle routingproblems with time windows[J]. Journal of the Operational Research Society, 2001, 52 (8): 928-936.
[68] Cordeau, J. F.,Laporte, G.,Mercier, A. Improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows[J]. Journal of the Operational Research Society, 2004, 55 (5): 542-546.
[69] Zachariadis, E. E.,Tarantilis, C. D.,Kiranoudis, C. T. A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints[J]. European Journal of Operational Research, 2009, 195 (3): 729-743.
[70] Brand?o, J. A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem[J]. European Journal of Operational Research, 2009, 195 (3): 716-728.
[71] Ergun, ?.,Orlin, J.,Steele-Feldman, A. Creating very large scale neighborhoods out of smaller ones by compounding moves[J]. Journal of Heuristics, 2006, 12 (1): 115-140.
[72] Van Breedam, A. Improvement heuristics for the Vehicle Routing Problem based on simulated annealing[J]. European Journal of Operational Research, 1995, 86 (3): 480-490.
[73] Tavakkoli-Moghaddam, R.,Safaei, N.,Gholipour, Y. A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length[J]. Applied Mathematics and Computation, 2006, 176 (2): 445-454.
[74] Leclerc, F.,Potvin, J.-Y. Genetic algorithms for vehicle dispatching[J]. International Transactions in Operational Research, 1997, 4 (5-6): 391-400.
[75] Berger, J.,Barkaoui, M. A parallel hybrid genetic algorithm for the vehicle routing problem with time windows[J]. Computers & Operations Research, 2004, 31 (12): 2037-2053.
[76] Park, Y.-B. A hybrid genetic algorithm for the vehicle scheduling problem with due times and time deadlines[J]. International Journal of Production Economics, 2001, 73 (2): 175-188.
[77] Hwang, H.-S. An improved model for vehicle routing problem with time constraint based on genetic algorithm[J]. Computers & Industrial Engineering, 2002, 42 (2-4): 361-369.
[78] Jeon, G.,Leep, H. R.,Shim, J. Y. A vehicle routing problem solved by using a hybrid genetic algorithm[J]. Computers & Industrial Engineering, 2007, 53 (4): 680-692.
[79] Baker, B. M.,Ayechew, M. A. A genetic algorithm for the vehicle routing problem[J]. Computers & Operations Research, 2003, 30 (5): 787-800.
[80] Rochat, Y.,Taillard,é. Probabilistic diversification and intensification in local search for vehicle routing[J]. Journal of Heuristics, 1995, 1 (1): 147-167.
[81] Bozkaya, B.,Erkut, E.,Laporte, G. A tabu search heuristic and adaptive memory procedure for political districting[J]. European Journal of Operational Research, 2003, 144 (1): 12-26.
[82] Tarantilis, C.,Kiranoudis, C. BoneRoute: an adaptive memory-based method for effective fleet management[J]. Annals of Operations Research, 2002, 115 (1): 227-241.
[83] Mester, D.,Br?ysy, O. Active guided evolution strategies for large-scale vehicle routing problems with time windows[J]. Computers & Operations Research, 2005, 32 (6): 1593-1614.
[84] Berger, J.,Barkaoui, M. A new hybrid genetic algorithm for the capacitated vehicle routing problem[J]. Journal of the Operational Research Society, 2003, 54 (12): 1254-1262.
[85] Bell, J. E.,McMullen, P. R. Ant colony optimization techniques for the vehicle routing problem[J]. Advanced Engineering Informatics, 2004, 18 (1): 41-48.
[86] Wang, H.,Shen, J. Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints[J]. Applied Mathematics and Computation, 2007, 190 (2): 1237-1249.
[87] Fuellerer, G.,Doerner, K. F.,Hartl, R. F.,Iori, M. Ant colony optimization for the two-dimensional loading vehicle routing problem[J]. Computers & Operations Research, 2009, 36 (3): 655-673.
[88] Gajpal, Y.,Abad, P. Multi-ant colony system (MACS) for a vehicle routing problem with backhauls[J]. European Journal of Operational Research, 2009, 196 (1): 102-117.
[89] Reimann, M.,Doerner, K.,Hartl, R. F. D-ants: Savings based ants divide and conquer the vehicle routing problem[J]. Computers & Operations Research, 2004, 31 (4): 563-591.
[90] Lenstra, J.,Kan, A. On general routing problems[J]. Networks, 1976, 6 (3): 273-280.
[91] Christofides, N.,Campos, V.,Corberan, A.,Mota, E. An algorithm for the rural postman problem[J]. Report IC. OR, 1981, 81.
[92] Christofides, N.,Campos, V.,Corberan, A.,Mota, E. An algorithm for the rural postman problem on a directed graph[J]. Mathematical Programming Study, 1986, 26 155-166.
[93] Belenguer, J. M.,Benavent, E. A cutting plane algorithm for the capacitated arc routing problem[J]. Computers & Operations Research, 2003, 30 (5): 705-728.
[94] Hirabayashi, R.,Saruwatari, Y.,Nishida, N. Tour construction algorithm for the capacitated arc routing problem[J]. Asia-Pacific Journal of Operational Research, 1992, 9 (2): 155-175.
[95] Baldacci, R.,Maniezzo, V. Exact methods based on node-routing formulations for undirected arc-routing problems[J]. Networks, 2006, 47 (1): 52-60.
[96] Longo, H.,De Arag?o, M. P.,Uchoa, E. Solving capacitated arc routing problems using a transformation to the CVRP[J]. Computers & Operations Research, 2006, 33 (6): 1823-1837.
[97] Dror, M. Arc routing: theory, solutions and applications[M]. Kluwer Academic Publishers, 2000.
[98] W?hlk. Contributions to arc routing[M]. University Press of Southern Denmark, 2005.
[99] Eglese, R. W. Routeing winter gritting vehicles[J]. Discrete Applied Mathematics, 1994, 48 (3): 231-244.
[100] Hertz, A.,Laporte, G.,Mittaz, M. A tabu search heuristic for the capacitated arc routingproblem[J]. Operations Research, 2000, 48 (1): 129-135.
[101] Amberg, A.,Domschke, W.,Vo?, S. Multiple center capacitated arc routing problems: A tabu search algorithm using capacitated trees[J]. European Journal of Operational Research, 2000, 124 (2): 360-376.
[102] Greistorfer, P. A tabu scatter search metaheuristic for the arc routing problem[J]. Computers & Industrial Engineering, 2003, 44 (2): 249-266.
[103] Lacomme, P.,Prins, C.,Ramdane-Cherif, W. Competitive memetic algorithms for arc routing problems[J]. Annals of Operations Research, 2004, 131 (1): 159-185.
[104] Ke, T.,Yi, M.,Xin, Y. Memetic Algorithm With Extended Neighborhood Search for Capacitated Arc Routing Problems[J]. IEEE Transactions on Evolutionary Computation, 2009, 13 (5): 1151-1166.
[105] Ulusoy, G. The fleet size and mix problem for capacitated arc routing[J]. European Journal of Operational Research, 1985, 22 (3): 329-337.
[106] Lacomme, P.,Prins, C.,Tanguy, A. First competitive ant colony scheme for the CARP[J]. Lecture Notes in Computer Science, 2004, 426-427.
[107] Beullens, P.,Muyldermans, L.,Cattrysse, D.,Van Oudheusden, D. A guided local search heuristic for the capacitated arc routing problem[J]. European Journal of Operational Research, 2003, 147 (3): 629-643.
[108] Hertz, A.,Mittaz, M. A variable neighborhood descent algorithm for the undirected capacitated arc routing problem[J]. Transportation Science, 2001, 35 (4): 425-434.
[109] Sariklis, D.,Powell, S. A heuristic method for the open vehicle routing problem[J]. Journal of the Operational Research Society, 2000, 51 (5): 564-573.
[110] Letchford, A.,Lysgaard, J.,Eglese, R. A branch-and-cut algorithm for the capacitated open vehicle routing problem[J]. Journal of the Operational Research Society, 2006, 58 (12): 1642-1651.
[111] Brand?o, J. A tabu search algorithm for the open vehicle routing problem[J]. European Journal of Operational Research, 2004, 157 (3): 552-564.
[112] Gendreau, M.,Hertz, A.,Laporte, G. New insertion and postoptimization procedures for the traveling salesman problem[J]. Operations Research, 1992, 40 (6): 1086-1094.
[113] Fu, Z.,Eglese, R.,Li, L. A new tabu search heuristic for the open vehicle routing problem[J]. Journal of the Operational Research Society, 2005, 56 (3): 267-274.
[114] Tarantilis, C. D.,Diakoulaki, D.,Kiranoudis, C. T. Combination of geographical information system and efficient routing algorithms for real life distribution operations[J]. European Journal of Operational Research, 2004, 152 (2): 437-453.
[115] Tarantilis, C. D.,Ioannou, G.,Kiranoudis, C. T.,Prastacos, G. P. Solving the open vehicle routeing problem via a single parameter metaheuristic algorithm[J]. Journal of the Operational Research Society, 2005, 56 (5): 588-596.
[116] Desaulniers, G.,Lavigne, J.,Soumis, F. Multi-depot vehicle scheduling problems with time windows and waiting costs[J]. European Journal of Operational Research, 1998, 111 (3): 479-494.
[117] Laporte, G.,Nobert, Y.,Taillefer, S. Solving a family of multi-depot vehicle routing and location-routing problems[J]. Transportation Science, 1988, 22 (3): 161.
[118] Forbes, M.,Holt, J.,Watts, A. An exact algorithm for multiple depot bus scheduling[J]. European Journal of Operational Research, 1994, 72 (1): 115-124.
[119] Mesquita, M.,Paixao, J. Exact algorithms for the multi-depot vehicle scheduling problem based on multicommodity network flow type formulations[J]. Lecture notes in economics and mathematical systems, 1999, 471 221-243.
[120] Kliewer, N.,Mellouli, T.,Suhl, L. A time-space network based exact optimization model for multi-depot bus scheduling[J]. European Journal of Operational Research, 2006, 175 (3): 1616-1627.
[121] Tillman, F. The multiple terminal delivery problem with probabilistic demands[J]. Transportation Science, 1969, 3 (3): 192.
[122] Tillman, F.,Hering, R. A study of a look-ahead procedure for solving the multiterminal delivery problem[J]. Transportation Research, 1971, 5 225-229.
[123] Tillman, F.,Cain, T. An upperbound algorithm for the single and multiple terminal delivery problem[J]. Management Science, 1972, 18 (11): 664-682.
[124] Gillett, B.,Johnson, J. Multi-terminal vehicle-dispatch algorithm[J]. Omega, 1976, 4 (6): 711-718.
[125] Golden, B.,Magnanti, T.,Nguyen, H. Implementing vehicle routing algorithms[J]. Networks, 1977, 7 (2): 113-148.
[126] Raft, O. A modular algorithm for an extended vehicle scheduling problem[J]. European Journal of Operational Research, 1982, 11 (1): 67-76.
[127] Renaud, J.,Laporte, G.,Boctor, F. F. A tabu search heuristic for the multi-depot vehicle routing problem[J]. Computers & Operations Research, 1996, 23 (3): 229-235.
[128] Crevier, B.,Cordeau, J. F.,Laporte, G. The multi-depot vehicle routing problem with inter-depot routes[J]. European Journal of Operational Research, 2007, 176 (2): 756-773.
[129] Salhi, S.,Sari, M. A multi-level composite heuristic for the multi-depot vehicle fleet mix problem[J]. European Journal of Operational Research, 1997, 103 (1): 95-112.
[130] Lim, A.,Wang, F. Multi-depot vehicle routing problem: A one-stage approach[J]. IEEE Transactions on Automation Science and Engineering, 2005, 2 (4): 397-402.
[131] Dondo, R.,Cerdá, J. A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows[J]. European Journal of Operational Research, 2007, 176 (3): 1478-1507.
[132] Arunapuram, S.,Mathur, K.,Solow, D. Vehicle routing and scheduling with full truckloads[J]. Transportation Science, 2003, 37 (2): 170-182.
[133] Cordeau, J.,Gendreau, M.,Laporte, G.,Potvin, J.,Semet, F. A guide to vehicle routing heuristics[J]. Journal of the Operational Research Society, 2002, 53 (5): 512-522.
[134] Tagmouti, M.,Gendreau, M.,Potvin, J. Y. Arc routing problems with time-dependent service costs[J]. European Journal of Operational Research, 2007, 181 (1): 30-39.
[135] Fran?a, P. M.,Mendes, A.,Moscato, P. A memetic algorithm for the total tardiness single machine scheduling problem[J]. European Journal of Operational Research, 2001, 132 (1): 224-242.
[136] Berretta, R.,Rodrigues, L. F. A memetic algorithm for a multistage capacitated lot-sizing problem[J]. International Journal of Production Economics, 2004, 87 (1): 67-81.
[137] Boudia, M.,Prins, C. A memetic algorithm with dynamic population management for an integrated production-distribution problem[J]. European Journal of Operational Research, 2009, 195 (3): 703-715.
[138] Pishvaee, M. S.,Farahani, R. Z.,Dullaert, W. A memetic algorithm for bi-objective integrated forward/reverse logistics network design[J]. Computers & Operations Research, 2010, 37 (6): 1100-1112.
[139] Prins, C. Two memetic algorithms for heterogeneous fleet vehicle routing problems[J]. Engineering Applications of Artificial Intelligence, 2009, 22 (6): 916-928.
[140] Liu, S.,Huang, W.,Ma, H. An effective genetic algorithm for the fleet size and mix vehicle routing problems[J]. Transportation Research Part E: Logistics and Transportation Review, 2009, 45 (3): 434-445.
[141] Golden, B.,Assad, A.,Levy, L.,Gheysens, F. The fleet size and mix vehicle routing problem[J]. Computers & Operations Research, 1984, 11 (1): 49-66.
[142] Cirasella, J.,Johnson, D.,McGeoch, L.,Zhang, W. The asymmetric traveling salesman problem: Algorithms, instance generators, and tests[J]. Lecture Notes in Computer Science, 2001, 32-59.
[143] Brest, J.,?erovnik, J. A heuristic for the asymmetric traveling salesman problem[A]. In The Sixth Metaheuristic International Conference[C], 2005.
[144] Hertz, A.,Widmer, M. Guidelines for the use of meta-heuristics in combinatorial optimization[J]. European Journal of Operational Research, 2003, 151 (2): 247-252.
[145] S?rensen, K.,Sevaux, M. MA|PM: Memetic algorithms with population management[J]. Computers & Operations Research, 2006, 33 (5): 1214-1225.
[146] Campos, V.,Laguna, M.,Marti, R. Context-independent scatter and tabu search for permutation problems[J]. Informs journal on computing, 2005, 17 (1): 111-122.
[147] Goldberg, D. E.,Robert Lingle, J. AllelesLociand the Traveling Salesman Problem[A]. In Proceedings of the 1st International Conference on Genetic Algorithms[C], 1985; 154-159.
[148] Oliver, I.,Smith, D.,Holland, J. A study of permutation crossover operators on the traveling salesman problem[A]. In 1987; 224-230.
[149] Syswerda, G. Uniform crossover in genetic algorithms[A]. In 1989; 2-9.
[150] Irnich, S.,Funke, B.,Grünert, T. Sequential search and its application to vehicle-routing problems[J]. Computers & Operations Research, 2006, 33 (8): 2405-2429.
[151] Tarantilis, C. D.,Kiranoudis, C. T. Distribution of fresh meat[J]. Journal of Food Engineering, 2002, 51 (1): 85-91.
[152] Li, F.,Golden, B.,Wasil, E. The open vehicle routing problem: Algorithms, large-scale test problems, and computational results[J]. Computers & Operations Research, 2007, 34 (10): 2918-2930.
[153] Pisinger, D.,Ropke, S. A general heuristic for vehicle routing problems[J]. Computers & Operations Research, 2007, 34 (8): 2403-2435.
[154] Aksen, D.,Ozyurt, Z.,Aras, N. Open vehicle routing problem with driver nodes and time deadlines[J]. Journal of the Operational Research Society, 2007, 58 (9): 1223-1234.
[155] Desrochers, M.,Laporte, G. Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints[J]. Operations Research Letters, 1991, 10 (1): 27-36.
[156] Kara, I.,Laporte, G.,Bektas, T. A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem[J]. European Journal of Operational Research, 2004, 158 (3): 793-795.
[157] Desrosiers, J., E Pelletier, E Soumis. Plus court chemin avec contraintes d'horaires[J]. RAIRO, 1983, 17 357-377(in French).
[158] Augerat, P.,Belenger, J.,Benavent, E.,Corberan, A.,Naddef, D.,Rinaldi, G. Computational results with a branch and cut code for the capacitated vehicle routing problem[R]. 1995.
[159] Dantzig, G.,Fulkerson, R.,Johnson, S. Solution of a Large-Scale Traveling-Salesman Problem[J]. Operations research, 1954, 2 (4): 393-410.
[160] Toth, P.,Vigo, D. Models, relaxations and exact approaches for the capacitated vehicle routing problem[J]. Discrete Applied Mathematics, 2002, 123 (1-3): 487-512.
[161] Gronalt, M.,Hartl, R. F.,Reimann, M. New savings based algorithms for time constrained pickup and delivery of full truckloads[J]. European Journal of Operational Research, 2003, 151 (3): 520-535.
[162] Muyldermans, L.,Beullens, P.,Cattrysse, D.,Van Oudheusden, D. Exploring Variants of 2-Opt and 3-Opt for the General Routing Problem[J]. Operations research, 2005, 53 (6): 982-995.
[163] Hertz, A.,Laporte, G.,Hugo, P. N. Improvement procedures for the undirected rural postman problem[J]. Informs journal on computing, 1999, 11 (1): 53-62.
[164]艾学山,王先甲,范文涛.基于Shapley值法的梯级水库收益分配研究[J].武汉理工大学学报, 2008, 30 (5): 79-81.
[165]叶飞.基于合作对策的供应链协作利益分配方法研究[J].计算机集成制造系统, 2004, 10 (12): 1523-1529.
[166]陈志,段贵军.基于Shapley值法的班轮运输联盟利益分配研究[J].交通运输工程与信息学报, 2005, 3 (4): 55-60.
[167]李波,杨灿军,陈鹰.基于合作对策的行业联合采购费用分摊研究[J].系统工程理论与实践, 2003, 23 (011): 65-70.
[168]姜连馥,刘维宁,满杰.多人合作对策理论在供应链联盟决策中的应用[J].北京交通大学学报, 2005, 4 (001): 19-22.
[169] Young, H.,Okada, N.,Hashimoto, T. Cost Allocation in Water Resources Development-A Case Study of Sweden[J]. Water Resources Research, 1982, 463-475.
[170]徐向阳,安景文,王银和.多人合作费用分摊的有效解法及其应用[J].系统工程理论与实践, 2000, 20 (3): 116-119.
[171] Aguilera, N. E.,Di Marco, S. C.,Escalante, M. S. The Shapley value for arbitrary families of coalitions[J]. European Journal of Operational Research, 2010, 204 (1): 125-138.
[172] Bilbao, J. M.,Ordó?ez, M. Axiomatizations of the Shapley value for games on augmenting systems[J]. European Journal of Operational Research, 2009, 196 (3): 1008-1014.
[173]陈文颖,侯盾.基于多人合作对策思想的总量控制优化治理投资费用分摊方法[J].环境科学学报, 1999, 19 (1): 57-62.
[174]熊国强.基于核心的多人合作对策的一种满意协调分配方式[J].系统工程, 2005, 23 (9): 8-11.
[175]于晓辉,张强.基于区间Shapley值的生产合作利益分配研究[J].北京理工大学学报, 2008, 28 (7): 655-658.
[176]李翠娟,宣国良.基于Shapley值的企业知识合作剩余分配与协调[J].上海交通大学学报, 2006, 40 (4): 588-592.
[177] Quigley, J.,Walls, L. Trading reliability targets within a supply chain using Shapley's value[J]. Reliability Engineering & System Safety, 2007, 92 (10): 1448-1457.
[178] Monderer, D.,Samet, D. Chapter 54 Variations on the shapley value. In Handbook of Game Theory with Economic Applications, Robert, A.,Sergiu, H., Eds. Elsevier: 2002; Vol. Volume 3, 2055-2076.
[179]张润红,罗荣桂.基于Shapley值法的共同配送利益分配研究[J].武汉理工大学学报, 2008, 30 (1): 150-153.
[180] Desrosiers, J.,Laporte, G.,Sauve, M.,Soumis, F.,Taillefer, S. Vehicle routing with full loads[J]. Computers and Operations Research, 1988, 15 (3): 219-226.
[181] Currie, R. H.,Salhi, S. Exact and Heuristic Methods for a Full-Load, Multi-Terminal,Vehicle Scheduling Problem with Backhauling and Time Windows[J]. The Journal of the Operational Research Society, 2003, 54 (4): 390-400.