以修正之拉式鬆弛法之啟發式解法求解車輛路線問題

Abstract

由於市場競爭愈趨激烈，以最低的成本迅速回應顧客的需要，已成為物流配送業者欲積極達成的目標。在滿足顧客需求，及符合指定時效、車輛載量等作業限制的前題下，物流業者若能以最經濟的顧客配送順序，來降低運輸成本，必能有效提昇競爭力，而這類相關的研究即學術上所提及的車輛路線問題。 本研究將車輛路線問題轉以集合涵蓋問題描述，再以常用之拉氏鬆弛法為基礎，結合變數產生法之觀念來設計一啟發式演算法。求解過程中只產生「部分車輛路線」作為解題空間，再於遞迴運算中將解題空間內的車輛路線進行調整，使得挑出的車輛路線逐步逼近最佳解。本研究最主要之貢獻在於發展一較為適宜作業需求之啟發式解法，以保留少數車輛路線做為調整解題空間的方式，大幅降低運算負荷，在短時間內找尋近似最佳解。 本研究以車輛路線問題常用的題庫進行演算法之數值測試，結果顯示演算法具穩定之求解品質，與最佳解皆相當接近，且運算的時間可滿足現今動態快速的經營環境。有關之後續研究，可將演算法之進一部加以修正與調整，並進一步發展不同類型之車輛路線問題演算法。

Under strong market competition, the goal of the distributors is to satisfy the needs of the customers rapidly at the lowest cost. Considering the demand of the customers and the operational constraint such as vehicle capacity and time requirement, the distributors can significantly raise their competitiveness, if they can determine the economical routes for delivery with low transportation cost. The most important study in this area is the vehicle routing problem (VRP). We used the well-known set covering problem (SCP) to model the vehicle routing problem and developed a Lagrangian relaxation based heuristics. We also adopted the concept of columan generation (CG), ‘generating a partial set of feasible routes to be the solution space.’ The solution space is carefully adjusted through the iterative solution procedure to contain relatively better routes, and the solution found is subsequently improved. To sum up, the major contribution of this study is to design a simple but effective Lagrangian relaxation based heuristics, which contains only few routes in the solution space, to alleviate the computational load and to find the near optimal solution in a short period of time. The numerical experiment is carried out with respect to the popular vehicle routing test problem set in the literature. This heuristic algorithm has good and stable performance in the experiment, and the heuristic solutions are closely to the optimal solutions. The extension of this research can be focused on refining the heuristic algorithm and on developing the algorithm for various versions of the vehicle routing problems.