簡易檢索 / 詳目顯示

回結果列表
研究生： 何怡萱
Yi-Hsuan Ho
論文名稱： 考慮區間需求之區位途程問題
Location-Routing Problem with Demand Range 研
指導教授： 喻奉天
Vincent F. Yu
口試委員: 曹譽鐘
Yu-Chung Tsao
盧宗成
Chung-Cheng Lu
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2018
畢業學年度： 106
語文別： 英文
論文頁數： 66
中文關鍵詞： 區位途程問題 、模擬退火法 、粒子群演算法 、區間需求
外文關鍵詞： location routing problem, simulated annealing, particle swarm algorithm, demand range
相關次數： 點閱：793  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 本研究提出考慮需求為預測區間之區位途程問題(Location Routing Problem with Demand Range ; LRPDR)，LRPDR為區位途程問題(Location Routing Problem ; LRP)的變形，也同時參考需求為預測區間之車輛途程問題(Vehicle Routing Problem with Demand Range ; VRPDR)的概念來進行延伸。本研究為此問題建構一數學模型，其目標為在滿足所有限制條件下最小化總目標值，其中包含旅行成本、車輛及場站的固定成本和針對不同顧客所設計的額外收益，並由總成本減掉總收益計算而來，而每個顧客的需求為一預測區間，有別於以往LRP的固定需求，並根據不同顧客每單位的額外收益遞送適合的貨量。本研究為LRR新的延伸問題，於是先使用Gurobi求解，其實驗結果顯示此數學模型適用於此類問題，同時提出一個以模擬退火法(Simulated Annealing ; SA)為基礎並結合粒子群演算法(Particle swarm algorithm ; PSO)的啟發式演算法來求解相同的問題，最後，將兩實驗結果進行比較，結果顯示本研究所提出之SAPSO演算法在求解LRPDR的題庫上較Gurobi更具效率。

    This research proposes and formulates a new variant of the location routing problem called LRP with demand range (LRPDR) for a special Business to Business case. It extends the location routing problem by allowing flexibility in the delivery quantity. The goal of LRPDR is minimizing the objective value calculated by the total cost minus the extra revenue. The total cost consists of traveling cost of vehicles, the opening cost of the depot, and the activation cost of vehicles. This study proposes a new hybrid algorithm that combines simulated annealing (SA) and particle swarm algorithm (PSO) for solving LRPDR. Since this problem has not been studied in the literature yet, Gurobi is used to deal with the model in order to take it as a benchmark and to compare with our proposed metaheuristic SAPSO. The results show that the proposed SAPSO is more effective than Gurobi for solving LRPDR instances.

    摘要 ....................................................................... II ABSTRACT ................................................................... III TABLE OF CONTENTS .......................................................... IV LIST OF FIGURES ............................................................ VI LIST OF TABLES ............................................................. VII CHAPTER 1 INTRODUCTION...................................................... 9 1.1 Background ............................................................. 9 1.2 Objectives ............................................................. 10 1.3 Research contribution .................................................. 11 1.4 Organization of thesis ................................................. 11 CHAPTER 2 LITERATURE REVIEW ................................................ 13 2.1 Location routing problem ............................................... 13 2.2 Demand issue for routing problem ....................................... 14 2.3 Simulated annealing .................................................... 15 2.4 Particle swarm optimization ............................................ 16 CHAPTER 3 MODEL DEVELOPMENT ................................................ 17 3.1 Problem definitions and assumptions .................................... 17 3.2 Mathematical formulations of LRPDR ..................................... 19 CHAPTER 4 METHODOLOGY ...................................................... 23 4.1 Solution representation ................................................ 23 4.2 Initial solution ....................................................... 26 4.3 Neighborhood structures ................................................ 27 4.4 Parameters used ........................................................ 29 4.5 Proposed SAPSO procedure ............................................... 30 CHAPTER 5 EXPERIMENTAL RESULTS ............................................. 35 5.1 LRPDR test instance .................................................... 35 5.2 Parameter settings and sensitivity analysis for algorithm parameters ... 36 5.3 Computational results .................................................. 51 5.3.1 LRP instances ........................................................ 52 5.3.2 LRPDR instances ...................................................... 56 CHAPTER 6 CONCLUSION AND FUTURE RESEARCH ................................... 59 6.1 Conclusion ............................................................. 59 6.2 Future research ........................................................ 60 REFERENCES ................................................................. 61

    1. Ahn, J., de Weck, O., Geng, Y., & Klabjan, D. (2012). Column generation based heuristics for a generalized location routing problem with profits arising in space exploration. European Journal of Operational Research, 223(1), 47-59.
    2. Askarzadeh, A., Coelho, L. d. S., Klein, C. E., & Mariani, V. C. (2016, 9-12 Oct. 2016). A population-based simulated annealing algorithm for global optimization. Paper presented at the 2016 IEEE International Conference on Systems, Man, and Cybernetics (SMC).
    3. Barreto, S. d. S. (2004). Análise e Modelização de Problemas de localização-distribuição [Analysis and modelling of location-routing problem] PhD thesis, University of Aveiro, campus universitário de Santiago, 3810-193 Aveiro, Portugal.
    4. 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.
    5. Bertsimas, D. J. (1992). A vehicle routing problem with stochastic demand. Operations Research, 40(3), 574-585.
    6. Campbell, A. M. (2006). The vehicle routing problem with demand range. Annals of Operations Research, 144(1), 99-110.
    7. Contardo, C., Cordeau, J.-F., & Gendron, B. (2014). A GRASP+ ILP-based metaheuristic for the capacitated location-routing problem. Journal of Heuristics, 20(1), 1-38.
    8. Drexl, M., & Schneider, M. (2015). A survey of variants and extensions of the location-routing problem. European Journal of Operational Research, 241(2), 283-308.
    9. Dror, M., Laporte, G., & Trudeau, P. (1994). Vehicle routing with split deliveries. Discrete Applied Mathematics, 50(3), 239-254.
    10. 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.
    11. Eddaly, M., Jarboui, B., & Siarry, P. (2016). Combinatorial particle swarm optimization for solving blocking flowshop scheduling problem. Journal of Computational Design and Engineering, 3(4), 295-311.
    12. Escobar, J. W., Linfati, R., Baldoquin, M. G., & Toth, P. (2014). A granular variable tabu neighborhood search for the capacitated location-routing problem. Transportation Research Part B: Methodological, 67, 344-356.
    13. Escobar, J. W., Linfati, R., & Toth, P. (2013). A two-phase hybrid heuristic algorithm for the capacitated location-routing problem. Computers & Operations Research, 40(1), 70-79.
    14. Ghaffari-Nasab, N., Ahari, S. G., & Ghazanfari, M. (2013). A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands. Scientia Iranica, 20(3), 919-930.
    15. Hemmelmayr, V. C., Cordeau, J.-F., & Crainic, T. G. (2012). An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Computers & Operations Research, 39(12), 3215-3228.
    16. Jarboui, B., Ibrahim, S., Siarry, P., & Rebai, A. (2008). A combinatorial particle swarm optimisation for solving permutation flowshop problems. Computers & Industrial Engineering, 54(3), 526-538.
    17. Javad, M. O. M., & Karimi, B. (2017). A simulated annealing algorithm for solving multi-depot location routing problem with backhaul. International Journal of Industrial and Systems Engineering, 25(4), 460-477.
    18. Karaoglan, I., & Altiparmak, F. (2010, 25-28 July 2010). A hybrid genetic algorithm for the location-routing problem with simultaneous pickup and delivery. Paper presented at the The 40th International Conference on Computers & Indutrial Engineering.
    19. Kennedy, J., & Eberhart, R. (1995, Nov/Dec 1995). Particle swarm optimization. Paper presented at the Neural Networks, 1995. Proceedings., IEEE International Conference on Neural Networks.
    20. Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680.
    21. Kleywegt, A. J., Shapiro, A., & Homem-de-Mello, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479-502.
    22. Lin, S.-W., Ying, K.-C., Lee, Z.-J., & Hsi, F.-H. (2006). Applying simulated annealing approach for capacitated vehicle routing problems. Paper presented at the Systems, Man and Cybernetics, 2006. SMC'06. IEEE International Conference on Neural Networks.
    23. Lopes, R. B., Ferreira, C., & Santos, B. S. (2016). A simple and effective evolutionary algorithm for the capacitated location–routing problem. Computers & Operations Research, 70, 155-162.
    24. Low, C., Hsu, C.-J., & Su, C.-T. (2010). A modified particle swarm optimization algorithm for a single-machine scheduling problem with periodic maintenance. Expert Systems with Applications, 37(9), 6429-6434.
    25. Melechovský, J., Prins, C., & Calvo, R. W. (2005). A metaheuristic to solve a location-routing problem with non-linear costs. Journal of Heuristics, 11(5), 375-391.
    26. 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.
    27. Mughal, M. A., Ma, Q., & Xiao, C. (2017). Photovoltaic cell parameter estimation using hybrid particle swarm optimization and simulated annealing. Energies, 10(8), 1213.
    28. Prins, C., Prodhon, C., & Calvo, R. W. (2006). Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. 4OR: A Quarterly Journal of Operations Research, 4(3), 221-238.
    29. Prins, C., Prodhon, C., & Wolfler-Calvo, R. (2004). Nouveaux algorithmes pour le problème de localisation et routage sous contraintes de capacité. MOSIM' 04, 2. France: Lavoisier, Ecole des Mines de Nantes; 2004; 1115-1122. Proceedings of the MOSIM.
    30. Salhi, S., & Rand, G. K. (1989). The effect of ignoring routes when locating depots. European Journal of Operational Research, 39(2), 150-156.
    31. Tan, K. C., Cheong, C. Y., & Goh, C. K. (2007). Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation. European Journal of Operational Research, 177(2), 813-839.
    32. Teodorović, D., & Pavković, G. (1996). The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain. Fuzzy Sets and Systems, 82(3), 307-317.
    33. 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.
    34. Ting, C.-J., Wu, K.-C., & Chou, H. (2014). Particle swarm optimization algorithm for the berth allocation problem. Expert Systems with Applications, 41(4, Part 1), 1543-1550.
    35. 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.
    36. Yu, V. F., & Lin, S.-W. (2014). Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery. Applied Soft Computing, 24, 284-290.
    37. 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.
    38. Yu, V. F., & Lin, S.-Y. (2015). A simulated annealing heuristic for the open location-routing problem. Computers & Operations Research, 62, 184-196.
    39. Yu, V. F., & Lin, S.-Y. (2016). Solving the location-routing problem with simultaneous pickup and delivery by simulated annealing. International Journal of Production Research, 54(2), 526-549.

    無法下載圖示 全文公開日期 2023/01/25 (校內網路)
    全文公開日期 本全文未授權公開 (校外網路)
    全文公開日期 本全文未授權公開 (國家圖書館：臺灣博碩士論文系統)
    QR CODE