新VRP啟發式解法之開發

Abstract

在追求運輸配送作業的效率化與精確化的過程中，運具巡行路線的配置是最核心的問題。近年來，國內外於車輛巡行問題相關研究之焦點均集中在巨集啟發式解法之開發，即透過新近發展之人工智慧搜尋機制改善傳統車輛巡行問題啟發式解法精度不佳之毛病。但其往往使得整個解題結構變得龐大而複雜且計算繁複，令一般人對於該等演算法在理解與應用方面有相當大的接近障礙。因此，本研究嚐試構建求解架構簡單且計算量精簡之車輛巡行問題演算法。 本研究針對基本車輛巡行問題，發展兩階段式啟發式解法—先集群化後構建路線的方法，第一階段依客戶點之分布位置執行集群化工作，第二階段配合前一階段集群化提出路線建構搜尋策略，完成車輛巡行問題求解。其中，第一階段集群化工作中，以客戶點極座標（r,θ）為輸入資料，以K平均數法為集群方法，將極座標系統中相鄰之客戶點歸入同一集群中，第二階段路線建構工作配合這樣的集群法則，結合半徑方向搜尋與角度方向搜尋建構出具效率性之路線，再執行精化路線步驟。 本演算法測試了十題TSPLIB題庫例題並與塔布搜尋法、掃描法與節省法之運算結果相比較。在計算時間方面，明顯優於其它演算法（塔布搜尋法、掃描法與節省法），皆能於5秒內完成運算。由例題測試結果可發現本演算法當問題規模越大，運算時間上的優勢越明顯，且計算時間隨著客戶點規模增加，呈現近似線性的成長。至於求解品質方面，平均劣於塔布搜尋法7.21%；平均優於掃描法2.62%，其中有三題求解結果超越掃描法；平均劣於節省法1.02%，其中有兩題求解結果超越節省法。在叢集性明顯的客戶點分布型態下，幾可與塔布搜尋法並駕齊驅，且計算時間上達到大幅度之節省。