標題: 節省法與路線間交換改善法在車輛路線問題(VRP)上之應用
Applications of savings and between-routes interchange methods to vehicle routing problems
作者: 陳正元
CHEN, ZHENG-YUAN
韓復華
HAN, FU-HUA
土木工程學系
關鍵字: 車輛路線問題;節省法;節線交換法
公開日期: 1991
摘要: 車輛路線問題 (VRP) 在學術上已被證明為 NP-Hard 問題,無法在合理的運算時間 內求得一最佳解,因此,為了能簡單迅速找到一近似解,一般皆採用啟發式解法。 Clarke and Wright 所提出的節省法,因模式簡單且很容易加入新的限制式,在實 務上最常被使用,但是節省法的精確度不高,為提高模式的精確度,本研究將插入 法的精神納入節省法中發展出節省插入法。另外,傳統有關起始解改善法,一般都 直接採用旅行推銷員問題的節線交換法,但是該方法僅能就同一路線內的節線進行 交換,本研究另針對車輛路線問題的特性,提出路線間的節點交換法,進一步提昇 問題求解的精確度。 本研究採用過去文獻中所提出之例題作為模式比較的基礎,針對循序節省法、平行 節省法、循序節省插入法及平行節省插入法,分別配合路線內節線交換法及路線間 節點交換法撰寫程式,經實際測試後發現,總距離平均改善4﹪-10﹪左右,計算機 時間增加約30﹪-43﹪ ,但仍不會超過25秒。 車輛路線問題求解模式往往因為實際的限制,無法直接應用於實務上,本研究針對 高速公路出入限制及行駛速率較高的特性,發展一路網成本轉換的方法,使得車輛 路線問題求解模式也能直接應用於有高速公路存在的狀況。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT802015026
http://hdl.handle.net/11536/55636
Appears in Collections:Thesis