在供應鏈管理中，物流運輸是相當重要的一環，它不僅僅是連接供應商、零售商……等的重要金鑰，更是輸配送過程當中與消費者接觸的第一線。完善的物流運輸規畫能有效降低物流成本，同時減少貨損與裝卸載效率。
本研究以具裝載限制的車輛途程問題 (VRP) 為基礎，以個案物流公司實際案例進行探討與改善裝載最佳化之議題。考量 B2B 的商品特性，使用模擬退火法搜索出初始路線，搭配R裝載演算法的模擬裝載，搭配啟發式演算法進行貨物裝載最佳化求解。研究結果顯示，市面上常用的裝載軟體之結果仍有改進空間。本研究運用 R 語言所撰寫之裝載演算法，透過不同的案例分析，探討不同車隊配置與裝載策略，可以顯著提升裝載效率與降低配送路程。

In the supply chain management, logistics transportation is a very important part. It is not only an important key to connect suppliers, retailers, etc., but also the first line to contact with consumers during the delivery process. A complete logistics transportation planning can effectively reduce logistics costs, and reducing cargo damage,loading and unloading at the same time.
This study is based on the vehicle routing problem (VRP) with loading restrictions. Discuss and improve the issues with loading optimization with actual cases of individual logistics companies.
Considering the characteristics of B2B cargos, the simulated annealing method was used to search out the initial route. Use R loading algorithm to simulate loading, and heuristic algorithm to optimize the solution of cargo loading. The result reveals that there still has room for improvement in the loading software commonly used in the market. This research uses the loading algorithm written in R language and analyzes it through different cases. By discussing different fleet configurations and loading
strategies can significantly improve loading efficiency and reduce delivery distance.

摘要 I
Abstract II
目錄 III
圖目錄 V
表目錄 VI
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究範圍與對象 4
1.4 研究流程 5
第二章 文獻回顧 7
2.1 車輛途程問題 7
2.1.2 車輛途程問題之種類 8
2.1.3 車輛途程問題之解決方法 10
2.2 裝箱問題 ( Container Loading Problem , CLP ) 14
2.2.1 裝箱問題之定義 14
2.2.2 裝箱問題之種類 15
2.2.3 裝箱問題之求解方法 16
2.3 三維裝箱之車輛途程問題(Three-Dimensional Container-Loading Problem with Vehicle Routing Problem ,3L-CVRP) 18
2.3.1 3L-CVRP之問題結合 18
2.3.1 3L-CVRP解決方法之文獻 20
2.4 文獻回顧小結 24
第三章 研究方法 25
3.1 研究問題 25
3.2 模型建構 26
3.2.1 模型概念 26
3.2.2 參數設定 29
3.2.3 模型建立 31
3.2.4 演算邏輯流程圖 33
3.2.3 演算邏輯流程圖 – 裝載及合併路線流程圖 34
3.3 求解方法 35
3.3.1 第一階段 - Routing-形成一路線(初始解) 35
3.3.2 第二階段 – Packing-模擬裝載 37
3.3.3 第三階段 – Fixing-路線合併 45
第四章 案例分析 49
4-1 Gendreau公開範例測試 49
4-2 個案物流公司實際數據測試 139
第五章 結論與建議 167
5.1 測試總結 167
5.2 管理意涵 167
5.2 研究限制 168
5.3 未來研究建議 168
參考文獻 171

