物流已是現今企業角逐的戰場，無論是民營企業或是國營企業，皆希望透過降低物流成本來獲取利益，其中運輸是物流活動中重要的一項環節。根據統計資料顯示，運輸成本平均占物流成本的44%，占物流總成本比例相當大，故可推論若運輸網路規劃得宜，將可大幅減少運輸成本，增加企業利潤，並提高企業競爭優勢。
本研究以我國某電力公司之物料配送路線規劃為研究標的，並以該電力公司第一階層至第二階層之物流網路為研究範圍，以實際資料作為分析，並設計六種種情境來探討。本研究問題為一車輛途程問題。車輛途程問題已被證實為一個NP-hard問題 (Lenstra and Kan，1981)，隨著節點數的增加，求解的時間呈現指數性的成長，增加求解的時間以及困難度。為簡化本研究問題的複雜度以增進求解效率，以符合實務上的運作，本研究將採取「先分群，後路線」的方法，並提出四階段求解法來規劃個案電力公司料件之配送模式。第一階段為劃分兩儲運中心的配送範圍，各區處的輕重料件訂單由其所屬的儲運中心進行配送。第二階段本研究提出四個分群模型，進行儲運中心配送範圍內區處分群。第三階段進行群集調整，本研究根據情境設計的不同，提出四個調整演算法，以求得更佳的結果。第四階段進行各群集路線建構，此階段將視為旅行銷售員問題以求解。
研究結果顯示，就總行駛距離來說，本研究提出的配送模式，其總行駛距離明顯小於個案電力公司現行配送模式下的總行駛距離，代表本研究的配送模式能夠有效解決個案電力公司現行的運輸問題-跨區長途的配送比例高，造成運輸成本高的情形。

Logistics is the battlefield for enterprises nowadays. No matter it is a private enterprise or a state-owned enterprise, they all hopes to obtain benefits by reducing logistics costs. Transportation is an important part of logistics activities. According to statistics, transportation costs account for an average of 44% of logistics costs, accounting for a large proportion of total logistics costs. Therefore, we can infer that if the transportation network is properly planned, it will greatly reduce transportation costs, increase profits and enhance competitive advantage for corporation.
This study focus on the material distribution route planning of a power company in Taiwan, and takes the logistics network from the first to the second level of the power company as the research scope.Take the actual data to analylze, and designs six kinds of situations to explore. The problem of this research is about vehicle route problem. The vehicle routing problem has been proven as an NP-hard problem (Lenstra and Kan, 1981). When the number of nodes increases, the solution time grows rapidly, and it is more difficult to solve the problem. In order to simplify the complexity of the research and improve the efficiency, in order to meet the practical operation, this study will adopt the method called “Cluster first, route second” and propose a four-stage method to plan the distribution mode of the case power company. The first stage is to divide the distribution scope of the two logistics centers. In the second stage, this study proposes four clustering models for grouping within the distribution area of the logistics center. In the third stage, cluster adjustment is carried out. According to the different situation, this study proposes four adjustment algorithms to obtain better results. The fourth phase is to construct each cluster route, which will be considered as a travel salesman problem to solve.
The result reveals that the distribution mode proposed in this study is better than the current distribution mode in terms of indicators of total travel distances and total ton-kilometer . It represents that the distribution mode proposed in this study can solve the high transportation costs problem of the case company.

摘要 III
Abstract IV
目錄 V
圖目錄 VII
表目錄 X
第一章 緒論 1
1.1研究背景與動機 1
1.2研究目的 3
1.3研究範圍與對象 5
1.4研究流程 7
第二章 文獻回顧 9
2.1車輛途程問題(Vehicle Routing Problem ,VRP) 9
2.1.1車輛途程問題之定義 9
2.1.2車輛途程問題之類型 12
2.2多車種車輛途程問題(HVRP) 14
2.2.1多車種車輛途程問題之定義與分類 14
2.2.2多車種車輛途程問題之定義 15
2.3車輛途程問題之求解方法 16
2.3.1車輛途程問題之方法論類別 16
2.3.2常見之傳統啟發式演算法 18
2.4車輛途程問題相關文獻回顧 23
2.4.1.單一車種之車輛途程問題 23
2.4.2.多車種之車輛途程問題 23
2.5先分群，後路徑 25
2.6小節與求解方法 30
第三章 研究方法 31
3.1研究問題 31
3.1.1問題定義 32
3.1.2求解工具 32
3.2基本假設與限制 33
3.2.1基本假設 33
3.2.2限制條件 34
3.3模型建立與求解流程 35
第四章 案例分析 61
4.1索羅門測試例題 61
4.1.1測試數值設定 61
4.1.2測試例題之分群結果與路線 63
4.2個案電力公司實際配送路網 68
4.2.1個案電力公司路網設計 70
4.2.2個案電力公司直送及分群結果 84
4.2.3不同車種之配送結果比較 115
4.3配送模式比較 117
4.3.1推估個案電力公司在現行配送模式下之總行駛距離 117
4.3.2本研究配送模式與現行個案電力公司配送模式比較 131
第五章 結論與建議 139
5.1結論 139
5.2管理意涵 141
5.3未來研究 143
參考文獻 145
附錄 149

顏憶茹、張淳智(民94) 。《物流管理：原理、方法與實例》。前程企業管理有限公
司。

廖彩雲、黃琬淑(2007)。以兩階段法求解即時需求物流配送問題之研究。
International Journal of Advanced Information Technologies

沈煜鈞(2005)。油料配送途程規劃問題之研究-以中油公司某供油中心為例。國防管
理學院後勤管理研究所碩士論文。

李沛盈(2008)。多趟次多車種途程問題之研究。國立東華大學全球運籌管理研究所碩
士論文。

