研究生: |
Carlos Eduardo Carrillo Mendez Carlos - Eduardo Carrillo Mendez |
---|---|
論文名稱: |
Team Orienteering Problem with Time Windows and Fuzzy Scores Team Orienteering Problem with Time Windows and Fuzzy Scores |
指導教授: |
喻奉天
Vincent F. Yu |
口試委員: |
郭人介
Ren-Jieh Kuo 楊亦東 I-Tung Yang |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2016 |
畢業學年度: | 104 |
語文別: | 英文 |
論文頁數: | 93 |
中文關鍵詞: | Team Orienteering Problem 、Time Window 、Fuzzy Score 、Genetic Algorithm 、Fuzzy Ranking |
外文關鍵詞: | Team Orienteering Problem, Time Window, Fuzzy Score, Genetic Algorithm, Fuzzy Ranking |
相關次數: | 點閱:228 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
Team Orienteering Problem with Time Windows (TOPTW) is an extension of the well-known Orienteering Problem (OP). In this study we introduces Team Orienteering Problem with Time Windows and Fuzzy Scores (TOPTWFS) which aims to maximize the total collected scores represented by normal triangular fuzzy numbers (TFNs) at the visiting points. For solving the proposed fuzzy model we developed a Genetic Algorithm (GA) where each phenotype is split into P sub-tours so as to define the maximum number of nodes that can be visited while the genotype is represented as a permutation of N elements. Consequently, the GA is coupled with 8 heuristics commonly used on routing problems for running away from local optima in order to improve the solution quality. Furthermore, the solution approach incorporates a new way to deal with Linear Programming Problems with Fuzzy Parameters in the Objective Function by using different defuzzification and fuzzy ranking methods to evaluate the phenotypes. Finally, by applying non-parametric test, the experimental results show how the performance of the algorithm change due to the evaluation of method selected allowing to compare its efficacy and effectiveness.
Team Orienteering Problem with Time Windows (TOPTW) is an extension of the well-known Orienteering Problem (OP). In this study we introduces Team Orienteering Problem with Time Windows and Fuzzy Scores (TOPTWFS) which aims to maximize the total collected scores represented by normal triangular fuzzy numbers (TFNs) at the visiting points. For solving the proposed fuzzy model we developed a Genetic Algorithm (GA) where each phenotype is split into P sub-tours so as to define the maximum number of nodes that can be visited while the genotype is represented as a permutation of N elements. Consequently, the GA is coupled with 8 heuristics commonly used on routing problems for running away from local optima in order to improve the solution quality. Furthermore, the solution approach incorporates a new way to deal with Linear Programming Problems with Fuzzy Parameters in the Objective Function by using different defuzzification and fuzzy ranking methods to evaluate the phenotypes. Finally, by applying non-parametric test, the experimental results show how the performance of the algorithm change due to the evaluation of method selected allowing to compare its efficacy and effectiveness.
Abbasbandy, S., & Asady, B. (2006). Ranking of fuzzy numbers by sign distance. Information Sciences, 176(16), 2405-2416.
Abbasbandy, S., & Hajjari, T. (2009). A new approach for ranking of trapezoidal fuzzy numbers. Computers & Mathematics with Applications, 57(3), 413-419.
Bahri, O., Amor, N. B., & El-Ghazali, T. (2014a). New Pareto approach for ranking triangular fuzzy numbers. Proceedings of the Information Processing and Management of Uncertainty in Knowledge-Based Systems (pp. 264-273).
Bahri, O., Ben Amor, N., & El-Ghazali, T. (2014b). Optimization algorithms for multi-objective problems with fuzzy data. Proceedings of the Computational Intelligence in Multi-Criteria Decision-Making (MCDM), 2014 IEEE Symposium on (pp. 194-201).
Buijs, R. (2015). Implementation of an iterated local search heuristic for the team orienteering problem with time windows.
Butt, S. E., & Cavalier, T. M. (1994). A heuristic for the multiple tour maximum collection problem. Computers & Operations Research, 21(1), 101-111.
Chao, I.-M., Golden, B. L., & Wasil, E. A. (1996a). A fast and effective heuristic for the orienteering problem. European Journal of Operational Research, 88(3), 475-489.
Chao, I.-M., Golden, B. L., & Wasil, E. A. (1996b). The team orienteering problem. European journal of operational research, 88(3), 464-474.
Chen, S.-H. (1985). Ranking fuzzy numbers with maximizing set and minimizing set. Fuzzy sets and Systems, 17(2), 113-129.
Cheng, C.-H. (1998). A new approach for ranking fuzzy numbers by distance method. Fuzzy sets and systems, 95(3), 307-317.
Choobineh, F., & Li, H. (1993). An index for ordering fuzzy numbers. Fuzzy sets and systems, 54(3), 287-294.
Chou, S.-Y., Dat, L. Q., & Yu, V. F. (2011). A revised method for ranking fuzzy numbers using maximizing set and minimizing set. Computers & Industrial Engineering, 61(4), 1342-1348.
Chu, T.-C., & Tsao, C.-T. (2002). Ranking fuzzy numbers with an area between the centroid point and original point. Computers & Mathematics with Applications, 43(1), 111-117.
Conover, W. J. (1980). Practical Nonparametric Statistics.
Cordeau, J.-F., Gendreau, M., & Laporte, G. (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30(2), 105-119.
Cura, T. (2014). An artificial bee colony algorithm approach for the team orienteering problem with time windows. Computers & Industrial Engineering, 74, 270-290.
Delling, D., Dibbelt, J., Pajor, T., Wagner, D., & Werneck, R. F. (2013). Computing multimodal journeys in practice Experimental Algorithms. (pp. 260-271): Springer.
Diamond, P., & Kloeden, P. (1990). Metric spaces of fuzzy sets. Fuzzy sets and systems, 35(2), 241-249.
Falkenauer, E., & Bouffouix, S. (1991). A genetic algorithm for job shop. Proceedings of the Robotics and Automation, 1991. Proceedings., 1991 IEEE International Conference on (pp. 824-829).
Gambardella, L. M., Taillard, É., & Agazzi, G. (1999). MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows.
Garcia-Cascales, M. S., & Lamata, M. T. (2007). A modification of the index of Liou and Wang for ranking fuzzy number. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 15(04), 411-424.
Gavalas, D., Konstantopoulos, C., Mastakas, K., Pantziou, G., & Tasoulas, Y. (2013). Cluster-based heuristics for the team orienteering problem with time windows Experimental Algorithms. (pp. 390-401): Springer.
Goldberg, D. E. (1989). Genetic algorithms in search optimization and machine learning (Vol. 412): Addison-wesley Reading Menlo Park.
Golden, B. L., Levy, L., & Vohra, R. (1987). The orienteering problem. Naval research logistics, 34(3), 307-318.
Golozari, F., Jafari, A., & Amiri, M. (2013). Application of a hybrid simulated annealing-mutation operator to solve fuzzy capacitated location-routing problem. The International Journal of Advanced Manufacturing Technology, 67(5-8), 1791-1807.
Guibadj, R. N., & Moukrim, A. (2013). Memetic Algorithm with an Efficient Split Procedure for the Team Orienteering Problem with Time Windows. Proceedings of the Artificial Evolution (pp. 183-194).
Gunawan, A., Lau, H. C., & Lu, K. (2015). SAILS: Hybrid Algorithm for the Team Orienteering Problem with Time Windows. Proceedings of the Proceedings of the 7th Multidisciplinary International Scheduling Conference (MISTA 2015).
Hellendoorn, H., & Thomas, C. (1993). Defuzzification in fuzzy controllers. Journal of Intelligent & Fuzzy Systems, 1(2), 109-123.
Hochberg, Y., & Tamhane, A. (1987). Multiple comparison procedures. Wiley series in probability and mathematical statistics (Applied probability and statistics) Show all parts in this sub series.
Holland, J. H. (1975). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence: U Michigan Press.
Hu, Q., & Lim, A. (2014). An iterative three-component heuristic for the team orienteering problem with time windows. European Journal of Operational Research, 232(2), 276-286.
Irnich, S. (2008). A unified modeling and solution framework for vehicle routing and local search-based metaheuristics. INFORMS Journal on Computing, 20(2), 270-287.
Jong, K. A. D. (1985). Genetic algorithms: A 10 Year Perspective. Proceedings of the Proceedings of the 1st International Conference on Genetic Algorithms (pp. 169-177).
Kabassi, K. (2009). Fuzzy Simple Additive Weighting for Evaluating a Personalised Geographical Information System New Directions in Intelligent Interactive Multimedia Systems and Services-2. (pp. 275-284): Springer.
Karabulut, K., & Tasgetiren, M. F. (2013). A discrete artificial bee colony algorithm for the team orienteering problem with time windows. Proceedings of the Computational Intelligence In Production And Logistics Systems (CIPLS), 2013 IEEE Workshop on (pp. 99-106).
Ke, L., Guo, H., & Zhang, Q. (2014). A cooperative approach between metaheuristic and branch-and-price for the team orienteering problem with time windows. Proceedings of the Evolutionary Computation (CEC), 2014 IEEE Congress on (pp. 1878-1882).
Klir, G., & Yuan, B. (1995). Fuzzy sets and fuzzy logic (Vol. 4): Prentice hall New Jersey.
Kołodziejczyk, W. (1986). Orlovsky's concept of decision-making with fuzzy preference relation-further results. Fuzzy Sets and Systems, 19(1), 11-20.
Kumar, A., Singh, P., Kaur, P., & Kaur, A. (2011). A new approach for ranking of L–R type generalized fuzzy numbers. Expert Systems with Applications, 38(9), 10906-10910.
Labadi, N., Melechovský, J., & Calvo, R. (2010). An effective hybrid evolutionary local search for orienteering and team orienteering problems with time windows. Parallel Problem Solving from Nature, PPSN XI, 219-228.
Labadie, N., Mansini, R., Melechovský, J., & Calvo, R. W. (2012). The team orienteering problem with time windows: An lp-based granular variable neighborhood search. European Journal of Operational Research, 220(1), 15-27.
Labadie, N., Melechovský, J., & Calvo, R. W. (2011). Hybridized evolutionary local search algorithm for the team orienteering problem with time windows. Journal of Heuristics, 17(6), 729-753.
Li, X. (2013). Multi-day and multi-stay travel planning using geo-tagged photos. Proceedings of the Proceedings of the Second ACM SIGSPATIAL International Workshop on Crowdsourced and Volunteered Geographic Information (pp. 1-8).
Lilliefors, H. W. (1967). On the Kolmogorov-Smirnov test for normality with mean and variance unknown. Journal of the American Statistical Association, 62(318), 399-402.
Lilliefors, H. W. (1969). On the Kolmogorov-Smirnov test for the exponential distribution with mean unknown. Journal of the American Statistical Association, 64(325), 387-389.
Lin, S.-W., & Yu, V. F. (2012). A simulated annealing heuristic for the team orienteering problem with time windows. European Journal of Operational Research, 217(1), 94-107.
Liou, T.-S., & Wang, M.-J. J. (1992). Ranking fuzzy numbers with integral value. Fuzzy sets and systems, 50(3), 247-255.
Liu, L., Xu, J., Liao, S. S., & Chen, H. (2014). A real-time personalized route recommendation system for self-drive tourists based on vehicle to vehicle communication. Expert Systems with Applications, 41(7), 3409-3417.
Ma, M., Friedman, M., & Kandel, A. (1999). A new fuzzy arithmetic. Fuzzy sets and systems, 108(1), 83-90.
Ma, M., Friedman, M., & Kandel, A. (2000). Duality in fuzzy linear systems. Fuzzy sets and systems, 109(1), 55-58.
Mahulae, E. M. (2014). Applying Particle Swarm Optimization for Solving Team Orienteering Problem with Time Windows. Jurnal Teknik Industri, 16(1), 9-16.
Milliken, G. A., & Johnson, D. E. (2009). Analysis of messy data volume 1: designed experiments (Vol. 1): CRC Press.
Montemanni, R., & Gambardella, L. (2009). An ant colony system for team orienteering problems with time windows. Foundations of computing and Decision Sciences, 34, 287-306.
Ordoobadi, S. M. (2009). Development of a supplier selection model using fuzzy logic. Supply Chain Management: An International Journal, 14(4), 314-327.
Pedrycz, W., & Gomide, F. (1998). An introduction to fuzzy sets: analysis and design: Mit Press.
Pedrycz, W., & Gomide, F. (2007). Fuzzy systems engineering: toward human-centric computing: John Wiley & Sons.
Peng, Y., & Qian, Y.-m. (2010). A particle swarm optimization to vehicle routing problem with fuzzy demands. Journal of Convergence Information Technology, 5(6), 112-119.
Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31(12), 1985-2002.
Ross, T. J. (2004). Fuzzy Logic with Engineering Applications: Wiley.
Searle, S., Speed, F., & Milliken, G. (1980). Population Marginal Means in the Linear Model: An Alternative to Least Squares Means. American Statistician, 216-221.
Sheskin, D. J. (2007). Handbook of Parametric and Nonparametric Statistical Procedures.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
Sugeno, M. (1985). An introductory survey of fuzzy control. Information sciences, 36(1), 59-83.
Talbi, E.-G. (2009). Metaheuristics: from design to implementation (Vol. 74): John Wiley & Sons.
Tang, H., & Miller-Hooks, E. (2005). A tabu search heuristic for the team orienteering problem. Computers & Operations Research, 32(6), 1379-1407.
Tricoire, F., Romauch, M., Doerner, K. F., & Hartl, R. F. (2010). Heuristics for the multi-period orienteering problem with multiple time windows. Computers & Operations Research, 37(2), 351-367.
Vansteenwegen, P., Souffriau, W., Berghe, G. V., & Van Oudheusden, D. (2009). Iterated local search for the team orienteering problem with time windows. Computers & Operations Research, 36(12), 3281-3290.
Vansteenwegen, P., Souffriau, W., & Van Oudheusden, D. (2011). The orienteering problem: A survey. European Journal of Operational Research, 209(1), 1-10.
Verdegay, J. L. (1984). A dual approach to solve the fuzzy linear programming problem. Fuzzy sets and systems, 14(2), 131-141.
Verma, M., & Shukla, K. (2015). Application of fuzzy optimization to the orienteering problem. Advances in Fuzzy Systems, 2015, 8.
Wang, Y.-M., & Luo, Y. (2009). Area ranking of fuzzy numbers based on positive and negative ideal points. Computers & Mathematics with Applications, 58(9), 1769-1779.
Wang, Z.-X., Liu, Y.-J., Fan, Z.-P., & Feng, B. (2009). Ranking L–R fuzzy number based on deviation degree. Information Sciences, 179(13), 2070-2077.
Xu, J., Goncalves, G., & Hsu, T. (2008). Genetic algorithm for the vehicle routing problem with time windows and fuzzy demand. Proceedings of the Evolutionary Computation, 2008. CEC 2008.(IEEE World Congress on Computational Intelligence). IEEE Congress on (pp. 4125-4129).
Yamashiro, M. (1994). The median for a trapezoidal fuzzy number. Microelectronics Reliability, 34(9), 1509-1511.
Yang, M.-y., Van Coillie, F., Hens, L., De Wulf, R., Ou, X.-k., & Zhang, Z.-m. (2014). Nature conservation versus scenic quality: A GIS approach towards optimized tourist tracks in a protected area of Northwest Yunnan, China. Journal of Mountain Science, 11(1), 142-155.
Yao, J.-S., & Wu, K. (2000). Ranking fuzzy numbers based on decomposition principle and signed distance. Fuzzy sets and Systems, 116(2), 275-288.
Yu, V. F., & Dat, L. Q. (2014). An improved ranking method for fuzzy numbers with integral values. Applied Soft Computing, 14, 603-608.
Zadeh, L. A. (1965). Fuzzy sets. Information and control, 8(3), 338-353.