Aprile D, Egeblad J, Garavelli A, Lisi S, Pisinger D (2007) Logistics optimization: vehicle routing with loading constraints. In: Proceedings of the 19th international conference on production research.
Aprile, D., Egeblad, J., Garavelli, A. C., Lisi, S., & Pisinger, D. (2007, July). Logistics optimization: vehicle routing with loading constraints. In Proceedings of the 19th international conference on production research.
Battarra M, Monaci M, & Vigo D. (2009) An adaptive guidance approach for the
Bortfeldt, A. (2012). A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. Computers&Operations Research, Vol. 39, pp.2248–2257.
Bortfeldt, A. (2012). A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. Computers & Operations Research, 39(9), 2248-2257.
Bortfeldt, A., & Homberger, J. (2013). Packing first, routing second—a heuristic for the vehicle routing and loading problem. Computers & Operations Research, Vol. 40, pp. 873–885.
Bortfeldt, A., & Wäscher, G. (2013). Constraints in container loading—A state-of-the-art review. European Journal of Operational Research, Vol. 229, pp. 1–20.
Bortfeldt, A., Hahn, T., Männel, D., & Mönch, L. (2015). Hybrid algorithms for the vehicle routing problem with clustered backhauls and 3D loading constraints. European Journal of Operational Research, Vol. 243, pp. 82–96.
Bowersox, D. J., and Closs, D. J (1996). Logistical Management—The Integrated Supply Chain Process. McGraw-Hill Companies, New York.
Brijesh Krishna, R.P., Sahay, M. (2017) Preplanned truck optimization using cargowiz. Proceedings of the international conference on industrial engineering and operations management. pp. 1080-1089.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4), 568-581.
Cordeau, J.-F., Laporte G. & Mercier, A. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, Vol. 20, pp.928-936.
Dantzig, G. B., & J. M. Ramser. (1959). The Truck Dispatching Problem. Management Science, Vol.6, pp. 81-91.
Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations research, 8(1), 101-111.
Dyckhoff, H. (1990). A typology of cutting and packing problems. European Journal of Operational Research. Vol. 44. pp. 145-159.
Fuellerer, G., Doerner, K. F., Hartl, R. F., & Iori, M. (2010). Metaheuristics for vehicle routing problems with three-dimensional loading constraints. European Journal of Operational Research, Vol. 201, pp. 751–759.
Fuellerer, G., Doerner, K. F., Hartl, R. F., & Iori, M. (2010). Metaheuristics for vehicle routing problems with three-dimensional loading constraints. European Journal of Operational Research, 201(3), 751-759.
Gendreau, M., Iori, M., Laporte, G., & Martello, S. (2006). A tabu search algorithm for a routing and container loading problem. Transportation Science, 40(3), 342-350.
Gendreau, M., Iori, M., Laporte, G., &Martello, S. (2006). A tabu search algorithm for a routing and container loading problem. Transportation Science. Vol. 40, pp. 342–350.
George, J. A., & Robinson, D. F. (1980). A heuristic for packing boxes into a container. Computers & Operations Research. Vol. 7, pp.147-156.
Gillett, B. E., & Miller, L. R. (1974). A Heuristic Algorithm for the Vehicle-dispatch Problem. Operations Research, Vol.21, pp.340-349.
Guibas, L. J., & Sedgewick, R. (1978, October). A dichromatic framework for balanced trees. In 19th Annual Symposium on Foundations of Computer Science (sfcs 1978) (pp. 8-21). IEEE.
heuristic solution of a minimum multiple trip vehicle routing problem. Computer & Operations Research, Vol. 36 (11), pp.3041–3050.
Hokama, P., Miyazawa, F. K., & Xavier, E. C. (2016). A branch-and-cut approach for the vehicle routing problem with loading constraints. Expert Systems with Applications, Vol. 47, pp. 1–13.
Iori, M., & Martello, S. (2010). Routing problems with loading constraints. Top, 18(1), 4-27.
Jin, Z., Ito, T., & Ohno, K. (2003). The three-dimensional bin packing problem and its practical algorithm. JSME International Journal Series C-Mechanical Systems Machine Elements and Manufacturing, Vol.46, pp. 60-66.
Junqueira, L., Oliveira, J. F., Carravilla, M. A., & Morabito, R. (2013). An optimization model for the vehicle routing problem with practical three-dimensional loading constraints. International Transactions in Operational Research, Vol. 20, pp. 645–666.
Kirkpatrick, S., Gelatt Jr, C. D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. American Association for the Advancement of Science. Vol. 220, pp.671-680.
Lacomme, P., Toussaint, H., & Duhamel, C. (2013). A GRASP x ELS for the vehicle routing problem with basic three-dimensional loading constraints. Engineering Applications of Artificial Intelligence, Vol. 26, pp. 1795–1810.
Mahvash, B., Awasthi, A., & Chauhan, S. (2017). A column generation based heuristic for the capacitated vehicle routing problem with three-dimensional loading constraints. International Journal of Production Research, Vol. 55, pp. 1730–1747.
Männel, D., & Bortfeldt, A. (2016). A hybrid algorithm for the vehicle routing problem with pickup and delivery and three-dimensional loading constraints. European Journal of Operational Research, Vol. 254, pp. 840–858.
Miao, L., Ruan, Q., Woghiren, K., & Ruo, Q. (2012). A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints. Rairo-Operations Research, Vol. 46, pp. 63–82.
Moura A, Oliveira JF (2005) A GRASP approach to the Container Loading Problem. IEEE Intell Syst — Spec Issue Metaheuristic Methods Transport Logistics (July/August) Vol. 20. pp. 50–57.
Moura, A., & Oliveira, J. F. (2009). An integrated approach to the vehicle routing and container loading problems. OR Spectrum, Vol. 31, pp. 775–800.
Nagy, G., & Salhi, S. (2005). Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European journal of operational research, 162(1), 126-141.
Osman, I. H. (1993) Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem. Annals of Operations Research. Vol. 41, pp.421-451.
Pisinger, D. (2002). Heuristics for the container loading problem. European Journal of Operational Research, Vol.141, 382–392.
Shin, K., & Han, S. (2011) A centroid-based heuristic algorithm for the capacitated vehicle routing problem. Computing and Informatics, Vol.30. pp.721-732.
Tao, Y., & Wang, F. (2015). An effective tabu search approach with improved loading algorithms for the 3L-CVRP. Computers & Operations Research, Vol. 55, pp. 127–140.
Tarantilis, C. D., Zachariadis, E. E., & Kiranoudis, C. T. (2009). A hybrid metaheuristic algorithm for the integrated vehicle routing and three-dimensional container-loading problem. IEEE Transactions on Intelligent Transportation Systems, 10(2), 255-271.
Tarantilis, C. D., Zachariadis, E. E., & Kiranoudis, C. T. (2009). A hybrid metaheuristic algorithm for the integrated vehicle routing and three-dimensional container-loading problem. IEEE Transactions on Intelligent Transportation Systems, 10(2), 255-271.
Wang, L., Guo, S., Chen, S., Zhu, W., & Lim, A. (2010, August). Two natural heuristics for 3D packing with practical loading constraints. In Pacific Rim International Conference on Artificial Intelligence (pp. 256-267). Springer, Berlin, Heidelberg.
Wäscher, G. Haußner, H. & Schumann, H. (2007) An improved typology of cutting and packing problems. European Journal of Operational Research. Vol. 183, pp. 1109-1130.
Wassan, N., Wassan, N., Nagy, G., & Salhi, S. (2017). The multiple trip vehicle routing problem with backhauls: Formulation and a two-level variable neighbourhood search. Computers & Operations Research, 78, 454-467.
Wei, L., Zhang, Z., Zhang, D., & Leung, S. H. (2018) A Simulated Annealing Algorithm for the Capacitated Vehicle Routing Problem with Two-Dimensional Loading Constraints. European Journal of Operational Research. Vol, 265. pp.843-859.
Zachariadis, E. E., Tarantilis, C. D., & Kiranoudis, C. T. (2013). Designing vehicle routes for a mix of different request types, under time windows and loading constraints. European Journal of Operational Research, Vol. 229, pp. 303–317.
Zhang, Z., Wei, L., & Lim, A. (2015). An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints. Transportation Research Part B: Methodological, 82, 20-35.
Zhang, Z., Wei, L., &Lim, A. (2015). An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints. Transportation Research Part B-Methodological, Vol. 82, pp. 20–35.
Zhu, W., Qin, H., Lim, A., & Wang, L. (2012). A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP. Computers & Operations Research, 39(9), 2178-2195.