在供應鏈管理當中，運輸成本控管是相當重要的一環。有效率的物流配送規劃不僅能節省成本，也能增加顧客滿意度，但配送過程須小心謹慎，例如：裝載時符合商品特性與裝卸貨順序，使得物流業者無不在配送規劃上耗費心思。本研究經訪談物流業者後發現，業者在實務上常會面臨裝載不可行之窘境，在僅考慮貨車有重量限制地情況下，往往因貨物體積與質量大小不一，使得實際執行裝載之難度倍增，同時增加時間與金錢的額外負擔。
本研究以Ｌ個案物流公司之B2B（Business to Business）業務為例，協助改善裝載可行性之課題。B2B商品特性為種類繁多，且每一顧客的貨品之件數、重量以及體積皆有明顯差異（如電視機、冰箱、手機、記憶卡等）。在學術研究上，經典車輛途程問題CVRP（Capacitated Vehicle routing problem）較不易完整呈現現實的配送裝載問題。本研究亦發現近年來有許多研究陸續探討加入裝載限制條件的車輛途程問題，將裝載問題Bin packing problem（BPP）等與CVRP問題作結合，但以實際數據實作的研究較少，商品種類也相對簡單。故本研究以個案公司之實際輸配送資料，以模擬退火演算法（Simulated annealing algorithm）尋找僅考慮總重量及總體積的初始解，搭配CargoWiz裝載軟體的輔助，以最小化車輛使用數為目標，提出一系列啟發式求解法來解決考量裝載可行性之車輛途程問題。實測結果證明方法可行，本研究亦針對結果分析貨品裝載的各項特性。

In the supply chain management, the cost of transporting the cargo was account for a large part in the operation process. The efficiency distribution planning not only can save the cost, but also to increase the customer satisfaction. However, distribution planning was much difficult in practice, especially in the loading problem. Three dimensional loading is an NP-hard problem. In the logistics company, they always face to a plight that they cannot load cargos into a specific vehicle completely, so that the workers have to reload again or use extra vehicle. In the past, we just consider the limit of weight or capacity of vehicle in CVRP problem, the results were hard to be executed in the real situation, and probably increased the extra operation cost and time.
The main idea of this paper was to solve the 3L-CVRP problem by the proposed heuristics algorithms, based on “Routing first- Packing second” strategy. We used simulated annealing algorithm to find an initial solution of the improved CVRP problem and solve the loading problem based on CargoWiz software. The object was to minimize the number of vehicle used.
And we took the real data of a B2B (Business to Business) logistics company for instance in this paper, that was rarely seem in before. The characteristics of B2B cargos were a wide variety and the qualities were so much different. Eventually, we found feasible solutions by the methods we proposed. The logistics company can follow our methods to make a distribution plan in advance to avoid the loading infeasibility.

第一章 緒論 1
1.1研究背景與動機 1
1.2研究目的 3
1.3研究範圍 4
1.4研究流程 5
第二章 文獻回顧 7
2.1車輛途程問題 7
2.1.1車輛途程問題之定義 7
2.1.2車輛途程問題之求解方法 8
2.1.3 模擬退火演算法 10
2.2容器裝載問題 14
2.2.1容器裝載問題之定義 14
2.2.2 C&P問題之常見類型 18
2.2.3容器裝載問題之求解方法 20
2.3考量裝載可行性之車輛途程問題 24
2.3.1 3L-CVRP之問題定義 24
2.3.2 3L-CVRP之求解方法 30
2.4 小結 33
第三章 研究方法 35
3.2模型建構 36
3.2.1模型假設 36
3.2.2情境模擬 38
3.3求解方法 39
3.3.1 Routing-產生初始路線 39
3.3.2 Packing-嘗試裝載 39
3.3.3 Fixing-路線合併 44
3.3.4求解方法流程圖 47
第四章 案例分析 49
4.1公開範例測試 49
4.1.1第一階段-產生初始路線（公開範例） 61
4.1.2第二階段-嘗試裝載（公開範例） 67
4.1.3第三階段-路線合併（公開範例） 76
4.1.4 小結（公開範例） 90
4.2　實際案例測試 96
4.2.1 實際案例：案例一 97
4.2.2 實際案例：案例二 112
4.2.3 小結（實際案例） 130
4.3　總結 137
第五章 結論與建議 139
5.1 結論與管理意涵 139
5.2　未來研究建議 141
參考文獻 143

