随机顾客和需求的配送优化
|
摘要
在物流配送优化调度中,配送模式规划和配送路径优化是两大核心问题,对应到组合优化研究领域分别为聚类分析和路径问题。这些问题自提出至今已有几十年时间,广大研究者在这些领域开展了大量研究工作,并取得了丰富成果。然而,在日常物流配送的实际应用中,顾客需求往往不是固定不变的,更多情况下需要在顾客需求的存在性和需求量不确定的情况下对配送模式和配送路径进行先验优化,但目前关于顾客和需求不确定的配送优化问题研究十分有限。
针对顾客和需求不确定背景下物流配送优化研究中存在的不足,论文在确定性聚类分析,确定性旅行商问题和确定性车辆路径问题已有研究成果的基础上,分别深入探讨顾客需求存在性和需求量为随机元素时配送优化中的概率聚类问题,概率旅行商问题,以及随机顾客和需求的车辆路径问题三个子问题。通过对三个子问题建立数学模型并分析问题特征,给出相应的启发式求解算法。
首先,提出顾客需求存在性随机的概率聚类问题(CPSE),在分析了CPSE问题特点后,给出了CPSE问题的数学模型。受基于经典聚类问题(BCP问题)的K-means算法启发,以K-means为原型,给出将其拓展到CPSE问题的PK-means算法。针对K-means族算法初始类簇代表点随机选择策略存在解稳定性和收敛性较差的弊端,提出针对BCP问题的基于邻域密度初始类簇代表点选择策略和针对CPSE问题的基于期望邻域密度初始类簇代表点选择策略,并分别将其应用于DK-means算法和DPK-means算法。仿真实验证实了对于顾客需求存在性随机的聚类分析问题,有必要将其与经典确定性聚类问题区别研究,且有必要设计特别针对CPSE问题的聚类算法。实验结果同时验证了提出的DPK-means算法在求解CPSE问题时的有效性,以及其相对于简单PK-means算法的改进效果。
其次,针对实际物流配送的路径优化过程中顾客需求具有不确定性的特点,将顾客需求的存在性作为随机元素,讨论了一种较经典旅行商问题(TSP)更为普遍,也更为复杂的概率旅行商问题(PTSP)。通过对PTSP问题定义和建模,发现目标函数计算复杂度过高是制约问题求解的瓶颈。受到TSP问题邻域搜索思想的启发,给出了针对PTSP的两种邻域搜索策略及邻域搜索过程中计算目标函数改变量的递归推导公式,采用这些递归公式可以将邻域搜索的计算复杂度从O(n4)降为O(n2),有效提高局部搜索效率。此外,为了适应更多求解算法的设计要求,还给出两种PTSP先验路径目标函数近似估计的方法,结合仿真实验分析了近似估计中参数取值与估计精度之间的关系。在验证了PTSP解与TSP解之间关系后,给出了一种求解PTSP的全局优化HGSA算法,通过仿真实验验证了算法的有效性。
最后,针对实际物流配送中顾客和需求均具有不确定性的特点,将顾客的存在性和具体需求量作为随机元素,在受车辆装载能力约束的前提下,讨论了较经典带容量约束车辆路径问题(CVRP)更为普遍,也更为复杂的顾客和需求量随机的车辆路径问题(VRPSCD)。通过对VRPSCD问题定义和建立模型,发现目标函数中路径成本期望的计算复杂度过高是制约问题求解的瓶颈。受到CVRP问题邻域搜索思想的启发,给出了针对VRPSCD版本的邻域搜索策略及邻域搜索过程中近似估计路径成本期望改变量的方法。为了适应更多求解算法的设计要求,给出VRPSCD解路径成本期望的取样近似估计法,并结合仿真实验分析了近似估计中样本规模与估计精度之间的关系。最后,在不同顾客需求概率下,结合仿真实验对比了VRPSCD求解与基于历史平均需求水平的确定性CVRP求解的差异性。
Distribution model planning and distribution routing are two major problems of logistics distribution optimization and scheduling. In combinatorial optimization, these two problems are researched as clustering problem and routing problem. Both of the two problems have been proposed for decades. Researchers have already explored deep in these fields and acquired valuable results. In daily logistics distribution, the requirements of customers are not constant. On the contrary, mostly people have to complete the optimization with uncertainty before exact requirements and demands are available. But by now, researches on distribution optimization with uncertain customers and demands are still rare.
Based on the existing researches on distribution optimization, especially on the certain clustering, certain traveling salesman problem and certain vehicle routing problem, this thesis focuses on three subproblems of uncertain distribution optimization, in which customers and demands are stochastic. These subproblems includ clustering problem with stochastic object existence, probabilistic traveling salesman problem, and vehicle routing problem with stochastic customers and demands. After problem formulation and modeling, some heuristic algorithms are proposed for each subproblem respectively.
Firstly, a new uncertain clustering problem model with stochastic object existence named CPSE is proposed. Based on the K-means algorithm of classic certain clustering problem, a new heuristic algorithm named PK-means is proposed for CPSE. Since clustering results of K-means family algorithms depend on initial clustering centers strongly. To overcome this shortcoming, an improved initialization of clustering centers based on neighbor density is proposed, then it is used in both DK-means algorithm for certain clustering and DPK-means algorithm for CPSE. Experimental results show that, it is necessary to research CPSE separated from nomal certain clustering problme, and design particular algorithms for CPSE. In addition, the experimental results also prove the efficiency of DPK-means for CPSE and its improvement compared with DK-means.
Secondly, this thesis considers customer requirements as random element, since in most logistics distribution application, customer requirements are uncertain when people scheduling routes. An uncertain routing problem named probabilistic traveling salesman problem (PTSP) is proposed. Compared with nomal classic traveling salesman problem (TSP), PTSP is much more difficult to solve. After problem formulation and modeling, author found the bottleneck of PTSP solving is complex and costly object function computing. Samilar to the neighborhood search idea of TSP, two neighborhood search methods for PTSP is proposed. With derivation of cost change evaluation, the compute complexity of PTSP's neighborhood search is efficiently decressed from O(n4) to O(n2). Moreover, for common algorithms designing, two approximate evaluations for expected tour length are proposed, and their parameters are analysised with experiments. After discuss the relationship between PTSP solutions and TSP solutions, a new global optimization algorithm named HGSA is proposed. Experimental results indicate that HGSA is more efficient to solve PTSP.
Finally, considering the uncertainty of customers and demands in actual logistics distribution, with the capacity restriction of vehicles, an vehicle routing problem with stochastic customers and demands (VRPSCD) is discussed. VRPSCD is much more difficult than classic capacitated vehicle routing problem (CVRP) to solve. After problem formulation and modeling, it is found that the bottleneck to solve VRPSCD is high compute complexition of object value eveluation. Based on neighborhood search idea of CVRP, an approximated evaluation method to compute the change of expected object function value in VRPSCD neighborhood search is proposed. To fit more algorithms designing, sampling approximation for VRPSCD's expected object value is proposed, and the relationship between sampling scale and approximation precision is discussed with experiments. At last, with different customer requirement probabilistic distributions, VRPSCD solutions and CVRP solution with historic average demands are compared with experiments.
针对顾客和需求不确定背景下物流配送优化研究中存在的不足,论文在确定性聚类分析,确定性旅行商问题和确定性车辆路径问题已有研究成果的基础上,分别深入探讨顾客需求存在性和需求量为随机元素时配送优化中的概率聚类问题,概率旅行商问题,以及随机顾客和需求的车辆路径问题三个子问题。通过对三个子问题建立数学模型并分析问题特征,给出相应的启发式求解算法。
首先,提出顾客需求存在性随机的概率聚类问题(CPSE),在分析了CPSE问题特点后,给出了CPSE问题的数学模型。受基于经典聚类问题(BCP问题)的K-means算法启发,以K-means为原型,给出将其拓展到CPSE问题的PK-means算法。针对K-means族算法初始类簇代表点随机选择策略存在解稳定性和收敛性较差的弊端,提出针对BCP问题的基于邻域密度初始类簇代表点选择策略和针对CPSE问题的基于期望邻域密度初始类簇代表点选择策略,并分别将其应用于DK-means算法和DPK-means算法。仿真实验证实了对于顾客需求存在性随机的聚类分析问题,有必要将其与经典确定性聚类问题区别研究,且有必要设计特别针对CPSE问题的聚类算法。实验结果同时验证了提出的DPK-means算法在求解CPSE问题时的有效性,以及其相对于简单PK-means算法的改进效果。
其次,针对实际物流配送的路径优化过程中顾客需求具有不确定性的特点,将顾客需求的存在性作为随机元素,讨论了一种较经典旅行商问题(TSP)更为普遍,也更为复杂的概率旅行商问题(PTSP)。通过对PTSP问题定义和建模,发现目标函数计算复杂度过高是制约问题求解的瓶颈。受到TSP问题邻域搜索思想的启发,给出了针对PTSP的两种邻域搜索策略及邻域搜索过程中计算目标函数改变量的递归推导公式,采用这些递归公式可以将邻域搜索的计算复杂度从O(n4)降为O(n2),有效提高局部搜索效率。此外,为了适应更多求解算法的设计要求,还给出两种PTSP先验路径目标函数近似估计的方法,结合仿真实验分析了近似估计中参数取值与估计精度之间的关系。在验证了PTSP解与TSP解之间关系后,给出了一种求解PTSP的全局优化HGSA算法,通过仿真实验验证了算法的有效性。
最后,针对实际物流配送中顾客和需求均具有不确定性的特点,将顾客的存在性和具体需求量作为随机元素,在受车辆装载能力约束的前提下,讨论了较经典带容量约束车辆路径问题(CVRP)更为普遍,也更为复杂的顾客和需求量随机的车辆路径问题(VRPSCD)。通过对VRPSCD问题定义和建立模型,发现目标函数中路径成本期望的计算复杂度过高是制约问题求解的瓶颈。受到CVRP问题邻域搜索思想的启发,给出了针对VRPSCD版本的邻域搜索策略及邻域搜索过程中近似估计路径成本期望改变量的方法。为了适应更多求解算法的设计要求,给出VRPSCD解路径成本期望的取样近似估计法,并结合仿真实验分析了近似估计中样本规模与估计精度之间的关系。最后,在不同顾客需求概率下,结合仿真实验对比了VRPSCD求解与基于历史平均需求水平的确定性CVRP求解的差异性。
Distribution model planning and distribution routing are two major problems of logistics distribution optimization and scheduling. In combinatorial optimization, these two problems are researched as clustering problem and routing problem. Both of the two problems have been proposed for decades. Researchers have already explored deep in these fields and acquired valuable results. In daily logistics distribution, the requirements of customers are not constant. On the contrary, mostly people have to complete the optimization with uncertainty before exact requirements and demands are available. But by now, researches on distribution optimization with uncertain customers and demands are still rare.
Based on the existing researches on distribution optimization, especially on the certain clustering, certain traveling salesman problem and certain vehicle routing problem, this thesis focuses on three subproblems of uncertain distribution optimization, in which customers and demands are stochastic. These subproblems includ clustering problem with stochastic object existence, probabilistic traveling salesman problem, and vehicle routing problem with stochastic customers and demands. After problem formulation and modeling, some heuristic algorithms are proposed for each subproblem respectively.
Firstly, a new uncertain clustering problem model with stochastic object existence named CPSE is proposed. Based on the K-means algorithm of classic certain clustering problem, a new heuristic algorithm named PK-means is proposed for CPSE. Since clustering results of K-means family algorithms depend on initial clustering centers strongly. To overcome this shortcoming, an improved initialization of clustering centers based on neighbor density is proposed, then it is used in both DK-means algorithm for certain clustering and DPK-means algorithm for CPSE. Experimental results show that, it is necessary to research CPSE separated from nomal certain clustering problme, and design particular algorithms for CPSE. In addition, the experimental results also prove the efficiency of DPK-means for CPSE and its improvement compared with DK-means.
Secondly, this thesis considers customer requirements as random element, since in most logistics distribution application, customer requirements are uncertain when people scheduling routes. An uncertain routing problem named probabilistic traveling salesman problem (PTSP) is proposed. Compared with nomal classic traveling salesman problem (TSP), PTSP is much more difficult to solve. After problem formulation and modeling, author found the bottleneck of PTSP solving is complex and costly object function computing. Samilar to the neighborhood search idea of TSP, two neighborhood search methods for PTSP is proposed. With derivation of cost change evaluation, the compute complexity of PTSP's neighborhood search is efficiently decressed from O(n4) to O(n2). Moreover, for common algorithms designing, two approximate evaluations for expected tour length are proposed, and their parameters are analysised with experiments. After discuss the relationship between PTSP solutions and TSP solutions, a new global optimization algorithm named HGSA is proposed. Experimental results indicate that HGSA is more efficient to solve PTSP.
Finally, considering the uncertainty of customers and demands in actual logistics distribution, with the capacity restriction of vehicles, an vehicle routing problem with stochastic customers and demands (VRPSCD) is discussed. VRPSCD is much more difficult than classic capacitated vehicle routing problem (CVRP) to solve. After problem formulation and modeling, it is found that the bottleneck to solve VRPSCD is high compute complexition of object value eveluation. Based on neighborhood search idea of CVRP, an approximated evaluation method to compute the change of expected object function value in VRPSCD neighborhood search is proposed. To fit more algorithms designing, sampling approximation for VRPSCD's expected object value is proposed, and the relationship between sampling scale and approximation precision is discussed with experiments. At last, with different customer requirement probabilistic distributions, VRPSCD solutions and CVRP solution with historic average demands are compared with experiments.
引文
[1]A. Jain. Data Clustering:50 Years Beyond K-means[J]. Pattern Recognition Letters,2008, 31(8):651-666.
[2]A. K. Jain,R. C. Dubes. ALGORITHMS FOR CLUSTERING DATA[M]. New Jersey: Prentice Hall,1988.
[3]Sokal,Sneath. Principles of Numerical Taxonomy[M]. San Francisco:W.H. Freeman,1963.
[4]M. R. Anderberg. Cluster Analysis for Applications [M]. New York, NY:Academic Press,1973.
[5]J. A. Hartigan. Clustering algorithms[M]. Wiley,1975.
[6]R. Duda, P. Hart,D. Stork. Pattern Classification[M]. New York:John Wiley and Sons,2001.
[7]J. Han,M. Kamber. Data Mining:Concepts and Techniques[M]. Morgan Kaufmann,2000.
[8]P. N. Tan, M. Steinbach,V. Kumar. Introduction to Data Mining[M]. Boston, MA, USA: Addison-Wesley Longman Publishing Co. Inc,2005.
[9]C. M. Bishop. Pattern Recognition and Machine Learning[M]. Springer,2006.
[10]刘位龙.面向不确定性数据的聚类算法研究[D].山东师范大学,2011.
[11]M. Chau, R. Cheng, B. Kao, et al. Uncertain Data Mining:An Example in Clustering Location Data Advances in Knowledge Discovery and Data Mining[C]. Advances in Knowledge Discovery and Data Mining,10th Pacific-Asia Conference, PAKDD 2006. Singapore,2006,3918:199-204.
[12]S. D. Lee, B. Kao,R. Cheng. Reducing UK-means to k-means[C].17th IEEE International Conference on Data Mining Workshops, ICDM Workshops 2007, October 28,2007-October 31,2007. Omaha, NE, United states,2007,483-488.
[13]B. Kao, S. D. Lee, D. W. Cheung, et al. Clustering uncertain data using voronoi diagrams[C].8th IEEE International Conference on Data Mining, ICDM 2008, December 15,2008-December 19,2008. Pisa, Italy,2008,333-342.
[14]H. P. Kriegel,M. Pfeifle. Density-based clustering of uncertain data[C]. Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. Chicago, Illinois, USA,2005,672-677.
[15]孔德昌,刘蓉.一种概率聚类的新算法[J].计算机应用与软件,2007,24(11)：180-182.
[16]周傲英,金澈清,王国仁,et al.不确定性数据管理技术研究综述[J].计算机学报,2009,31(01)：1-16.
[17]许华杰,李国徽,杨兵,et al.基于密度的不确定性数据概率聚类[J].计算机科学,2009,36(05)：68-71.
[18]李云飞,王丽珍,周丽华.不确定数据的高效聚类算法[J].广西师范大学学报(自然科学版),2011,29(02)：161-166.
[19]戴东波,赵杠,孙圣力.基于概率数据流的有效聚类算法[J].软件学报,2009,20(05)：1313-1328.
[20]张晨,金澈清,周傲英.一种不确定数据流聚类算法[J].软件学报,2010,21(09)：2173-2182.
[21]张新猛,蒋盛益.一种基于相似度概率的不确定分类数据聚类算法[J].山东大学学报(工学版),2011,41(03)：12-16.
[22]李雪.不确定数据聚类研究[D].大连理工大学,2009.
[23]R. E. Bland,D. F. Shallcross. Large Traveling Salesman Problem Arising from Experiments in X-ray Crystallography:a Preliminary Report on Computation[R]. Technical Report No.730, School of OR/IE, Cornell University. Ithaca, New York,1987.
[24]H. D. Ratliff,A. S. Rosenthal. Order-Picking in a Rectangular Warehouse:A Solvable Case for the Traveling Salesman Problem[R]. PDRC Report Series No.81-10. Georgia Institute of Technology, Atlanta, Georgia,1981.
[25]E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, et al. TheTraveling Salesman Problem[M]. Chichester:John Wiley,1985.
[26]S. Goyal. A Survey on Travelling Salesman Problem[C]. Midwest Instruction and Computing Symposium. Eau Claire,2010,
[27]S. Lin,B. W. Kernighan. An Effective Heuristic Algorithm for the Traveling Salesman Problem[J]. Informs Journal on Operations Research,1973,
[28]P. C. P. Kanellakis, C.H.. Local search for the asymmetric traveling salesman problem[J]. Operations Research 1980,28(5):1086-99.
[29]K. Helsgaun. An effective implementation of the Lin-Kernighan traveling salesman heuristic[J]. European Journal of Operational Research,2000,126(1):106-130.
[30]D. Applegate, W. Cook,A. Rohe. Chained Lin-Kernighan for large traveling salesman problems[J]. Informs Journal on Computing,2003,15(1):82-92.
[31]O. Martin, S. W. Otto,E. W. Felten. Large-step markov chains for the TSP incorporating local search heuristics[J]. Operations Research Letters,1992,11(4):219-224.
[32]D. Karapetyan,G. Gutin. Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem[J]. European Journal of Operational Research,2011,208(3): 221-232.
[33]J. Schneider. Searching for Backbones-a high-performance parallel algorithm for solving combinatorial optimization problems[J]. Future Generation Computer Systems, 2003,19(1):121-131.
[34]邹鹏,周智,陈国良,et a1.求解tsp问题的多级归约算法[J].软件学报,2003,14(01)：35-42.
[35]W. X. Zhang,M. Looks. A novel local search algorithm for the traveling salesman problem that exploits backbones[C]. Proceedings of the 19th international joint conference on Artificial intelligence. Edinburgh, Scotland,2005,343-348.
[36]G. Laporte. The traveling salesman problem:An overview of exact and approximate algorithms[J]. European Journal of Operational Research,1992,59(2):231-247.
[37]C. Rego, D. Gamboa, F. Glover, et al. Traveling salesman problem heuristics:Leading methods, implementations and latest advances[J]. European Journal of Operational Research,2010,211(3):427-441.
[38]Concorde TSP Solver[OL]. http://www.tsp.gatech.edu/concorde/index.html.2012
[39]LKH [OL]. http://www.akira.ruc.dk/-keld/research/LKH/.2012
[40]林冬梅,王东.改进的求解TSP混合分支裁剪法[J].计算机工程与设计,2008,29(02)：424-425.
[41]王东,吴湘滨,毛先成,et a1.小规模TSP边集裁剪策略研究[J].系统工程与电子技术,2008,30(09)：1693-1696.
[42]王东,林冬梅.优化初始边集提高分支裁剪法求解TSP效率[J].计算机工程与设计,2007,28(15)：3797-3799.
[43]江贺,周智,陈国良.TSP问题启发集的分析及应用[J].中国科学技术大学学报,2005,35(05)：683-692.
[44]江贺,周智,邹鹏,et a1.求解TSP问题的并集搜索的新宏启发算法[J].中国科学技术大学学报,2005,35(03)：367-375.
[45]江贺,胡燕,李强,et al. TSP问题的脂肪计算复杂性与启发式算法设计[J].软件学报,2009,20(09)：2344-2351.
[46]饶卫振,金淳,黄英艺.求解TSP问题的最近邻域与插入混合算法[J].系统工程理论与实践,2011,31(08)：1419-1428.
[47]钟一文,杨建刚,宁正元.求解TSP问题的离散粒子群优化算法[J].系统工程理论与实践,2006,26(06)：88-94.
[48]王宇平,李英华.求解TSP的量子遗传算法[J].计算机学报,2007,30(05)：748-755.
[49]戚玉涛,刘芳,焦李成.求解大规模TSP问题的自适应归约免疫算法[J].软件学报,2008,19(06)：1265-1273.
[50]王东,吴湘滨,毛先成,et a1.一种改进的求解TSP混合粒子群优化算法[J].计算机工程,2008,34(06)：185-187.
[51]刘朝华,章兢,张英杰,et a1.竞争合作型协同进化免疫算法及其在旅行商问题中的应用[J].控制理论与应用,2010,27(10)：1322-1330.
[52]周伟,蒲晓蓉,屈鸿.LT递归神经网络求解旅行商问题研究[J].电子科技大学学报,2011,40(04)：592-595.
[53]吴建辉,章兢,张小刚,et a1.分层协同进化免疫算法及其在TSP问题中的应用[J].电子学报,2011,29(02)：336-344.
[54]何小娟,曾建潮.基于优良模式连接的分布估计算法求解TSP问题[J].模式识别与人工智能,2011,24(02)：185-193.
[55]杜占玮,杨永健,孙永雄,et a1.基于互信息的混合蚁群算法及其在旅行商问题上的应用[J].东南大学学报(自然科学版),2011,41(03)：478-481.
[56]Y. H. Liu. A hybrid scatter search for the probabilistic traveling salesman problem[J]. Computers & Operations Research,2007,34(10):2949-2963.
[57]P. Jaillet. A priori solution of a traveling salesman problem in which a random subset of the customers are visited[J]. Operations Research,1988,36(6):929-936
[58]J. J. Bartholdi, III,L. K. Platzman. Heuristics Based on Spacefilling Curves for Combinatorial Problems in Euclidean Space[J]. Management Science,1988,34(3): 291-305.
[59]J. J. Bartholdi, L. K. Platzman, R. L. Collins, et al. A Minimal Technology Routing System for Meals on Wheels[J]. Interfaces,1983,13(3):1-8.
[60]H. Tang, E. Miller-Hooks,Trb. Approximate procedures for probabilistic traveling salesperson problem[R]. Transportation Network Modeling.2004.
[61]D. Bertsimas, P. Chervi,M. Peterson. Computational approaches to stochastic vehicle routing problems[J]. Transportation Science,1995,29(4):342-352
[62]P. Jaillet. Probabilistic Traveling Salesman Problems[D]. Massachusette Institute of Technology,1985.
[63]O. Berman,D. Simchi-Levi. Finding the optimal a priori tour and location of a traveling Salesman with nonhomogeneous customers[J]. Transportation Science 1988,22(2): 148-154.
[64]G. Laporte, F. V. Louveaux,H. Mercure. A Priori Optimization of the Probabilistic Traveling Salesman Problem[J]. Operations Research,1994,42(3):543-549.
[65]F. Rossi,I. Gavioli. Aspects of heuristic methods in the "Probabilistic Traveling Salesman Problem" (PTSP)[C]. Stochastic in combinatorial optimization, Adv. Sch. CISM. Udine, Italy,1987,214-227.
[66]D. Bertsimas,L. H. Howell. Further results on the probabilistic traveling salesman problem[J]. European Journal of Operational Research,1993,65(1):68-95.
[67]P. Chervi. A Computational Approach to Probabilistic Vehicle Routing Problems[D]. Massachusette Institute of Technology,1988.
[68]J. J. Bartholdi,L. K. Platzman. An O(n log n) planar travelling salesman heuristic based on spacefilling curves[J]. Operations Research Letters,1982,1(4):121-125.
[69]S. Lin. Computer Solutions of the Traveling Salesman Problem[J]. Bell System Technological Journal,1965,44(10):2245-2269.
[70]L. Bianchi, J. Knowles,N. Bowler. Local search for the probabilistic traveling salesman problem:Correction to the 2-p-opt and 1-shift algorithms[J]. European Journal of Operational Research,2005,162(1):206-219.
[71]L. Bianchi,A. M. Campbell. Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem[J]. European Journal of Operational Research,2007,176(1):131-144.
[72]P. Beraldi, G. Ghiani, G. Laporte, et al. Efficient neighborhood search for the Probabilistic Pickup and Delivery Travelling Salesman Problem[J]. Networks,2005, 45(4):195-198.
[73]N. E. Bowler, T. M. A. Fink,R. C. Ball. Characterization of the probabilistic traveling salesman problem[J]. Physical Review E,2003,68(3):
[74]A. M. Campbell,B. W. Thomas. Challenges and Advances in A priori Routing[M]. Springer,2008.
[75]L. Bianchi, L. Gambardella,M. Dorigo. Solving the Homogeneous Probabilistic Traveling Salesman Problem by the ACO Metaheuristic Ant Algorithms[C]. Ant Algorithms,3rd International Workshop, ANTS 2002.2002,2463:25-38.
[76]L. Bianchi, L. M. Gambardella,M. Dorigo. An ant colony optimization approach to the probabilistic traveling salesman problem[C]. Parallel Problem Solving from Nature-PPSN VII.7th International Conference Proceedings.2002,2439:883-892.
[77]Comparison of an Exact Branch-and-Bound and an Approximative Evolutionary Algorithm for the Probabilistic Traveling Salesman Problem [OL]. working paper, available at http://www2.hsu-hh.de/uebe/paper-engl-SOR98.pdf.1998
[78]S. Rosenow. A heuristic for the probabilistic traveling salesman problem[C]. Operations Research Proceedings 1996, Selected Papers of the Symposium on Operations Research (SOR 96).1997,
[79]J. J. Grefenstette, R. Gopal, B. J. Rosmaita, et al. Genetic Algorithms for the Traveling Salesman Problem[C]. Proceedings of the 1st International Conference on Genetic Algorithms. Hillsdale, New York,1985,160-168.
[80]Y. H. Liu. A scatter search based approach with approximate evaluation for the heterogeneous probabilistic traveling salesman problem[C]. Proceedings of the 2006 IEEE Congress on Evolutionary Computation.2006,1588-1594.
[81]Y. H. Liu. Diversified local search strategy under scatter search framework for the probabilistic traveling salesman problem[J]. European Journal of Operational Research, 2008,191(2):332-346.
[82]Y. H. Liu. Different initial solution generators in genetic algorithms for solving the probabilistic traveling salesman problem[J]. Applied Mathematics and Computation, 2010,216(1):125-137.
[83]F. A. Tillman. The Multiple Terminal Delivery Problem with Probabilistic Demands[J]. Transportation Science,1969,3(3):192-204.
[84]A. M. Campbell,B. W. Thomas. Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines[J]. Computers & Operations Research,2009, 36(4):1231-1248.
[85]A. M. Campbell,B. W. Thomas. Probabilistic Traveling Salesman Problem with Deadlines[J]. Transportation Science,2008,42(1):1-21.
[86]胡平,常晓宇,王康平,et al.用基于蚂蚁算法的混合方法求解不确定TSP问题[J].吉林大学学报(理学版),2007,45(02)：221-224.
[87]G. B. Dantzig,J. H. Ramser. The truck dispatching problem[J]. Management Science, 1959,6(1):80-91.
[88]G. Cornuejols,F. Harche. Polyhedral study of the capacitated vehicle routing problem[J]. Mathematical Programming,1993,60(1):21-52.
[89]G. Clarke,J. W. Wright. Scheduling of vehicles from a central depot to a number of delivery points[J]. Operations Research,1964,12(4):568-81.
[90]A. Levin. Scheduling and fleet routing models for transportation systems[J]. Transportation Science,1971,53(3):232-256.
[91]N. Wilson,J. Sussman. Implementation of computer algorithms for the dial-a-bus system[C].39th national meeting of the Operations Research Society of America.1971, 19:
[92]A. D. O'Connor,C. A. De Wald. A sequential deletion algorithm for the design of optimal transportation networks [C].37th national meeting of the Operations Research Society of America.1970,18:
[93]D. H. Marks,R. Strieker. Routing for public service vehicles[J]. ASCE Journal of the Urban Planning and Development Division,1970,97(UP2):165-178.
[94]S. Eilon, C. D. T. Watson-Gandy,N. Christofides. Distribution management: Mathematical modelling and practical analysis[M]. NY:Hafner Publication Co.,1971.
[95]J. C. Liebman. Mathematical models for solid waste collection and disposal[C].38th national meeting of the Operations Research Society of America.1970,18:
[96]B. L. Golden, T. L. Magnanti,H. Q. Nguyan. Implementing vehicle routing algorithms[J]. Networks,1972,7(2):113-148.
[97]R. Baldacci, P. Toth,D. Vigo. Recent advances in vehicle routing exact algorithms[J]. 4or-a Quarterly Journal of Operations Research,2007,5(4):269-298.
[98]B. Eksioglu, A. V. Vural,A. Reisman. The vehicle routing problem:A taxonomic review[J]. Computers & Industrial Engineering,2009,57(4):1472-1483.
[99]N. Christofides, A. Mingozzi,P. Toth. Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations[J]. Mathematical Programming, 1981,20(1):255-282.
[100]G. Laporte, H. Mercure,Y. Nobert. An exact algorithm for the asymmetrical capacitated vehicle routing problem[J]. Networks,1986,16(1):33-46.
[101]P. Toth,D. Vigo. An exact algorithm for the vehicle routing problem with backhauls[J]. Transportation Science,1997,31(4):372-385.
[102]C. A. Valle, A. Salles da Cunha, G. R. Mateus, et al. Exact algorithms for a selective Vehicle Routing Problem where the longest route is minimized[J]. Electronic Notes in Discrete Mathematics,2009,35(133-138.
[103]A. G. Qureshi, E. Taniguchi,T. Yamada. An exact solution approach for vehicle routing and scheduling problems with soft time windows[J]. Transportation Research Part E: Logistics and Transportation Review,2009,45(6):960-977.
[104]B. Gillett,L. Miller. A heuristic algorithm for the vehicle dispatching problem[J]. Operations Research,1974,22(340-349.
[105]I. Or. traveling salesman-type combinatorial problems and their relation to the logistics of blood banking[D]. Northwestern University,1976.
[106]M. Gendreau, G. Laporte,J.-Y. Potvin. Metaheuristics for the vehicle routing problem[R]. Technical report, Les Cahiers du GERAD. Montreal, Canada,1998.
[107]P. D. Wasserman. Neural computing:Theory and practice[M]. New York:VanNostrand Reinhold,1989.
[108]I. H. Osman,J. P. Kelly. Meta-heuristics:An overview[M]. Boston:Kluwer Academic Publishers,1996.
[109]I. H. Osman,G. Laporte. Metaheuristics:A bibliography[J]. Annals of operations research, 1996,63(1):513-628.
[110]M. Dorigo, V. Maniezzo,A. Colorni. The ant system:optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems Man and Cybernetics Part B,1996, 26(1):29-41.
[111]E. Aarts,J. K. Lenstra. Local search in combinatorial optimization[M]. New York:John Wiley & Sons Inc.,1997.
[112]J. F. Cordeau, M. Gendreau, G. Laporte, et al. A guide to vehicle routing heuristics[J]. Journal of the Operational Research Society,2002,53(5):512-522.
[113]F. Glover,M. Laguna. Tabu search[M]. Boston:Kluwer Academic Publishers,1997.
[114]G. Laporte. Fifty Years of Vehicle Routing[J]. Transportation Science,2009,43(4): 408-416.
[115]郭耀煌,李军.车辆优化调度[M].成都：成都科技大学出版社,1994.
[116]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社,2001.
[117]刘宝碇,赵瑞清.不确定规划及应用[M].北京：清华大学出版社,2003.
[118]李琳,刘士新,唐加福.改进的蚁群算法求解带时间窗的车辆路径问题[J].控制与决策,2010,25(09)：1379-1383.
[119]曹二保,赖明勇,聂凯.带时间窗的车辆路径问题的改进差分进化算法研究[J].系统仿真学报,2009,21(08)：2420-2423.
[120]蔡延光,钱积新,孙优贤.带时间窗的多重运输调度问题的自适应Tabu Search算法[J].系统工程理论与实践,2000,20(12)：42-50.
[121]李相勇,田澎.带时间窗和随机时间车辆路径问题：模型和算法[J].系统工程理论与实践,2009,29(08)：81-90.
[122]陈美军,张志胜,史金飞.多约束下多车场车辆路径问题的蚁群算法研究[J].中国机械工程,2008,19(16)：1939-1944.
[123]张景玲,赵燕伟,王海燕,et al.多车型动态需求车辆路径问题建模及优化[J].计算机集成制造系统,2010,16(03)：543-550.
[124]龙磊,陈秋双,华彦宁,et al.具有同时集送货需求的车辆路径问题的自适应混合遗传算法[J].计算机集成制造系统,2008,14(03)：548-556.
[125]龙磊,陈秋双,华彦宁,et al.具有同时集送货需求的车辆路径问题的粗粒度并行遗传算法[J].系统仿真学报,2009,21(07)：1962-1968.
[126]吴斌,钱存华,董敏,et al.具有同时集送货需求车辆路径问题的混沌量子进化算法研究[J].控制与决策,2010,25(03)：383-388.
[127]李延晖,刘向.沿途补货的多车场开放式车辆路径问题及蚁群算法[J].计算机集成制造系统,2008,14(03)：557-562.
[128]刘冉,江志斌,耿娜,et al.半开放式多车场车辆路径问题[J].上海交通大学学报,2010,44(11)：1539-1545.
[129]彭北青.开放式模糊需求车辆路径问题的差分进化算法[J].武汉理工大学学报,2009,31(09)：75-79.
[130]李相勇,田澎.开放式车辆路径问题的蚁群优化算法[J].系统工程理论与实践,2008,28(06)：81-93.
[131]潘震东,唐加福,韩毅.带货物权重的车辆路径问题及遗传算法[J].管理科学学报,2007,10(03)：23-29.
[132]唐加福,孔媛,潘震东,et al.基于划分的蚁群算法求解货物权重车辆路径问题[J].控制理论与应用,2008,25(04)：699-702.
[133]祝崇隽,刘民,吴澄,et al.针对模糊需求的VRP的两种2-OPT算法[J].电子学报,2001,29(08)：1035-1037.
[134]曹二保,赖明勇,李董辉.基于混合差分进化算法的模糊需求车辆路径问题[J].系统工程理论与实践,2009,29(02)：106-113.
[135]郭强,谢秉磊.随机旅行时间车辆路径问题的模型及其算法[J].系统工程学报,2003,18(03)：244-247.
[136]张涛,余绰娅,刘岚,et al.同时送取货的随机旅行时间车辆路径问题方法[J].系统工程理论与实践,2011,31(10)：1912-1920.
[137]娄山佐.一种解决多库房随机车辆路径问题方法[J].系统仿真学报,2007,19(04)：879-882.
[138]娄山佐,吴耀华,肖际伟,et a1.基于增强学习解决随机需求车辆路径问题[J].系统仿真学报,2008,20(14)：2675-2678.
[139]陆琳,谭清美.一类随机需求VRP的混合粒子群算法研究[J].系统工程与电子技术,2006,28(2)：244-247.
[140]彭勇.变需求车辆路线问题建模及基于Inver-over操作的PSO-DP算法[J].系统工程理论与实践,2008,28(10)：76-81.
[141]娄山佐,史忠科.基于交叉熵法解决随机用户和需求车辆路径问题[J].控制与决策,2007,22(01)：7-10.
[142]谢秉磊,安实,郭耀煌.随机车辆路径问题的多回路优化策略[J].系统工程理论与实践,2007,27(02)：167-171.
[143]郭耀煌,谢秉磊.一类随机动态车辆路径问题的策略分析[J].管理工程学报,2003,17(04)：114-115.
[144]郭耀煌.不确定信息条件下动态车辆路径[J].学术动态,2004,13(02)：23-25.
[145]贾永基,谷寒雨,席裕庚.动态车辆调度系统的滚动时域调度算法(英文)[J]. Journal of Southeast University,2005,21(1):92-96.
[146]王江晴,康立山.动态车辆路径问题中的实时最短路径算法研究[J].武汉理工大学学报(交通科学与工程版),2007,31(01)：46-49.
[147]宋伟刚,张宏霞,佟玲.有时间窗约束非满载车辆调度问题的节约算法[J].东北大学学报(自然科学版),2006,27(01)：65-68.
[148]李松,刘兴,张爱国,et a1.基于SWEEP方法的改进车辆路径协作策略研究[J].系统工程与电子技术,2008,30(03)：489-491.
[149]陈萍,黄厚宽,董兴业.基于多邻域的车辆路径优化迭代局部搜索算法[J].北京交通大学学报,2009,33(02)：1-5.
[150]祝崇隽,刘民,吴澄.供应链中车辆路径问题的研究进展及前景[J].计算机集成制造系统,2001,7(11)：1-6.
[151]冯辉宗,陈勇,刘飞.基于遗传算法的配送车辆优化调度[J].计算机集成制造系统,2004,10(S1)：81-84.
[152]宋伟刚,张宏霞,佟玲.有时间窗约束非满载车辆调度问题的遗传算法[J].系统仿真学报,2005,17(11)：2593-2597.
[153]井祥鹤.陆路物流物资配载及输送路径优化问题的模型与算法[D].南京理工大学,2007.
[154]钟石泉.物流配送车辆路径优化方法研究[D].天津大学,2007.
[155]胡大伟.设施定位和车辆路线问题模型及其启发式算法研究[D].长安大学,2008.
[156]蔡延光,钱积新,孙优贤.多重运输调度问题的模拟退火算法[J].系统工程理论与实践,1998,18(10)：11-15.
[157]陈宝文.蚁群优化算法在车辆路径问题中的应用研究[D].哈尔滨工业大学,2009.
[158]刘志硕,柴跃廷,申金升.蚁群算法及其在有硬时间窗的车辆路径问题中的应用[J].计算机集成制造系统,2006,12(04)：596-602.
[159]张涛,田文馨,张玥杰,et a1.基于剩余装载能力的蚁群算法求解同时送取货车辆路 径问题[J].控制理论与应用,2009,26(05)：546-549.
[160]吴斌.车辆路径问题的粒子群算法研究与应用[D].浙江工业大学,2008.
[161]刘芹,史忠科.混合粒子群算法求解交通路网中的车辆调度问题[J].控制与决策,2006,21(11)：1284-1288.
[162]马慧民,吴勇,叶春明.车辆路径问题的并行粒子群算法研究[J].上海理工大学学报,2007,29(05)：435-439.
[163]王芳,丁海利,高成修.改进的粒子群优化算法在随机需求车辆路径问题中的应用[J].武汉大学学报(理学版),2007,53(01)：4]-44.
[164]张海刚,顾幸生,徐震浩.基于免疫算法的带软时间窗车辆调度问题[J].华东理工大学学报(自然科学版),2007,33(01)：104-107.
[165]赵燕伟,彭典军,张景玲,et a1.有能力约束车辆路径问题的量子进化算法[J].系统工程理论与实践,2009,29(02)：159-166.
[166]B. L. Golden,J. R. Yee. A Framework For Probabilistic Vehicle Routing[J]. A I I E Transactions,1979,11(2):109-112.
[167]W. R. Stewart Jr,B. L. Golden. Stochastic vehicle routing:A comprehensive approach[J]. European Journal of Operational Research,1983,14(4):371-385.
[168]G. Laporte, F. Louveaux,H. Mercure. Models and exact solutions for a class of stochastic location-routing problems[J]. European Journal of Operational Research,1989,39(1): 71-78.
[169]C. Bastian, K. Rinnooy,H. G. Alexander. The stochastic vehicle routing problem revisited[J]. European Journal of Operational Research,1992,56(3):407-412.
[170]M. Dror, G. Laporte,P. Trudeau. Vehicle routing with stochastic demands:properties and solution frameworks[J]. Transportation Science 1989,23(3):166-176.
[171]M. Dror. Modeling vehicle routing with uncertain demands as a stochastic program: Properties of the corresponding solution[J]. European Journal of Operational Research, 1993,64(3):432-441.
[172]M. Gendreau, G. Laporte,R. Seguin. An exact algorithm for the vehicle routing problem with stochastic demands and customers[J]. Transportation Science,1995,29(2):143-155
[173]D. J. Bertsimas. A vehicle routing problem with stochastic demand[J]. Operations Research,1992,40(3):574-585.
[174]M. W. P. Savelsbergh,M. Goetschalckx. A Comparison of the Efficiency of Fixed Versus Variable Vehicle Routes[J]. Journal of Business Logistics,1995,46(2):474-490.
[175]W. H. Yang, K. Mathur,R. H. Ballou. Stochastic vehicle routing problem with restocking[J]. Transportation Science 2000,34(1):99-112
[176]C. Novoa,R. Storer. An approximate dynamic programming approach for the vehicle routing problem with stochastic demands[J]. European Journal of Operational Research, 2009,196(2):509-515.
[177]M. Gendreau, G. Laporte,R. Seguin. A tabu search heuristic for the vehicle routing problem with stochastic demands and customers[J]. Operations Research,1996,44(3): 469-477.
[178]N. Secomandi. Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands[J]. Computers and Operations Research,2000, 27(11-12):1201-1225.
[179]VRP Web[OL]. http://neo.lcc.uma.es/radi-aeb/WebVRP/.2012
[180]J. Branke,M. Guntsch. Solving the Probabilistic TSP with Ant Colony Optimization[J]. Journal of Mathematical Modelling and Algorithms,2004,3(4):403-425.
[2]A. K. Jain,R. C. Dubes. ALGORITHMS FOR CLUSTERING DATA[M]. New Jersey: Prentice Hall,1988.
[3]Sokal,Sneath. Principles of Numerical Taxonomy[M]. San Francisco:W.H. Freeman,1963.
[4]M. R. Anderberg. Cluster Analysis for Applications [M]. New York, NY:Academic Press,1973.
[5]J. A. Hartigan. Clustering algorithms[M]. Wiley,1975.
[6]R. Duda, P. Hart,D. Stork. Pattern Classification[M]. New York:John Wiley and Sons,2001.
[7]J. Han,M. Kamber. Data Mining:Concepts and Techniques[M]. Morgan Kaufmann,2000.
[8]P. N. Tan, M. Steinbach,V. Kumar. Introduction to Data Mining[M]. Boston, MA, USA: Addison-Wesley Longman Publishing Co. Inc,2005.
[9]C. M. Bishop. Pattern Recognition and Machine Learning[M]. Springer,2006.
[10]刘位龙.面向不确定性数据的聚类算法研究[D].山东师范大学,2011.
[11]M. Chau, R. Cheng, B. Kao, et al. Uncertain Data Mining:An Example in Clustering Location Data Advances in Knowledge Discovery and Data Mining[C]. Advances in Knowledge Discovery and Data Mining,10th Pacific-Asia Conference, PAKDD 2006. Singapore,2006,3918:199-204.
[12]S. D. Lee, B. Kao,R. Cheng. Reducing UK-means to k-means[C].17th IEEE International Conference on Data Mining Workshops, ICDM Workshops 2007, October 28,2007-October 31,2007. Omaha, NE, United states,2007,483-488.
[13]B. Kao, S. D. Lee, D. W. Cheung, et al. Clustering uncertain data using voronoi diagrams[C].8th IEEE International Conference on Data Mining, ICDM 2008, December 15,2008-December 19,2008. Pisa, Italy,2008,333-342.
[14]H. P. Kriegel,M. Pfeifle. Density-based clustering of uncertain data[C]. Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. Chicago, Illinois, USA,2005,672-677.
[15]孔德昌,刘蓉.一种概率聚类的新算法[J].计算机应用与软件,2007,24(11)：180-182.
[16]周傲英,金澈清,王国仁,et al.不确定性数据管理技术研究综述[J].计算机学报,2009,31(01)：1-16.
[17]许华杰,李国徽,杨兵,et al.基于密度的不确定性数据概率聚类[J].计算机科学,2009,36(05)：68-71.
[18]李云飞,王丽珍,周丽华.不确定数据的高效聚类算法[J].广西师范大学学报(自然科学版),2011,29(02)：161-166.
[19]戴东波,赵杠,孙圣力.基于概率数据流的有效聚类算法[J].软件学报,2009,20(05)：1313-1328.
[20]张晨,金澈清,周傲英.一种不确定数据流聚类算法[J].软件学报,2010,21(09)：2173-2182.
[21]张新猛,蒋盛益.一种基于相似度概率的不确定分类数据聚类算法[J].山东大学学报(工学版),2011,41(03)：12-16.
[22]李雪.不确定数据聚类研究[D].大连理工大学,2009.
[23]R. E. Bland,D. F. Shallcross. Large Traveling Salesman Problem Arising from Experiments in X-ray Crystallography:a Preliminary Report on Computation[R]. Technical Report No.730, School of OR/IE, Cornell University. Ithaca, New York,1987.
[24]H. D. Ratliff,A. S. Rosenthal. Order-Picking in a Rectangular Warehouse:A Solvable Case for the Traveling Salesman Problem[R]. PDRC Report Series No.81-10. Georgia Institute of Technology, Atlanta, Georgia,1981.
[25]E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, et al. TheTraveling Salesman Problem[M]. Chichester:John Wiley,1985.
[26]S. Goyal. A Survey on Travelling Salesman Problem[C]. Midwest Instruction and Computing Symposium. Eau Claire,2010,
[27]S. Lin,B. W. Kernighan. An Effective Heuristic Algorithm for the Traveling Salesman Problem[J]. Informs Journal on Operations Research,1973,
[28]P. C. P. Kanellakis, C.H.. Local search for the asymmetric traveling salesman problem[J]. Operations Research 1980,28(5):1086-99.
[29]K. Helsgaun. An effective implementation of the Lin-Kernighan traveling salesman heuristic[J]. European Journal of Operational Research,2000,126(1):106-130.
[30]D. Applegate, W. Cook,A. Rohe. Chained Lin-Kernighan for large traveling salesman problems[J]. Informs Journal on Computing,2003,15(1):82-92.
[31]O. Martin, S. W. Otto,E. W. Felten. Large-step markov chains for the TSP incorporating local search heuristics[J]. Operations Research Letters,1992,11(4):219-224.
[32]D. Karapetyan,G. Gutin. Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem[J]. European Journal of Operational Research,2011,208(3): 221-232.
[33]J. Schneider. Searching for Backbones-a high-performance parallel algorithm for solving combinatorial optimization problems[J]. Future Generation Computer Systems, 2003,19(1):121-131.
[34]邹鹏,周智,陈国良,et a1.求解tsp问题的多级归约算法[J].软件学报,2003,14(01)：35-42.
[35]W. X. Zhang,M. Looks. A novel local search algorithm for the traveling salesman problem that exploits backbones[C]. Proceedings of the 19th international joint conference on Artificial intelligence. Edinburgh, Scotland,2005,343-348.
[36]G. Laporte. The traveling salesman problem:An overview of exact and approximate algorithms[J]. European Journal of Operational Research,1992,59(2):231-247.
[37]C. Rego, D. Gamboa, F. Glover, et al. Traveling salesman problem heuristics:Leading methods, implementations and latest advances[J]. European Journal of Operational Research,2010,211(3):427-441.
[38]Concorde TSP Solver[OL]. http://www.tsp.gatech.edu/concorde/index.html.2012
[39]LKH [OL]. http://www.akira.ruc.dk/-keld/research/LKH/.2012
[40]林冬梅,王东.改进的求解TSP混合分支裁剪法[J].计算机工程与设计,2008,29(02)：424-425.
[41]王东,吴湘滨,毛先成,et a1.小规模TSP边集裁剪策略研究[J].系统工程与电子技术,2008,30(09)：1693-1696.
[42]王东,林冬梅.优化初始边集提高分支裁剪法求解TSP效率[J].计算机工程与设计,2007,28(15)：3797-3799.
[43]江贺,周智,陈国良.TSP问题启发集的分析及应用[J].中国科学技术大学学报,2005,35(05)：683-692.
[44]江贺,周智,邹鹏,et a1.求解TSP问题的并集搜索的新宏启发算法[J].中国科学技术大学学报,2005,35(03)：367-375.
[45]江贺,胡燕,李强,et al. TSP问题的脂肪计算复杂性与启发式算法设计[J].软件学报,2009,20(09)：2344-2351.
[46]饶卫振,金淳,黄英艺.求解TSP问题的最近邻域与插入混合算法[J].系统工程理论与实践,2011,31(08)：1419-1428.
[47]钟一文,杨建刚,宁正元.求解TSP问题的离散粒子群优化算法[J].系统工程理论与实践,2006,26(06)：88-94.
[48]王宇平,李英华.求解TSP的量子遗传算法[J].计算机学报,2007,30(05)：748-755.
[49]戚玉涛,刘芳,焦李成.求解大规模TSP问题的自适应归约免疫算法[J].软件学报,2008,19(06)：1265-1273.
[50]王东,吴湘滨,毛先成,et a1.一种改进的求解TSP混合粒子群优化算法[J].计算机工程,2008,34(06)：185-187.
[51]刘朝华,章兢,张英杰,et a1.竞争合作型协同进化免疫算法及其在旅行商问题中的应用[J].控制理论与应用,2010,27(10)：1322-1330.
[52]周伟,蒲晓蓉,屈鸿.LT递归神经网络求解旅行商问题研究[J].电子科技大学学报,2011,40(04)：592-595.
[53]吴建辉,章兢,张小刚,et a1.分层协同进化免疫算法及其在TSP问题中的应用[J].电子学报,2011,29(02)：336-344.
[54]何小娟,曾建潮.基于优良模式连接的分布估计算法求解TSP问题[J].模式识别与人工智能,2011,24(02)：185-193.
[55]杜占玮,杨永健,孙永雄,et a1.基于互信息的混合蚁群算法及其在旅行商问题上的应用[J].东南大学学报(自然科学版),2011,41(03)：478-481.
[56]Y. H. Liu. A hybrid scatter search for the probabilistic traveling salesman problem[J]. Computers & Operations Research,2007,34(10):2949-2963.
[57]P. Jaillet. A priori solution of a traveling salesman problem in which a random subset of the customers are visited[J]. Operations Research,1988,36(6):929-936
[58]J. J. Bartholdi, III,L. K. Platzman. Heuristics Based on Spacefilling Curves for Combinatorial Problems in Euclidean Space[J]. Management Science,1988,34(3): 291-305.
[59]J. J. Bartholdi, L. K. Platzman, R. L. Collins, et al. A Minimal Technology Routing System for Meals on Wheels[J]. Interfaces,1983,13(3):1-8.
[60]H. Tang, E. Miller-Hooks,Trb. Approximate procedures for probabilistic traveling salesperson problem[R]. Transportation Network Modeling.2004.
[61]D. Bertsimas, P. Chervi,M. Peterson. Computational approaches to stochastic vehicle routing problems[J]. Transportation Science,1995,29(4):342-352
[62]P. Jaillet. Probabilistic Traveling Salesman Problems[D]. Massachusette Institute of Technology,1985.
[63]O. Berman,D. Simchi-Levi. Finding the optimal a priori tour and location of a traveling Salesman with nonhomogeneous customers[J]. Transportation Science 1988,22(2): 148-154.
[64]G. Laporte, F. V. Louveaux,H. Mercure. A Priori Optimization of the Probabilistic Traveling Salesman Problem[J]. Operations Research,1994,42(3):543-549.
[65]F. Rossi,I. Gavioli. Aspects of heuristic methods in the "Probabilistic Traveling Salesman Problem" (PTSP)[C]. Stochastic in combinatorial optimization, Adv. Sch. CISM. Udine, Italy,1987,214-227.
[66]D. Bertsimas,L. H. Howell. Further results on the probabilistic traveling salesman problem[J]. European Journal of Operational Research,1993,65(1):68-95.
[67]P. Chervi. A Computational Approach to Probabilistic Vehicle Routing Problems[D]. Massachusette Institute of Technology,1988.
[68]J. J. Bartholdi,L. K. Platzman. An O(n log n) planar travelling salesman heuristic based on spacefilling curves[J]. Operations Research Letters,1982,1(4):121-125.
[69]S. Lin. Computer Solutions of the Traveling Salesman Problem[J]. Bell System Technological Journal,1965,44(10):2245-2269.
[70]L. Bianchi, J. Knowles,N. Bowler. Local search for the probabilistic traveling salesman problem:Correction to the 2-p-opt and 1-shift algorithms[J]. European Journal of Operational Research,2005,162(1):206-219.
[71]L. Bianchi,A. M. Campbell. Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem[J]. European Journal of Operational Research,2007,176(1):131-144.
[72]P. Beraldi, G. Ghiani, G. Laporte, et al. Efficient neighborhood search for the Probabilistic Pickup and Delivery Travelling Salesman Problem[J]. Networks,2005, 45(4):195-198.
[73]N. E. Bowler, T. M. A. Fink,R. C. Ball. Characterization of the probabilistic traveling salesman problem[J]. Physical Review E,2003,68(3):
[74]A. M. Campbell,B. W. Thomas. Challenges and Advances in A priori Routing[M]. Springer,2008.
[75]L. Bianchi, L. Gambardella,M. Dorigo. Solving the Homogeneous Probabilistic Traveling Salesman Problem by the ACO Metaheuristic Ant Algorithms[C]. Ant Algorithms,3rd International Workshop, ANTS 2002.2002,2463:25-38.
[76]L. Bianchi, L. M. Gambardella,M. Dorigo. An ant colony optimization approach to the probabilistic traveling salesman problem[C]. Parallel Problem Solving from Nature-PPSN VII.7th International Conference Proceedings.2002,2439:883-892.
[77]Comparison of an Exact Branch-and-Bound and an Approximative Evolutionary Algorithm for the Probabilistic Traveling Salesman Problem [OL]. working paper, available at http://www2.hsu-hh.de/uebe/paper-engl-SOR98.pdf.1998
[78]S. Rosenow. A heuristic for the probabilistic traveling salesman problem[C]. Operations Research Proceedings 1996, Selected Papers of the Symposium on Operations Research (SOR 96).1997,
[79]J. J. Grefenstette, R. Gopal, B. J. Rosmaita, et al. Genetic Algorithms for the Traveling Salesman Problem[C]. Proceedings of the 1st International Conference on Genetic Algorithms. Hillsdale, New York,1985,160-168.
[80]Y. H. Liu. A scatter search based approach with approximate evaluation for the heterogeneous probabilistic traveling salesman problem[C]. Proceedings of the 2006 IEEE Congress on Evolutionary Computation.2006,1588-1594.
[81]Y. H. Liu. Diversified local search strategy under scatter search framework for the probabilistic traveling salesman problem[J]. European Journal of Operational Research, 2008,191(2):332-346.
[82]Y. H. Liu. Different initial solution generators in genetic algorithms for solving the probabilistic traveling salesman problem[J]. Applied Mathematics and Computation, 2010,216(1):125-137.
[83]F. A. Tillman. The Multiple Terminal Delivery Problem with Probabilistic Demands[J]. Transportation Science,1969,3(3):192-204.
[84]A. M. Campbell,B. W. Thomas. Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines[J]. Computers & Operations Research,2009, 36(4):1231-1248.
[85]A. M. Campbell,B. W. Thomas. Probabilistic Traveling Salesman Problem with Deadlines[J]. Transportation Science,2008,42(1):1-21.
[86]胡平,常晓宇,王康平,et al.用基于蚂蚁算法的混合方法求解不确定TSP问题[J].吉林大学学报(理学版),2007,45(02)：221-224.
[87]G. B. Dantzig,J. H. Ramser. The truck dispatching problem[J]. Management Science, 1959,6(1):80-91.
[88]G. Cornuejols,F. Harche. Polyhedral study of the capacitated vehicle routing problem[J]. Mathematical Programming,1993,60(1):21-52.
[89]G. Clarke,J. W. Wright. Scheduling of vehicles from a central depot to a number of delivery points[J]. Operations Research,1964,12(4):568-81.
[90]A. Levin. Scheduling and fleet routing models for transportation systems[J]. Transportation Science,1971,53(3):232-256.
[91]N. Wilson,J. Sussman. Implementation of computer algorithms for the dial-a-bus system[C].39th national meeting of the Operations Research Society of America.1971, 19:
[92]A. D. O'Connor,C. A. De Wald. A sequential deletion algorithm for the design of optimal transportation networks [C].37th national meeting of the Operations Research Society of America.1970,18:
[93]D. H. Marks,R. Strieker. Routing for public service vehicles[J]. ASCE Journal of the Urban Planning and Development Division,1970,97(UP2):165-178.
[94]S. Eilon, C. D. T. Watson-Gandy,N. Christofides. Distribution management: Mathematical modelling and practical analysis[M]. NY:Hafner Publication Co.,1971.
[95]J. C. Liebman. Mathematical models for solid waste collection and disposal[C].38th national meeting of the Operations Research Society of America.1970,18:
[96]B. L. Golden, T. L. Magnanti,H. Q. Nguyan. Implementing vehicle routing algorithms[J]. Networks,1972,7(2):113-148.
[97]R. Baldacci, P. Toth,D. Vigo. Recent advances in vehicle routing exact algorithms[J]. 4or-a Quarterly Journal of Operations Research,2007,5(4):269-298.
[98]B. Eksioglu, A. V. Vural,A. Reisman. The vehicle routing problem:A taxonomic review[J]. Computers & Industrial Engineering,2009,57(4):1472-1483.
[99]N. Christofides, A. Mingozzi,P. Toth. Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations[J]. Mathematical Programming, 1981,20(1):255-282.
[100]G. Laporte, H. Mercure,Y. Nobert. An exact algorithm for the asymmetrical capacitated vehicle routing problem[J]. Networks,1986,16(1):33-46.
[101]P. Toth,D. Vigo. An exact algorithm for the vehicle routing problem with backhauls[J]. Transportation Science,1997,31(4):372-385.
[102]C. A. Valle, A. Salles da Cunha, G. R. Mateus, et al. Exact algorithms for a selective Vehicle Routing Problem where the longest route is minimized[J]. Electronic Notes in Discrete Mathematics,2009,35(133-138.
[103]A. G. Qureshi, E. Taniguchi,T. Yamada. An exact solution approach for vehicle routing and scheduling problems with soft time windows[J]. Transportation Research Part E: Logistics and Transportation Review,2009,45(6):960-977.
[104]B. Gillett,L. Miller. A heuristic algorithm for the vehicle dispatching problem[J]. Operations Research,1974,22(340-349.
[105]I. Or. traveling salesman-type combinatorial problems and their relation to the logistics of blood banking[D]. Northwestern University,1976.
[106]M. Gendreau, G. Laporte,J.-Y. Potvin. Metaheuristics for the vehicle routing problem[R]. Technical report, Les Cahiers du GERAD. Montreal, Canada,1998.
[107]P. D. Wasserman. Neural computing:Theory and practice[M]. New York:VanNostrand Reinhold,1989.
[108]I. H. Osman,J. P. Kelly. Meta-heuristics:An overview[M]. Boston:Kluwer Academic Publishers,1996.
[109]I. H. Osman,G. Laporte. Metaheuristics:A bibliography[J]. Annals of operations research, 1996,63(1):513-628.
[110]M. Dorigo, V. Maniezzo,A. Colorni. The ant system:optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems Man and Cybernetics Part B,1996, 26(1):29-41.
[111]E. Aarts,J. K. Lenstra. Local search in combinatorial optimization[M]. New York:John Wiley & Sons Inc.,1997.
[112]J. F. Cordeau, M. Gendreau, G. Laporte, et al. A guide to vehicle routing heuristics[J]. Journal of the Operational Research Society,2002,53(5):512-522.
[113]F. Glover,M. Laguna. Tabu search[M]. Boston:Kluwer Academic Publishers,1997.
[114]G. Laporte. Fifty Years of Vehicle Routing[J]. Transportation Science,2009,43(4): 408-416.
[115]郭耀煌,李军.车辆优化调度[M].成都：成都科技大学出版社,1994.
[116]李军,郭耀煌.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社,2001.
[117]刘宝碇,赵瑞清.不确定规划及应用[M].北京：清华大学出版社,2003.
[118]李琳,刘士新,唐加福.改进的蚁群算法求解带时间窗的车辆路径问题[J].控制与决策,2010,25(09)：1379-1383.
[119]曹二保,赖明勇,聂凯.带时间窗的车辆路径问题的改进差分进化算法研究[J].系统仿真学报,2009,21(08)：2420-2423.
[120]蔡延光,钱积新,孙优贤.带时间窗的多重运输调度问题的自适应Tabu Search算法[J].系统工程理论与实践,2000,20(12)：42-50.
[121]李相勇,田澎.带时间窗和随机时间车辆路径问题：模型和算法[J].系统工程理论与实践,2009,29(08)：81-90.
[122]陈美军,张志胜,史金飞.多约束下多车场车辆路径问题的蚁群算法研究[J].中国机械工程,2008,19(16)：1939-1944.
[123]张景玲,赵燕伟,王海燕,et al.多车型动态需求车辆路径问题建模及优化[J].计算机集成制造系统,2010,16(03)：543-550.
[124]龙磊,陈秋双,华彦宁,et al.具有同时集送货需求的车辆路径问题的自适应混合遗传算法[J].计算机集成制造系统,2008,14(03)：548-556.
[125]龙磊,陈秋双,华彦宁,et al.具有同时集送货需求的车辆路径问题的粗粒度并行遗传算法[J].系统仿真学报,2009,21(07)：1962-1968.
[126]吴斌,钱存华,董敏,et al.具有同时集送货需求车辆路径问题的混沌量子进化算法研究[J].控制与决策,2010,25(03)：383-388.
[127]李延晖,刘向.沿途补货的多车场开放式车辆路径问题及蚁群算法[J].计算机集成制造系统,2008,14(03)：557-562.
[128]刘冉,江志斌,耿娜,et al.半开放式多车场车辆路径问题[J].上海交通大学学报,2010,44(11)：1539-1545.
[129]彭北青.开放式模糊需求车辆路径问题的差分进化算法[J].武汉理工大学学报,2009,31(09)：75-79.
[130]李相勇,田澎.开放式车辆路径问题的蚁群优化算法[J].系统工程理论与实践,2008,28(06)：81-93.
[131]潘震东,唐加福,韩毅.带货物权重的车辆路径问题及遗传算法[J].管理科学学报,2007,10(03)：23-29.
[132]唐加福,孔媛,潘震东,et al.基于划分的蚁群算法求解货物权重车辆路径问题[J].控制理论与应用,2008,25(04)：699-702.
[133]祝崇隽,刘民,吴澄,et al.针对模糊需求的VRP的两种2-OPT算法[J].电子学报,2001,29(08)：1035-1037.
[134]曹二保,赖明勇,李董辉.基于混合差分进化算法的模糊需求车辆路径问题[J].系统工程理论与实践,2009,29(02)：106-113.
[135]郭强,谢秉磊.随机旅行时间车辆路径问题的模型及其算法[J].系统工程学报,2003,18(03)：244-247.
[136]张涛,余绰娅,刘岚,et al.同时送取货的随机旅行时间车辆路径问题方法[J].系统工程理论与实践,2011,31(10)：1912-1920.
[137]娄山佐.一种解决多库房随机车辆路径问题方法[J].系统仿真学报,2007,19(04)：879-882.
[138]娄山佐,吴耀华,肖际伟,et a1.基于增强学习解决随机需求车辆路径问题[J].系统仿真学报,2008,20(14)：2675-2678.
[139]陆琳,谭清美.一类随机需求VRP的混合粒子群算法研究[J].系统工程与电子技术,2006,28(2)：244-247.
[140]彭勇.变需求车辆路线问题建模及基于Inver-over操作的PSO-DP算法[J].系统工程理论与实践,2008,28(10)：76-81.
[141]娄山佐,史忠科.基于交叉熵法解决随机用户和需求车辆路径问题[J].控制与决策,2007,22(01)：7-10.
[142]谢秉磊,安实,郭耀煌.随机车辆路径问题的多回路优化策略[J].系统工程理论与实践,2007,27(02)：167-171.
[143]郭耀煌,谢秉磊.一类随机动态车辆路径问题的策略分析[J].管理工程学报,2003,17(04)：114-115.
[144]郭耀煌.不确定信息条件下动态车辆路径[J].学术动态,2004,13(02)：23-25.
[145]贾永基,谷寒雨,席裕庚.动态车辆调度系统的滚动时域调度算法(英文)[J]. Journal of Southeast University,2005,21(1):92-96.
[146]王江晴,康立山.动态车辆路径问题中的实时最短路径算法研究[J].武汉理工大学学报(交通科学与工程版),2007,31(01)：46-49.
[147]宋伟刚,张宏霞,佟玲.有时间窗约束非满载车辆调度问题的节约算法[J].东北大学学报(自然科学版),2006,27(01)：65-68.
[148]李松,刘兴,张爱国,et a1.基于SWEEP方法的改进车辆路径协作策略研究[J].系统工程与电子技术,2008,30(03)：489-491.
[149]陈萍,黄厚宽,董兴业.基于多邻域的车辆路径优化迭代局部搜索算法[J].北京交通大学学报,2009,33(02)：1-5.
[150]祝崇隽,刘民,吴澄.供应链中车辆路径问题的研究进展及前景[J].计算机集成制造系统,2001,7(11)：1-6.
[151]冯辉宗,陈勇,刘飞.基于遗传算法的配送车辆优化调度[J].计算机集成制造系统,2004,10(S1)：81-84.
[152]宋伟刚,张宏霞,佟玲.有时间窗约束非满载车辆调度问题的遗传算法[J].系统仿真学报,2005,17(11)：2593-2597.
[153]井祥鹤.陆路物流物资配载及输送路径优化问题的模型与算法[D].南京理工大学,2007.
[154]钟石泉.物流配送车辆路径优化方法研究[D].天津大学,2007.
[155]胡大伟.设施定位和车辆路线问题模型及其启发式算法研究[D].长安大学,2008.
[156]蔡延光,钱积新,孙优贤.多重运输调度问题的模拟退火算法[J].系统工程理论与实践,1998,18(10)：11-15.
[157]陈宝文.蚁群优化算法在车辆路径问题中的应用研究[D].哈尔滨工业大学,2009.
[158]刘志硕,柴跃廷,申金升.蚁群算法及其在有硬时间窗的车辆路径问题中的应用[J].计算机集成制造系统,2006,12(04)：596-602.
[159]张涛,田文馨,张玥杰,et a1.基于剩余装载能力的蚁群算法求解同时送取货车辆路 径问题[J].控制理论与应用,2009,26(05)：546-549.
[160]吴斌.车辆路径问题的粒子群算法研究与应用[D].浙江工业大学,2008.
[161]刘芹,史忠科.混合粒子群算法求解交通路网中的车辆调度问题[J].控制与决策,2006,21(11)：1284-1288.
[162]马慧民,吴勇,叶春明.车辆路径问题的并行粒子群算法研究[J].上海理工大学学报,2007,29(05)：435-439.
[163]王芳,丁海利,高成修.改进的粒子群优化算法在随机需求车辆路径问题中的应用[J].武汉大学学报(理学版),2007,53(01)：4]-44.
[164]张海刚,顾幸生,徐震浩.基于免疫算法的带软时间窗车辆调度问题[J].华东理工大学学报(自然科学版),2007,33(01)：104-107.
[165]赵燕伟,彭典军,张景玲,et a1.有能力约束车辆路径问题的量子进化算法[J].系统工程理论与实践,2009,29(02)：159-166.
[166]B. L. Golden,J. R. Yee. A Framework For Probabilistic Vehicle Routing[J]. A I I E Transactions,1979,11(2):109-112.
[167]W. R. Stewart Jr,B. L. Golden. Stochastic vehicle routing:A comprehensive approach[J]. European Journal of Operational Research,1983,14(4):371-385.
[168]G. Laporte, F. Louveaux,H. Mercure. Models and exact solutions for a class of stochastic location-routing problems[J]. European Journal of Operational Research,1989,39(1): 71-78.
[169]C. Bastian, K. Rinnooy,H. G. Alexander. The stochastic vehicle routing problem revisited[J]. European Journal of Operational Research,1992,56(3):407-412.
[170]M. Dror, G. Laporte,P. Trudeau. Vehicle routing with stochastic demands:properties and solution frameworks[J]. Transportation Science 1989,23(3):166-176.
[171]M. Dror. Modeling vehicle routing with uncertain demands as a stochastic program: Properties of the corresponding solution[J]. European Journal of Operational Research, 1993,64(3):432-441.
[172]M. Gendreau, G. Laporte,R. Seguin. An exact algorithm for the vehicle routing problem with stochastic demands and customers[J]. Transportation Science,1995,29(2):143-155
[173]D. J. Bertsimas. A vehicle routing problem with stochastic demand[J]. Operations Research,1992,40(3):574-585.
[174]M. W. P. Savelsbergh,M. Goetschalckx. A Comparison of the Efficiency of Fixed Versus Variable Vehicle Routes[J]. Journal of Business Logistics,1995,46(2):474-490.
[175]W. H. Yang, K. Mathur,R. H. Ballou. Stochastic vehicle routing problem with restocking[J]. Transportation Science 2000,34(1):99-112
[176]C. Novoa,R. Storer. An approximate dynamic programming approach for the vehicle routing problem with stochastic demands[J]. European Journal of Operational Research, 2009,196(2):509-515.
[177]M. Gendreau, G. Laporte,R. Seguin. A tabu search heuristic for the vehicle routing problem with stochastic demands and customers[J]. Operations Research,1996,44(3): 469-477.
[178]N. Secomandi. Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands[J]. Computers and Operations Research,2000, 27(11-12):1201-1225.
[179]VRP Web[OL]. http://neo.lcc.uma.es/radi-aeb/WebVRP/.2012
[180]J. Branke,M. Guntsch. Solving the Probabilistic TSP with Ant Colony Optimization[J]. Journal of Mathematical Modelling and Algorithms,2004,3(4):403-425.