物流配送车辆路径方案的智能生成方法研究
|
摘要
针对车辆路径问题“规模增大导致组合爆炸”这一难题,从缩减解答空间入手,以节省求解时空为突破口,综合运用知识工程、模糊聚类分析、人工智能和运筹学理论,按照“物流配送区域及客户的聚类分析→车辆路径方案的智能生成→模型的构建及求解”这一研究思路,重点开展了以下研究工作:
(1)物流配送区域及客户的聚类分析。提出物流配送区域及客户聚类的原理,分析并总结影响配送过程的主要因素,以此对配送区域及客户进行初步划分,并采用模糊聚类分析方法细分各配送区域中的客户。配送区域及客户的聚类分析为形成后续的车辆路径方案智能生成方法奠定基础。
(2)车辆路径方案智能生成方法及其数学模型的构建与求解。在配送区域及客户聚类分析的基础上,总结归纳生成车辆路径方案的主要参数,设计带有控制策略的基于深度优先搜索的车辆路径方案生成算法,得出备选的车辆路径方案集合。构建并求解车辆路径方案整数规划模型,并设计邻域规则,将车辆路径方案的解映射为实际的行车方案。
(3)车辆路径方案智能求解系统的设计与实现。设计了由配送区域处理器、车辆路径方案生成器、车辆路径方案求解器三个主要模块组成的物流配送车辆路径方案智能求解系统,设计了求解体系统中的数据库和知识库。采用Java技术、SQL Server2000数据库、Amzi Prolog、运筹学求解软件Lindo等相关开发环境与技术实现了车辆路径方案智能求解系统。
(4)应用研究及车辆路径方案智能求解系统的性能分析。以北方食品公司猪肉配送问题为应用研究背景,开展车辆路径方案智能生成方法及其求解系统的实际应用研究,验证本文所提方法的有效性。并根据问题中两个关键参数的变化组合,对车辆路径方案智能求解系统进行性能分析。研究结果表明,本文提出的求解车辆路径问题的新方法,其求解问题的效率并不随问题规模的增大而迅速较低。
本项研究为解决车辆路径问题这一复杂的管理决策问题提供了一种定性推理与定量分析相结合的求解方法。其研究成果与研究团队已有的基于GIS的电子商务物流配送可视化信息平台、物流配送等值线生成系统、电子商务订单实时处理的智能系统、车辆监控与调度系统进行集成,可为物流配送中心的车辆实时导航、调度、监控工作提供决策支持。
Focusing on the state explosion problem in solving Vehicle Routing Problem,which is derived from the increase of the scale,this paper aims at great reduction of solution state-space.Applying theories of Artificial Intelligence,Knowledge Engineering and Operational Research,it presents an intelligent solution approach,which includes three steps, distribution area division and customer classification,intelligent routing scheme generation, and mathematical model construction and solution.The detailed work studied in the paper is as follows.
(1) Method for distribution area division and customer clustering.The principle of distribution area division and customer classification is first presented.And the factors according to what the distribution area is initially divided into smaller areas are analyzed. Then using fuzzy clustering analysis the customers are subdivided.This distribution area division and customer clustering provide a foundation for the intelligent approach to vehicle routing scheme generation.
(2) Intelligent generation approach to vehicle routing schemes,mathematical model construction and solution.Based on the distribution area division and customer classification, the formation process of routing schemes and its variety of parameters are summarized and the flowchart of the depth-first search process with control rules is disigned in the paper.Then a set of feasible routing schemes is achieved.After a mathematical model is constructed and solved,the better solutions are selected from the feasible scheme set.Finally,a nearest neighbor principle is developed to interpret solutions to the real problem's vehicle routings.
(3) Design and realization of a VRP scheme solution system.A solution system is designed,which includes three modules,distribution area division processor,VRP scheme generator,and VRP scheme solver.Applying Java techniques,SQL Server 2000 Databese, Amzi Prolog,Lindo,the paper realizes the VRP scheme solution system.
(4) Application and performance analysis of the VRP solution system.Choosing a pork distribution problem in North Grocery Company in Beijing as application background,the paper does some application research for the approach to routing sheme generation and its solution system to verify the approach's effectiveness of the theoretical result.And it analyzes several scenarios resulted from the combinations of two factors to observe the performance of the routing scheme solution system.The results indicate the new solution approach to VRP realizes that the computation time stays almost unchanged as the sizes of problems increase.
The research in this paper provides a new way to solve Vehicle Routing Problem,a kind of complex decision problems,which incorporates quantitative computing process and qualitative reasoning process.Integrating with related existing results in our group,which are GIS-based visualization for information platform in distribution under E-commerce, GIS-based isoline-generating system in urban distribution,real-time and intelligent system for E-Commerce order processing,the vehicle monitoring and scheduling system,the results can provide decision support for distribution center with realtime vehicle navigating,scheduling and monitoring.
(1)物流配送区域及客户的聚类分析。提出物流配送区域及客户聚类的原理,分析并总结影响配送过程的主要因素,以此对配送区域及客户进行初步划分,并采用模糊聚类分析方法细分各配送区域中的客户。配送区域及客户的聚类分析为形成后续的车辆路径方案智能生成方法奠定基础。
(2)车辆路径方案智能生成方法及其数学模型的构建与求解。在配送区域及客户聚类分析的基础上,总结归纳生成车辆路径方案的主要参数,设计带有控制策略的基于深度优先搜索的车辆路径方案生成算法,得出备选的车辆路径方案集合。构建并求解车辆路径方案整数规划模型,并设计邻域规则,将车辆路径方案的解映射为实际的行车方案。
(3)车辆路径方案智能求解系统的设计与实现。设计了由配送区域处理器、车辆路径方案生成器、车辆路径方案求解器三个主要模块组成的物流配送车辆路径方案智能求解系统,设计了求解体系统中的数据库和知识库。采用Java技术、SQL Server2000数据库、Amzi Prolog、运筹学求解软件Lindo等相关开发环境与技术实现了车辆路径方案智能求解系统。
(4)应用研究及车辆路径方案智能求解系统的性能分析。以北方食品公司猪肉配送问题为应用研究背景,开展车辆路径方案智能生成方法及其求解系统的实际应用研究,验证本文所提方法的有效性。并根据问题中两个关键参数的变化组合,对车辆路径方案智能求解系统进行性能分析。研究结果表明,本文提出的求解车辆路径问题的新方法,其求解问题的效率并不随问题规模的增大而迅速较低。
本项研究为解决车辆路径问题这一复杂的管理决策问题提供了一种定性推理与定量分析相结合的求解方法。其研究成果与研究团队已有的基于GIS的电子商务物流配送可视化信息平台、物流配送等值线生成系统、电子商务订单实时处理的智能系统、车辆监控与调度系统进行集成,可为物流配送中心的车辆实时导航、调度、监控工作提供决策支持。
Focusing on the state explosion problem in solving Vehicle Routing Problem,which is derived from the increase of the scale,this paper aims at great reduction of solution state-space.Applying theories of Artificial Intelligence,Knowledge Engineering and Operational Research,it presents an intelligent solution approach,which includes three steps, distribution area division and customer classification,intelligent routing scheme generation, and mathematical model construction and solution.The detailed work studied in the paper is as follows.
(1) Method for distribution area division and customer clustering.The principle of distribution area division and customer classification is first presented.And the factors according to what the distribution area is initially divided into smaller areas are analyzed. Then using fuzzy clustering analysis the customers are subdivided.This distribution area division and customer clustering provide a foundation for the intelligent approach to vehicle routing scheme generation.
(2) Intelligent generation approach to vehicle routing schemes,mathematical model construction and solution.Based on the distribution area division and customer classification, the formation process of routing schemes and its variety of parameters are summarized and the flowchart of the depth-first search process with control rules is disigned in the paper.Then a set of feasible routing schemes is achieved.After a mathematical model is constructed and solved,the better solutions are selected from the feasible scheme set.Finally,a nearest neighbor principle is developed to interpret solutions to the real problem's vehicle routings.
(3) Design and realization of a VRP scheme solution system.A solution system is designed,which includes three modules,distribution area division processor,VRP scheme generator,and VRP scheme solver.Applying Java techniques,SQL Server 2000 Databese, Amzi Prolog,Lindo,the paper realizes the VRP scheme solution system.
(4) Application and performance analysis of the VRP solution system.Choosing a pork distribution problem in North Grocery Company in Beijing as application background,the paper does some application research for the approach to routing sheme generation and its solution system to verify the approach's effectiveness of the theoretical result.And it analyzes several scenarios resulted from the combinations of two factors to observe the performance of the routing scheme solution system.The results indicate the new solution approach to VRP realizes that the computation time stays almost unchanged as the sizes of problems increase.
The research in this paper provides a new way to solve Vehicle Routing Problem,a kind of complex decision problems,which incorporates quantitative computing process and qualitative reasoning process.Integrating with related existing results in our group,which are GIS-based visualization for information platform in distribution under E-commerce, GIS-based isoline-generating system in urban distribution,real-time and intelligent system for E-Commerce order processing,the vehicle monitoring and scheduling system,the results can provide decision support for distribution center with realtime vehicle navigating,scheduling and monitoring.
引文
[1]Dantzig,G.B.,Ramser,J.H..The truck dispatching problem[J].Management Science,1959,6(1):80-91.
[2]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物资出版社,2001.2.
[3]Garey,M.R.,Johnson,D.S.Computers and Intractability:A Guide to the Theory of NP-Completeness[M].W.H.Freeman and Company.1979.
[4]Laporte G.The vehicle routing problem:An overview of exact and approximate algorithms[J].European Journal of Operational Research,1992,59:345-358.
[5]祝崇俊,刘民,吴澄.供应链中车辆路径问题的研究进展及前景[J].计算机集成制造系统——CIMS,2001,7(11):1-6.
[6]郭耀煌,李军.车辆优化调度问题的研究现状评述[J].西南交通大学学报,1995,30(4):376-382.
[7]谢秉磊,郭耀煌,郭强.动态车辆路径问题:现状与展望[J].系统工程理论方法应用,2002,11(2):116-120.
[8]刘云忠,宣慧玉.车辆路径问题的模型及算法研究综述[J].管理工程学报,2005,19(1):124-130.
[9]孙丽君,胡祥培,王征.车辆路径规划问题及其求解方法研究进展[J].系统工程,2006,24(11):31-37.
[10]Desrosiers J,Soumis F,Desrochers N.Routing with time windows by column generation[J].Networks.1984,14:545-565.
[11]Laporte G,Nobert Y,Desrochers M.Optimal routing under capacity and distance restrictions[J].Operations Research.1985,33:1050-1073.
[12]Fisher M L,Jaikumar R.A generalized assignment heuristic for vehicle routing[J].Networks,1981,11:109-124.
[13]S Martello,P Toth.Knapsack problems:algorithms and computer implementations[M].John Wiley &Sons,Inc.New York,1990:189-220.
[14]郎茂祥.装卸混合车辆路径问题的模拟退火算法研究[J].系统工程学报,2005,20(5):485-491.
[15]Balinski M,Quandt R.On an integer program for a delivery problem[J].Operations Research,1962,12:300-304.
[16]Rao M R,Ziont S.Allocation of transportation units to alternative trips-A column generation scheme with out-of-kilter subproblems[J].Operations Research,1968,12:52-63.
[17]Dror M,Laporte G,Trudeau P.Vehicle Routing with Split Deliveries[J].Discrete Applied Mathematics,1994,50(3):239-254.
[18]Cordeau J F,Gendreau M,Laporte G.A Tabu Search Heuristic for the Periodic and Multi-Depot Vehicle Routing Problems[J].Networks,1997,30(2):105-119.
[19]Cordeau J F,Laporte G.A Tabu Search Heuristic for the Site Dependent Vehicle Routing Problem with Time Windows[J].INFOR,2001,39(3):292-298.
[20]P.Toth,D.Vigo.The Vehicle Routing Problem[C],Philadelphia:SIAM Monographs on Discrete Mathematics and Applications,2002:157-194.
[21]Gendreau M,Laporte G,Musaraganyi C,Taillard E D.A Tabu Search Heuristic for the Heterogeneous Fleet Vehicle Routing Problem[J].Computers & Operations Research,1999,26(12):1153-1173.
[22]P.Toth,D.Vigo.The Vehicle Routing Problem[C],Philadelphia:SIAM Monographs on Discrete Mathematics and Applications,2002:195-224.
[23]Mitrovic-Minic S,Krishnamurti R,Laporte G.Double-Horizon Based Heuristics for the Dynamic Pickup and Delivery Problem with Time Windows[J].Transportation Research Part B:Methodological,2004,38(8):669-685.
[24]Scheuerer S.A tabu search heuristic for the truck and trailer routing problem[J].Computers &Operations Research,2006,33:894-909.
[25]李军.有时间窗的车辆路线安排问题的启发式算法[J].系统工程,1996,14(5):45-50.
[26]李军,谢秉磊,郭耀煌.非满载车辆调度问题的遗传算法[J].系统工程理论方法应用,2000,9(3):235-239.
[27]刘浩,钱小燕,李舒展.单类型车辆随机需求VRP的一个算法[J].南京建筑工程学院学报,2001,(4):25-29.
[28]张涛,张杰,王梦光.不确定车辆数的车辆路径问题模型和混合算法[J].系统工程理论方法应用,2002,11(2):121-130.
[29]张潜,高立群,胡祥培等.物流配送路径多目标优化的聚类—改进遗传算法[J].控制与决策,2003,18(4):418-422.
[30]张建勇,郭耀煌,李军.基于顾客满意度的多目标模糊车辆优化调度问题研究[J].铁道学报,2003,25(2):15-17.
[31]李臻,雷定猷.多车场车辆优化调度模型及算法[J].交通运输工程学报,2004,4(1):83-86.
[32]王景恒,金俊武.一种分送式物流配送车辆优化调度算法[J].工业技术经济,2005,24(2):108-110.
[33]Fisher M L.Optimal solution of vehicle routing problems using minimum k-trees[J].Operations Research,1994,42(4):141-153.
[34]Lorena Luiz A N,Senne Edson L F.A column generation approach to capacitated p-median problems [J].Computers and Operations Research,2004,31(6):863-876.
[35]Christofides N,Mingozzi A,Toth P.State Space Relaxation Procedures for the Computation of Bounds to Routing Problems[J].Networks,1981,11(2):145-164.
[36]Padberg M W,Rinaldi G.A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems[J].SIAM Review,1991,33(1):60-100.
[37]Fumero F.A modified subgradient algorithm for Lagrangean relaxation[J].Computers and Operations Research,2000,28(1):33-52.
[38]Paolo Toth,Daniele Vigo.Models,relaxations and exact approaches for the capacitated vehicle routing problem[J].Discrete Applied Mathematics.2002.123(1-3):487-512.
[39]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.
[40]Gaskell T J.Bases for vehicle fleet scheduling[J].Operational Research Quarterly,1967,18(3):281-295.
[41]Nelson M D,Nygard K E,Griffin J H et al.Implementation techniques for the vehicle routing problem[J].Computers and Operations Research,1985,12(3):273-283.
[42]Paessens H.The savings algorithm for the vehicle routing problem[J].European Journal of Operational Research,1988,34(3):336-344.
[43]Desrochers M,Verhoog T W.A matching based savings algorithm for the vehicle routing problem[R].Les Cahiers du GERAD G-89-04,Ecole des Hautes Etudes Commerciales de Montreal,1989.
[44]Altinkemer K,Gavish B.Parallel savings based heuristic for the delivery problem[J].Operations Research,1991,39(3):456-469.
[45]Wark P,Holt J.A repeated matching heuristic for the vehicle routing problem[J].Journal of the Operational Research Society,1994,45(10):1156-1167.
[46]Mole R H,Jameson S R.A sequential route-building algorithm employing a generalized savings criterion[J].Operational Research Quarterly,1976,27(2):503-511.
[47]Christofides N,Mingozzi A,Toth P.The vehicle routing problem[A].In:Christofides,N.,Mingozzi,A.,Toth,P.,Sandi,C.(Eds.),Combinatorial Optimization[C].Wiley,Chichester,1979.
[48]Lin S.Computer solutions of the traveling salesman problem[J].Bell System Technical Journal,1965,44(10):2245-2269.
[49]Or I.Traveling salesman-type combinatorial optimization problems and their relation to the logistics of regional blood banking[D].Evanston:Northwestern University,1976.
[50]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.
[51]G Laporte.The traveling salesman problem:An overview of exact and approximate algorithms[J].European Journal of Operational Research,1992,Vol.59:231-247.
[52]Gillett B E,Miller L R.A heuristic algorithm for the vehicle-dispatch problem[J].Operations Research,1974,22(2):240-349.
[53]Bramel J,Simchi-Levi D.A location based heuristic for general routing problems[J].Operations Research,1995,43(4):649-660.
[54]Tung-Lai Hu,Jiuh-Biing Sheu.A fuzzy-based customer classification method for demand-responsive logistical distribution operations[J].Fuzzy Sets and Systems,2003,139(2):431-450.
[55]K.Ganesh,T.T.Narendran.CLOVES:A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up[J].European Journal of Operational Research,2007,178(3):699-717.
[56]Rodolfo Dondo,Jaime Cerda.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.
[57]Glover F.Tabu Search:part Ⅰ[J].Journal on Computing,1989,1(3):190-206.
[58]Taillard E D.Parallel iterative search methods for vehicle routing problems[J].Networks,1993,23(8):661-673.
[59]Gendreau M,Hertz A,Laporte G A tabu search heuristic for the vehicle routing problem[J].Management Science,1994,40(10):1276-1290.
[60]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.
[61]Rego C,Roucairol C.A parallel tabu search algorithm using ejection chains for the vehicle routing problem[A].In:Osman,I.H.,Kelly,J.P.(Eds.),Meta-Heuristics:Theory and Applications[C].Kluwer,Boston,1996:661-675.
[62]Rochat Y,Taillard E D.Probabilistic diversification and intensification in local search for vehicle routing[J].Journal of Heuristics,1995,1(1):147-167.
[63]Toth P,Vigo D.Granular tabu search(D).Working paper,DEIS,University of Bologna,1998.
[64]Chao I M.A tabu search method for the truck and trailer routing problem[J].Computers & Operations Research,2002,29(1):33-51.
[65]Brandao J.A tabu search algorithm for the open vehicle routing problem[J].European Journal of Operational Research 2004,157(3):552-564.
[66]Ho S C,Haugland D.A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J].Computers & Operations Research,2004,31(12):1947-1964.
[67]Alfredo Tang Montan(?) F,Galvao R D.A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J].Computers & Operations Research,2006,33(3):595-619.
[68]Hopfield J,Tank D.Neural Computation of Decisions in Optimization Problems[J].Biological Cybernetics,1985,52(3):141-152.
[69]Wilson S,Pawley G.On the Stability of the Travelling Salesman Algorithm of Hopfield and Tank[J].Biological Cybernetics,1988,58(1):63-70.
[70]Kirkpatrick S,Gelatt C D,Vechi Jr M P.Optimization by Simulated Annealing[J].Science,1983,220(4598):671-680.
[71]Ululgu L E,Teghem J.Multiobjective combinatorial optimization problems:A survey[J].Journal of Multicriteria Decision Analysis,1994,3(2):83-104.
[72]Holland J H.Adaptation in natural and artilcial systems[M].Ann Arbor:University of Michigan Press,Ann Arbor,1975.
[73]Dorigo M,Maniezzo V,Colorni A.The Ant System:An Autocalytic Optimizing Process[R].Technical Report No.91-016 Revised,Politecnico di Milano,Italy,1991.
[74]Gambardella L M.,Dorigo M.Ant-Q:a reinforcement learning approach to the traveling salesman problem[A].Proc.12th International Conference on Machine Learning[C].Tahoe City,CA,1995:252-260.
[75]Gambardella L M.,Dorigo M.Solving symmetric and asymmetric TSPs by ant colonies[C],proc.IEEE International Conference on Evolutionary Computation.1996:622-627.
[76]Dorigo M,Gambardella L M.Ant colony system:A cooperative learning approach to the traveling salesman problem[J].IEEE Trans Evolutionary Computation,1997,1(1):53-66.
[77]Dorigo M,Gambardella L M.Ant Colonies for the Travelling Salesman problem[J].BioSystems,1997,43(2):73-81.
[78]St(u|¨)tzle T,Hoos H.The MAX-MIN ant system and local search for the traveling salesman problem[C].Proc.IEEE International Conference on Evolutionary Computation.1997:309-314.
[79]Bullnheimer B,Hartl R F,Strauss C.An improved ant system algorithm for the vehicle routing problem[J].Annals of Operations Research,1999,89:319-328.
[80]Mazzeo S,Loiseau I.An Ant Colony Algorithm for the Capacitated Vehicle Routing[J].Electronic Notes in Discrete Mathematics,2004,18:181-186.
[81]王柏祥,姜国均,陆生勋.Hopfield网络解TSP的改进算法[J].杭州大学学报(自然科学版),1994,21(4):408-412.
[82]李大卫,王莉,王梦光.遗传算法与禁忌搜索算法的混合策略[J].系统工程学报,1998,13(3):28-34.
[83]马良.TSP及其扩展问题的混合型启发式算法[J].上海理工大学学报,1999,21(1):25-28.
[84]李军,郭强,刘建新.组合运输的优化调度[J].系统工程理论与实践,2001,(2):117-121.
[85]陈子侠,叶庆泰.基于城市配送的单车线路算法研究[J].计算机工程,2005年6月,31(11):32-34.
[86]鹿应荣,杨印生,吕锋.基于模糊聚类分析的车辆优化调度[J].吉林大学学报(工学版),2006,36(增刊2):147-151.
[87]李金苹.现代物流配送系统的运输优化调度方案[J1.物流技术,2002,(5):11-13.
[88]霍佳震,张磊.有时间窗集的集货送货一体化车辆路径规划启发式算法研究[J].物流技术,2004,(5):64-66.
[89]徐海东,王大康.启发式算法在非满载货物运输优化调度中的应用[J].煤矿机械,2004,(11):7-8.
[90]林晓宇,李金铭,纪寿文.车辆路径问题Clarke-Wright算法的改进与实现[J].交通与计算机,2004,22(6):72-75.
[91]廖洁君,陈燕.城市物流中多目标配送模型[J].大连海事大学学报,2004,30(4):82-85.
[92]王惠,陈燕.基于遗传算法的多目标的有时间窗的车辆调度[J].计算机应用,2004,24(9):144-146.
[93]鄢洁,熊桂喜.基于遗传算法的商用车辆调度策略研究[J].计算机与现代化,2004,(12):9-12.
[94]张翠军,刘坤起,刘永军.求解一般车辆优化调度问题的一种改进遗传算法[J].计算机工程与应用,2004,(33):201-211.
[95]Gunter Dueck.New optimization heuristics for the great deluge algorithm and the record-to-record travel[J].Journal of Computational Physics,1993,104(1):86-92.
[96]Tarantilis,C.Kiranoudis.Boneroute:An adaptive memory-based method for effective fleet management[J].Annals of Operations Research,2002,115:227-241.
[97]P.Toth,D.Vigo.The granular tabu search and its application to the vehicle routing problem[J].INFORMS Journal on Computing,2003,15(4):333-346.
[98]Gunter Dueck,Tobias Scheuer.Threshold accepting:A general purpose optimization algorithm appearing superior to simulated annealing[J].Journal of Computational Physics,1990,90(1):161-175.
[99]C.Tarantilis.Threshold accepting-based heuristic for solving large scale vehicle routing problems.Working paper,National Technical University of Athens,Athens,Greece,2003.
[100]Li F.Solving variants of the vehicle routing problem:algorithms,test problems,and computational results[M].PhD dissertation,Department of Mathematics,University of Maryland,College Park,Maryland;2005.
[101]童俯,沈一栋.知识工程[M].北京:科学出版社,1992:74.
[102]王珏,袁小红,石纯一等.关于知识表示的讨论[J].计算机学报,1995,18(3):212-224.
[103]蔡自兴.人工智能及其应用(第二版)[M].北京:清华大学出版社,2000:17-59,60-92,93-103.
[104]Ensing Marco,Paton Ray.Objected- oriented approach to knowledge representation in a biomedical domain[J].Artificial Intelligence in Medicine.Vol.6,Dee 1994:244-248.
[105]Steven Walczak.Knowledge acquisition and knowledge representation with class:the object-oriented paradigm[J].Expert Systems with Applications,1998,15:235-244.
[106]X.Li,F.Lara-Rosano.Adaptive fuzzy petri nets for dynamic knowledge representation and inference[J].Expert Systems with Applications,2000,19:235-241.
[107]Yeung D S,Tsang ECC.Improved Fuzzy Knowledge Representation and Rule Valuation Using Petri Nets And Degree of Subsethood[J].International Journal of Intelligent System,1994,9(9):391-408.
[108]董海鹰,白建设,周震.基于模糊彩色Petri网的知识表示与获取研究[J].西安交通大学学报,2001,35(10):996-1001.
[109]Samuel H.Huang,Hao Xing.Extract intelligible and concise fuzzy rules from neural networks[J].Fuzzy Sets and Systems,2002,132:233-243.
[110]胡祥培,钱国明,胡运权.运筹学规划问题一种基于知识的树状表示法[J].哈尔滨工业大学学报.1997,29(3):8-11.
[111]胡祥培.生产作业计划问题的知识表示研究[J].管理科学学报,1999,2(2):41-48.
[112]胡祥培,许智超,杨德礼.智能运筹学与动态系统实时优化控制[J].管理科学学报,2002,5(4):13-21.
[113]李德英,张跃.广义故障树知识表示方法在锅炉故障诊断中的应用[J].系统工程与电子技术,1997,10:72-80.
[114]Philippe Martin,Peter Eklund.Embedding knowledge in Web documents[J].Computer Networks,1999,31:1403-1419.
[115]汪西原,汪西莉.启发式搜索策略(爬山法)的改进与实现[J].陕西师范大学学报(自然科学版),1999,27(1):58-60.
[116]黄明,闫淑娟,梁旭.遗传算法和禁忌搜索算法在车间调度中的研究进展[J].工业控制计算机,2004,17(2):4-5.
[117]唐立山,谢云尤,矢勇等.非数值并行算法——模拟退火算法[M].北京:科学出版社,1997:91-103.
[118]鞠全勇,朱剑英.基于混合遗传算法的动态车间调度系统的研究[J].中国机械工程.2007,18(1):40-43.
[119]马军建,董增川,王春霞等.蚁群算法研究进展[J].河海大学学报(自然科学版),2005,33(2):139-143
[120]Sprague,Ralph H..A framework for the development of Decision Support Systems[J].MIS Quarterly,1980:1-26
[121]Sprague,Ralph H..Decision support systems:a tutorial[C].DSS-81 Transactions,First International Conference on Decision Support Systems,Execucom System Corporation,1981,193-203.
[122]刘宏,袁捷.一种基于Agent的决策支持系统生成器新框架[J].计算机工程,1999,25(12):65-67.
[123]徐洁磐.决策支持系统生成器NDSSG的设计与实现[J].计算机研究与发展,1993,3:1-6.
[124]王宇,史永杰,王晓锋.一种决策支持系统生成器的设计与实现[J].大连海事大学学报, 1999,25(3):89-92.
[125]Fierbinteanu C.A decision support systems generator for transportation demand forecasting implemented by constraint logic programming[J].Decision Support System.1999,26:179-194.
[126]Execucom Systems Corporation,P.0.Box 9758,Austin,Texas,78766.
[127]TYMSHARE.20705 Valley Green Driver,Cupertino,California,95014.
[128]P.Keenan.Using a GIS as a DSS generator[M].In:J.Darzentas,J.S.Darzentas and T.Spyrou,Editors,Perspectives on DSS,University of the Aegean,Greece,1996:33-40.
[129]过秀成,吕慎.大城市快速轨道交通线网空间布局.城市发展研究,2001,8(1):58-61.
[130]LINDO System Inc.LINDO API User's Manual[M],http://www.lindo.com
[131]韩伯棠.管理运筹学[M].北京:高等教育出版社,2000年7月第一版.
[132]Xiangpei Hu,Qiulei Ding,Yongxian Li,Dan Song.An Improved Ant Colony System and Its Application[M].Computational Intelligence and Security,Springer Berlin/Heidelberg,2007:36-45.
[133]Li,F.Y.,Golden,B.and Wasil,E.(2007),"The open vehicle routing problem:algorithms,large-scale test problems,and computational results',Computers and Operational Research,34(10),2918-2930.
[2]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京:中国物资出版社,2001.2.
[3]Garey,M.R.,Johnson,D.S.Computers and Intractability:A Guide to the Theory of NP-Completeness[M].W.H.Freeman and Company.1979.
[4]Laporte G.The vehicle routing problem:An overview of exact and approximate algorithms[J].European Journal of Operational Research,1992,59:345-358.
[5]祝崇俊,刘民,吴澄.供应链中车辆路径问题的研究进展及前景[J].计算机集成制造系统——CIMS,2001,7(11):1-6.
[6]郭耀煌,李军.车辆优化调度问题的研究现状评述[J].西南交通大学学报,1995,30(4):376-382.
[7]谢秉磊,郭耀煌,郭强.动态车辆路径问题:现状与展望[J].系统工程理论方法应用,2002,11(2):116-120.
[8]刘云忠,宣慧玉.车辆路径问题的模型及算法研究综述[J].管理工程学报,2005,19(1):124-130.
[9]孙丽君,胡祥培,王征.车辆路径规划问题及其求解方法研究进展[J].系统工程,2006,24(11):31-37.
[10]Desrosiers J,Soumis F,Desrochers N.Routing with time windows by column generation[J].Networks.1984,14:545-565.
[11]Laporte G,Nobert Y,Desrochers M.Optimal routing under capacity and distance restrictions[J].Operations Research.1985,33:1050-1073.
[12]Fisher M L,Jaikumar R.A generalized assignment heuristic for vehicle routing[J].Networks,1981,11:109-124.
[13]S Martello,P Toth.Knapsack problems:algorithms and computer implementations[M].John Wiley &Sons,Inc.New York,1990:189-220.
[14]郎茂祥.装卸混合车辆路径问题的模拟退火算法研究[J].系统工程学报,2005,20(5):485-491.
[15]Balinski M,Quandt R.On an integer program for a delivery problem[J].Operations Research,1962,12:300-304.
[16]Rao M R,Ziont S.Allocation of transportation units to alternative trips-A column generation scheme with out-of-kilter subproblems[J].Operations Research,1968,12:52-63.
[17]Dror M,Laporte G,Trudeau P.Vehicle Routing with Split Deliveries[J].Discrete Applied Mathematics,1994,50(3):239-254.
[18]Cordeau J F,Gendreau M,Laporte G.A Tabu Search Heuristic for the Periodic and Multi-Depot Vehicle Routing Problems[J].Networks,1997,30(2):105-119.
[19]Cordeau J F,Laporte G.A Tabu Search Heuristic for the Site Dependent Vehicle Routing Problem with Time Windows[J].INFOR,2001,39(3):292-298.
[20]P.Toth,D.Vigo.The Vehicle Routing Problem[C],Philadelphia:SIAM Monographs on Discrete Mathematics and Applications,2002:157-194.
[21]Gendreau M,Laporte G,Musaraganyi C,Taillard E D.A Tabu Search Heuristic for the Heterogeneous Fleet Vehicle Routing Problem[J].Computers & Operations Research,1999,26(12):1153-1173.
[22]P.Toth,D.Vigo.The Vehicle Routing Problem[C],Philadelphia:SIAM Monographs on Discrete Mathematics and Applications,2002:195-224.
[23]Mitrovic-Minic S,Krishnamurti R,Laporte G.Double-Horizon Based Heuristics for the Dynamic Pickup and Delivery Problem with Time Windows[J].Transportation Research Part B:Methodological,2004,38(8):669-685.
[24]Scheuerer S.A tabu search heuristic for the truck and trailer routing problem[J].Computers &Operations Research,2006,33:894-909.
[25]李军.有时间窗的车辆路线安排问题的启发式算法[J].系统工程,1996,14(5):45-50.
[26]李军,谢秉磊,郭耀煌.非满载车辆调度问题的遗传算法[J].系统工程理论方法应用,2000,9(3):235-239.
[27]刘浩,钱小燕,李舒展.单类型车辆随机需求VRP的一个算法[J].南京建筑工程学院学报,2001,(4):25-29.
[28]张涛,张杰,王梦光.不确定车辆数的车辆路径问题模型和混合算法[J].系统工程理论方法应用,2002,11(2):121-130.
[29]张潜,高立群,胡祥培等.物流配送路径多目标优化的聚类—改进遗传算法[J].控制与决策,2003,18(4):418-422.
[30]张建勇,郭耀煌,李军.基于顾客满意度的多目标模糊车辆优化调度问题研究[J].铁道学报,2003,25(2):15-17.
[31]李臻,雷定猷.多车场车辆优化调度模型及算法[J].交通运输工程学报,2004,4(1):83-86.
[32]王景恒,金俊武.一种分送式物流配送车辆优化调度算法[J].工业技术经济,2005,24(2):108-110.
[33]Fisher M L.Optimal solution of vehicle routing problems using minimum k-trees[J].Operations Research,1994,42(4):141-153.
[34]Lorena Luiz A N,Senne Edson L F.A column generation approach to capacitated p-median problems [J].Computers and Operations Research,2004,31(6):863-876.
[35]Christofides N,Mingozzi A,Toth P.State Space Relaxation Procedures for the Computation of Bounds to Routing Problems[J].Networks,1981,11(2):145-164.
[36]Padberg M W,Rinaldi G.A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems[J].SIAM Review,1991,33(1):60-100.
[37]Fumero F.A modified subgradient algorithm for Lagrangean relaxation[J].Computers and Operations Research,2000,28(1):33-52.
[38]Paolo Toth,Daniele Vigo.Models,relaxations and exact approaches for the capacitated vehicle routing problem[J].Discrete Applied Mathematics.2002.123(1-3):487-512.
[39]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.
[40]Gaskell T J.Bases for vehicle fleet scheduling[J].Operational Research Quarterly,1967,18(3):281-295.
[41]Nelson M D,Nygard K E,Griffin J H et al.Implementation techniques for the vehicle routing problem[J].Computers and Operations Research,1985,12(3):273-283.
[42]Paessens H.The savings algorithm for the vehicle routing problem[J].European Journal of Operational Research,1988,34(3):336-344.
[43]Desrochers M,Verhoog T W.A matching based savings algorithm for the vehicle routing problem[R].Les Cahiers du GERAD G-89-04,Ecole des Hautes Etudes Commerciales de Montreal,1989.
[44]Altinkemer K,Gavish B.Parallel savings based heuristic for the delivery problem[J].Operations Research,1991,39(3):456-469.
[45]Wark P,Holt J.A repeated matching heuristic for the vehicle routing problem[J].Journal of the Operational Research Society,1994,45(10):1156-1167.
[46]Mole R H,Jameson S R.A sequential route-building algorithm employing a generalized savings criterion[J].Operational Research Quarterly,1976,27(2):503-511.
[47]Christofides N,Mingozzi A,Toth P.The vehicle routing problem[A].In:Christofides,N.,Mingozzi,A.,Toth,P.,Sandi,C.(Eds.),Combinatorial Optimization[C].Wiley,Chichester,1979.
[48]Lin S.Computer solutions of the traveling salesman problem[J].Bell System Technical Journal,1965,44(10):2245-2269.
[49]Or I.Traveling salesman-type combinatorial optimization problems and their relation to the logistics of regional blood banking[D].Evanston:Northwestern University,1976.
[50]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.
[51]G Laporte.The traveling salesman problem:An overview of exact and approximate algorithms[J].European Journal of Operational Research,1992,Vol.59:231-247.
[52]Gillett B E,Miller L R.A heuristic algorithm for the vehicle-dispatch problem[J].Operations Research,1974,22(2):240-349.
[53]Bramel J,Simchi-Levi D.A location based heuristic for general routing problems[J].Operations Research,1995,43(4):649-660.
[54]Tung-Lai Hu,Jiuh-Biing Sheu.A fuzzy-based customer classification method for demand-responsive logistical distribution operations[J].Fuzzy Sets and Systems,2003,139(2):431-450.
[55]K.Ganesh,T.T.Narendran.CLOVES:A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up[J].European Journal of Operational Research,2007,178(3):699-717.
[56]Rodolfo Dondo,Jaime Cerda.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.
[57]Glover F.Tabu Search:part Ⅰ[J].Journal on Computing,1989,1(3):190-206.
[58]Taillard E D.Parallel iterative search methods for vehicle routing problems[J].Networks,1993,23(8):661-673.
[59]Gendreau M,Hertz A,Laporte G A tabu search heuristic for the vehicle routing problem[J].Management Science,1994,40(10):1276-1290.
[60]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.
[61]Rego C,Roucairol C.A parallel tabu search algorithm using ejection chains for the vehicle routing problem[A].In:Osman,I.H.,Kelly,J.P.(Eds.),Meta-Heuristics:Theory and Applications[C].Kluwer,Boston,1996:661-675.
[62]Rochat Y,Taillard E D.Probabilistic diversification and intensification in local search for vehicle routing[J].Journal of Heuristics,1995,1(1):147-167.
[63]Toth P,Vigo D.Granular tabu search(D).Working paper,DEIS,University of Bologna,1998.
[64]Chao I M.A tabu search method for the truck and trailer routing problem[J].Computers & Operations Research,2002,29(1):33-51.
[65]Brandao J.A tabu search algorithm for the open vehicle routing problem[J].European Journal of Operational Research 2004,157(3):552-564.
[66]Ho S C,Haugland D.A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J].Computers & Operations Research,2004,31(12):1947-1964.
[67]Alfredo Tang Montan(?) F,Galvao R D.A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J].Computers & Operations Research,2006,33(3):595-619.
[68]Hopfield J,Tank D.Neural Computation of Decisions in Optimization Problems[J].Biological Cybernetics,1985,52(3):141-152.
[69]Wilson S,Pawley G.On the Stability of the Travelling Salesman Algorithm of Hopfield and Tank[J].Biological Cybernetics,1988,58(1):63-70.
[70]Kirkpatrick S,Gelatt C D,Vechi Jr M P.Optimization by Simulated Annealing[J].Science,1983,220(4598):671-680.
[71]Ululgu L E,Teghem J.Multiobjective combinatorial optimization problems:A survey[J].Journal of Multicriteria Decision Analysis,1994,3(2):83-104.
[72]Holland J H.Adaptation in natural and artilcial systems[M].Ann Arbor:University of Michigan Press,Ann Arbor,1975.
[73]Dorigo M,Maniezzo V,Colorni A.The Ant System:An Autocalytic Optimizing Process[R].Technical Report No.91-016 Revised,Politecnico di Milano,Italy,1991.
[74]Gambardella L M.,Dorigo M.Ant-Q:a reinforcement learning approach to the traveling salesman problem[A].Proc.12th International Conference on Machine Learning[C].Tahoe City,CA,1995:252-260.
[75]Gambardella L M.,Dorigo M.Solving symmetric and asymmetric TSPs by ant colonies[C],proc.IEEE International Conference on Evolutionary Computation.1996:622-627.
[76]Dorigo M,Gambardella L M.Ant colony system:A cooperative learning approach to the traveling salesman problem[J].IEEE Trans Evolutionary Computation,1997,1(1):53-66.
[77]Dorigo M,Gambardella L M.Ant Colonies for the Travelling Salesman problem[J].BioSystems,1997,43(2):73-81.
[78]St(u|¨)tzle T,Hoos H.The MAX-MIN ant system and local search for the traveling salesman problem[C].Proc.IEEE International Conference on Evolutionary Computation.1997:309-314.
[79]Bullnheimer B,Hartl R F,Strauss C.An improved ant system algorithm for the vehicle routing problem[J].Annals of Operations Research,1999,89:319-328.
[80]Mazzeo S,Loiseau I.An Ant Colony Algorithm for the Capacitated Vehicle Routing[J].Electronic Notes in Discrete Mathematics,2004,18:181-186.
[81]王柏祥,姜国均,陆生勋.Hopfield网络解TSP的改进算法[J].杭州大学学报(自然科学版),1994,21(4):408-412.
[82]李大卫,王莉,王梦光.遗传算法与禁忌搜索算法的混合策略[J].系统工程学报,1998,13(3):28-34.
[83]马良.TSP及其扩展问题的混合型启发式算法[J].上海理工大学学报,1999,21(1):25-28.
[84]李军,郭强,刘建新.组合运输的优化调度[J].系统工程理论与实践,2001,(2):117-121.
[85]陈子侠,叶庆泰.基于城市配送的单车线路算法研究[J].计算机工程,2005年6月,31(11):32-34.
[86]鹿应荣,杨印生,吕锋.基于模糊聚类分析的车辆优化调度[J].吉林大学学报(工学版),2006,36(增刊2):147-151.
[87]李金苹.现代物流配送系统的运输优化调度方案[J1.物流技术,2002,(5):11-13.
[88]霍佳震,张磊.有时间窗集的集货送货一体化车辆路径规划启发式算法研究[J].物流技术,2004,(5):64-66.
[89]徐海东,王大康.启发式算法在非满载货物运输优化调度中的应用[J].煤矿机械,2004,(11):7-8.
[90]林晓宇,李金铭,纪寿文.车辆路径问题Clarke-Wright算法的改进与实现[J].交通与计算机,2004,22(6):72-75.
[91]廖洁君,陈燕.城市物流中多目标配送模型[J].大连海事大学学报,2004,30(4):82-85.
[92]王惠,陈燕.基于遗传算法的多目标的有时间窗的车辆调度[J].计算机应用,2004,24(9):144-146.
[93]鄢洁,熊桂喜.基于遗传算法的商用车辆调度策略研究[J].计算机与现代化,2004,(12):9-12.
[94]张翠军,刘坤起,刘永军.求解一般车辆优化调度问题的一种改进遗传算法[J].计算机工程与应用,2004,(33):201-211.
[95]Gunter Dueck.New optimization heuristics for the great deluge algorithm and the record-to-record travel[J].Journal of Computational Physics,1993,104(1):86-92.
[96]Tarantilis,C.Kiranoudis.Boneroute:An adaptive memory-based method for effective fleet management[J].Annals of Operations Research,2002,115:227-241.
[97]P.Toth,D.Vigo.The granular tabu search and its application to the vehicle routing problem[J].INFORMS Journal on Computing,2003,15(4):333-346.
[98]Gunter Dueck,Tobias Scheuer.Threshold accepting:A general purpose optimization algorithm appearing superior to simulated annealing[J].Journal of Computational Physics,1990,90(1):161-175.
[99]C.Tarantilis.Threshold accepting-based heuristic for solving large scale vehicle routing problems.Working paper,National Technical University of Athens,Athens,Greece,2003.
[100]Li F.Solving variants of the vehicle routing problem:algorithms,test problems,and computational results[M].PhD dissertation,Department of Mathematics,University of Maryland,College Park,Maryland;2005.
[101]童俯,沈一栋.知识工程[M].北京:科学出版社,1992:74.
[102]王珏,袁小红,石纯一等.关于知识表示的讨论[J].计算机学报,1995,18(3):212-224.
[103]蔡自兴.人工智能及其应用(第二版)[M].北京:清华大学出版社,2000:17-59,60-92,93-103.
[104]Ensing Marco,Paton Ray.Objected- oriented approach to knowledge representation in a biomedical domain[J].Artificial Intelligence in Medicine.Vol.6,Dee 1994:244-248.
[105]Steven Walczak.Knowledge acquisition and knowledge representation with class:the object-oriented paradigm[J].Expert Systems with Applications,1998,15:235-244.
[106]X.Li,F.Lara-Rosano.Adaptive fuzzy petri nets for dynamic knowledge representation and inference[J].Expert Systems with Applications,2000,19:235-241.
[107]Yeung D S,Tsang ECC.Improved Fuzzy Knowledge Representation and Rule Valuation Using Petri Nets And Degree of Subsethood[J].International Journal of Intelligent System,1994,9(9):391-408.
[108]董海鹰,白建设,周震.基于模糊彩色Petri网的知识表示与获取研究[J].西安交通大学学报,2001,35(10):996-1001.
[109]Samuel H.Huang,Hao Xing.Extract intelligible and concise fuzzy rules from neural networks[J].Fuzzy Sets and Systems,2002,132:233-243.
[110]胡祥培,钱国明,胡运权.运筹学规划问题一种基于知识的树状表示法[J].哈尔滨工业大学学报.1997,29(3):8-11.
[111]胡祥培.生产作业计划问题的知识表示研究[J].管理科学学报,1999,2(2):41-48.
[112]胡祥培,许智超,杨德礼.智能运筹学与动态系统实时优化控制[J].管理科学学报,2002,5(4):13-21.
[113]李德英,张跃.广义故障树知识表示方法在锅炉故障诊断中的应用[J].系统工程与电子技术,1997,10:72-80.
[114]Philippe Martin,Peter Eklund.Embedding knowledge in Web documents[J].Computer Networks,1999,31:1403-1419.
[115]汪西原,汪西莉.启发式搜索策略(爬山法)的改进与实现[J].陕西师范大学学报(自然科学版),1999,27(1):58-60.
[116]黄明,闫淑娟,梁旭.遗传算法和禁忌搜索算法在车间调度中的研究进展[J].工业控制计算机,2004,17(2):4-5.
[117]唐立山,谢云尤,矢勇等.非数值并行算法——模拟退火算法[M].北京:科学出版社,1997:91-103.
[118]鞠全勇,朱剑英.基于混合遗传算法的动态车间调度系统的研究[J].中国机械工程.2007,18(1):40-43.
[119]马军建,董增川,王春霞等.蚁群算法研究进展[J].河海大学学报(自然科学版),2005,33(2):139-143
[120]Sprague,Ralph H..A framework for the development of Decision Support Systems[J].MIS Quarterly,1980:1-26
[121]Sprague,Ralph H..Decision support systems:a tutorial[C].DSS-81 Transactions,First International Conference on Decision Support Systems,Execucom System Corporation,1981,193-203.
[122]刘宏,袁捷.一种基于Agent的决策支持系统生成器新框架[J].计算机工程,1999,25(12):65-67.
[123]徐洁磐.决策支持系统生成器NDSSG的设计与实现[J].计算机研究与发展,1993,3:1-6.
[124]王宇,史永杰,王晓锋.一种决策支持系统生成器的设计与实现[J].大连海事大学学报, 1999,25(3):89-92.
[125]Fierbinteanu C.A decision support systems generator for transportation demand forecasting implemented by constraint logic programming[J].Decision Support System.1999,26:179-194.
[126]Execucom Systems Corporation,P.0.Box 9758,Austin,Texas,78766.
[127]TYMSHARE.20705 Valley Green Driver,Cupertino,California,95014.
[128]P.Keenan.Using a GIS as a DSS generator[M].In:J.Darzentas,J.S.Darzentas and T.Spyrou,Editors,Perspectives on DSS,University of the Aegean,Greece,1996:33-40.
[129]过秀成,吕慎.大城市快速轨道交通线网空间布局.城市发展研究,2001,8(1):58-61.
[130]LINDO System Inc.LINDO API User's Manual[M],http://www.lindo.com
[131]韩伯棠.管理运筹学[M].北京:高等教育出版社,2000年7月第一版.
[132]Xiangpei Hu,Qiulei Ding,Yongxian Li,Dan Song.An Improved Ant Colony System and Its Application[M].Computational Intelligence and Security,Springer Berlin/Heidelberg,2007:36-45.
[133]Li,F.Y.,Golden,B.and Wasil,E.(2007),"The open vehicle routing problem:algorithms,large-scale test problems,and computational results',Computers and Operational Research,34(10),2918-2930.