臺灣博碩士論文加值系統

路徑問題自提出以來，一直是網路優化問題中最基本的問題之一，由於其應用的廣泛性和經濟上的重大價值，一直受到國內外學者的廣泛關注。路徑的實際問題包括配送中心配送、公車路線制定、信件和報紙投遞、航空和鐵路時間表安排、工業廢品收集、旅遊行程規劃等。
路徑問題又可以分為旅行銷售員問題、車輛路徑問題、中國郵差問題及多個物流中心的車輛路徑問題等。其中最受眾多學者喜愛並致力討論的非車輛路徑問題莫屬。由於車輛路徑問題本身是一個 NP-hard 的問題，若再加上時間窗限制或是其他限制，更增加了問題的複雜度及搜尋範圍的廣度。
已有許多學者致力於探討該如何在一定的約束條件下，目的使客戶的需求得到滿足並達到路程最短、成本最小、耗費時間最少等目的。此類的問題的研究文獻眾多，也提出了相當多的求解策略與方式，但鮮少有提出利用人工免疫系統的方法。因此在本論文中，利用人工免疫系統的特性來解具有制條件的問題，除去限制條件的違反量並具有提早收斂的效果，找出有效率的結果之啟發式演算法。
可回溯式門檻接受法(Backtracking Adaptive Threshold Accepting, BATA)是由Tarantilis et al.於2001年提出，它是從門檻接受法演變而來的新型巨集啟發式解法。其主要差異在於門檻值變化並非單調遞減；當找不到可接受的交換時，可允許放鬆門檻值再重新搜尋。本論文首先以改良式的掃瞄法產生起始解，再以鄰域搜尋模組改進，其方法共包括1-0 exchange、1-1 exchange和2-Opt等數種，並且以巨網結構的方式建構路線，使其能同時考慮「路線內」與「路線間」的交換。同時，本論文設計了一個能夠擴大鄰域搜尋範圍機制，以提高搜尋績效，實驗的結果顯示本論文所提出的方法在結果與效能上皆優於其他的排程方法。

Routing problem has been one of the fundamental problems in the network optimization problems since it was proposed. Due to its wide application and significant economic value, it has been received extensive attention of researchers. The practical routing problems include depot centers and distribution, bus routes, letters and newspaper delivery, air and rail timetables, industrial waste collection, itinerary planning, etc.
Routing problem can be divided into Traveling Salesman Problem (TSP), Vehicle Routing Problem (VRP), Chinese Postman Problem (CPP) and Multiple Depots for Vehicle Routing Problem (MDVRP). A lot of researches have focused on the vehicle routing problem. The VRP is an NP-hard problem when VRP with the time window limits or other restrictions are added. The more breadth of the search, the more complexity of the problem.
There have been so many research results about how to meet the customers’ needs and achieve the shortest paths, minimum cost and time-consuming under certain constraints. The literatures of such problems have proposed a considerable number of strategies and methods, but rarely have related with artificial intelligent algorithms.
This study will propose an artificial intelligent algorithm based on the immune system to solve VRP with pickup and delivery. The concept is from the artificial immune systems and uses genotypic-based distances to move from the infeasible region to the feasible region of a problem. It has the effect of early convergence in order to efficiently find a solution for our method.
The backtracking adaptive threshold accepting is proposed by Tarantilis et al. in 2001. It is from the threshold according to the new type of Meta-heuristics. Its major difference in threshold value of the change is not monotonic decreasing. When it can not find an acceptable values, it will allow relaxing threshold value. In this dissertation, we utilize a imporved sweep method to generate an initial solution first, and then improve neighbor domain Search module. The methods including 1-0 Exchange, 1-1 Exchange and 2-Opt, etc. Meanwhile, in this dissertation, we design an expand neighborhood search mechanisms to improve the search performance. The experimental results show that the performance of the proposed method is superior to the others.

