- 學位論文
利用分支價格切面法求解移動式反光量測車輛之路線規劃
A Branch-and-Price-and-Cut Method for the Planning of MRU Vehicles
摘要
道路標線的可視性是交通安全中重要之功能，應透過週期性之評估確保適切之標線維護。以往之評估是透過如視覺調查或使用手持設備進行之手動檢測。近年來，相關機構已開始使用移動式反光量測儀器代替過去不安全、耗時且需大量人力資源之評估方法。使用移動式反光量測儀器可以有效地蒐集大規模的標線反光值數據。然而，就本研究所知，目前尚未有相關研究為前述方法提出用於安排評估時程和路徑的最佳化數學模型及有效之演算法。 因此，本研究提出基於車輛路徑問題之數學模型，最佳化使用移動式反光量測儀器評估道路標線，並發展分支價格切面演算法，提高求解之效率。演算法包括列生成法，分支界定法和Gomory切面法來加速求解此問題。本研究利用美國佛羅里達州交通局之移動式反光量測儀器路徑規劃，進行驗證。結果顯示本研究提出之演算法在小規模的問題下，上下界值之optimality gap為0%，亦即求得最佳解。而中規模的問題也能求得optimality gap在0.02%以內之可行解;大規模的問題，雖然測試案例中最差的optimality gap為51.95%，但亦能求出可行解。 此外，當限制評估任務僅能被拜訪一次時，能減少求解時間且找到更好的可行解。而當允許評估任務能被重複拜訪時，加入Gomory切面能加速求解效率並提升下界值。
並列摘要
The visibility of pavement markings is an important factor for traffic safety, and a periodical assessment plan is critical for maintaining its function. Traditional assessment methods, such as visual surveys or manual detection using handheld devices, are unsafe, time-consuming, and labor-intensive. In recent years, relevant agencies begin to adopt mobile retroreflectivity units (MRUs) to replace those traditional methods. Using MRUs can collect large-scale retroreflectivity data in an efficient manner. However, no relevant research has yet proposed an optimized mathematical model for arranging the evaluation schedule and paths for this purpose. Accordingly, this study aims to propose a VRP-based model for the optimization of pavement markings assessment through MRUs. To have an efficient solution, this work also develops a branch-and-price-and-cut (BPC) algorithm, including column generation, branch-and-bound, and Gomory’s cut. Computational experiments have been performed on the Florida MRU program for validation of this work. Results show that the algorithm proposed in this study not only finds the optimal for small-scale problems; but in the medium-scale problems the solution optimality gap can be within 0.02%. Although in large-scale problems the worst optimality gap in the tested cases is 51.95%, it still provides a feasible solution. In addition, when the evaluation tasks can only be visited once, the solution time can be reduced with a better feasible solution. When the evaluation tasks can be visited repeatedly, adding the Gomory’s cut can accelerate the solution efficiency and improve the lower bound.