模糊条件下市区集送货的计算机辅助调度
摘要
针对目前研究中存在的集送货代价描述不准确,不确定信息假设不合理,集送货动态调度方法效率较低等问题,建立评价调度方案优劣的代价函数,拟合模糊信息的隶属度曲线,设计高效的随机合理化禁忌算法、同步优化算法等,为建立高效实用的市区集送货计算机辅助调度系统打下基础。
论文首先建立集送货问题的数学系统,并提出扇面Dijkstra算法完成复杂路网模型下最短路径集合的快速求解。通过模糊综合判断方法计算车厢整理代价,同时综合考虑油耗代价、折旧代价、司机代价和正常装卸代价,建立评价调度方案优劣的集送货代价函数。同时,以典型路段的交通数据和实际物流企业的业务数据为基础,拟合模糊车速和模糊发货体积的隶属度函数,在此基础上引入调度人员的主观评价指标描述集送货问题的多模糊约束条件。
其次对具有模糊车速和模糊发货体积的集送货问题进行描述,提出随机合理化禁忌算法。在对线路的可行性进行分析的基础上,设计备选方案的随机合理化动态衍生方法,详细阐述基于均衡原理和代价最小原理的双特赦准则以及自适应的禁忌长度选取策略,并给出初始可行方案的快速生成方法。
然后针对集送货执行过程中出现新的发货客户这一突发情况,确定动态调度的开始时刻,并引入“虚拟客户”概念将动态问题静态化。在此基础上提出将同步优化算法与顺路插入算法紧密结合,并通过模糊综合判断方法进行智能选取的求解策略,同时设计车辆位置的分段模糊递推法消除由于执行时间的不确定性带来的车辆位置变化对优化结果的影响。
分析由于集送货任务变化导致调度方案无法按照原计划继续执行的情况,提出将变化客户和变化线路分开处理的两阶段应急调度算法。
最后详细介绍集送货计算机辅助调度系统,并利用系统对集送货代价函数、静态调度算法和动态调度算法进行实用性验证。通过近半年时间的运行,集送货计算机辅助调度系统在稳定性、安全性、实时性等方面均能满足设计要求。
In current research, costs of pickup and delivery are described not very accurately, uncertain information is assumed not very reasonably, efficiency of dynamic pickup and delivery dispatch method is not high. Therefore, cost function to evaluate dispatch solution is establlished, membership function of fuzzy information is simulated and efficient algorithms such as Random Reasonable Tabu Algorithm and Synchronized Optimization Algorithm are designed. These are all basis to design efficient and practical computer aided dispatch system for city pickup and delivery.
In this thesis, mathematic system of pickup and delivery problem is set up and shortest routes set under complex road network model are fast solved by Sector Dijkstra Algorithm. Carriage arranging cost is calculated through fuzzy judgment method. Fuel cost, depreciation cost, driver cost and common load/unload cost are all taken into consideration. Therefore, cost function of pickup and delivery is established to evaluate dispatch solution. Membership function of fuzzy velocity and fuzzy pickup volume is simulated based on traffic data on typical roads and operation data in real logistics enterprise. Subjective evaluation index from dispatcher is brought in to describe multiple fuzzy restrictions in pickup and delivery problem.
Second, pickup and delivery problem under fuzzy velocity and fuzzy pickup volume is described. Random Reasonable Tabu Algorithm is put forwards. Analyzing the routes feasibility, Random reasonable dynamic derivative method is designed. Dual-aspiration criterion based on equilibrium theory and minimum cost theory as well as self-adaptive Tabu length selection strategy is applied. Method that can fast create initial feasible solution is given.
Third, when new pickup client comes into pickup and delivery execution process, start time of dynamic dispatch is determined. Concept of“virtual client”is assumed to turn the dynamic problem into static. Based on this, solving strategy is designed, which combines the Synchronized Optimization Algorithm and by-way insertion algorithm tightly, then selects the solution by fuzzy judgement method. Vehicle location change, which comes from uncertainty of execution time, may influence the optimization result. In order to eliminate this influence, subsection fuzzy evolutive method is designed to estimate vehicle location.
The situation is analyzed, when planned solution of pickup and delivery can not be operated because tasks change.Two-phase emergency dispatch algorithm is set up, which separates changed clients and changed routes.
At last, computer aided dispatch system for pickup and delivery is explained in detail. Pickup and delivery cost function, static dispatch algorithm and dynamic dispatch algorithm are validated in practice. Half a year operation of this system shows that computer aided dispatch system for pickup and delivery meets the designed requirements in stability, safety and real-time performance.
论文首先建立集送货问题的数学系统,并提出扇面Dijkstra算法完成复杂路网模型下最短路径集合的快速求解。通过模糊综合判断方法计算车厢整理代价,同时综合考虑油耗代价、折旧代价、司机代价和正常装卸代价,建立评价调度方案优劣的集送货代价函数。同时,以典型路段的交通数据和实际物流企业的业务数据为基础,拟合模糊车速和模糊发货体积的隶属度函数,在此基础上引入调度人员的主观评价指标描述集送货问题的多模糊约束条件。
其次对具有模糊车速和模糊发货体积的集送货问题进行描述,提出随机合理化禁忌算法。在对线路的可行性进行分析的基础上,设计备选方案的随机合理化动态衍生方法,详细阐述基于均衡原理和代价最小原理的双特赦准则以及自适应的禁忌长度选取策略,并给出初始可行方案的快速生成方法。
然后针对集送货执行过程中出现新的发货客户这一突发情况,确定动态调度的开始时刻,并引入“虚拟客户”概念将动态问题静态化。在此基础上提出将同步优化算法与顺路插入算法紧密结合,并通过模糊综合判断方法进行智能选取的求解策略,同时设计车辆位置的分段模糊递推法消除由于执行时间的不确定性带来的车辆位置变化对优化结果的影响。
分析由于集送货任务变化导致调度方案无法按照原计划继续执行的情况,提出将变化客户和变化线路分开处理的两阶段应急调度算法。
最后详细介绍集送货计算机辅助调度系统,并利用系统对集送货代价函数、静态调度算法和动态调度算法进行实用性验证。通过近半年时间的运行,集送货计算机辅助调度系统在稳定性、安全性、实时性等方面均能满足设计要求。
In current research, costs of pickup and delivery are described not very accurately, uncertain information is assumed not very reasonably, efficiency of dynamic pickup and delivery dispatch method is not high. Therefore, cost function to evaluate dispatch solution is establlished, membership function of fuzzy information is simulated and efficient algorithms such as Random Reasonable Tabu Algorithm and Synchronized Optimization Algorithm are designed. These are all basis to design efficient and practical computer aided dispatch system for city pickup and delivery.
In this thesis, mathematic system of pickup and delivery problem is set up and shortest routes set under complex road network model are fast solved by Sector Dijkstra Algorithm. Carriage arranging cost is calculated through fuzzy judgment method. Fuel cost, depreciation cost, driver cost and common load/unload cost are all taken into consideration. Therefore, cost function of pickup and delivery is established to evaluate dispatch solution. Membership function of fuzzy velocity and fuzzy pickup volume is simulated based on traffic data on typical roads and operation data in real logistics enterprise. Subjective evaluation index from dispatcher is brought in to describe multiple fuzzy restrictions in pickup and delivery problem.
Second, pickup and delivery problem under fuzzy velocity and fuzzy pickup volume is described. Random Reasonable Tabu Algorithm is put forwards. Analyzing the routes feasibility, Random reasonable dynamic derivative method is designed. Dual-aspiration criterion based on equilibrium theory and minimum cost theory as well as self-adaptive Tabu length selection strategy is applied. Method that can fast create initial feasible solution is given.
Third, when new pickup client comes into pickup and delivery execution process, start time of dynamic dispatch is determined. Concept of“virtual client”is assumed to turn the dynamic problem into static. Based on this, solving strategy is designed, which combines the Synchronized Optimization Algorithm and by-way insertion algorithm tightly, then selects the solution by fuzzy judgement method. Vehicle location change, which comes from uncertainty of execution time, may influence the optimization result. In order to eliminate this influence, subsection fuzzy evolutive method is designed to estimate vehicle location.
The situation is analyzed, when planned solution of pickup and delivery can not be operated because tasks change.Two-phase emergency dispatch algorithm is set up, which separates changed clients and changed routes.
At last, computer aided dispatch system for pickup and delivery is explained in detail. Pickup and delivery cost function, static dispatch algorithm and dynamic dispatch algorithm are validated in practice. Half a year operation of this system shows that computer aided dispatch system for pickup and delivery meets the designed requirements in stability, safety and real-time performance.
引文
[1]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物资出版社,2001
[2] Balinsk M., Quandi R.. On an integer program for a delivery problem. Operations Research, 1964, 12: 300-304
[3] Stefan Irnich.A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles, European Journal of Operational Research, 2000, 122: P310-328
[4]李军,谢秉磊,郭耀煌.非满载车辆调度问题的遗传算法[J].系统工程理论方法应用, 2000, 9 (3) : 235-239.
[5] Fisher ML, Jaikumar R. A generalized assignment heuristic for vehicle routing problem[J]. Networks, 1981, 11: 109-124.
[6]曹剑东,郑四发,李兵等.基于中心分拨模式的多车场集送货一体化车辆优化调度方法[J].公路交通科技, 2006, 23(9): 140-144.
[7]郎茂祥.装卸混合车辆路径问题的模拟退火算法研究[J].系统工程学报, 2005, 20 (5) : 485-491.
[8] G.. Clarke and J.V. Wright. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 1964, 12: 568-581
[9]王鑫,谭畅.一种解决车辆调度问题的算法研究[J].控制工程, 2006,增刊, 193-195
[10]龚延成,郭晓芬,田光均等.带时间窗约束的物流配送线路启发式算法[J].交通与计算机, 2003, 6(21). 78-80
[11] Altinkemer K., Gavish B. Parallel savings based heuristics for the delivery problem[J]. Operations Research,1991, 39: 456-469
[12] Wark P., Holt J. A repeated matching heuristic for the vehicle routing problem[J]. Journal of the Operational Research Society, 1994, 45:1156-1167
[13] Mole R.H., Jameson S.R.. A sequential route-building algorithm employing a generalized savings criterion. Operational Research Quarterly, 1976, 27: 503-511
[14] Lin S. Computer solutions of the traveling salesman problem[J]. Bell System Technical Journal, 1965, 44: 2245-2269
[15] Gillett B.E., Miller L.R.. A heuristics algorithm for the vehicle dispatch problem. Operations Research, 1974, 22(4): 340-349
[16]刘浩,钱小燕.路径长度受限的随机需求VRP的模型和算法[J].南京工业大学学报, 2005, 27(3): 36-38
[17]陈伊菲,刘军.仓储拣选作业路径VRP模型设计与应用[J].计算机工程与应用, 2006, 6: 209-211
[18] Bramel J., Simchi-Levi D.. A location based heuristic for general routing problems[J]. Operations Research, 1995, 43: 649-660
[19] Christofides N.. The vehicle routing problem[J]. RAIRO, 1976, 10: 55-70
[20] Foster B.A., Ryan D.M.. An integer programming approach to the vehicle scheduling problem[J].Operations Research, 1976, 27: 367-384
[21] Ryan D.M, Hjorring C., Glover F.. Extensions of the petal method for vehicle routing[J]. Journal of Operational Research Society, 1993, 44: 289-296
[22] Renaud J., Boctor F.F., Laporte G.. An improved petal heuristic for the vehicle routing problem[J]. Journal of Operational Research Society, 1996, 47: 329-336
[23] Beasley J.E.. Route-first cluster-second methods for vehicle routing[J]. Omega, 1983, 11: 403-408
[24] Lin S., Kernighan B.W.. An effective heuristic algorithm for the traveling salesman problem. Operations Research, 1973, 21: 498-516
[25] Renaud J., Boctor F.F., Laporte G.. A fast composite heuristic for the symmetric traveling salesman problem[J]. INFORMS Journal on computing, 1996, 8(2): 134-143
[26] Thompson P.M., Psaraftis H.N.. Cyclic transfer algorithm for multi-vehicle routing and scheduling problems. Operations Research, 1993, 41: 935-946
[27]李大卫,王莉,王梦光.一个求解带有时间窗口约束的车辆路径问题的启发式算法.系统工程, 1998, 16(4): 20-24
[28]李军.车辆调度问题的分派启发式算法.系统工程理论与实践, 1999, (l): 27-33
[29]李军.有时间窗的车辆调度问题的网络启发式算法.系统工程, 1999, 17(2): 66-71
[30]叶耀华,朱晓梅,陈霖.一种带时间窗口和在前约束的车辆路线问题及其算法.系统工程理论与实践, 2000, 3:110-112
[31]刑文训,谢金星.现代优化计算方法[M].北京:清华大学出版社, 2003
[32] RobustéF., Daganzo C.F., Souleyrette R..Implementing vehicle routing models[J]. Transportation Research B, 1990, 24(4): 263-286
[33] Alfa A.S., Heragu S.S., Chen M. A 3-opt based simulated annealing algorithm for vehicle routing problems[J]. Computers & Industrial Engineering, 1991, 21: 635-639
[34] Osman I.H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 1993, 41(2): 421-451
[35]胡大伟,朱志强,胡勇.车辆路径问题的模拟退火算法.中国公路学报, 2006, 19(4): 123-126
[36] Van Breedam A.. Improvement heuristics for the vehicle routing problem based onsimulated annealing. European Journal of Operational Research, 1995, 86: 480-490
[37] Willard J A G. Vehicle routing using r-optimal tabu search: [MSc.dissertation]. London: The Imperial College, 1989
[38] Pureza V.M., Franca P.M.. Vehicle routing problems via tabu search metaheuristic. Technical Report CRT-347, Centre for Research on Transportation, Montreal, Canada, 1991
[39] Taillard E.. Parallel iterative search methods for vehicle routing problems[J]. Networks,1993, 23(8): 661-673
[40] Xu J., Kelly J.P.. A network flow-based tabu search heuristic for the vehicle routing problem[J]. Transportation Science, 1996, 30(4): 379-393
[41] Rochat Y., Taillard E.D.. Probabilistic diversification and intensification in local search for vehicle routing[J]. Journal of Heuristics, 1995, 1: 147-167
[42] Toth P., Vigo D.. The granular tabu search (and its application to the vehicle routing problem). Technical Report OR/98/9, DEIS, University of Bologna, Italy, 1998
[43] Rego C., Roucairol C.. A parallel tabu search algorithm using ejection chains for the vehicle routing problem. In: I.H. Osman and J.P. Kelly(eds). Meta-Heuristics: Theory and Apllications. Kluwer, Boston, MA, 1996. 661-675
[44] Rego C. A subpath ejection method for the vehicle routing problem[J]. Management Science, 1998, 10: 1447-1459
[45] Gendreau M. ,Hertz A. , Laporte G. A tabu search heuristics for the vehicle routing problem[J]. Management Science, 1994, 40(10): 1276-1290
[46] Gendreau M., Laporte G., Semet F.. A dynamic model and parallel tabu search heuristic for real-time ambulance relocation. Parallel Computing, 2001, 27: 1641-1653
[47] Osman I H, Wassan N A. A reactive tabu search meta heuristic for the vehicle routing problem with backhauls[J]. Journal of Scheduling, 2002, 5(4): 263–285
[48] Barbarosoglu G., Ozgur D.. A tabu search algorithm for the vehicle routing problem[J]. Computer and Operations Research, 1999, 26(3): 255-270
[49]袁庆达,杜文,周再玲.带软时间窗的混合车队车辆路线问题的模型和算法研究[J].西南交通大学学报, 2001, 36(4): 401-406
[50]袁庆达,闫昱,周再玲. Tabu Search算法在优化配送线路问题中的应用[J].计算机工程, 2001, 27(11):86-89
[51]郎茂祥,胡思继.车辆路径问题的禁忌搜索算法研究.管理工程学报. 2004, 18(1): 81-84
[52]贾永基,谷寒雨,席裕庚.一类货运车辆调度问题的混合禁忌搜索算法.信息与控制. 2004, 33(6): 724-728
[53]玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社,2004
[54] Van Breedam A.. An analysis of the effect of local improvement operators in genetic algorithms and simulated annealing for the vehicle routing problem. RUCA working Paper 96/14, University of Antwerp, Belgium, 1996
[55] Schmitt L.J.. An evaluation of a genetic algorithmic approach to the vehicle routing problem. Working paper, Department of Information Techonogy Management, Christian Brothers University, Memphis, TN, 1995
[56] Christofides N., Mingozzi A., Toth. P.. The Vehicle routing problem. In: N. Christofides, A. Mingozzi, P. Toth, et al.eds.Combinatorial Optimization, Chichester: Wiley, 1979. 315-338
[57] Potvin J.Y., Bengio S.. The Vehicle routing problem with time windows PartⅡ:Genetic search. INFORMS Journal on Computing, 1996, 8(2): 165-172
[58] Thangiah S.R.. Vehicle routing with time windows using genetic algorithms. Technical Report SRU-CpSc-TR-93-23, Slippery Rock University, Slippery Rock, PA, 1993
[59]杨云,孙向军,曹立鑫,刘凤玉.一种启发式遗传算法及其在最短路径求取中的应用.计算机工程与应用, 2003, 1:12-14
[60]邓欣,朱征宇,曾凡超.一种多车场车辆路径问题的单亲遗传算法.交通与计算机. 2007, 25(134): 31-35
[61]孙小年,陈幼林,杨东援.装卸一体化车辆路径问题的遗传算法研究.系统工程理论与实践. 2007, (2): 149-152
[62]戴树贵,姜昌华,潘荫荣,胡幼华.求解车辆路径安排问题的混合遗传算法.计算机工程与应用. 2007, 43(21): 225-228
[63]潘震东,唐加福,韩毅.带货物权重的车辆路径问题及遗传算法.管理科学学报. 2007, 10(3): 24-29
[64]张建勇,李军.具有同时配送和回收需求的车辆路径问题的混合遗传算法.中国公路学报, 2006, 19(4): 118-122
[65]吴璟莉,刘仁辉.分批配送的有时间窗车辆路径问题的遗传算法.计算机工程, 2007, 32(8): 213-215
[66]李勇,叶世杰,王勇,但斌. VFP&VRP联合优化模型及其多目标遗传算法.系统工程学报, 2006, 21(5): 529-533
[67]宋伟刚,张宏霞,佟玲.有时间窗约束非满载车辆调度问题的遗传算法.系统仿真学报, 2005, 17(11): 2593-2597
[68] Deif I., Bodin L.. Extension of the Clarke and Wright algorithm for solving the vehicle routing problem with backhauling[J]. Proceedings of the Badson Conference on Software Uses in Transportation and Logistics Management. 1984; 75-96
[69] Goetschalckx M., Jacobs-Blecha C.. The vehicle routing problem with backhauls[J]. European Journal of Operational Research. 1989, 42(1): 39-51
[70] Toth P., Vigo D.. A heuristic algorithm for the symmetric and asymmetric vehicle routingroblems with backhauls[J]. European Journal of Operational Research, 1999, 113(3): 528-543
[71] Duhamel C., Jean-Yves P., Jean-Marc R.. A tabu search heuristic for the vehicle routing problem with backhauls and time windows[J]. Transportation Science, 1997, 31(1): 49-59
[72] Salhi S., Nagy G.. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling[J]. Journal of the Operational Research Society, 1999, 50(10): 1034-1042
[73] Anne W., Said S.. An ant system algorithm for the vehicle routing problem with backhauls[C]. 4th Metaheuristics International Conference, 2001: 199-203
[74]吴泰熙,陈正芳,徐俊诚.含取货之车辆途程问题解法之研究[D]. Journal of the Chinese Institute of Industrial Engineers, 2003, 20(6): 651-665
[75]郭伏,隆颖.带时窗回程取货的车辆路径问题的算法.东北大学学报(自然科学版), 2006, 27(5): 575-578
[76]曹剑东,郑四发,李兵等.单程多次装卸的市内集送货代价优化.系统仿真学报, 2008, 20(1): 29-32
[77] Teodorovic D., Pavkovic G.. The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain[J]. Fuzzy Set and System, 1996, 82(3): 307-317
[78] Perincherry V., Kicuchil S.. A fuzzy approach to the transshipment problem[A]. Proceeding of ISUMA’90, The International Symposium on Uncertainty Modeling and Analysis[C], 1990
[79]张建勇,郭耀煌,李军.模糊需求信息条件下的车辆路径问题研究.系统工程学报, 2004, 19(1): 74-78
[80] Teodorovic D., Radivojevic G.. A fuzzy logic approach to dynamic dial-a-ride problem[J]. Fuzzy Set and System, 2000, 116: 23-33
[81]张建勇,李军.具有模糊旅行时间的VRP的一种混合遗传算法[J].管理工程学报, 2006, 20(4): 13-16
[82] Chen R., Gen M.. Vehicle routing problem with fuzzy due-time using genetic algorithms[J]. Japanese Journal of Fuzzy Theory and System, 1995, 7(5): 1050-1061
[83]张建勇,李军,郭耀煌.具有模糊预约时间的VRP混合遗传算法[J].管理科学学报, 2005, 8(3): 64-70
[84] Psaraftis H. N.. A dynamic programming solution to the single vehicle many-to-many immediate request Dial-a-Ride problem. Transport Science, 1980, 14(2): 130-154
[85] Bell w., Dalberto L. M., Fisher M. L., etal. Improving the distribution of industrial gases with an online computerized routing optimizer[J]. Interfaces, 1983, (13): 4-23
[86]李兵,郑四发,曹剑东等.求解客户需求动态变化的车辆路径规划方法[J].交通运输工程学报, 2007, 7(1): 106-110
[87] Madsen O. B. G., Ravn H. F.. A heuristic method for dispatching repairmen[J]. Annals of Operations Research, 1995, (61): 193-208
[88] Shen Y., Potvin J.Y., Rousseau J.M., etal. A computer assistant for vehicle dispatching with learning capability[J]. Annals of Operations Research, 1995, (61): 189-211
[89]郭伏,隆颖,赵希男.取送货混排的车辆路径问题的模糊动态研究.东北大学学报(自然科学版), 2007, 28(10): 2505-1508
[90] Agostino Nuzzolo, Francesco Russo, Umberto Crisalli. A doubly dynmic schedule-based assignment model for transit networks. Transportation Science, 2001, 35(3): 268-285
[91] Tarantilis C.D., Kiranoudis C.T.. Using a spatial decision support system for solving the vehicle routing problem[J]. Information Management, 2002, 39: 359-375
[92] Hwang H.. An improved model for vehicle routing problem with time constraint based on genetic algorithm[J]. Computers & Industrial engineering, 2002, 42: 361-369
[93]宋延,王海忠,石建军,许国华.基于ITS技术构建物流车辆调度信息平台.交通标准化, 2005, 137: 77-80
[94]丁学政.浅论智能公交调度管理系统.城市公共交通, 2005, 2: 35-37
[95]王文俊,王月龙,罗英伟,汪小林,许卓群.基于GIS的“119”消防指挥调度系统的设计与实现.计算机工程, 2004, 30(5): 9-11
[96]张李勇,腾继涛,张飞舟.基于GPS的运营车辆监控调度.计算机工程, 2004, 30(1): 48-49
[97] Floyd, R.W. Algorithm 97: shortest path[J]. Communications of the ACM, 1962, 35(5,6):345
[98] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.算法导论[M].北京:高等教育出版社, 2002
[99] Dijkstra. E. A note on two problems with graphs[J]. Numerische Mathematik. 1959, 1: 267~271
[100] Hart. P., N. Nilsson, B. Raphael. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transportation System Science and Cybernetics. 1968, 4: 100~107
[101] Hart. P., N. Nilsson, B. Raphael. Correction to“A formal basis for the heuristic determination of minimum cost paths”[J]. SIGART Newsletters. 1972, 37: 38~39
[102]李挺,杨殿阁,罗禹贡,等.道路网络中门到门包含重复节点的最优路径算法[J].清华大学学报(自然科学版), 2007, 47(5): 707-709
[103]孙增圻,张再兴,邓志东.智能控制理论与技术[M].北京:清华大学出版社,1997
[2] Balinsk M., Quandi R.. On an integer program for a delivery problem. Operations Research, 1964, 12: 300-304
[3] Stefan Irnich.A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles, European Journal of Operational Research, 2000, 122: P310-328
[4]李军,谢秉磊,郭耀煌.非满载车辆调度问题的遗传算法[J].系统工程理论方法应用, 2000, 9 (3) : 235-239.
[5] Fisher ML, Jaikumar R. A generalized assignment heuristic for vehicle routing problem[J]. Networks, 1981, 11: 109-124.
[6]曹剑东,郑四发,李兵等.基于中心分拨模式的多车场集送货一体化车辆优化调度方法[J].公路交通科技, 2006, 23(9): 140-144.
[7]郎茂祥.装卸混合车辆路径问题的模拟退火算法研究[J].系统工程学报, 2005, 20 (5) : 485-491.
[8] G.. Clarke and J.V. Wright. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 1964, 12: 568-581
[9]王鑫,谭畅.一种解决车辆调度问题的算法研究[J].控制工程, 2006,增刊, 193-195
[10]龚延成,郭晓芬,田光均等.带时间窗约束的物流配送线路启发式算法[J].交通与计算机, 2003, 6(21). 78-80
[11] Altinkemer K., Gavish B. Parallel savings based heuristics for the delivery problem[J]. Operations Research,1991, 39: 456-469
[12] Wark P., Holt J. A repeated matching heuristic for the vehicle routing problem[J]. Journal of the Operational Research Society, 1994, 45:1156-1167
[13] Mole R.H., Jameson S.R.. A sequential route-building algorithm employing a generalized savings criterion. Operational Research Quarterly, 1976, 27: 503-511
[14] Lin S. Computer solutions of the traveling salesman problem[J]. Bell System Technical Journal, 1965, 44: 2245-2269
[15] Gillett B.E., Miller L.R.. A heuristics algorithm for the vehicle dispatch problem. Operations Research, 1974, 22(4): 340-349
[16]刘浩,钱小燕.路径长度受限的随机需求VRP的模型和算法[J].南京工业大学学报, 2005, 27(3): 36-38
[17]陈伊菲,刘军.仓储拣选作业路径VRP模型设计与应用[J].计算机工程与应用, 2006, 6: 209-211
[18] Bramel J., Simchi-Levi D.. A location based heuristic for general routing problems[J]. Operations Research, 1995, 43: 649-660
[19] Christofides N.. The vehicle routing problem[J]. RAIRO, 1976, 10: 55-70
[20] Foster B.A., Ryan D.M.. An integer programming approach to the vehicle scheduling problem[J].Operations Research, 1976, 27: 367-384
[21] Ryan D.M, Hjorring C., Glover F.. Extensions of the petal method for vehicle routing[J]. Journal of Operational Research Society, 1993, 44: 289-296
[22] Renaud J., Boctor F.F., Laporte G.. An improved petal heuristic for the vehicle routing problem[J]. Journal of Operational Research Society, 1996, 47: 329-336
[23] Beasley J.E.. Route-first cluster-second methods for vehicle routing[J]. Omega, 1983, 11: 403-408
[24] Lin S., Kernighan B.W.. An effective heuristic algorithm for the traveling salesman problem. Operations Research, 1973, 21: 498-516
[25] Renaud J., Boctor F.F., Laporte G.. A fast composite heuristic for the symmetric traveling salesman problem[J]. INFORMS Journal on computing, 1996, 8(2): 134-143
[26] Thompson P.M., Psaraftis H.N.. Cyclic transfer algorithm for multi-vehicle routing and scheduling problems. Operations Research, 1993, 41: 935-946
[27]李大卫,王莉,王梦光.一个求解带有时间窗口约束的车辆路径问题的启发式算法.系统工程, 1998, 16(4): 20-24
[28]李军.车辆调度问题的分派启发式算法.系统工程理论与实践, 1999, (l): 27-33
[29]李军.有时间窗的车辆调度问题的网络启发式算法.系统工程, 1999, 17(2): 66-71
[30]叶耀华,朱晓梅,陈霖.一种带时间窗口和在前约束的车辆路线问题及其算法.系统工程理论与实践, 2000, 3:110-112
[31]刑文训,谢金星.现代优化计算方法[M].北京:清华大学出版社, 2003
[32] RobustéF., Daganzo C.F., Souleyrette R..Implementing vehicle routing models[J]. Transportation Research B, 1990, 24(4): 263-286
[33] Alfa A.S., Heragu S.S., Chen M. A 3-opt based simulated annealing algorithm for vehicle routing problems[J]. Computers & Industrial Engineering, 1991, 21: 635-639
[34] Osman I.H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 1993, 41(2): 421-451
[35]胡大伟,朱志强,胡勇.车辆路径问题的模拟退火算法.中国公路学报, 2006, 19(4): 123-126
[36] Van Breedam A.. Improvement heuristics for the vehicle routing problem based onsimulated annealing. European Journal of Operational Research, 1995, 86: 480-490
[37] Willard J A G. Vehicle routing using r-optimal tabu search: [MSc.dissertation]. London: The Imperial College, 1989
[38] Pureza V.M., Franca P.M.. Vehicle routing problems via tabu search metaheuristic. Technical Report CRT-347, Centre for Research on Transportation, Montreal, Canada, 1991
[39] Taillard E.. Parallel iterative search methods for vehicle routing problems[J]. Networks,1993, 23(8): 661-673
[40] Xu J., Kelly J.P.. A network flow-based tabu search heuristic for the vehicle routing problem[J]. Transportation Science, 1996, 30(4): 379-393
[41] Rochat Y., Taillard E.D.. Probabilistic diversification and intensification in local search for vehicle routing[J]. Journal of Heuristics, 1995, 1: 147-167
[42] Toth P., Vigo D.. The granular tabu search (and its application to the vehicle routing problem). Technical Report OR/98/9, DEIS, University of Bologna, Italy, 1998
[43] Rego C., Roucairol C.. A parallel tabu search algorithm using ejection chains for the vehicle routing problem. In: I.H. Osman and J.P. Kelly(eds). Meta-Heuristics: Theory and Apllications. Kluwer, Boston, MA, 1996. 661-675
[44] Rego C. A subpath ejection method for the vehicle routing problem[J]. Management Science, 1998, 10: 1447-1459
[45] Gendreau M. ,Hertz A. , Laporte G. A tabu search heuristics for the vehicle routing problem[J]. Management Science, 1994, 40(10): 1276-1290
[46] Gendreau M., Laporte G., Semet F.. A dynamic model and parallel tabu search heuristic for real-time ambulance relocation. Parallel Computing, 2001, 27: 1641-1653
[47] Osman I H, Wassan N A. A reactive tabu search meta heuristic for the vehicle routing problem with backhauls[J]. Journal of Scheduling, 2002, 5(4): 263–285
[48] Barbarosoglu G., Ozgur D.. A tabu search algorithm for the vehicle routing problem[J]. Computer and Operations Research, 1999, 26(3): 255-270
[49]袁庆达,杜文,周再玲.带软时间窗的混合车队车辆路线问题的模型和算法研究[J].西南交通大学学报, 2001, 36(4): 401-406
[50]袁庆达,闫昱,周再玲. Tabu Search算法在优化配送线路问题中的应用[J].计算机工程, 2001, 27(11):86-89
[51]郎茂祥,胡思继.车辆路径问题的禁忌搜索算法研究.管理工程学报. 2004, 18(1): 81-84
[52]贾永基,谷寒雨,席裕庚.一类货运车辆调度问题的混合禁忌搜索算法.信息与控制. 2004, 33(6): 724-728
[53]玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社,2004
[54] Van Breedam A.. An analysis of the effect of local improvement operators in genetic algorithms and simulated annealing for the vehicle routing problem. RUCA working Paper 96/14, University of Antwerp, Belgium, 1996
[55] Schmitt L.J.. An evaluation of a genetic algorithmic approach to the vehicle routing problem. Working paper, Department of Information Techonogy Management, Christian Brothers University, Memphis, TN, 1995
[56] Christofides N., Mingozzi A., Toth. P.. The Vehicle routing problem. In: N. Christofides, A. Mingozzi, P. Toth, et al.eds.Combinatorial Optimization, Chichester: Wiley, 1979. 315-338
[57] Potvin J.Y., Bengio S.. The Vehicle routing problem with time windows PartⅡ:Genetic search. INFORMS Journal on Computing, 1996, 8(2): 165-172
[58] Thangiah S.R.. Vehicle routing with time windows using genetic algorithms. Technical Report SRU-CpSc-TR-93-23, Slippery Rock University, Slippery Rock, PA, 1993
[59]杨云,孙向军,曹立鑫,刘凤玉.一种启发式遗传算法及其在最短路径求取中的应用.计算机工程与应用, 2003, 1:12-14
[60]邓欣,朱征宇,曾凡超.一种多车场车辆路径问题的单亲遗传算法.交通与计算机. 2007, 25(134): 31-35
[61]孙小年,陈幼林,杨东援.装卸一体化车辆路径问题的遗传算法研究.系统工程理论与实践. 2007, (2): 149-152
[62]戴树贵,姜昌华,潘荫荣,胡幼华.求解车辆路径安排问题的混合遗传算法.计算机工程与应用. 2007, 43(21): 225-228
[63]潘震东,唐加福,韩毅.带货物权重的车辆路径问题及遗传算法.管理科学学报. 2007, 10(3): 24-29
[64]张建勇,李军.具有同时配送和回收需求的车辆路径问题的混合遗传算法.中国公路学报, 2006, 19(4): 118-122
[65]吴璟莉,刘仁辉.分批配送的有时间窗车辆路径问题的遗传算法.计算机工程, 2007, 32(8): 213-215
[66]李勇,叶世杰,王勇,但斌. VFP&VRP联合优化模型及其多目标遗传算法.系统工程学报, 2006, 21(5): 529-533
[67]宋伟刚,张宏霞,佟玲.有时间窗约束非满载车辆调度问题的遗传算法.系统仿真学报, 2005, 17(11): 2593-2597
[68] Deif I., Bodin L.. Extension of the Clarke and Wright algorithm for solving the vehicle routing problem with backhauling[J]. Proceedings of the Badson Conference on Software Uses in Transportation and Logistics Management. 1984; 75-96
[69] Goetschalckx M., Jacobs-Blecha C.. The vehicle routing problem with backhauls[J]. European Journal of Operational Research. 1989, 42(1): 39-51
[70] Toth P., Vigo D.. A heuristic algorithm for the symmetric and asymmetric vehicle routingroblems with backhauls[J]. European Journal of Operational Research, 1999, 113(3): 528-543
[71] Duhamel C., Jean-Yves P., Jean-Marc R.. A tabu search heuristic for the vehicle routing problem with backhauls and time windows[J]. Transportation Science, 1997, 31(1): 49-59
[72] Salhi S., Nagy G.. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling[J]. Journal of the Operational Research Society, 1999, 50(10): 1034-1042
[73] Anne W., Said S.. An ant system algorithm for the vehicle routing problem with backhauls[C]. 4th Metaheuristics International Conference, 2001: 199-203
[74]吴泰熙,陈正芳,徐俊诚.含取货之车辆途程问题解法之研究[D]. Journal of the Chinese Institute of Industrial Engineers, 2003, 20(6): 651-665
[75]郭伏,隆颖.带时窗回程取货的车辆路径问题的算法.东北大学学报(自然科学版), 2006, 27(5): 575-578
[76]曹剑东,郑四发,李兵等.单程多次装卸的市内集送货代价优化.系统仿真学报, 2008, 20(1): 29-32
[77] Teodorovic D., Pavkovic G.. The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain[J]. Fuzzy Set and System, 1996, 82(3): 307-317
[78] Perincherry V., Kicuchil S.. A fuzzy approach to the transshipment problem[A]. Proceeding of ISUMA’90, The International Symposium on Uncertainty Modeling and Analysis[C], 1990
[79]张建勇,郭耀煌,李军.模糊需求信息条件下的车辆路径问题研究.系统工程学报, 2004, 19(1): 74-78
[80] Teodorovic D., Radivojevic G.. A fuzzy logic approach to dynamic dial-a-ride problem[J]. Fuzzy Set and System, 2000, 116: 23-33
[81]张建勇,李军.具有模糊旅行时间的VRP的一种混合遗传算法[J].管理工程学报, 2006, 20(4): 13-16
[82] Chen R., Gen M.. Vehicle routing problem with fuzzy due-time using genetic algorithms[J]. Japanese Journal of Fuzzy Theory and System, 1995, 7(5): 1050-1061
[83]张建勇,李军,郭耀煌.具有模糊预约时间的VRP混合遗传算法[J].管理科学学报, 2005, 8(3): 64-70
[84] Psaraftis H. N.. A dynamic programming solution to the single vehicle many-to-many immediate request Dial-a-Ride problem. Transport Science, 1980, 14(2): 130-154
[85] Bell w., Dalberto L. M., Fisher M. L., etal. Improving the distribution of industrial gases with an online computerized routing optimizer[J]. Interfaces, 1983, (13): 4-23
[86]李兵,郑四发,曹剑东等.求解客户需求动态变化的车辆路径规划方法[J].交通运输工程学报, 2007, 7(1): 106-110
[87] Madsen O. B. G., Ravn H. F.. A heuristic method for dispatching repairmen[J]. Annals of Operations Research, 1995, (61): 193-208
[88] Shen Y., Potvin J.Y., Rousseau J.M., etal. A computer assistant for vehicle dispatching with learning capability[J]. Annals of Operations Research, 1995, (61): 189-211
[89]郭伏,隆颖,赵希男.取送货混排的车辆路径问题的模糊动态研究.东北大学学报(自然科学版), 2007, 28(10): 2505-1508
[90] Agostino Nuzzolo, Francesco Russo, Umberto Crisalli. A doubly dynmic schedule-based assignment model for transit networks. Transportation Science, 2001, 35(3): 268-285
[91] Tarantilis C.D., Kiranoudis C.T.. Using a spatial decision support system for solving the vehicle routing problem[J]. Information Management, 2002, 39: 359-375
[92] Hwang H.. An improved model for vehicle routing problem with time constraint based on genetic algorithm[J]. Computers & Industrial engineering, 2002, 42: 361-369
[93]宋延,王海忠,石建军,许国华.基于ITS技术构建物流车辆调度信息平台.交通标准化, 2005, 137: 77-80
[94]丁学政.浅论智能公交调度管理系统.城市公共交通, 2005, 2: 35-37
[95]王文俊,王月龙,罗英伟,汪小林,许卓群.基于GIS的“119”消防指挥调度系统的设计与实现.计算机工程, 2004, 30(5): 9-11
[96]张李勇,腾继涛,张飞舟.基于GPS的运营车辆监控调度.计算机工程, 2004, 30(1): 48-49
[97] Floyd, R.W. Algorithm 97: shortest path[J]. Communications of the ACM, 1962, 35(5,6):345
[98] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.算法导论[M].北京:高等教育出版社, 2002
[99] Dijkstra. E. A note on two problems with graphs[J]. Numerische Mathematik. 1959, 1: 267~271
[100] Hart. P., N. Nilsson, B. Raphael. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transportation System Science and Cybernetics. 1968, 4: 100~107
[101] Hart. P., N. Nilsson, B. Raphael. Correction to“A formal basis for the heuristic determination of minimum cost paths”[J]. SIGART Newsletters. 1972, 37: 38~39
[102]李挺,杨殿阁,罗禹贡,等.道路网络中门到门包含重复节点的最优路径算法[J].清华大学学报(自然科学版), 2007, 47(5): 707-709
[103]孙增圻,张再兴,邓志东.智能控制理论与技术[M].北京:清华大学出版社,1997