以記錄更新法求解旅行維修員問題

10.29893/NCUTMAN.201811.0005

許育銓；丁慶榮

旅行維修員問題 ； 記錄更新法 ； 隨機變動鄰域尋優法 ； 公共自行車

管理學術研討會

第十六屆（2018 / 11 / 01）

14 - 23

繁體中文

旅行維修員問題（Traveling Repairman Problem, TRP），也稱最小延遲問題（Minimum Latency Problem, MLP）旨在找一路線使各需求點的總累積完工時間（總延遲時間）最小，此為旅行推銷員問題（traveling salesman problem, TSP）的變異。TRP已被證明屬於NP-Hard問題，在大型問題上，大多以啟發式演算法進行求解。本研究以記錄更新法（Record-to-Record Travel Algorithm, RRT）為基礎，搭配隨機變動鄰域尋優法（Randomized Variable Neighborhood Descent, RVND）加強深度搜尋能力進行測試，其中鄰域搜尋分別為insert、SWAP、2-opt、Or-opt。本研究提出之RRT+RVND方法以文獻提出之標竿例題進行測試，130題例題中找到71題已知文獻最佳解，整體平均誤差為0.95%，顯示本研究發展之演算法可行。實例應用上以本研究RRT+RVND方法應用新北市舊公共自行車系統（NewBike）之維修車維修路線規劃。