謝騰飛(2010)。使用螞蟻演算法求解隨機需求車輛路徑問題－以販賣機補貨車為例。
國立高雄第一科技大學運籌管理所碩士論文。

胡智維(2013) 。粒子群演算法應用於多車種固定車隊之車輛途程問題。元智大學工
業工程與管理學系碩士論文。

Brandão, J. (2011). A Tabu search algorithm for the heterogeneous
fixed fleet vehicle routing problem. Computers & Operations
Research, vol. 38,pp. 140-151, 2011.

Boonsam, P., Member, IAENG, Suthikarnnarunai, N., Member, IAENG, &
Chitphaiboon, W. (2011).Assignment Problem and Vehicle Routing
Problem for an Improvement of Cash Distribution. Proceedings of
the World Congress on Engineering and Computer Science 2011 Vol
II.

BİRİM,S.(2016). Vehicle routing problem with cross docking: A
simulated annealing Approach. Social and Behavioral Sciences
235 , 149–158.

Bodin, L., B. Golden, A. Assad and M. Ball. (1983). Routing and
scheduling of vehicles and crews: The state of the art.
Computers and Operations Research, 10, 69-193.

Clarke ,G., & Wright, J.(1964). Scheduling of vehicles from a
central depot to a number of delivery points. Operations
Research, Vol. 12, No. 4, pp. 568-581.

CO¨ MERT, S., YAZGAN,H., SERTVURAN,I., S¸& ENGU¨ L, H.(2017). A new
approach for solution of vehicle routing problem with hard
time window: an application in a supermarket chain. Indian
Academy of Sciences, Sa¯dhana¯Vol. 42, No. 12, December 2017,
pp. 2067–2080.

Carrabs, F., Cerulli1, R., Sciomachen, A. (2017). An exact approach
for the grocery delivery problem in urban areas. Soft Comput
(2017) 21, pp. 2439–2450.
Calvete, H. I., Gale, C., Oliveros, M.J. (2007). A goal programming
approach to vehicle routing problems with soft time windows.
European Journal of Operational Research 177, pp. 1720–1733.

Dantzig, G.B. and J.H. Ramser (1959).The Truck Dispatching Problem.
Management Science, Vol. 6, pp. 80-91.

Gillett, B., & Miller, L. (1974). A Heuristic Algorithm for the
Vehicle Dispatch Problem. Operations Research 22, pp.340-349.

Golden, B.L., Magnanti, T.L. and Nguyen, H.Q. (1977). Implementing
Vehicle Routing Algorithm. Networks, 7(2), pp.113-148.

Golden, B.L., A. Assad, L. Levy and F.G. Gheysens (1984).The Fleet
Size and Mix Vehicle Routing Problem. Computers & Operations
Research, Vol.11, pp.49-66.

Geetha S. (2014). Analysis of vehicle routing problem using various
particle swarm optimization techniques. Anna University.
Kwangcheol, S., & Sangyong,H.(2011). A CENTROID-BASED HEURISTIC
ALGORITHM FOR THE CAPACITATED VEHICLE ROUTING
PROBLEM. Computing and Informatics, Vol. 30, pp. 721–732.

Kabcome, P., & Mouktonglang, T. (2015). Vehicle Routing Problem for
Multiple Product Types, Compartments, and Trips with Soft Time
Windows.International Journal of Mathematics and Mathematical
Sciences.

Lenstra, J. K. , & Rinnooy Kan, A. H. G.(1981) . Complexity of
vehicle routing and scheduling problems. NETWORKS, Vol. 11,
Issue2 , pp. 221-227.

Lin, S. (1965).Computer Solution of the Traveling Salesman Problem.
Bell System Technology Journal, Vol.11, pp.2245-2269.

Laporte,G.(2007). What You Should Know about the Vehicle Routing
Problem. Canada Research Chair in Distribution Management, HEC
Montréal 3000, chemin de la Côte-Sainte-Catherine,Montréal,
Canada H3T 2A7.

Osman, I. H. (1993). Metastrategy Simulated Annealing and Tabu
Search Algorithms for the Vehicle Routing Problem. Annals of
Operations Research, Vol. 41, No.4, pp. 421-451.

Peiqing, L., Jie, H., Dunyong ,Z., Yongsheng ,H., & Chenhao ,F.
(2015)Vehicle Routing Problem with Soft Time Windows Based on
Improved Genetic Algorithm for Fruits and Vegetables
Distribution. Hindawi Publishing Corporation.

Shuguang, L., Weilai, H., & Huiming M. (2008). An effective genetic
algorithm for the fleet size and mix vehicle routing problems.
Transportation Research Part E 45 , pp. 434–445.

Şule BİRİM. (2016). Vehicle routing problem with cross docking: A
simulated annealing approach. Procedia - Social and Behavioral
Sciences 235 , pp. 149 – 158.

Taillard, E. D.(1999). A heuristic column generation method for the
heterogeneous fleet vrp. RAIRO, vol. 33, pp. 1-14.

Tarantilis ,C.D and. Kiranoudis, C.T. (2001). A Meta-heuristic
Algorithm for the Efficient Distribution of Perishable Food.
Journal of Food Engineering, Vol.50, pp.1-9.

Tarantilis ,C.D and. Kiranoudis, C.T. (2007). A flexible adaptive
memory-based algorithm for real-life transportation operations:
Two case studies from dairy and construction sector. European
Journal of Operational Research 179 , pp.806–822.

Tavakkoli-Moghaddama, R., N., Safaeib, Kahc, M.M.O., & Rabbania, M.
(2007) A New Capacitated Vehicle Routing Problem with Split
Service for Minimizing Fleet Cost by Simulated Annealing.
Journal of the Franklin Institute 344 , pp.406–425.