臺灣博碩士論文加值系統

多旅行銷售員問題(Multiple Traveling Salesman Problem, mTSP) 為一組合最佳化問題，它衍生自著名的旅行銷售員問題（Traveling Salesman Problem, TSP）；mTSP不僅具備學術研究價值，其應用亦相當廣泛，例如車輛路徑規劃(Vehicle Routing)，校車路徑規劃(School Bus Routing)，印刷排程(Printing Press Scheduling)，船員排程(Crew Scheduling)等路徑規劃與任務排程問題，皆可轉換成mTSP 求解；另，mTSP屬NP-Hard，值得對該問題進行不同求解策略的研究與探討。
本研究提出任務導向蟻隊優化演算法來求解mTSP，參與解題之螞蟻將進行任務編組，以達成所賦予之優化任務。經過任務編組後的蟻隊，其成員在出發前均被指派了不同的任務方向(即，各螞蟻有不同的重點搜尋方向)。蟻隊中的各螞蟻除企圖完成個自任務外，並以Max-Min 的方式通力合作以求取低總成本與勞務均衡(Min-Max)之優化解。本蟻隊優化演算法包含四個主要元素：路徑費洛蒙(pathpheromone)，任務費洛蒙(mission pheromone)，貪婪因子(greedy factor)與強化弱者行動準則(Max-Min firing rule)。實驗結果顯示本研究提出來的方法除具有創新性與建設性外，解品質與其它演算法比較亦毫不遜色。

The multiple traveling salesman problem (mTSP) is a combinatorial optimization problem and is an extension of the famous Traveling Salesman Problem (TSP). Not only does the mTSP possess academic research value, but its application is extensive. For example, the vehicle routing problem (VRP) and operations scheduling can all be reduced to mTSP solutions. The mTSP is an NP-hard problem, and multifaceted discussions of its solutions are worthwhile.
This study assigned ants to teams with mission-oriented approaches to enhance ant colony optimization algorithms. Missions were appointed to ant teams before they departed (each ant had a different focal search direction). In addition to attempting to complete its own mission, each ant used the Max-Min strategy to work together to optimize the solution.
The goal of the appointing missions is to reduce the total distance,whereas the goal of using the max–min search method for paths was to achieve Min-Max, or the goal of labor balance. During the solving process, each ant will refer to the pheromone concentration on the paths and the mission tips as their action guidelines. After each round, the mission configuration will be changed in accordance with the state of solution obtained from each mission-coordinated team and the pheromone concentration on the path will be reconfigured. Four main elements were involved in the search process of the ant teams: mission pheromone, path pheromone, greedy factor, and Max-Min ant firing scheme. The experimental results revealed this novel approach to be innovative and effective.

TABLE OF CONTENTS
ACKNOWLEDGEMENTS i
ENGLISH ABSTRACT ii
CHINESE ABSTRACT iii
TABLE OF CONTENTS iv
LIST OF FIGURES vii
LIST OF TABLES ix
1 Introduction 1
1.1 Overview 1
1.2 Thesis Organization 4
2 Related Researches to Solving
Multiple Traveling Salesman Problems 6
2.1 Overview 6
2.2 Definition of mTSP 7
2.3 NP-Hardness 10
2.4 Exact algorithms to solve mTSP 11
2.4.1 Problem Reduction— mTSP to TSP 11
2.4.2 Brute force method 11
2.4.3 Local/Global Search Algorithm —- Generalized k-OPT 12
2.4.4 Integer Linear Programming and Cutting-Plane Algorithm 13
2.4.5 Dynamic Programming and Held-Karp algorithm 13
2.4.6 Branch-and-Bound Algorithm 13
2.5 Genetic Algorithm— (GA) 14
2.5.1 GA related researches to solving mTSP 15
2.6 Simulated Annealing— (SA) 16
2.7 Neural-Network— (NN’s) 18
2.7.1 Hopfield Neural-network Model 18
2.7.2 Competitive Neural-Network Model 19
2.8 Ant Colony Optimization Algorithm 19
2.8.1 ACO related researches to solving mTSP 23
2.8.2 Exploration and exploitation 25
2.8.3 Pheromone update 25
2.9 Conclusions 26
3 Mission-Oriented Ant-Team ACO 27
3.1 Overview 27
3.2 The Min-Max Objective 28
3.3 Intra-entanglement vsInter-entanglement 29
3.4 MOAT-ACO 30
3.4.1 Mission-Oriented Ant Team and Mission Pheromone 30
3.4.2 Exploration and Exploitation of MOAT-ACO 32
3.4.3 On Mission Pheromone— Initialization, Update and Reference 33
3.4.4 Max-Min Firing Rule 34
3.4.5 On Path Pheromone 35
3.5 MOAT-ACO Story 36
3.6 Conclusions 38
4 Experimental Results 39
4.1 Overview 39
4.2 MOAT-ACO Executive 39
4.3 The Role of Mission Pheromone on Min-Max Objective 41
4.4 Comparisons on One-Depot mTSP 42
4.5 MOTA-ACO for Multi-Depot mTSP 44
4.6 Summary 45
5 Conclusions and Future Work 47
5.1 Conclusion 47
5.2 Future Work 48
REFERENCES 49

