靜態撥召服務問題啟發式解法之研究

Abstract

撥召服務問題(DARP, Dial-A-Ride Problem)基本上是由旅行推銷員問題( TSP, Traveling Salesman Problem)加上起迄點關係的限制條件而形成， 基於求解其最佳解的困難及節線交換法在旅行推銷員問題上之良好績效， 本研究採用 Psaraftis的兩階段解法架構：先產生起始路線、再以其設計 之節線交換法加以改善，但在第一階段本研究以自行設計修正之最近鄰點 法、最省插入法、最近插入法與曾俊傑之點對插入法來構建起始路線。本 研究將各種解法以 C語言撰寫程式，並隨機產生例題在 PC /80486上進行 測試演算，再以 Stein推導之 DARP路線長度極限公式為計算精確度的依 據，結果發現：在階段一的四種解法中，以最近鄰點法的求解精確度最佳 、求解速度最快，其求得之近似解平均誤差約為 21%。而在階段二，兩種 節線交換的搜尋方式之求解精確度並無明顯差異，但以橫向優先搜尋方式 之求解速度較快、所需執行之節線交換次數也較少。另就不同的起始路線 經節線交換後的結果而言，較佳的起始路線往往也能達到較佳的 k-opti mal路線 (k=2,3)，尤其當k=2時起始路線的影響效果更為明顯。綜合兩階 段的解法而言，以(最近鄰點法+橫向優先搜尋之節線交換)的組合求解效 率為最佳，其求得之近似解平均誤差約為 6 %，而且就本研究所測試的最 大規模例題（40位乘客）而言，平均僅需3分21秒即可求出其近似解。若 與 Psaraftis以(MST-based heuristic +節線交換法)求解之結果比較， 本研究的求解精確度在 2-optimal路線方面略優，在 3-optimal路線方面 則無明顯差異。