研究生: |
Andro Nicus Sutanto Andro Nicus Sutanto |
---|---|
論文名稱: |
Set Team Orienteering Problem with Time Windows Set Team Orienteering Problem with Time Windows |
指導教授: |
喻奉天
Vincent F. Yu 郭伯勳 Po-Hsun Kuo |
口試委員: |
喻奉天
Vincent F. Yu 郭伯勳 Po-Hsun Kuo 林詩偉 Shih-Wei Lin |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2020 |
畢業學年度: | 108 |
語文別: | 英文 |
論文頁數: | 72 |
中文關鍵詞: | Set Team Orienteering Problem with Time Windows 、Adaptive Large Neighborhood Search 、Mathematical model |
外文關鍵詞: | Set Team Orienteering Problem with Time Windows, Adaptive Large Neighborhood Search, Mathematical model |
相關次數: | 點閱:272 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
In this research, an extension of TOPTW called Set Team Orienteering Problem with Time Windows (STOPTW) is developed. In STOPTW, customers are grouped into clusters, and each clusters are associated with profit that will be collected if at least a customer is visited in the cluster. The objective of STOPTW is to find the best route that can maximize the total collected profit without violating given time windows. A mathematical model is formulated to address this problem. Furthermore, an adaptive large neighborhood search is proposed to solve this problem. Two type of datasets originated from TOPTW benchmark dataset are generated for this research, called set A (small dataset with up to 20 clusters) and set B (large dataset with up to 100 clusters). STOPTW finds it applications in mass distribution where distributor need to find the best routes to deliver products to customers in a chain (e.g. convenience store chain). It is more preferable to have a delivery during store leisure time, so distributor need to delivers in between the provided time by customers.
Angelelli, Enrico, Archetti, Claudia, & Vindigni, Michele. (2014). The clustered orienteering problem. European Journal of Operational Research, 238(2), 404-414.
Archetti, Claudia, Carrabs, Francesco, & Cerulli, Raffaele. (2018). The set orienteering problem. European Journal of Operational Research, 267(1), 264-272.
Archetti, Claudia, Feillet, Dominique, Hertz, Alain, & Speranza, Maria Grazia. (2009). The capacitated team orienteering and profitable tour problems. Journal of the Operational Research Society, 60(6), 831-842.
Chao, I-Ming, Golden, Bruce L, & Wasil, Edward A. (1996a). A fast and effective heuristic for the orienteering problem. European Journal of Operational Research, 88(3), 475-489.
Chao, I-Ming, Golden, Bruce L, & Wasil, Edward A. (1996b). The team orienteering problem. European Journal of Operational Research, 88(3), 464-474.
Cordeau, Jean-François, Laporte, Gilbert, & Mercier, Anne. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52(8), 928-936.
Golden, Bruce L, Levy, Larry, & Vohra, Rakesh. (1987). The orienteering problem. Naval Research Logistics (NRL), 34(3), 307-318.
Gunawan, Aldy, Lau, Hoong Chuin, & Vansteenwegen, Pieter. (2016). Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research, 255(2), 315-332.
Hammami, Farouk, Rekik, Monia, & Coelho, Leandro C. (2020). A hybrid adaptive large neighborhood search heuristic for the team orienteering problem. Computers & Operations Research, 105034.
Kantor, Marisa G, & Rosenwein, Moshe B. (1992). The orienteering problem with time windows. Journal of the Operational Research Society, 43(6), 629-635.
Karunakaran, Deepak, Mei, Yi, & Zhang, Mengjie. (2019). Multitasking Genetic Programming for Stochastic Team Orienteering Problem with Time Windows. Paper presented at the 2019 IEEE Symposium Series on Computational Intelligence (SSCI).
Labadie, Nacima, Melechovský, Jan, & Calvo, Roberto Wolfler. (2011). Hybridized evolutionary local search algorithm for the team orienteering problem with time windows. Journal of Heuristics, 17(6), 729-753.
Pěnička, Robert, Faigl, Jan, & Saska, Martin. (2019). Variable neighborhood search for the set orienteering problem and its application to other orienteering problem variants. European Journal of Operational Research, 276(3), 816-825.
Righini, Giovanni, & Salani, Matteo. (2006). Dynamic programming for the orienteering problem with time windows.
Righini, Giovanni, & Salani, Matteo. (2009). Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computers & Operations Research, 36(4), 1191-1203.
Ropke, Stefan, & Pisinger, David. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4), 455-472.
Shaw, Paul. (1998). Using constraint programming and local search methods to solve vehicle routing problems. Paper presented at the International conference on principles and practice of constraint programming.
Solomon, Marius M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254-265.
Solomon, Marius M, & Desrosiers, Jacques. (1988). Survey paper—time window constrained routing and scheduling problems. Transportation Science, 22(1), 1-13.
Tang, Hao, & Miller-Hooks, Elise. (2005). A tabu search heuristic for the team orienteering problem. Computers & Operations Research, 32(6), 1379-1407.
Tsiligirides, Theodore. (1984). Heuristic methods applied to orienteering. Journal of the Operational Research Society, 35(9), 797-809.
Vansteenwegen, Pieter, Souffriau, Wouter, Berghe, Greet Vanden, & Van Oudheusden, Dirk. (2009a). A guided local search metaheuristic for the team orienteering problem. European Journal of Operational Research, 196(1), 118-127.
Vansteenwegen, Pieter, Souffriau, Wouter, Berghe, Greet Vanden, & Van Oudheusden, Dirk. (2009b). Metaheuristics for tourist trip planning. In Metaheuristics in the service industry (pp. 15-31): Springer.
Vansteenwegen, Pieter, Souffriau, Wouter, & Van Oudheusden, Dirk. (2011). The orienteering problem: A survey. European Journal of Operational Research, 209(1), 1-10.
Yu, V. F., Jewpanya, Parida, Lin, Shih-Wei, & Redi, AAN Perwira. (2019). Team orienteering problem with time windows and time-dependent scores. Computers & Industrial Engineering, 127, 213-224.
Yu, V. F., Redi, A. A. N. P., Jewpanya, P., & Gunawan, A. (2019). Selective discrete particle swarm optimization for the team orienteering problem with time windows and partial scores. Computers & Industrial Engineering, 138, 106084. doi:UNSP 106084