TABLE OF CONTENTS
Chapter 1 Introduction..........................................................................................4
1.1 Background ..............................................................................................4
1.2 Motivation.................................................................................................5
1.3 The Vehicle Routing Problem with Pick-up and Deliveries .................8
1.4 The Vehicle Routing Problem with Time Windows ............................10
1.5 Organization of the Dissertation .......................................................... 11
Chapter 2 Related Works ....................................................................................12
2.1 The Vehicle Routing Problem...............................................................13
2.1.1 The Problem ...................................................................................13
2.1.2 The Model .......................................................................................13
2.1.3 VRP in Real Life.............................................................................14
2.1.4 The Vehicle Routing Problem with Pick-up and Deliveries .......15
2.1.5 The Vehicle Routing Problem with Time Windows. .....………..15
2.2 The Artificial Immnue System..............................................................17
2.2.1 The Primary and Scendonary of Immune System......................19
2.2.2 B Cell Object...................................................................................20
2.2.3 Antibodies .......................................................................................22
2.2.4 Antigen ............................................................................................23
2.2.5 Antibody/Antigen Binding ............................................................24
2.2.6 B Cell Stimulation/Immune Network Influence..........................24
2.2.7 Clonal Selection..............................................................................26
2.2.8 Affinity Maturation........................................................................27
2.3 Backtracking adaptive threshold accepting (BATA)………………...28
2.3.1 BATA Algorithm……………………………………………….…28
2.3.2 2-Opt Move………………………………………………………..29
2.3.3 1-1 Exchange Move……………………………………………..29
2.3.4 1-0 Exchange Move…………………………………………….30
2.4 Summary…….................................................................................31
Chapter 3 Applied Arificial Immune System in VRPPD .................................32
3.1 Representing VRP with pickup and delivery ......................................32
3.1.1 Problem Definition...........................................................................32
3.1.2 Notations .........................................................................................33
3.2 Finding the initial solution ....................................................................36
3.3 The AIS in VRP with pickup and delivery...........................................39
Chapter 4 Applied Backtracking adaptive threshold accepting in VRPBTW50
4.1 Problem Definition.................................................................................51
4.2 Augmented Objective function and Penalty function ........................54
4.2.1 Augmented Objective function .......................................................54
4.2.2 Penalty function................................................................................55
4.3 Initial Solution........................................................................................56
4.4 Route Improvement and Relaxed BATA.............................................57
4.4.1 Route Improvement .........................................................................57
4.4.1.1 Intra-Route Exchange:2-OPT..............................................58
4.4.1.2 Inter-Route Exchange:1-0 Exchange and 1-1 Exchange ...58
4.4.1.3 1-0 Exchange..........................................................................58
4.4.1.4 1-1 Exchange........................................................................58
4.4.2 Relaxed BATA ..................................................................................60
Chapter 5 Experiments........................................................................................64
5.1 Experimental Results in VRPPD..........................................................65
5.2 Experimental Results in VRPBTW......................................................67
Chapter 6 Conclusion and Future Work............................................................72
References……………………………………………………………………….74
Publication List………………………………………………………………….79

