週期性車輛路線問題(PVRP)啟發式解法之探討

Abstract

週期性車輛路線問題(Period Vehicle Routing Problem, PVRP)是考慮在 一定期間(一週期)內﹐如何同時決定時間(運送日期)與車輛路線的組合決 策型態﹐在達到服務水準之範圍內﹐以最低的成本運送。此類問題型態相 當符合實際上所面臨的情形﹐因此PVRP在實務運應用上十分廣泛與重要。 由於PVRP是屬於NP-hard ﹐因此應用於實務上的解法皆為啟發式解法。本 研究依據Russell and Gribbin(1991)[14] 提出之多階段啟發式解法為架 構。多階段啟發式解法分為四個階段：第一階段為一般化網路問題、第二 階段為求解替代性週期性旅行推銷員問題 ( Period Traveling Salesman Problem, PTSP) 、第三階段為實際計算每日之車輛路線問題( Vehicle Routing Problem, VRP)、第四階段為解 0-1路線改善模式。 Russell與Gribbin[14]提出文獻上的最佳結果﹐但其方法的執行仍有賴於 良好的細部設計與電腦執行的技巧。本研究進行各階段細部的設計﹐使多 階段啟發式解法可實際應用執行。本研究在求解數學規劃方面使用套裝軟 體 XPRESS-MP﹐在執行啟發式解法方面﹐以ANSI C撰寫程式﹐在 SUN電腦 工作站上執行。一共執行了六題文獻上所列的例題﹐分別為50、75及 100個顧客點的網路大小。執行結果與Russell & Gribbin[14] 及 Christofides & Beas- ley[5]結果比較平均誤差分別為7.3%及 5.85%。 未來欲改善其執行精確度﹐則尚有賴於本土化TSP與VRP問題之求解工具的 提升與精進。