-
掃描法
鎖定
Gillett和Miller於1974年所提出的求解車輛路線問題(Vehicle Routing Problem,VRP)的方法,此方法屬於先分羣再排路線的方式[1]。該方法採用極座標來表示各需求點的區位,然後任取一需求點為起始點,定其角度為零度,以順時鐘或逆時鐘方向,以車容量為限制條件進行服務區域之分割,再借由Lin與Kernighan的交換法進行需求點的排序,建構車輛排程路線[2]。
- 中文名
- 掃描法
- 提 出
- Gillett和Miller
- 採 用
- 極座標
- 表 示
- 各需求點的區位
掃描法掃描法的步驟
掃描法分為兩階段性步驟:
第一階段:利用極座標來表示各需求點的區位,然後任取一需求點為起點,以車輛容量為分羣的約束,再以該需求點為零度按順時針或逆時針的方向,進行顧客的掃描分羣。
第二階段:依據求解旅行商問題的算法,求解各顧客羣的排程。
掃描法詳情
Solomon於1983年將此方法應用於求解時窗限制車輛路線問題(vehicle routing problems with time windows,VRPTW),與原掃描法不同點在於第二階段的求解各顧客羣排程,其以插入法進行各顧客羣的排程,並檢查時間可行性,若有顧客點無法滿足時間窗的約束,則先排除此顧客點。若所有的顧客羣都以排入行程,則所有的顧客點都已被服服務,則完成路線的建構;若有顧客點尚未被服務,則沿原掃描方
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:8次歷史版本
- 最近更新: 无名小卒hrf