以拉式鬆弛演算法求解車輛定線問題

Abstract

車輛定線問題之混合整數規劃模式，在處理較大規模的問題時，其求解效能並不理想。根據文獻，大多數路由以及排班問題，可藉由集合涵蓋問題來求解，並且集合涵蓋問題已有相當成熟且效能不錯之求解方法，如拉式鬆弛法即是其中之一。 因此本研究將車輛定線問題模式，以集合涵蓋問題描述，而後以常用之拉式鬆弛法為基礎，並結合列運算技巧之觀念來設計一啟發式演算法，求解過程中只產生「部分候選車輛巡迴路線」，並利用拉式鬆弛演算法遞迴運算的資料為指標，對集合空間進行調整，使得演算法解能逐步逼近最佳解。本研究最主要之貢獻在於新建一簡單之啟發式解法，在其中顧客分群後並未求解旅行推銷員問題，而是透過逐步的修正來提升車輛巡迴路線之適當性。 本研究之演算法經數值範例測試求解後，演算法在50個顧客數以下具穩定之求解品質，且與最佳解皆相當接近，後續研究可進一步加強更多車輛定線問題之測試以及演算法之修正與調整。

關鍵字：車輛定線問題、整數規劃、集合涵蓋模式、拉式鬆弛演算法

Vehicle routing problem can be modeled by integer programming. However, as the problem size grows, the performance of the solution algorithms tend to unsatisfactory. According to the literature, set covering problem (SCP) is a good way to model many routing or scheduling problems. Particularly, SCP model has been well studied for years, and Lagrangian relaxation is one of the effective methods. Therefore, we use SCP to model the vehicle routing problem and develop a Lagrangian relaxation based heuristic. We also adopt the concept of column generation, ‘generating a partial set of feasible routes to solve the problem.’ We employ the information from the iterative procedure of Lagrangian relaxation as the indices to improve the solution space. In the iteration of the solution procedure, we modify the solution without solving traveler salesman problems. The algorithm is tested on the test instances of the literature. Our heuristic has good and stable performance for the vehicle routing problems with 50-or-less customers. To sum up, the major contribution of this study is to design a simple but effective Lagrangian relaxation based heuristic. The further research can be focused on performing more numerical experiments of various vehicle routing problems and refining the heuristic algorithm.

Key Words: Vehicle Routing Problem, Integer Programming, Set Covering Problem, Lagrangian Relaxation.