研究生: |
馬美玲 Meilinda - Fitriani Nur Maghfiroh |
---|---|
論文名稱: |
以變動鄰域搜尋法與路徑重連法求解具時窗限制之開放式區域途程問題 Variable Neighborhood Search with Path Relinking for the Location Routing Problem with Time Windows |
指導教授: |
喻奉天
Vincent F. Yu |
口試委員: |
王孔政
Kung-Jeng Wang 楊朝龍 Chao-Lung Yang |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2013 |
畢業學年度: | 101 |
語文別: | 英文 |
論文頁數: | 71 |
中文關鍵詞: | 區域途程問題 、時間窗 、萬用啟發式演算法 、變動鄰域搜尋法 、路徑重連 |
外文關鍵詞: | location routing problem, time windows, metaheuristic, variable neighborhood search, path relinking |
相關次數: | 點閱:202 下載:12 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
在節省運輸成本之下,城市配送中心的選址規劃是重要的。重要的配送中心之生產力可透過最佳化設計途程模型,並同時考慮策略方針(設施選址)和操作決策(車輛途程)來加以實現。然而,現實生活中的應用需要考慮額外的實際限制。因此,本研究結合產能區域途程問題(CLRP)和時間窗限制的具時窗限制之開放式區域途程問題(LRPTW)。具時窗限制之開放式區域途程問題是NP-hard問題,因為CLRP是NP-hard問題。所以,此研究提出變動鄰域搜尋法與路徑重連法求解具時窗限制之開放式區域途程問題(VNSPR)。變動鄰域搜尋法與路徑重連法求解具時窗限制之開放式區域途程問題是在測試大量的CLRP基準實例和LRPTW的實例。LRPTW實例來自CLRP基準數據集。結果顯示,此研究所提出之VNSPR演算法在目前所提出之LRP中視具有競爭力的。而且,此研究所提出的VNSPR可獲得LRPTW實例之近似最佳解。
Location planning for urban distribution centers is crucial in saving distribution cost. Significant distribution center productivity can be achieved through optimal design of location routing models that simultaneously considers both strategic policy (facility location) and operational decisions (vehicle routing). However, real-life applications require considerations of additional practical constraints. Therefore, this study combines the capacitated location routing problem (CLRP) and time windows constraints into the location routing problem with time windows (LRPTW). LRPTW is NP-hard since CLRP is NP-hard. Therefore, this study proposes a variable neighborhood search with path relinking (VNSPR) for the LRPTW. The proposed VNSPR method is tested on a large number of CLRP benchmark instances and LRPTW instances. The LRPTW instances are derived from CLRP benchmark datasets. Computational results indicate that the proposed VNSPR heuristic is competitive with existing approaches for the LRP. Moreover, the proposed VNSPR obtains near optimal solutions to LRPTW instances.
Akca, Z., Berger, R. T., & Ralphs, T. K. (2009). A Branch-and-Price Algorithm for Combined Location and Routing Problems Under Capacity Restrictions. In J. Chinneck, B. Kristjansson & M. Saltzman (Eds.), Operations Research and Cyber-Infrastructure. Operations Research/Computer Science Interfaces. (Vol. 47, pp. 309-330): Springer US.
Albareda-Sambola, M., Dı́az, J. A., & Fernandez, E. (2005). A compact model and tight bounds for a combined location-routing problem. Computers & Operations Research, 32(3), 407-428.
Alvarenga, G. B., Mateus, G. R., & de Tomi, G. (2007). A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows. Computers & Operations Research, 34(6), 1561-1584.
Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30, 787-800.
Baldacci, R., Mingozzi, A., & Calvo, R. W. (2011). An Exact Method for the Capacitated Location-Routing Problem. [Article]. Operations Research, 59(5), 1284-1296.
Balseiro, S. R., Loiseau, I., & Ramonet, J. (2011). An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows. Computers & Operations Research, 38(6), 954-966.
Barreto (2004). Analise e Modelizacao de Problemas de localizacao-distribuicao [Analysis and modelling of location-routing problems]. University of Aveiro, Portugal.
Barreto, S., Ferreira, C., Paixao, J., & Santos, B. S. (2007). Using clustering analysis in a capacitated location-routing problem. European Journal of Operational Research, 179(3), 968-977.
Belenguer, J.-M., Benavent, E., Prins, C., Prodhon, C., & Wolfler Calvo, R. (2011). A Branch-and-Cut method for the Capacitated Location-Routing Problem. Computers & Operations Research, 38(6), 931-941.
Bent, R., & Van Hentenryck, P. (2004). A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science, 38(4), 515-530.
Berger, J., & Barkaoui, M. (2004). A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Computers & Operations Research, 31(12), 2037-2053.
Bookbinder, J. H., & Reece, K. E. (1988). Vehicle routing considerations in distribution system design. European Journal of Operational Research, 37(2), 204-213.
Brandao, J. (2004). A tabu search algorithm for the open vehicle routing problem. European Journal of Operational Research, 157(3), 552-564.
Braysy, O. (2003a). A Reactive Variable Neighborhood Search for the Vehicle-Routing Problem with Time Windows. INFORMS in Journal on Computing, 15(4), 347-368.
Braysy, O. (2003b). A reactive variable neighborhood search for the vehicle-routing problem with time windows. Informs Journal on Computing, 15(4), 347-368.
Chopra, S. M., Peter (2012). Supply Chain Management: Strategy, Planning, and Operation (5th ed.): Prentice Hall.
Clarke, G., & Wright, J. V. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12, 568-581.
Cordeau, J. F., & Laporte, G. (2002). Tabu search heuristics for the vehicle routing problem. GERAD Technical Report, G-2002-15. Montreal, Canada: University of Montreal.
Derigs, U., & Reuter, K. (2009). A simple and efficient tabu search heuristic for solving the open vehicle routing problem. Journal of the Operational Research Society, 60(12), 1658-1669.
Ding, Q., Hu, X., Sun, L., & Wang, Y. (2012). An improved ant colony optimization and its application to vehicle routing problem with time windows. Neurocomputing, 98(0), 101-107.
Duhamel, C., Lacomme, P., Prins, C., & Prodhon, C. (2010). A GRASP×ELS approach for the capacitated location-routing problem. Computers & Operations Research, 37(11), 1912-1923.
Escobar, J. W., Linfati, R., & Toth, P. (2013). A two-phase hybrid heuristic algorithm for the capacitated location-routing problem. [Article]. Computers & Operations Research, 40(1), 70-79.
Fallahi, A. E., Prins, C., & Wolfler Calvo, R. (2008). A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Computers & Operations Research, 35(5), 1725-1741.
Fisher, M. L., & Jaikumar, R. (1981). Generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.
Gendreau, M., Hertz, A., & Laporte, G. (1994). Tabu search heuristic for the vehicle routing problem. Management Science, 40(10), 1276-1290.
Gillett, B., & Miller, L. (1974). A heuristic algorithm for the vehicle dispatch problem. Operations Research, 22(2), 340-349.
Glover, F. (1999). Scatter search and path relinking. In M. D. D. Corne, F. Glover (Ed.), New ideas in optimization. McGraw–Hill.
Gunduz, H. (2011). The Single-Stage Location-Routing Problem with Time Windows. In J. Bose, H. Hu, C. Jahn, X. Shi, R. Stahlbock & S. Vos (Eds.), Computational Logistics. Lecture Notes in Computer Science. (Vol. 6971, pp. 44-58): Springer Berlin Heidelberg.
Hansen, P., & Mladenović, N. (1997). Variable neighborhood search for the p-median. Location Science, 5(4), 207-226.
Hansen, P., Mladenović, N., & Moreno Perez, J. (2008). Variable neighbourhood search: methods and applications. 4OR, 6(4), 319-360.
Hansen, P. M., N. (2003). Variable neighborhood search. Handbook of metaheuristics (2nd ed.). London: Kluwer Academic Publisher.
Hashimoto, H., & Yagiura, M. (2008). A path relinking approach with an adaptive mechanism to control parameters for the vehicle routing problem with time windows. Proceedings of the 8th European conference on Evolutionary computation in combinatorial optimization, Naples, Italy.
Ioannou, G., Kritikos, M., & Prastacos, G. (2001). A Greedy Look-Ahead Heuristic for the Vehicle Routing Problem with Time Windows. The Journal of the Operational Research Society, 52(5), 523-537.
Jarboui, B., Derbel, H., Hanafi, S., & Mladenović, N. (2013). Variable neighborhood search for location routing. Computers & Operations Research, 40(1), 47-57.
Laporte, G., Gendreau, M., Potvin, J. Y., & Semet, F. (2000). Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research, 7(4-5), 285-300.
Laporte, G., & Nobert, Y. (1981). An exact algorithm for minimizing routing and operating costs in depot location. European Journal of Operational Research, 6(2), 224-226.
Laporte, G., Nobert, Y., & Arpin, D. (1986). An exact algorithm for solving a capacitated location-routing problem. Annals of Operations Research, 6(9), 291-310.
Laporte, G., Nobert, Y., & Pelletier, P. (1983). Hamiltonian location problems. European Journal of Operational Research, 12(1), 82-89.
Lenstra, J. K., & Kan, A. H. G. R. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2), 221-227.
Lin, S. (1965). Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44(10), 2245-2269.
Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling salesman problem. Operations Research, 21, 498-516.
Lin, S. W., Lee, Z. J., Ying, K. C., & Lee, C. Y. (2009). Applying hybrid meta-heuristics for capacitated vehicle routing problem. Expert Systems with Applications, 36(2), 1505-1512.
Luiz Usberti, F., Morelato Franca, P., & Franca, A. L. M. GRASP with evolutionary path-relinking for the capacitated arc routing problem. Computers & Operations Research(0).
Nagy, G., & Salhi, S. (2007). Location-routing: Issues, models and methods. European Journal of Operational Research, 177(2), 649-672.
Nguyen, V.-P., Prins, C., & Prodhon, C. (2012a). A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem. Engineering Applications of Artificial Intelligence, 25(1), 56-71.
Nguyen, V.-P., Prins, C., & Prodhon, C. (2012b). Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking. European Journal of Operational Research, 216(1), 113-126.
Osman, I. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41(4), 421-451.
Paraskevopoulos, D. C., Repoussis, P. P., Tarantilis, C. D., Ioannou, G., & Prastacos, G. P. (2008). A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows. Journal of Heuristics, 14(5), 425-455.
Polacek, M., Hartl, R. F., Doerner, K., & Reimann, M. (2004). A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows. Journal of Heuristics, 10(6), 613-627.
Prins, C., & Prodhon, C. (2007). Solving the capacitated location-routing problem by a cooperative lagrangean relaxation-granular tabu search heuristic. Transportation Science, 41(4), 470-483.
Prins, C., Prodhon, C., & Calvo, R. (2006). Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. 4OR, 4(3), 221-238.
Prins, C., Prodhon, C., & Wolfler Calvo, R. (2004). Nouveaux algorithmes pour le probleme de localisation et routage sous contraintes de capacite. MOSIM (4eme Conference Francophone de Modelisation et Simulation)’04, Nantes, France.
Repoussis, P. P., Paraskevopoulos, D. C., Tarantilis, C. D., & Ioannou, G. (2006). A reactive greedy randomized variable neighborhood Tabu search for the. vehicle routing problem with time windows. Hybrid Metaheuristics, Proceedings, 4030, 124-138.
Rousseau, L.-M., Gendreau, M., & Pesant, G. (2002). Using Constraint-Based Operators to Solve the Vehicle Routing Problem with Time Windows. Journal of Heuristics, 8(1), 43-58.
Salhi, S., & Rand, G. K. (1989). The effect of ignoring routes when locating depots. European Journal of Operational Research, 39(2), 150-156.
Sorensen, K., & Schittekat, P. Statistical analysis of distance-based path relinking for the capacitated vehicle routing problem. Computers & Operations Research(0).
Souffriau, W., Vansteenwegen, P., Vanden Berghe, G., & Van Oudheusden, D. (2010). A Path Relinking approach for the Team Orienteering Problem. Computers & Operations Research, 37(11), 1853-1859.
Su, C.-T. (1999). Dynamic vehicle control and scheduling of a multi-depot physical distribution system. Integrated Manufacturing Systems, 10 (1), 56 - 65.
Taillard, E. B., P., Gendreau, M., Guertin, F., Potvin, J.Y. (1997). A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows. Transportation Science 31(2), 170-186.
Tan, K. C., Lee, L. H., & Ou, K. (2001). Artificial intelligence heuristics in solving vehicle routing problems with time window constraints. Engineering Applications of Artificial Intelligence, 14(6), 825-837.
Ting, C.-J., & Chen, C.-H. (2013). A multiple ant colony optimization algorithm for the capacitated location routing problem. International Journal of Production Economics, 141(1), 34-44.
Toth, P., & Vigo, D. (2002). The Vehicle Routing Problem. Philadelphia, PA: SIAM Monographs on Discrete Mathematics and Applications.
Tuzun, D., & Burke, L. I. (1999). A two-phase tabu search approach to the location routing problem. European Journal of Operational Research, 116(1), 87-99.
Villegas, J. G., Prins, C., Prodhon, C., Medaglia, A. L., & Velasco, N. (2011). A GRASP with evolutionary path relinking for the truck and trailer routing problem. Computers & Operations Research, 38(9), 1319-1334.
Wang, W., Wu, B., Zhao, Y., & Feng, D. (2006). Particle swarm optimization for open vehicle routing problem. Lecture Notes in Artificial Intelligence, 4114, 999-1007.
Wu, T.-H., Low, C., & Bai, J.-W. (2002). Heuristic solutions to multi-depot location-routing problems. Computers & Operations Research, 29(10), 1393-1415.
Yu, V. F., Lin, S.-W., Lee, W., & Ting, C.-J. (2010). A simulated annealing heuristic for the capacitated location routing problem. Computers & Industrial Engineering, 58(2), 288-299.