節省法與路線間交換改善法在車輛路線問題(VRP)上之應用

Abstract

車輛路線問題 (VRP) 在學術上已被證明為 NP-Hard 問題，無法在合理的運算時間 內求得一最佳解，因此，為了能簡單迅速找到一近似解，一般皆採用啟發式解法。 Clarke and Wright 所提出的節省法，因模式簡單且很容易加入新的限制式，在實 務上最常被使用，但是節省法的精確度不高，為提高模式的精確度，本研究將插入 法的精神納入節省法中發展出節省插入法。另外，傳統有關起始解改善法，一般都 直接採用旅行推銷員問題的節線交換法，但是該方法僅能就同一路線內的節線進行 交換，本研究另針對車輛路線問題的特性，提出路線間的節點交換法，進一步提昇 問題求解的精確度。 本研究採用過去文獻中所提出之例題作為模式比較的基礎，針對循序節省法、平行 節省法、循序節省插入法及平行節省插入法，分別配合路線內節線交換法及路線間 節點交換法撰寫程式，經實際測試後發現，總距離平均改善4﹪-10﹪左右，計算機 時間增加約30﹪-43﹪ ，但仍不會超過25秒。 車輛路線問題求解模式往往因為實際的限制，無法直接應用於實務上，本研究針對 高速公路出入限制及行駛速率較高的特性，發展一路網成本轉換的方法，使得車輛 路線問題求解模式也能直接應用於有高速公路存在的狀況。