Abstract
由巡回售貨員問題(Travelling Salesman Problem: TSP)推廣而成的車輛路線問題(Vehicle Routing Problem:VRP)因為將實際狀況的限制因素考慮進去，所以比較接近實務上的需求而廣被應用。本文討論的主題是VRP 模式的規劃。模擬一家貨運公司在某一時段，同時發出數量貨車，向顧客們收送同貨品的最佳巡回路徑規劃問題。亦即對VRP 中只有一個收發中心(depot) 的型態來建立完整的整數線性模式。在規劃中，除需滿足恰有一輛貨車(vehicle) 服務一顧客之限制外，問題的層面還涵蓋了滿足顧客的時間限制、裝卸混合作業型態(pick up & delivery)、先后順序的要求等多項限制。至於模式之建立則利用流量變數(flow variable) 的觀念來改進過去的不完整性和非線性的缺點。在目標的訴求上，通常以路徑總花費成本最少為最佳路徑方案。但是如果同時考慮不能化為同一單位的多個準則時，如：路徑總花費時間(total time)、路徑總距離(to-tal distance) 等等，則宜考慮以多目標規劃來建立模式。最后并對VRP 整數規劃問題的敏感度分析提出一個近似的演算法。