研究生: |
Chau Tuan Cuong Chau Tuan Cuong |
---|---|
論文名稱: |
Vehicle Routing Problem with Cross-docking for Perishable Products under Uncertain Freshness Life and Traveling Time Vehicle Routing Problem with Cross-docking for Perishable Products under Uncertain Freshness Life and Traveling Time |
指導教授: |
喻奉天
Vincent F. Yu 周碩彥 Shuo-Yan Chou |
口試委員: |
喻奉天
Vincent F. Yu 周碩彥 Shuo-Yan Chou 郭伯勳 Po-Hsun Kuo |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2022 |
畢業學年度: | 111 |
語文別: | 英文 |
論文頁數: | 72 |
中文關鍵詞: | Vehicle routing problem with cross-docking 、Robust optimization 、Uncertain freshness-life 、Uncertain traveling time 、Perishable product 、Adaptive large neighborhood search |
外文關鍵詞: | Vehicle routing problem with cross-docking, Robust optimization, Uncertain freshness-life, Uncertain traveling time, Perishable product, Adaptive large neighborhood search |
相關次數: | 點閱:236 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
This thesis presents the vehicle routing problem with cross-docking for perishable products (VRPCD-PP) where a set of homogeneous vehicles are used to transport the orders from suppliers to customers via a single cross-dock. The objective of the model is to minimize the summation of logistical cost and freshness-quality cost respecting the time window constraints and truck capacity constraints. Two separated robust counterparts and the combined formulation are developed when the travel times of the network and freshness-life of products are uncertain. In this thesis, the mixed integer linear programming formulation for robust VRPCD-PP under uncertain freshness-life and traveling time is introduced. The proposed mathematical model utilizes the compact formulation in defining the worst-case scenario of the polyhedral uncertainty set instead of using the standard dualization technique. In addition, the Adaptive Large Neighborhood Search (ALNS) metaheuristic algorithm is developed to solve the deterministic and robust formulation for large instances. Computational experiments using Wen’s dataset for VRPCD show the proposed algorithm provides reasonable solutions to the deterministic problem. Moreover, the results of robust solutions are analyzed through the price of robustness to obtain a more reliable solution for the practical decision making process.
This thesis presents the vehicle routing problem with cross-docking for perishable products (VRPCD-PP) where a set of homogeneous vehicles are used to transport the orders from suppliers to customers via a single cross-dock. The objective of the model is to minimize the summation of logistical cost and freshness-quality cost respecting the time window constraints and truck capacity constraints. Two separated robust counterparts and the combined formulation are developed when the travel times of the network and freshness-life of products are uncertain. In this thesis, the mixed integer linear programming formulation for robust VRPCD-PP under uncertain freshness-life and traveling time is introduced. The proposed mathematical model utilizes the compact formulation in defining the worst-case scenario of the polyhedral uncertainty set instead of using the standard dualization technique. In addition, the Adaptive Large Neighborhood Search (ALNS) metaheuristic algorithm is developed to solve the deterministic and robust formulation for large instances. Computational experiments using Wen’s dataset for VRPCD show the proposed algorithm provides reasonable solutions to the deterministic problem. Moreover, the results of robust solutions are analyzed through the price of robustness to obtain a more reliable solution for the practical decision making process.
Agra, A., Christiansen, M., Figueiredo, R., Hvattum, L. M., Poss, M., & Requejo, C. (2013). The robust vehicle routing problem with time windows. Computers & Operations Research, 40(3), 856-866. https://doi.org/10.1016/j.cor.2012.10.002
Agra, A., Christiansen, M., Figueiredo, R., Magnus Hvattum, L., Poss, M., & Requejo, C. (2012, 2012). Layered formulation for the robust vehicle routing problem with time windows. Combinatorial Optimization, Berlin, Heidelberg.
Ben-Tal, A., & Nemirovski, A. (1998). Robust convex optimization. Mathematics of Operations Research, 23(4), 769-805. https://doi.org/10.1287/moor.23.4.769
Ben-Tal, A., & Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations Research Letters, 25(1), 1-13. https://doi.org/10.1016/S0167-6377(99)00016-4
Bertsimas, D., & Sim, M. (2003). Robust discrete optimization and network flows. Mathematical Programming, 98(1), 49-71. https://doi.org/10.1007/s10107-003-0396-4
Bertsimas, D., & Sim, M. (2004). The Price of Robustness. Operations Research, 52(1), 35-53. https://doi.org/10.1287/opre.1030.0065
Cordeau, J.-F., Laporte, G., & Mercier, A. (2004). Improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows. Journal of the Operational Research Society, 55(5), 542-546. https://doi.org/10.1287/moor.28.1.1.14260
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91. https://doi.org/10.1287/mnsc.6.1.80
De La Vega, J., Munari, P., & Morabito, R. (2019). Robust optimization for the vehicle routing problem with multiple deliverymen. Central European Journal of Operations Research, 27(4), 905-936. https://doi.org/10.1007/s10100-017-0511-x
Demir, E., Bektaş, T., & Laporte, G. (2012). An adaptive large neighborhood search heuristic for the pollution-routing problem. European Journal of Operational Research, 223(2), 346-359. https://doi.org/10.1016/j.ejor.2012.06.044
Desaulniers, G., Desrosiers, J., Erdmann, A., Solomon, M. M., & Soumis, F. (2002). VRP with pickup and delivery. 9, 225-242.
El Ghaoui, L., Oustry, F., & Lebret, H. (1998). Robust solutions to uncertain semidefinite programs. SIAM Journal on Optimization, 9(1), 33-52. https://doi.org/10.1137/S1052623496305717
Fisher, M. (1995). Vehicle Routing. Handbooks in Operations Research and Management Science, 8, 1-33. https://doi.org/10.1016/S0927-0507(05)80105-7
Goldfarb, D., & Iyengar, G. (2003). Robust portfolio selection problems. Mathematics of Operations Research, 28(1), 1-38. https://doi.org/10.1287/moor.28.1.1.14260
Gounaris, C. E., Repoussis, P. P., Tarantilis, C. D., Wiesemann, W., & Floudas, C. A. (2014). An adaptive memory programming framework for the robust capacitated vehicle routing problem. Transportation Science, 50(4), 1239-1260. https://doi.org/10.1287/trsc.2014.0559
Gounaris, C. E., Wiesemann, W., & Floudas, C. A. (2013). The robust capacitated vehicle routing problem under demand uncertainty. Operations Research, 61(3), 677-693. https://doi.org/10.1287/opre.1120.1136
Grangier, P., Gendreau, M., Lehuédé, F., & Rousseau, L.-M. (2017). A matheuristic based on large neighborhood search for the vehicle routing problem with cross-docking. Computers & Operations Research, 84, 116-126. https://doi.org/10.1016/j.cor.2017.03.004
Grimault, A., Bostel, N., & Lehuédé, F. (2017). An adaptive large neighborhood search for the full truckload pickup and delivery problem with resource synchronization. Computers & Operations Research, 88, 1-14. https://doi.org/10.1016/j.cor.2017.06.012
Gunawan, A., Widjaja, A. T., Vansteenwegen, P., & Yu, V. F. (2020). Adaptive large neighborhood search for vehicle routing problem with cross-docking. 2020 IEEE Congress on Evolutionary Computation (CEC), July 19-24, 2020, Glasgow, UK.
Gunawan, A., Widjaja, A. T., Vansteenwegen, P., & Yu, V. F. (2021). A matheuristic algorithm for the vehicle routing problem with cross-docking. Applied Soft Computing, 103, 107163. https://doi.org/10.1016/j.asoc.2021.107163
Laporte, G., & Osman, I. H. (1995). Routing problems: A bibliography. Annals of Operations Research, 61, 227-262. https://doi.org/10.1007/Bf02098290
Lee, C., Lee, K., & Park, S. (2012). Robust vehicle routing problem with deadlines and travel time/demand uncertainty. Journal of the Operational Research Society, 63(9), 1294-1306. https://doi.org/10.1057/jors.2011.136
Lee, Y. H., Jung, J. W., & Lee, K. M. (2006). Vehicle routing scheduling for cross-docking in the supply chain. Computers & Industrial Engineering, 51(2), 247-256. https://doi.org/10.1016/j.cie.2006.02.006
Liao, C.-J., Lin, Y., & Shih, S. C. (2010). Vehicle routing with cross-docking in the supply chain. Expert Systems with Applications, 37(10), 6868-6873. https://doi.org/10.1016/j.eswa.2010.03.035
Masson, R., Lehuédé, F., & Péton, O. (2013a). An adaptive large neighborhood search for the pickup and delivery problem with transfers. Transportation Science, 47(3), 344-355. https://doi.org/10.1287/trsc.1120.0432
Masson, R., Lehuédé, F., & Péton, O. (2013b). Efficient feasibility testing for request insertion in the pickup and delivery problem with transfers. Operations Research Letters, 41(3), 211-215. https://doi.org/10.1016/j.orl.2013.01.007
Morais, V. W. C., Mateus, G. R., & Noronha, T. F. (2014). Iterated local search heuristics for the vehicle routing problem with cross-docking. Expert Systems with Applications, 41(16), 7495-7506. https://doi.org/10.1016/j.eswa.2014.06.010
Munari, P., Moreno, A., De La Vega, J., Alem, D., Gondzio, J., & Morabito, R. (2019). The robust vehicle routing problem with time windows: compact formulation and branch-price-and-cut method. Transportation Science, 53(4), 1043-1066. https://doi.org/10.1287/trsc.2018.0886
Nikolopoulou, A. I., Repoussis, P. P., Tarantilis, C. D., & Zachariadis, E. E. (2017). Moving products between location pairs: cross-docking versus direct-shipping. European Journal of Operational Research, 256(3), 803-819. https://doi.org/10.1016/j.ejor.2016.06.053
Ordóñez, F. (2010). Robust Vehicle Routing. In Risk and Optimization in an Uncertain World (pp. 153-178). INFORMS. https://doi.org/10.1287/educ.1100.0078
Osvald, A., & Stirn, L. Z. (2008). A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food. Journal of Food Engineering, 85(2), 285-295. https://doi.org/10.1016/j.jfoodeng.2007.07.008
Pisinger, D., & Ropke, S. (2007). A general heuristic for vehicle routing problems. Computers & Operations Research, 34(8), 2403-2435.
Rahbari, A., Nasiri, M. M., Werner, F., Musavi, M., & Jolai, F. (2019). The vehicle routing and scheduling problem with cross-docking for perishable products under uncertainty: two robust bi-objective models. Applied Mathematical Modelling, 70, 605-625. https://doi.org/10.1016/j.apm.2019.01.047
Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4), 455-472. https://doi.org/10.1287/trsc.1050.0135
Savelsbergh, M. W. (1992). The vehicle routing problem with time windows: minimizing route duration. ORSA journal on computing, 4(2), 146-154. https://doi.org/10.1287/ijoc.4.2.146
Shahabi-Shahmiri, R., Asian, S., Tavakkoli-Moghaddam, R., Mousavi, S. M., & Rajabzadeh, M. (2021). A routing and scheduling problem for cross-docking networks with perishable products, heterogeneous vehicles and split delivery. Computers & Industrial Engineering, 157, 107299. https://doi.org/https://doi.org/10.1016/j.cie.2021.107299
Sloof, M., Tijskens, L. M. M., & Wilkinson, E. C. (1996). Concepts for modelling the quality of perishable products. Trends in Food Science & Technology, 7(5), 165-171. https://doi.org/10.1016/0924-2244(96)81257-X
Sungur, I., Ordóñez, F., & Dessouky, M. (2008). A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Transactions, 40(5), 509-523. https://doi.org/10.1080/07408170701745378
Tarantilis, C. D. (2013). Adaptive multi-restart Tabu Search algorithm for the vehicle routing problem with cross-docking. Optimization Letters, 7(7), 1583-1596. https://doi.org/10.1007/s11590-012-0558-5
Verbic, M. (2006). Discussing the parameters of preservation of perishable goods in a cold logistic chain model. Applied Economics, 38(2), 137-147. https://doi.org/10.1080/00036840500367609
Wen, M., Larsen, J., Clausen, J., Cordeau, J. F., & Laporte, G. (2009). Vehicle routing with cross-docking. Journal of the Operational Research Society, 60(12), 1708-1718. https://doi.org/10.1057/jors.2008.108