References
[1]T. J. Ai and V. Kachitvichyanukul , “A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery.”, Computers & Operations Research, Vol.36, pp.1693–1702, 2009.
[2] F. Al-Anzi and A. Allahverdi, “An artificial immune system heuristic for two-stage multi-machine assembly scheduling problem to minimize total completion time”, Journal of Manufacturing Systems, 2013.
[3] M. Bailey, Z. Christoforidou and M. Lewis, “Evolution of immune systems: Specificity and autoreactivity”, Autoimmunity Reviews, Vol. 12, pp. 643-647, 2013.
[4] M. Basu, “Artificial immune system for combined heat and power economic dispatch”, International Journal of Electrical Power and Energy Systems, Vol. 43, pp.1-5, 2012.
[5]C. Berek and M. Ziegner, “The maturation of the immune response”, Immunology Today, Vol.14, No.8, pp.400–402, 1993.
[6]N. Bianchessi and G. Righini, “Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery”, Computers & Operations Research, Vol.34, pp.578–594, 2007.
[7]J. Bramel and D. Simchi-Levi, “Probabilistic Analyses and Practical Algorithms for the Vehicle Routing Problem with Time Windows”, Operations Research, Vol.44, pp.501–509, 1996.
[8]O. Braysy and M. Gendreau, “ Vehicle routing problem with time windows Part II Metaheuristics”, Transportation Science, Vol. 39, No. 1, pp.119–139, 2005.
[9]M. Burnet, “The Clone Selection Theory of Acquired Immunity”, Cambridge University Press, 1959.
[10] A. M. Campbell and M. Savelsbergh, “Efficient insertion heuristics for vehicle routing and scheduling problems”, Transportation Science, Vol.38(3), pp.369–378, 2004.
[11]A. M. Campbell and M. Savelsbergh, “Decision support for consumer direct grocery initiatives”, Transportation Science, Vol.39, pp.313–327, 2005.
[12] L. N. Castro and F. J. V. Zuben, “The clonal selection Algorithm with Engineering Applications”, Proceedings of GECCO, pp.36–37, 2000.
[13]W. Chiang and R. A.Russell, “Simulated annealing metaheuristics for the vehicle routing problem with time window”, Annals of Operations Research, Vol.63, pp.3-27, 1996.
[14] W. Chiang and R. A. Russell, “A reactive tabu search metaheuristic for the vehicle routing problem with time windows”, INFORMS Journal on Computing, Vol. 9 (4), pp. 417–430, 1997.
[15]W. Cook and J. L. Rich, “A Parallel Cutting-Plane Algorithm for the Vehicle Routing Problems with Time Windows”, Working Paper, Department of Computational and Applied Mathematics, Rice University, Houston, U.S.A, 1999.
[16] J. F. Cordeau, G. Laporte and A. Mercier, “A unified tabu search heuristic for vehicle routing problems with time windows”, Journal of Operational Research Society, Vol.52, pp.928–936, 2001.
[17]G. A. Croes, “A method for solving traveling salesman problems”, Operations Research, Vol. 5, pp.791–812, 1958.
[18] E. Cuevas, V. Osuna-Enciso, F. Wario, D. Zaldivar and M. Perez-Cisneros, “Automatic multiple circle detection based on artificial immune systems”, Expert System with Applications, Vol. 39, pp.713-722, 2012.
[19]G. B. Dantzig and J. H. Ramser, “The truck dispatching problem”, Management Science, Vol.6, pp.80–91, 1959.
[20]R. J. Deboer and A. S. Perelson, “How diverse should the immune system be?”, Proceedings of the Royal Society of London B, Vol.252, pp.171–175, 1991.
[21]L. N. DeCastro, F. J. V, Zuben and G. A. deDeus Jr., “The construction of a Boolean competitive network using ideas from immunology”, Neurocomputing, Vol.50C, pp.51–85, 2003.
[22]J. Dethloff, “Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up”, OR Spektrum, Vol.23, pp.79–96, 2001.
[23]G. Dueck and T. Scheuer, “Threshold accepting. A general purpose optimization algorithm appearing superior to simulated annealing”, J. Comput. Phys, Vol.90 (1), pp.161–175, 1990.
[24]W. Dullaert and O. Braysy, “Routing Relatively Few Customers per Route”, TOP 11, pp.325–336, 2003.
[25]I. Ellabib, O. A. Basir and P. Calamai, “An Experimental Study of a Simple Ant Colony System for the Vehicle Routing Problem with Time Windows”, ANTS, LNCS, Vol.2463, pp.53-64, 2002.
[26]M. L. Fisher, “Optimal solution of vehicle routing problems using minimum k-trees”, Operation Research, Vol.42, pp.626–642,1994.
[27] B. Fleischmann, “The vehicle routing problem with multiple use of the vehicles”, Working Paper, Fachbereich Wirtschaftswissenschaften, Universitat Hamburg, Germany, 1990.
[28]Y. Gajpal, P. L. Abad, “Multi-ant colony system (MACS) for a vehicle routing problem with backhauls”, European Journal of Operational Research, Vol.196, pp.102–117, 2009.
[29]B. L. Golden and A. A. Assad, “Perspectives on Vehicle Routing: Exciting New Developments”, Operations Research, Vol.34, pp.803–809, 1986.
[30]N. K. Jeme, “Towards a network theory of the immune system”, Ann. Immunol. (Inst. Pasteur), Vol. 125C, pp.373–389, 1974.
[31]T. B. Kepler and A. S. Perelson, “Somatic hypermutation in B cells: an optimal control treatment”, Journal of Theoretical Biology, Vol.164, pp.37–64, 1993.
[32] R. J. Kuo, M. C. Shieh, J. W. Zhang and K.Y. Chen, “The application of an artificial immune system-based back-propagation neural network with feature selection to an RFID positioning system”, Robotics and Computer-Integrated manufacturing, Vol. 29, pp. 431-438, 2013.
[33]G. Laporte, M. Ggendreau, J.-Y. Potvin and F. Semet, “Classical and modern heuristics for the vehicle routing problem”, Inter. Trans. Oper, Vol. 7, pp.285–300, 2000.
[34]J. Larsen, “Parallelization of the Vehicle Routing Problem with Time Windows”, Ph.D. thesis, Institute of Mathematical Modeling, Technical University of Denmark, Lyngby, Denmark, 1999.
[35] C. A. Laurenty, R.M. Palhares and W. M. Caminhas, “A novel Artificial Immune System for fault behavior detection”, Expert System with Applications, Vol. 38, pp.6957-6966, 2011.
[36] C. A. Laurentys, R.M. Palhares and W. M. Caminhas, “Design of an artificial immune system based on Danger Model for fault detection”, Expert System with Applications, Vol. 37, pp.5145-5152, 2010.
[37] F. B. Leao, R. A. F. Pereira and J. R. S. Mantovani, “Fault section estimation in electric power systems using an optimization immune algorithm”, Electric Power Systems Research, Vol. 80, pp. 1341-1352, 2010.
[38]S. Liu and C. Chung, “A heuristic method for the vehicle routing problem with backhauls and inventory”, Journal of Intelligent Manufacturing, Vol.20, pp.29–42, 2009.
[39]H. Min, “The multiple vehicle routing problem with simultaneous delivery and pick-up points”, Transportation Research A, Vol.23, pp.377–386, 1989.
[40]G. Nagy, S. Salhi, “Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries”, European Journal of Operational Research, Vol.162, pp.126–141, 2005.
[41]A. S. Perelson, “Immune network theory”, Immunological Review, Vol.110, pp.5–36, 1989.
[42]J. Y. Potvin and J. M. Rousseau, “A Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Windows”, European Journal of Operational Research, Vol.66, pp.331–340, 1993.
[43]S. Ropke and D. Pisinger, “A unified heuristic for a large class of vehicle routing problems with backhauls”, 2004.
[44]M. M. Solomon, “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints”, Operations Research, Vol.35, pp.254–265, 1987.
[45] E. D. Taillard, “A heuristic column generation method for the heterogeneous fleet VRP”, RAIRO Operation Research, Vol. 33, pp. 1–34, 1996.
[46] E. D. Taillard, G. Laporte and M. Gendreav, “Vehicle routing with multiple use of vehicles”, Journal of the Operational Research Society, Vol. 47, pp.1065-1070, 1996.
[47] C. D Tarantilis, C.T Kiranousdis and V.S Vassiliadis, “A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem”, European Journal Operation Research, Vol. 152, No.1, pp. 148–158, 2004.
[48] C. D Tarantilis, C.T Kiranousdis and V.S Vassiliadis, “A list based threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem”, Journal of the Operational Research Society, Vol. 54 (1), pp. 65–71, 2003.
[49]P. Toth and D. Vigo, “Models, reaxations and exact approaches for the capacitated Vehicle Routing Problem”, Discrete Applied Mathematic, Vol.9, pp. 487-512, 2002.
[50] S. Venkatesan, R. Baskaran, C. Chellappan, A. Vaish and P. Dhavachelvan, “Artificial immune system based mobile agent platform protection”, Computer Standards & Interfaces, Vol. 35, pp. 365-373, 2013.
[51]E. E. Zachariadis and C. T. Kiranoudis, “A strategy for reducing the computational complexity of local search-based methods for the vehicle routing problem”, Computers & Operations Research, Vol.37, pp.2089–2105, 2010.
[52]Q. Zhao, S. Wang, K-K Lai and G. Xia, “The vehicle routing problem with multiple use of vehicles”, Advanced Modeling and Optimization, Vol.4, No. 3, pp.21–40, 2002.