掃描法

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

掃描法（Sweep Algorithm）

什麼是掃描法

　　掃描法是指Gillett和Miller於1974年所提出的求解車輛路線問題（Vehicle Routing Problem,VRP）的方法，此方法屬於先分群再排路線的方式^[1]。該方法採用極坐標來表示各需求點的區位，然後任取一需求點為起始點，定其角度為零度，以順時鐘或逆時鐘方向，以車容量為限制條件進行服務區域之分割，再藉由Lin與Kernighan的交換法進行需求點的排序，建構車輛排程路線^[2]。簡單地理解，就是在地圖或方格圖中確定所有站點（含倉庫）的位置；自倉庫始沿任一方向向外劃一條直線。沿順時針或逆時針方向旋轉該直線到與某站點相交。繼續旋轉，直到最大容量使得排定各路線上每個站點的順序使行車距離最短。排序時可以使用“水滴”法或求解“流動推銷員”問題的任何演算法。

[編輯]

掃描法的步驟^[1]

　　掃描法分為兩階段性步驟：

　　第一階段：利用極坐標來表示各需求點的區位，然後任取一需求點為起點，以車輛容量為分群的約束，再以該需求點為零度按順時針或逆時針的方向，進行顧客的掃描分群。

　　第二階段：依據求解旅行商問題的演算法，求解各顧客群的排程。

　　Solomon於1983年將此方法應用於求解時窗限制車輛路線問題（vehicle routing problems with time windows，VRPTW），與原掃描法不同點在於第二階段的求解各顧客群排程，其以插入法進行各顧客群的排程，並檢查時間可行性，若有顧客點無法滿足時間窗的約束，則先排除此顧客點。若所有的顧客群都以排入行程，則所有的顧客點都已被服服務，則完成路線的建構；若有顧客點尚未被服務，則沿原掃描方向，將剩餘的尚未服務的顧客點重覆進行掃描與插入的步驟，直到所有的顧客點都被服務。

[編輯]