研究生: |
許佑宇 Yu-Yu Hsu |
---|---|
論文名稱: |
考量時間窗與服務時間之團隊定向節線途程問題 The Team Orienteering Arc Routing Problem with Time Windows and Service Times |
指導教授: |
喻奉天
Vincent F. Yu |
口試委員: |
林詩偉
Shih-Wei Lin 郭伯勳 Po-Hsun Kuo |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2023 |
畢業學年度: | 111 |
語文別: | 中文 |
論文頁數: | 84 |
中文關鍵詞: | 節線途程問題 、團隊定向問題 、服務時間 、時間窗 |
外文關鍵詞: | Arc routing problem, Team Orienteering Problem, Service Time, Time Window |
相關次數: | 點閱:133 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本研究提出考慮時間窗和服務時間的團隊定向節線途程問題(Team Orienteering Arc Routing Problem with Time Windows and Service Times; TOARPTW-ST),這是團隊定向節線途程問題(Team Orienteering Arc Routing Problem; TOARP)的一種新型延伸問題。其目標是在給定的條件下,找出能最大化路徑利潤的一組路徑。在這個問題中,車輛可能需要多次訪問同一個節點,且在配送過程中必須考慮到時間窗的限制,以避免配送過早或過晚到達。為了求解這個問題,我們基於問題的特性和需求開發了模擬退火法(Simulated Annealing; SA)。我們也建立了一個TOARPTW-ST的新測試題庫,並使用SA演算法求解。本研究根據實驗結果對SA演算法的效能和效率進行了詳細分析。結果顯示,本研究所提出的SA演算法,在求解小型和大型TOARPTW-ST測試問題上都有相當穩定和優良的表現。
This study proposes the Team Orienteering Arc Routing Problem with Time Windows and Service Times (TOARPTW-ST), which is a new extension of the Team Orienteering Arc Routing Problem (TOARP). The goal of TOARPTW-ST is to find a set of routes that maximizes profits under given conditions. In TOARPTW-ST, vehicles may need to visit the same node multiple times, and the time window constraints must be considered during delivery to avoid arriving too early or too late. To solve this problem, we develop a Simulated Annealing (SA) algorithm. We also generate a new set of benchmark problems of TOARPTW-ST, which is solved by the proposed SA algorithm. This study performs an in-depth analysis of the effectiveness and efficiency based on the experimental results. The results suggest that the proposed SA algorithm consistently performs well in solving small and large TOARPTW-ST instances.
Statista. (2022). Retail e-commerce sales worldwide from 2014 to 2025. Retrieved from https://www.statista.com/statistics/379046/worldwide-retail-e-commerce-sales/
Archetti, C., Feillet, D., Hertz, A., & Speranza, M. G. (2010). The undirected capacitated arc routing problem with profits. Computers & operations research, 37(11), 1860-1869.
Archetti, C., Guastaroba, G., & Speranza, M. G. (2014a). An ILP-refined tabu search for the directed profitable rural postman problem. Discrete Applied Mathematics, 163, 3-16.
Archetti, C., Corberán, Á., Plana, I., Sanchis, J. M., & Speranza, M. G. (2015). A matheuristic for the team orienteering arc routing problem. European Journal of Operational Research, 245(2), 392-401.
Archetti, C., Speranza, M. G., Corberán, Á., Sanchis, J. M., & Plana, I. (2014b). The team orienteering arc routing problem. Transportation Science, 48(3), 442-457.
Bayliss, C., Juan, A. A., Currie, C. S., & Panadero, J. (2020). A learnheuristic approach for the team orienteering problem with aerial drone motion constraints. Applied Soft Computing, 92, 106280.
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.
Corberán, Á., Eglese, R., Hasle, G., Plana, I., & Sanchis, J. M. (2021). Arc routing problems: A review of the past, present, and future. Networks, 77(1), 88-115.
Cura, T. (2013). An artificial bee colony approach for the undirected capacitated arc routing problem with profits. International Journal of Operational Research, 17(4), 483-508.
Doulabi, S. H. H., & Seifi, A. (2013). Lower and upper bounds for location-arc routing problems with vehicle capacity constraints. European Journal of Operational Research, 224(1), 189-208.
FedEx. (2021). What's Next in E-Commerce. Retrieved from https://fedexbusinessinsights.com/whats-next-in-e-commerce/
Feillet, D., Dejax, P., & Gendreau, M. (2005). The profitable arc tour problem: Solution with a branch-and-price algorithm. Transportation Science, 39(4), 539-552.
Forum, W. E. (2020). Retrieved from https://www.weforum.org/reports/the-future-of-the-last-mile-ecosystem/
Gavalas, D., Konstantopoulos, C., Mastakas, K., Pantziou, G., & Vathis, N. (2015). Heuristics for the time dependent team orienteering problem: Application to tourist route planning. Computers & Operations Research, 62, 36-50.
Golden, B. L., Levy, L., & Vohra, R. (1987). The orienteering problem. Naval Research Logistics (NRL), 34(3), 307-318.
Kirkpatrick, S., Gelatt Jr, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
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.
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.
Kwan,Mei-Ko.(1962). Graphic programming using odd or even points. Chinese Math, 1, 237-277.
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6), 1087-1092.
Sabar, N. R., Ayob, M., & Kendall, G. (2013). A hybrid of differential evolution and simulated annealing algorithms for the capacitated ARC routing problems. Paper presented at the Proceedings of the 6th Multidisciplinary International Conference on Scheduling: Theory and Applications. Gent, Belgium.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
Souffriau, W., Vansteenwegen, P., Berghe, G. V., & Van Oudheusden, D. (2011). The planning of cycle trips in the province of East Flanders. Omega, 39(2), 209-213.
Tang, H., & Miller-Hooks, E. (2005). A tabu search heuristic for the team orienteering problem. Computers & operations research, 32(6), 1379-1407.
Tirkolaee, E. B., Mahdavi, I., & Esfahani, M. M. S. (2018). A robust periodic capacitated arc routing problem for urban waste collection considering drivers and crew’s working time. Waste Management, 76, 138-146.
UPS. (2023).端到端物流:解決供應鏈中的棘手問題. Retrieved from https://www.ups.com/hk/zh/supplychain/logistics-solutions/end-to-end-logistics.page.
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.
Yu,V. F., Jewpanya, P., Lin, S.-W., & Redi, A. P. (2019). Team orienteering problem with time windows and time-dependent scores. Computers & Industrial Engineering, 127, 213-224.