結合自有車隊與委外貨運的車輛路線問題

Abstract

過去貨物多透過公司自有車輛運輸，隨著經營型態的轉變，開始出現精密分工、講究專業，促使第三方物流(Third-party Logistics, 3PL)的出現。然而，對於許多貨運量龐大或貨物運送頻繁的公司而言，完全的委外運輸成本上不見得經濟，且基於某些策略上考量，也有可能必須維持保有自身車隊。加上需求不確定的現象相當普遍，自有車隊過於龐大，於需求相對較弱時，會造成資產之閒置。反之，若自有車隊規模不足時，在需求相對高檔時，則會造成運量不足的瓶頸。面對以上情況，企業為追求運輸成本最小化與客服滿意極大化的目標，有必要同時整合自有車輛與委外貨運服務的使用，目前同時整合自有車輛與貨運業者的相關文獻有限，因此本研究選擇以同時結合委外運輸安排及自有車隊之路線規劃之車輛路線問題作為核心問題。

在車輛路線類型問題的求解上，一般傳統式的啟發式解法的缺點為精確度與彈性較為不足，巨集式解法則在解題速度與方法單純性上居於弱勢。本研究以平衡兩者特性為基本的研究理念，將問題轉以集合涵蓋問題描述，進一步以拉氏鬆弛法為基礎，結合變數產生法之觀念來設計一啟發式演算法。求解過程中只產生「部分車輛路線」作為解題空間，再於遞迴運算中將解題空間內的車輛路線進行調整，使得挑出的車輛路線逐步逼近最佳解。僅保留少數車輛路線做為調整解題空間的方式，大幅降低運算負荷，在短時間內找尋近似最佳解。數值測試例題修改自一般車輛路線問題常用題庫。由於演算法本身放鬆特性符合求解結合自有車隊與委外貨運的車輛路線問題之問題本質，可因此加快求解速度。目標在實務運用容許的時間內，找出理想的解答，以期有效協助企業降低運輸成本，並提升服務滿意度。

Vehicle Routing Problems have been studied for almost 50 years, but only a few addresses the issue of both private fleets and common carriers. In the past, most companies delivered goods through their own fleets. When people began to perceive the importance of cost reservation, a new style of company that provided specific services such as third-party logistics emerged. For those that still require frequent and massive shipments, delivery through common carriers is not economical – private fleets are therefore indispensable. However, private fleets cannot satisfy every customer's needs. The irregularity of demand and quantity increase demonstrates the necessity of the common carrier. Combining the usage of common carrier and private fleets could improve the cost reduction and customer satisfaction enhancement. Numerous heuristic solution methods have been proposed for VRP known as NP-hard. They can be classified as classical heuristics and metaheuristics. Recent research has shown that both categories have their advantages and disadvantages. Classical heuristics is simpler and easier to implement, but can not compete with the accuracy and flexibility of metaheuristics. In order to find a balance between these two, the Set Covering Model and the concept of column generation was used to develop a Lagrangian relaxation based heuristics. The calculation is initiated through generating a partial set of feasible routes to be the solution space which would be carefully adjusted through the iterative solution procedure to contain relatively better routes instead of all possible ones, and the result is subsequently improved. The popular vehicle routing test problem set in the literature is revised to the numerical experiment examples of this research. Derived from the characteristic of the vehicle routing problem consisting of private fleets and common carrier, we took the step of relaxing the covering constraint. By using this method, the benefit is able to find reasonably approximate solutions and the computational time shortened.