[1] Samerkae Somhom, Abdolhamid Modares, and Takao Enkawa. Competitionbased neural network for the multiple travelling salesmen problem with minmax objective. Computers and Operations Research, 26(4):395–407, 1999.
[2] Utkarsh Jaiswal and Shweta Aggarwal. Ant colony optimization. International Journal of Scientific and Engineering Research, 2:1–7, 2011.
[3] Tolga Bektas. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34(3):209–219, 2006.
[4] Honglu Zhou, Mingli Song, and Witold Pedrycz. A comparative study of improved ga and pso in solving multiple traveling salesmen problem. Applied Soft Computing, 64:564–580, 2018.
[5] Eka N. Kencana, Ida Harini, and K. Mayuliana. The performance of ant system in solving multi traveling salesmen problem. Procedia Computer Science, 124:46 – 52, 2017. 4th Information Systems International Conference 2017, ISICO 2017, 6-8 November 2017, Bali, Indonesia.
[6] Julio Brito, F Javier Martínez, JA Moreno, and José L Verdegay. An aco hybrid metaheuristic for close–open vehicle routing problems with time windows and fuzzy constraints. Applied Soft Computing, 32:154–163, 2015.
[7] K.M. Dhanya and S.Kanmani. Dynamic vehicle routing problem: Solution by ant colony optimization with hybrid immigrant schemes. International Journal of Intelligent Systems and Applications, 9(7):52–60, 2017.
[8] Shan-Huen Huang, Ying-Hua Huang, Carola A Blazquez, and Germán Paredes-Belmar. Application of the ant colony optimization in the resolution of the bridge inspection routing problem. Applied Soft Computing, 65:443–461, 2018.
[9] Lixin Tang, Jiyin Liu, Aiying Rong, and Zihou Yang. A multiple traveling salesman problem model for hot rolling scheduling in shanghai baoshan iron and steel complex. European Journal of Operational Research, 124:267–282, 2000.
[10] Douglas Moura Miranda, Ricardo S. de Camargo, Samuel V. Conceição, Marcelo F. Porto, and Nilson T.R. Nunes. A multi-loading school bus routing problem. Expert Systems with Applications, 101:228 – 242, 2018.
[11] Samuel Gorenstein. Printing press scheduling for multi-edition periodicals. Management Science, 16(6):B–373, 1970.
[12] Arthur E Carter and Cliff T Ragsdale. Scheduling pre-printed newspaper advertising inserts using genetic algorithms. Omega, 30(6):415–421, 2002.
[13] Manuel López-Ibáñez and Christian Blum. Beam-aco for the travelling salesman problem with time windows. Computers and Operations Research, 37(9):1570–1583, 2010.
[14] Marco Dorigo. Optimization, Learning and Natural Algorithms. PhD thesis, Politecnico di Milano, Italy, 1992.
[15] Marco Dorigo, Vittorio Maniezzo, and Alberto Colorni. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1):29–41, Feb 1996.
[16] Li-Chih Lu and Tai-Wen Yue. Mission-oriented ant-team aco for min–max mtsp. Applied Soft Computing, 76:436–444, 2019.
[17] Tolga Bektas. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34(3):209 – 219, 2006.
[18] Jean-Yves Potvin, Guy Lapalme, and Jean-Marc Rousseau. A generalized kopt exchange procedure for the mtsp. INFOR: Information Systems and Operational Research, 27(4):474–481, 1989.
[19] Imdat Kara and Tolga Bektas. Integer linear programming formulations of multiple salesman problems and its variations. European Journal of Operational Research, 174(3):1449 – 1458, 2006.
[20] Bernhard Fleischmann. A cutting plane procedure for the travelling salesman problem on road networks. European Journal of Operational Research, 21(3):307 – 317, 1985.
[21] Richard Bellman. Dynamic programming treatment of the travelling salesman problem. J. ACM, 9(1):61–63, January 1962.
[22] Michael Held and RichardMKarp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1):196–210, 1962.
[23] Keld Helbig Hansen and Jakob Krarup. Improvements of the held-karp algorithm for the symmetric traveling salesman problem. Mathematical Programming, 7:87–96, 12 1974.
[24] Ailsa H Land and Alison G Doig. An automatic method for solving discrete programming problems. 50 Years of Integer Programming 1958-2008, pages 105–132, 2010.
[25] Ahmad Husban. An exact solution method for the mtsp. Journal of the Operational Research Society, 40:461–469, 05 1989.
[26] Shakila Saad, Wan Nurhadani Wan Jaafar, and Siti Jasmida Jamil. Solving standard traveling salesman problem and multiple traveling salesman problem by using branch-and-bound. AIP Conference Proceedings, 1522(1):1406–1411, 2013.
[27] M. Sedighpour, M. Yousefikhoshbakht, and N. Mahmoodi Darani. An effective genetic algorithm for solving the multiple traveling salesman problem. Journal of Optimization in Industrial Engineering (JOIE), 4(8):73–79, 2011.
[28] Fanggeng Zhao, Jinyan Dong, Sujian Li, and Xirui Yang. An improved genetic algorithm for the multiple traveling salesman problem. In Control and Decision Conference, 2008. CCDC 2008. Chinese, pages 1935–1939. IEEE, 2008.
[29] Shuai Yuan, Bradley Skinner, Shoudong Huang, and Dikai Liu. A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms. European Journal of Operational Research, 228(1):72–82, 2013.
[30] Zhanqing Lu, Kai Zhang, Juanjuan He, and Yunyun Niu. Applying k-means clustering and genetic algorithm for solving mtsp. In Bio-Inspired Computing-Theories and Applications, pages 278–284. Springer, 2016.
[31] Majd Latah. Solving multiple tsp problem by k-means and crossover based modified aco algorithm. IJERT, 5(2):430–4, 2016.
[32] Mohammad Taher Shirafkan, H Seidgar, J Rezaian-Zeidi, and N Javadian. Using a hybrid simulated annealing and genetic algorithms for non fixed destination multi-depot multiple traveling sales men problem with time window and waiting penalty. The Journal of Mathematics and Computer Science, 4(3):428–435, 2012.
[33] Mingji Xu, Sheng Li, and Jian Guo. Optimization of multiple traveling salesman problem based on simulated annealing genetic algorithm. In MATEC Web of Conferences, volume 100, page 02025. EDP Sciences, 2017.
[34] Xiutang Geng, Zhihua Chen, Wei Yang, Deqian Shi, and Kai Zhao. Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Applied Soft Computing, 11(4):3680–3689, 2011.
[35] Yong Wang, De Tian, and Yuhua Li. An improved simulated annealing algorithm for traveling salesman problem. In Proceedings of the 2012 International Conference on Information Technology and Software Engineering, pages 525–532. Springer, 2013.
[36] Sapna and Mandeep Kaur. Particle swarm optimization to solve multiple traveling salesman problem. International Research Journal of Engineering and Technology, 4(7):1179–1184, 2017.
[37] Dimitris Bertsimas and John Tsitsiklis. Simulated annealing. Statistical science, PAMI-6(1):10–15, 1993.
[38] Stuart Geman and Donald Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Transactions on pattern analysis and machine intelligence, 8(6):721–741, 1984.
[39] John J Hopfield and DavidWTank. Computing with neural circuits: A model. Science, 233(4764):625–633, 1986.
[40] GVWilson and GS Pawley. On the stability of the travelling salesman problem algorithm of hopfield and tank. Biological Cybernetics, 58(1):63–70, 1988.
[41] MengShu Hou and DaiBo Liu. A novel method for solving the multiple traveling salesmen problem with multiple depots. Chinese science bulletin, 57(15):1886–1892, 2012.
[42] Bernard Angeniol, Gael De La Croix Vaubois, and Jean-Yves Le Texier. Selforganizing feature maps and the travelling salesman problem. Neural Networks, 1(4):289–293, 1988.
[43] Marco Dorigo, Mauro Birattari, and Thomas Stutzle. Ant colony optimization. IEEE Computational Intelligence Magazine, 1(4):28–39, Nov 2006.
[44] Marco Dorigo and Luca Maria Gambardella. Ant colonies for the travelling salesman problem. Biosystems, 43(2):73–81, 1997.
[45] Gajendra Singh Chandel Krishna H. Hingrajiya, Ravindra Kumar Gupta. An approach for solving multiple travelling salesman problem using ant colony optimization. Computer Engineering and Intelligent Systems, 6(2):13–17, 2015.
[46] Weimin Liu, Sujian Li, Fanggeng Zhao, and Aiyun Zheng. An ant colony optimization algorithm for the multiple traveling salesmen problem. Industrial Electronics and Applications, 2009. ICIEA 2009. 4th IEEE Conference on, pages 1533–1537, 2009.
[47] Mohammad Bagher Dowlatshahi, Vali Derhami, and Hossein Nezamabadipour. Ensemble of filter-based rankers to guide an epsilon-greedy swarm optimizer for high-dimensional feature subset selection. Information, 8:152, 2017.
[48] Ahamed Fayeez Tuani, Edward Keedwell, and Matthew Collett. H-aco: A heterogeneous ant colony optimisation approach with application to the travelling salesman problem. In International Conference on Artificial Evolution (Evolution Artificielle), pages 144–161. Springer, 2017.
[49] Frumen Olivas, Fevrier Valdez, and Oscar Castillo. Dynamic parameter adaptation in ant colony optimization using a fuzzy system for tsp problems. IFSAEUSFLAT, pages 765–770, 2015.
[50] Frumen Olivas, Fevrier Valdez, Oscar Castillo, Claudia I Gonzalez, Gabriela Martinez, and Patricia Melin. Ant colony optimization with dynamic parameter adaptation based on interval type-2 fuzzy logic systems. Applied Soft Computing, 53:74–87, 2017.
[51] S. Tseng, C. Tsai, M. Chiang, and C. Yang. A fast ant colony optimization for traveling salesman problem. In IEEE Congress on Evolutionary Computation, pages 1–6, July 2010.
[52] Chun-Wei Tsai, Shih-Pang Tseng, Chu-Sing Yang, and Ming-Chao Chiang. Preaco: A fast ant colony optimization for codebook generation. Applied Soft Computing, 13(6):3008–3020, 2013.
[53] Orhan Engin and Abdullah Guclu. A new hybrid ant colony optimization algorithm for solving the no-wait flow shop scheduling problems. Applied Soft Computing, 72:166 – 176, 2018.
[54] Qiang Zhang and Shengwu Xiong. Routing optimization of emergency grain distribution vehicles using the immune ant colony optimization algorithm. Applied Soft Computing, 71:917 – 925, 2018.
[55] Yuzhe Yan, Han-suk Sohn, and German Reyes. A modified ant system to achieve better balance between intensification and diversification for the traveling salesman problem. Applied Soft Computing, 60:256–267, 2017.
[56] Samrat Hore, Aditya Chatterjee, and Anup Dewanji. Improving variable neighborhood search to solve the traveling salesman problem. Applied Soft Computing, 68:83–91, 2018.
[57] Arthur E Carter and Cliff T Ragsdale. A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European journal of operational research, 175(1):246–257, 2006.
[58] Alok Singh and Anurag Singh Baghel. A new grouping genetic algorithm approach to the multiple traveling salesperson problem. Soft Computing, 13(1):95–101, 2009.
[59] Pandiri Venkatesh and Alok Singh. Two metaheuristic approaches for the multiple traveling salesperson problem. Applied Soft Computing, 26:74–89, 2015.
[60] Banu Soylu. A general variable neighborhood search heuristic for multiple traveling salesmen problem. Computers and Industrial Engineering, 90:390–401, 2015.