簡易檢索 / 詳目顯示

回結果列表
研究生： 馬美玲
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
相關次數： 點閱：201  下載：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.

    Abstract ii Acknowledgment iii List of Figures vii List of Tables viii CHAPTER 1 INTRODUCTION 1 1.1. Background 1 1.2. Purposes 3 1.3. Research Scopes and Limitations 3 1.4. Research Framework 4 CHAPTER 2 LITERATURE REVIEW 5 2.1. Location Routing Problem (LRP) 5 2.1.1. Solving LRP Using Exact Method 5 2.1.2. Solving LRP Using Heuristic Approaches 7 2.2. Vehicle Routing Problem with Time Windows 10 2.3. Location Routing Problem with Time Windows 10 2.4. Solution Method 11 2.4.1. Construction heuristics 11 2.4.2. Improvement heuristics 12 2.4.3. Meta-heuristics 13 2.4.4. Variable Neighborhood Search 14 2.4.5. Path Relinking 15 CHAPTER 3 PROBLEM DEFINITION AND MATHEMATICAL FORMULATION 17 3.1. Problem Definition 17 3.2. Mathematical Formulation 18 CHAPTER 4 SOLUTION METHODOLOGY 22 4.1. Variable Neighborhood Search with Path-Relinking 22 4.2. Solution Representation 23 4.3. Initial Solution 24 4.4. Variable Neighborhood Search Procedure 27 4.4.1. Neighborhood Structure 29 4.4.2. Local Search 34 4.5. Post Optimization: Path-Relinking 35 4.5.1. Distance Measure 35 4.5.2. Path Relinking Operator 36 CHAPTER 5 COMPUTATIONAL RESULT 38 5.1. Parameters Selection 38 5.2. Algorithm Verification 38 5.2.1. Barreto’s Data Set 40 5.2.2. Prins et.al’s Data Set 41 5.2.3. Tuzun and Burke’s Data Set 41 5.3. LRPTW Computation Result 51 5.3.1. Barreto’s Data Set 51 5.3.2. Prins et.al’s Data Set 52 5.3.3. Tuzun and Burke’s Data Set 54 CHAPTER 6 CONCLUSIONS AND FUTURE RESEARCH 56 6.1. Conclusions 56 6.2. Future Research 57 REFERENCES 58

    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.

    QR CODE