摘要
膜计算是自然计算的一个新的分支。它是由细胞以及由细胞组成的组织或器官的结构和功能得到启发,而抽象出来的一种计算模式。从“膜计算”的概念提出至今十几年的时间里,关于膜计算的计算理论、模型、算法及应用得到了飞速发展。膜计算为计算机科学提供了新的分布式并行信息处理方法和技术,促进了新型高性能计算技术的发展,为求解计算困难问题提供了新的途径。类细胞膜系统和类组织膜系统是膜计算模型的两种基本类型。本文主要研究了在这两种模型框架下求解计算困难问题的膜计算算法。
计算有效性描述的是模型求解计算困难问题的能力,是自然计算中的一个关键问题。膜计算模型基于常用的空间换时间的方法(通常使用受生物启发的操作,如膜分裂、膜分割和膜创生),可以在多项式时间内求解计算困难问题。如何构造算法在多项式时间内求解计算困难问题,特别是,NP完全问题,PSPACE完全问题；如何改进已有的结果,构造半统一形式(semi-uniform)的解与统一形式(uniform)的解等都是值得研究的方向。本文对几个经典的NP完全问题—CAP问题、三匹配问题、二次分配问题,给出了不同膜系统框架或不同规则使用模式下的算法,分析了不同膜系统模型在计算中的表现。
空间换时间的膜计算算法尽管从理论上来说是正确的,但目前尚无真正意义上的生物或物理实现。从算法实现的现实考虑,膜计算优化算法成为解决计算困难问题的另外一种途径。它是膜系统框架与优化算法结合而成的,可以通过电子计算机仿真实现,得到关于计算困难问题的近似解。本文分别构造了两类膜系统框架下的膜计算优化算法,并将它们应用到路径规划领域,成功地求解了带容量约束的交通路径问题和带时间窗的交通路径问题。膜系统提供的并行分布式计算模型、结构变化方式和信息交流方式可以很好的改进传统优化算法的性能。主要工作如下：
首先,研究了带活性膜的膜系统框架下的算法设计。带活性膜的膜系统是类细胞膜系统的一种重要类型。该模型在计算过程中往往包含膜结构的不断进化。早期的带活性膜的膜系统是受电荷(+,-,0)控制的模型。但是,电荷的频繁变化不符合生物实际,从计算的角度看,也浪费了大量的计算资源。对于一个经典的NP完全问题—CAP问题,本文改进了Perez-Jimenez等人的已有结论,设计了不带电荷的情况下,求解该问题的算法,并给出了由半统一形式的解到统一形式的解的改进。另外,本文还研究了在极小并行的规则使用模式下如何求解该问题。特别地,这里首次在极小并行的情况下,给出了无电荷的带活性膜的膜系统求解NP问题的统一形式的解。
其次,研究了组织膜系统框架下的算法设计。本文延续类细胞膜系统求解CAP问题的研究,给出了在组织膜系统框架下求解该问题的算法,证明了组织膜系统的有效性。通过与前面的算法比较可以看出,组织膜系统只用两类规则即可实现对该问题的求解。系统的结构和规则简单,易于理解。此外,本文还给出了组织膜系统求解三匹配问题的算法。三匹配问题的算例可以与图论中的超图联系起来。以前的文献构造的求解一般图论问题的算法通常都既与顶点数目有关,又与边的数目有关。当边的数目改变时,通常需要重新构造系统。本文构造的算法只与超图的顶点数目有关,与超边的数目无关。因此,当边的数目改变时,只要点的数目不变,都无需重新构造系统。从这个意义上说,本文的构造技术优于之前的构造技术。
本文还特别研究了带二元输入的组织膜系统。以往的膜系统在求解NP困难问题时,通常都是采用一元编码的方式。因此,二进制编码的NP问题通常要先转化成一元编码的形式,再通过膜系统求解。但是,对于NP完全数值问题或牵扯到大量数值计算的NP问题,一元编码机制并不适当(较复杂)。通过膜系统解决这类问题时,二进制编码需要的计算资源更少。本文通过使用带二元输入的组织膜系统求解二次分配问题,证明了二进制编码的NP问题可以直接通过带二元输入的组织膜系统求解,而不需要转化为一元编码的形式。
最后,本文设计了两类膜计算优化算法,并分别用于求解带容量约束的交通路径问题和带时间窗的交通路径问题,将膜算法的应用扩展到路径规划领域。带容量约束的交通路径问题是大量路径问题的基本模型。本文设计的膜算法采用类细胞的膜结构,蚁群算法作为其子算法。特别地,将膜计算中“非确定的规则使用模式”引入到算法设计中,改善了蚁群算法的性能,有助于平衡收敛速度与搜索效果之间的矛盾。带时间窗的交通路径问题增加了时间调度这一环节,有更广泛的实际应用背景。为解决这一问题,本文设计了一种基于类组织膜系统的膜算法。该算法融合了“分布式结构”、“同向传输”等膜系统特性,扩展了搜索模型,避免了遗传算法容易过早收敛的问题。通过将仿真实验结果与文献中的当前最好结果作比较,证明了该算法的竞争力。其中两个测例的搜索结果比当前最好结果分别少一辆车。
Membrane computing is a new branch of nature computing. It provides a new com-puting mode inspired from the structure and functioning of living cells, tissues and organs. Until now, there has been more than ten years since the concept "membrane computing" was introduced. The computational theory, models, algorithms and applications in mem-brane computing have been developed rather fast. Membrane computing provides a new distributed parallel information processing method, helps the improvement of highly ef-ficient computing technology, and suggests new ideas to solve computational hard prob-lems. Cell-like membrane systems and tissue-like membrane systems are two basic models in membrane computing. Research on algorithms dealing with computational intractable problems using the models is the main content of this thesis.
Computational efficiency is one of the most important topics of natural computing. Many models of membrane computing can solve presumably intractable problems in poly-nomial time by using bio-inspired operations such as cell division, cell separation and cell creation. The strategy is trading space for time. There are many interesting directions in this area, for example, how to design algorithms to solve intractable problems (such as NP-complete problems and PSPACE-complete problems) in polynomial time; how to improve pre-existing algorithms; how to construct semi-uniform solutions or uniform solutions. In this work, solutions for common algorithmic problem (CAP), tripartite matching problem (TMP) and quadratic assignment problem (QAP) are proposed. However, there are not re-alistic implementations for those algorithms by electronic media or bio-media. Membrane algorithm is another feasible way to solve intractable problems. It combines membrane computing with approximate algorithms, and can be simulated by electronic computer. It obtains approximate solutions for computational hard problems. In this work, two mem-brane algorithms are designed respectively in the frameworks of cell-like membrane system and tissue-like membrane system. They can be applied to the area of vehicle routing. They are used to solve capacitated vehicle routing problem and vehicle routing problem with time windows, respectively. In this work, it is proved that the characters of membrane system, such as distributed parallel model, structure transformation and communication mechanism, can greatly improve the performance of traditional heuristic algorithms. The detailed con-tents of this dissertation are as follows:
P system with active membranes is one of the most important models of cell-like P systems. The rules directly involve the membranes where they act, also making evolve the membrane structure during the computation. The application of rules in early P system with active membrane can be controlled by "electrical charges"+,-,0. However, the electrical charges used in P systems with active membranes are not quite realistic from a biological point of view. Moreover, it wastes lots of resources from a computational point of view. We improve the algorithm for CAP proposed by Perez-Jimenez et al., and solve this problem in the framework of P systems with polarizationless active membranes. Both semi-uniform and uniform solutions are presented. Especially, the uniform solution for CAP by a family of recognizer P systems with polarizationless active membranes working in the minimally parallel mode is the first algorithm for NP-complete problems by a family of recognizer P systems with polarizationless active membranes working in the minimally parallel mode.
The type of rules in tissue P system is simpler than in P system with active mem-branes. There are only two kinds of rules (communication rules and division rules) in tissue P system, but they are enough to solve NP-complete problems. That can be proved by con-structing a uniform solution to CAP in the framework of tissue p system. Moreover, the algorithm for TMP is also proposed. For an instance of TMP, we can associate a hyper-graph. In the hypergraph version of TMP, it is easy to see that the family of tissue P systems with cell division is independent of the number of hyperedges. For instances with different number of edges, it need not reconstruct systems. But in references when design algorithm for another problems in graph theory, the systems depend on both the number of vertices and the number of edges. When the number of edges are changed, a family of different P systems have to be constructed. The technique of constructing P systems given in this work is better.
When dealing with NP-complete problems by P systems, all instances are usually en-coded in unary notations. However, unary notations are not a suitable (or easy) encoding mechanism for NP-complete numerical problems, because there are a lot of numerical cal-culations. Binary encoding needs less computational resources than unary encoding in the framework of P systems. In this work, the solution for QAP is proposed by a recognizer tissue P system with binary input. It proves that problems encoded in binary notions can directly solved by tissue P systems with binary input without transforming to unary notions.
Finally, two kinds of membrane algorithms are designed and used to solve the capacitated vehicle routing problem and the vehicle routing problem with time windows respectively. They are applications to the area of routing schedule. The capacitated vehicle routing problem is the basic model of many routing problems. Membrane algorithm designed for this problem has a cell-like structure. Membrane system is considered as a non-deterministic distributed parallel framework, and two kinds of ant colony optimization are considered as sub-algorithms of elementary membranes. Especially, with the purpose of keeping balance between convergence rate and population diversity, it inherits the concept "non-deterministic" from membrane computing. Vehicle routing problem with time windows includes a scheduling part, that is, a time component, and has more realistic applications. In this work, a new kind of membrane algorithm based on tissue-like P system is also proposed. It inherits the concepts "distributed structure", "symport" from membrane computing. These characters of P system can decrease computation time, extend search model and avoid premature convergence of genetic algorithm. Our algorithm is tested on Solomon's 56 benchmark test problems of vehicle routing problem with time windows and compared with other heuristics in the previous literatures. The results show that the proposed algorithm is competitive in terms of the quality of the solutions. The complete solutions of two instances are listed, and each of them comprises one vehicle less than the previous best solutions.
引文
[1]Turing A. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society,1937,2(1):230.
[2]Turing A. Computability and A-dcfinability. Journal of Symbolic Logic,1937,2(4):153-163.
[3]李国杰.非传统的高性能计算技术.世界科技研究与发展,1998,20(003)：14-16.
[4]Bennett C. On constructing a molecular computer. IBM Journal of Research and Development, 1973,17:525-532.
[5]Conrad M. On design principles for a molecular computer. Communications of the ACM,1985, 28(5):464-480.
[6]Head T. Formal language theory and DNA:an analysis of the generative capacity of specific re-combinant behaviors. Bulletin of Mathematical Biology,1987,49(6):737-759.
[7]Adleman L. Molecular computation of solutions to combinatorial problems. Nature,1994,369:40.
[8]Alhazov A, Rogozhin Yu, Verlan S. Minimal Cooperation in Symport/Antiport Tissue P Systems. International Journal of Foundations of Computer Science,2007,18(1):163-180.
[9]Paun A, Paun G. The Power of Communication:P systems with Symport/Antiport. New Generation Computing,2002,20(3):295-305.
[10]Paun G. Computing with membranes. Journal of Computer and System Sciences,2000,61(1):108-143.
[11]Paun G. Membrane Computing. An Introduction. Berlin:Springer-Verlag,2002.
[12]Ciobanu G, Paun G, Perez-Jimenez M, et al. Applications of membrane computing. Springer,2006.
[13]Alhazov A. Communication in Membrane Systems with Symbol Objects:[PhD Dissertation]. Sevilla, Spain:University of Sevilla, Spain,2006.
[14]Popa B. Membrane Systems with Limited Parallelism:[PhD Dissertation]. Ruston, USA:College of Engineering and Science, Louisiana Tech University, Ruston, USA,2006.
[15]Sburlan D. Promoting and Inhibiting Contexts in Membrane Computing:[PhD Dissertation]. Sevilla, Spain:University of Sevilla,2006.
[16]黄亮Research on Membrane Computing Optimization Methods:[PhD Dissertation]杭州：浙江大学,2007.
[17]张兴义.脉冲神经膜系统的计算能力研究：[PhD Dissertation].武汉：华中科技大学,2009.
[18]江赟.网状结构膜系统的计算能力研究：[PhD Dissertation].武汉：华中科技大学,2011.
[19]曾湘祥.脉冲神经膜系统的计算性能研究：[PhD Dissertation].武汉：华中科技大学,2011.
[20]Paun G, Rozenberg G, Salomaa A. The Oxford Handbook of Membrane Computing. Oxford University Press,2010.
[21]张葛祥,潘林强.自然计算的新分支一膜计算.计算机学报,2010,33(2)：208-214.
[22]FREUND R, Paun A. Membrane systems with symport/antiport rules:Universality results. Lecture notes in computer science,2003, pages 270-287.
[23]Ionescu M, Paun G, Yokomori T. Spiking neural P systems. Fundamenta Informaticae,2006, 71(2-3):279-308.
[24]Suzuki Y, Ogishima S, Tanaka H. Modelling the p53 signaling network by using P systems. Pro-ceedings of the Brainstorming Week on Membrane Computing, Report No.26,2003,449-^54.
[25]Manca V, Bianco L, Fontana F. Evolutions and oscillations of P systems:theoretical considerations and applications to biochemical phenomena. LNCS,2005,3365:63-84.
[26]Manca V, Bianco L. Biological networks in metabolic P systems. BioSystems,2008,91(3):489-498.
[27]Romero-Campero F, Perez-Jimenez M. Modelling gene expression control using P systems:The lac operon, a case study. BioSystems,2008,91(3):438-457.
[28]Perez-Jimenez M, Romero-Campero F. A study of the robustness of the EGFR signalling cascade using continuous membrane systems. Lecture Notes in Computer Science,2005,3561:268-278.
[29]Nagy B, Szegedi L. Membrane Computing and Graphical Operating Systems. Journal of Universal Computer Science,2006,12(9):1312-1331.
[30]Ceterchi R, Gramatovici R, Jonoska N, et al. Tissue-like P systems with active membranes for picture generation. Fundamenta Informaticae,2003,56(4):311-328.
[31]Enguix G. Unstable P Systems:Applications to Linguistics. Lecture Notes in Computer Science, 2005,3365:190-209.
[32]Belenguix G, Gramatovici R. Parsing with active P automata. Lecture notes in computer science, 2004, pages 31-42.
[33]Paun G, Paun R. Membrane computing as a framework for modeling economic processes. in: Proceedings of Proceedings of the Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing,2006,8-11.
[34]Paun G, Paun R. Membrane computing and economics:Numerical P systems. Fundamenta Infor-maticae,2006,73(1):213-227.
[35]Mauri G, Cazzaniga P. Seasonal variance in P system models for metapopulations. Progress in Natural Science,17(4):392-400.
[36]Besozzi D, Cazzaniga P, Pescini D, et al. Modelling metapopulations with stochastic membrane systems. Biosystems,2008,91(3):499-514.
[37]Colomer M A, Margalida A, Sanuy D, et al. A bio-inspired computing model as a new tool for modeling ecosystems:The avian scavengers as a case study.2011,222:33-47.
[38]Martin-Vide C, Paun A, Paun G. On the power of P systems with symport rules. Journal of Universal Computer Science,2002,8(2):317-331.
[39]Paun G, Yu S. On synchronization in P systems. Fundamenta Informaticae,1999,38(4):397-410.
[40]Martin-Vide C, Pun G, Rozenberg G. Membrane systems with carriers. Theoretical Computer Science,2002,270(1-2):779-796.
[41]Dassow J, Paun G. On the power of membrane computing. Journal of Universal Computer Science, 1999,5(2):33-49.
[42]Alhazov A, Pan L, Paun G. Trading polarizations for labels in P systems with active membranes. Acta Informatica,2004,41 (2):111-144.
[43]Alhazov A, Pan L. Polarizationless P system with active membranes. Grammar,2004,7(1):141-159.
[44]Martin-Vide C, Paun G, Pazos J. Tissue P systems. Theoretical Computer Science,2003, 296(2):295-326.
[45]Cavaliere M, Genova D. P systems with symport/antiport of rules. Journal of Universal Computer Science,2004,10(5):540-558.
[46]Freund R, Paun G, Perez-Jimenez M. Tissue P systems with channel states. Theoretical Computer Science,2005,330(1):101-116.
[47]Bernardini F, Gheorghe M. Population P systems. Journal of Universal Computer Science,2004, 10(5):509-539.
[48]Pan L, Martin Vide C. Solving multidimensional 0-1 knapsack problem by P systems with input and active membranes. Journal of Parallel and Distributed Computing,2005,65:1578-1584.
[49]Diaz-Pernil D, Gutierrez-Naranjo M, Perez-Jimenez M, et al. A linear-time tissue P system based solution for the 3-coloring problem. Electronic Notes in Theoretical Computer Science,2007, 171:81-93.
[50]Perez-Jimenez M, Romero Campero F. Attacking the common algorithmic problem by recognizer P systems. LNCS,2005,3354:304-315.
[51]Petreska B, Teuscher C. A reconfigurable hardware membrane system. Lecture notes in computer science,2004, pages 269-285.
[52]Cecilia J, Garcia J, Guerrero G, et al. Simulating a P system based efficient solution to SAT by using GPUs. Journal of Logic and Algebraic Programming,2010,79(6):317-325.
[53]Canales J, Carrasco J, Hernandez G, et al. Simulation of P Systems with Active Membranes on CUDA. Briefings in Bioinformatics,2010, 11(3):313-322.
[54]Nishida T Y. An application of P-systems:a new algorithm for NP-complete optimization problems. Proceedings of 8th World Multi-Conference on Systems, Cybernetics and Informatics (N. Callaos et al.,eds.),2004,5:109-112.
[55]Nishida T Y. Membrane algorithm with brownian subalgorithm and genetic subalgorithm. Interna-tional Journal of Foundations of Computer Science,2007,18:1353-1360.
[56]Nishida T Y, Shiotani T, Takahashi Y. Membrane algorithm solving job-shop scheduling problems. Pre-Proceedings of WMC9, Edinburgh, UK,2008,363-370.
[57]Nishida T Y. Membrane algorithms. LNCS,2006,3850:55-66.
[58]Huang L, Wang N. An optimization algorithm inspired by membrane computing. LNCS,2006, 4222:49-52.
[59]Zhang G, Gheorghe M, Wu C. A quantum-inspired evolutionary algorithm based on P systems for knapsack problem. Fundamanta Informaticae,2008,87(1):93-116.
[60]Zhang G, Liu C, Gheorghe M, et al. Solving satisfiability problems with membrane algorithms. Proceedings of 2009 Fourth international conference on BIC-TA,2009,29-36.
[61]Chomsky N. Three models for the description of language. IRE Transactions on Information Theory,1956,2(3):113-124.
[62]Chomsky N. On certain formal properties of grammars. Information and Control,1959,2(2):137-167.
[63]Linz P. An introduction to formal languages and automata.北京：机械工业出版社,2004.
[64]Rozenberg G, Salomaa A. Handbook of formal languages:Beyond words. Springer Verlag,1997.
[65]冯志伟,孙乐.自然语言处理综论.北京：电子工业出版社,2005.
[66]蒋宗礼,姜守旭.形式语言与自动机理论.北京：清华大学出版社,2003.
[67]Freund R, Paun G, Perez-Jimenez M. Polarizationless P systems with active membranes working in the minimally parallel mode. LNCS,2007,4618:62-76.
[68]Perez-Jimenez M, Romero-Jimenez A, Sancho-Caparrini F. A polynomial complexity class in P systems using membrane division. Journal of Automata, Languages and Combinatorics,2006, 11(4):423-434.
[69]Ciobanu G, Pan L, Paun G, et al. P systems with minimal parallelism. Theoretical Computer Science,2007,378:117-130.
[70]Gutierrez-Naranjo M, Perez-Jimenez M, Riscos-Nunez A, et al. On the power of dissolution in P systems with active membranes. Lecture Notes in Computer Science,2006,3850:224-240.
[71]Leporati A, Zandron C, Gutierrez-naranjo M A. P systems with input in binary form. International Journal of Foundations of Computer Science,2006,17(1):127-146.
[72]Anstreicher K M, Brixius N W, Goux J P, et al. Solving large quadratic assignment problems on computational grids. Mathematical Programming,2002,91(3):563-588.
[73]Krarup J, Pruzan P M. Computer-aided layout design. Mathematical Programming Study,1978, 9:75-84.
[74]Hubert L. Assignment methods in combinatorial data analysis. New York:Marcel Dekker,1987.
[75]Brusco M J, Stahl S. Using quadratic assignment methods to generate initial permutations for least-squares unidimensional scaling of symmetric proximity matrices. Journal of Classification,2000, 17(2):197-223.
[76]Forsberg J H, Delaney R M, Zhao Q, et al. Analyzing lanthanide-included shifts in the NMR spec-tra of lanthanide (Ⅲ) complexes derived from 1,4,7,10-tetrakis (N, N-diethylacetamido)-1,4,7,10-tetraazacyclododecane. Inorganic Chemistry,1994,34:3705-3715.
[77]Dantzig G, Ramser J H. The truck dispatching problem. Management Science,1959,6:80-91.
[78]Lawrence B, Bruce G. Classification of vehicle routing and scheduling. Networks,1981,11:97-108.
[79]Tavakkoli-Moghaddam R, Safaei N, Gholipour Y. A hybrid simulated annealing for the capacitated vehicle routing problems with the independent tour length. Applied Mathematics and Computation, 2006,176:445-454.
[80]Baker B M, Ayechew M A. A genetic algorithm for the vehicle routing problem. Computer and Operational Research,2003,7:301-317.
[81]Osman I H, Abo-Sinna M A, Mouse A A. An effective genetic algorithm approach to multiobjective routing problems. Applied Mathematics and Computation,2005,162:769-781.
[82]Gendreau M, Laporte G, Musaraganyi C, et al. A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Computers and Operations Research,1999,41:421-451.
[83]Bulleneimer B, Hartl R F, Strauss C. An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research,1999,89:319-328.
[84]Yu B, Yang Z, Yao B. An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research,2009,196:171-176.
[85]Ai T J, Kachitvichyanukul V. A particle swarm optimization for the capacitated vehicle routing problem. International Journal of Logistics and SCM Systems,2007,2:50-55.
[86]Chen A L, Yang G K, Wu Z M. Hybrid discrete particle swarm optimization algorithm for capaci-tated vehicle routing problem. Journal of Zhejiang University Science A,2006,7:607-614.
[87]Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies. Proceedings of the First European Conference on Artificial Life,1991,134-142.
[88]Dorigo M, Di Caro G, Gambardella L M. Ant algorithms for discrete optimization. Artificial Life, 1999,5:137-172.
[89]Tarasewich P, McMullen P R. Swarm intelligence:power in numbers. Communications of the ACM,2002,45(8):62-67.
[90]Stutzle T, Hoos H. MAX-MIN ant system and local search for the traveling salesman problem. International Conference on Evolutionary Computation,1997,308-313.
[91]Stutzle T, Hoos H. MAX-MIN ant system. Future Generation Computer Systems,2000,16:889-914.
[92]Lin S, Kernighan B W. An effective heuristic algorithm for the TSP. Opereration Research,1973, 21:498-516.
[93]Zachariadis E, Tarantilis C, Kiranoudis C. A guided tabu search for the vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research,2009,195:729-743.
[94]Gendreau M, Iori M, Laporte G, et al. A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks,2008,1:4-18.
[95]Solomon M M, Baker E K, Schaffer J R. Vehicle routing problems with time window constraints: efficient implementations of solution improvement procedures. In Vehicle Routing:Methods and Studies, ed. Golden B L and Assad A A, North-Holland, Amsterdam,1988,85-105.
[96]Chiang W C, Russell R A. A reactive tabu search metaheuristic for the vehicle routing problem with time windows. INFORMS Journal on Computing,1997,9:417-430.
[97]Cordeau J F, Laporte G, Mercier A. A unified tabu search heuistic for vehicle routing problem with time windows. Journal of the Operational Research Society,2001,52:928-936.
[98]Garcia B L, Potvin J Y, Rousseau J M. A parallel implementation of the tabu search heuristic for vehicle routing problem with time window constrains. Computer Operation Research,1994, 21:1025-1033.
[99]Lau H C, Sim M, Teo K M. Vehicle routing problem with time windows and a limited number of vehicles. Europeen Journal of Operation Research,2003,148:559-568.
[100]Taillard E, Badaru P, Gendreau M, et al. A tabu search heuristic for the vehicle touting problem with soft time windows. Transportation Science,1997,31(2):170-186.
[101]Berger J, Barkaoui M, Braysy O. A route-directed hybrid genetic approach for the vehicle routing problem with time windows. Information Systems and Operations. Research,2003,41:179-194.
[102]Homberger J, Gehring H. Two evolutionary metaheuristic for the vehicle routing problem with time windows. Information Systems and Operational Research,1999,37:297-318.
[103]Homberger J, Gehring H. A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. European Journal of Operation Research,2005,162:220-238.
[104]Thangiah S. Vehicle routing with time windows using genetic algorithms. In:Application Hand-book of Genetic Algorithms:New Frontiers, Chambers L (Ed.) CRC Press, Boca Raton, ISBN: 0849325196,253-277.
[105]Gabardella L M, Taillard E., Agazzi G. MACS-VRPTW:A multiple ant colony system for ve-hicle routing problems with time windows. D. Corne, M. Dorigo, F. Glover eds. New Ideas in Optimization. McGraw-Hill, London, UK,1999,63-76.
[106]Chiang W C, Russell R A. Simulated annealing metaheuristics for the vehicle routing problem with time windows. Annals of Operations Research,1996,63:3-27.
[107]Bent R, Van Hentenryck P. A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science,2004,38(4):515-530.
[108]Tan K C, Lee L H, Ou K. Artificial intelligence heuristics in solving vehicle routing problems with time window constrains. Engineering Applications of Artificial Intelligence,2001,14:825-837.
[109]Gen M, Cheng R. Genetic Algorithms and Engineering Design. Wiley, New York,1997.
[110]Rochat Y, Taillard E. Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics,1995,1:147-167.
[111]Rousseau L M, Gendreau M, Pesant G. Using constraint-based operators with variable neigh-borhood search to solve the vehicle routing problem with time windows. Proceedings of the 1st Workshop on Ingegretion of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Feb.1999, University of Ferrara, Italy.
[112]Gehring H, Homberger J. Parallelization of a two-phase metaheauristic for routing problems with time windows. Journal of Heuristics,2002,8(3):251-276.
[113]Berger J, Barkaoui M. A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Computation Operation Research,2004,31:2037-2053.