孟沖、陳柏松、張會峰（民98）。基於Cargowiz的航空兵城建制空運裝載方案
分析。兵工自動化，第二十七卷，第三期，頁25-30。
陳慶瀚（民95）。退火式神經網路。108年5月4日
“http://ccy.dd.ncu.edu.tw/~chen/course/Neural/index.htm”。
顏憶茹、張淳志（民94）物流管理：原理、方法與實例。 四版：前程文化事業有限公司。
羅中育（民90）。田口品質工程應用於模擬退火法參數組合─以旅行推銷員問題（TSP）為例。國立雲林科技大學工業工程管理研究所碩士論文，未出版，雲林縣。
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.
Baker, B S, Coffman, E. G., JR., Rivest, R L. (1980) Orthogonal packings in two dimensions. SIAM Journal on Computing, Vol. 9(4), pp. 846-855.
Battarra M, Monaci M, & Vigo D. (2009) An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem. Computer & Operations Research, Vol. 36 (11), pp.3041–3050.
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., & 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., 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.
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.
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.
Carlos A. Vega-Mejía., Jairo R. Montoya-Torres. & Sardar M. N. Islam (2017) Consideration of triple bottom line objectives for sustainability in the optimization of vehicle routing and loading operations: a systematic literature review. Annals of Operations Research, Vol. 273, pp. 311-375.
Ceschia, S., Schaerf, A., Stützle, T., & Stuzle, T. (2013). Local search techniques for a routing-packing problem. Computers & Industrial Engineering, Vol. 66, pp. 1138–1149.
Chen, C.S., Lee S. M., & Shen Q. S. (1995) An analytical model for the container loading problem. European Journal of Operational Research. Vol. 80, pp. 68-76.
Chiang, W. C., & Russell, R. A. (1996). Simulated annealing metaheuristics for the Vehicle Routing Problem with Time Windows. Annals of Operations Research. Vol. 63, pp. 3-27.
Clarke, G., & Wright, J.W. (1964). Scheduling of vehicles from a Central Depot to a Number of Delivery Points. Operations Research, Vol. 12, pp. 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.
Dyckhoff, H. (1990). A typology of cutting and packing problems. European Journal of Operational Research. Vol. 44. pp. 145-159.
Egeblad, J., Garavelli, C., Lisi, S., & Pisinger, D. (2009). Heuristics for container loading of furniture. European Journal of Operational Research. Vol. 200, pp. 881-892.
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.
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.
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.
Huang, Y.-H., Hwang, F. J., & Lu, H.-C. (2016). An effective placement method for the single container loading problem. Computers & Industrial Engineering, Vol. 97, pp. 212–221.
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.
Li, K., Cheng, KH. (1990) On Three-Dimensioanl Packing. SIAM Journal on Computing, Vol. 19. pp. 847-867.
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.
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.
Pollaris, H., Braekers, K., Caris, A., Janssens, G. K., & Limbourg, S. (2015). Vehicle routing problems with loading constraints: state-of-the-art and future directions. OR Spectrum, Vol. 37, pp. 297–330.
Ramos, A. G., Oliveira, J. F., Gonçalves, J. F., & Lopes, M. P. (2016). A container loading algorithm with static mechanical equilibrium stability constraints. Transportation Research Part B-Methodological, Vol. 91, pp.565–581.
Ruan, Q., Zhang, Z., Miao, L., & Shen, H. (2013). A hybrid approach for the vehicle routing problem with three-dimensional loading constraints. Computers & Operations Research, Vol. 40, pp. 1579–1589.
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, Vol. 10, pp. 255–271.
Tricoire, F., Doerner, K. F., Hartl, R. F., & Iori, M. (2011). Heuristic and exact algorithms for the multi-pile vehicle routing problem. OR Spectrum, Vol. 33, pp. 931–959.
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.
Wei, L., Zhang, Z., & Lim, A. (2014). An adaptive variable neighborhood search for a heterogeneous fleet vehicle routing problem with three-dimensional loading constraints. IEEE Computational Intelligence Magazine, Vol. 9, pp. 18–30.
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.
Vega-Mejía, C A., Montoya-Torres., J R., & Islam, S M, N. (2017). Annals of Operations Research. Vol. 273, pp.311-375.
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, D., Cai, S., Ye, F., Si, Y.-W., & Nguyen, T. T. (2017). A hybrid algorithm for a vehicle routing problem with realistic constraints. Information Sciences, Vol. 394, pp. 167–182.
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, Vol. 39, pp. 2178–2195.