以修正之拉氏鬆弛啟發式解法求解包含委外運輸之車輛路線問題

Abstract

對物流管理者而言，如何將貨物由配送中心運送給顧客，是一項很重要的實務問題。在實際營運狀況下，需求具有變異性，所以當需求量大於業者本身車隊的容量時，業者必須考慮將過剩的需求委託貨運公司運送。本研究探討包含委外運輸之車輛路線問題，考慮顧客是否交由自有車隊運送或委外運輸。為了在求解時間與求解品質間取得平衡以符合實務之需要，本研究發展具備以數學規劃為主之啟發式演算法。首先，將包含委外運輸之車輛路線問題轉換成常見之集合涵蓋問題，再以拉氏鬆弛法做為演算法之基礎架構。其中，為降低運算負荷，求解過程中以變數產生法之觀念，產生部分車輛路線作為解題空間，並考慮顧客委外自行運輸之修正，來找出近似解。數值測試的結果顯示，本演算法具穩定之求解品質，求解結果與已知最佳解均相當接近，且運算的時間可滿足現今動態快速的經營環境。

The delivery of goods from a warehouse to local customers is an important and practical decision problem of a logistics operator. In reality, we are facing the fluctuation of demand. When the total demand is greater than the whole capacity of the private fleet, we need to consider using the common carrier. In this study, we focus on the vehicle routing problem with private fleet and common carrier (VRPPC), in which a customer can be served by the private fleet or assigned to a common carrier. In order to balance computational load and solution quality and to address the issue of flexibility and simplicity, this study developed a heuristic algorithm based on several classical mathematical programming techniques. The VRPPC is first formulated in the form of the set covering problem (SCP), and the Lagrangian relaxation is used as the backbone in designing the iterative algorithm. In addition, a concept similar to column generation is used to update the solution space, a partial set of routes, to reduce computational load. The heuristic procedure was designed to find the feasible solution. Based on the numerical experiment, the solution quality of the heuristic algorithm is stable. The result suggests that the solution algorithm should be able to deal with the operational problems arising from a highly dynamic environment.