掃描法

用手机看条目

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

掃描法(Sweep Algorithm)

目錄

什麼是掃描法

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

掃描法的步驟[1]

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

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

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

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

掃描法的相關案例

案例一

一個卡車公司,廂式貨車的載貨量是10000件,完成所有取貨任務一般需要整整一天的時間。需要多少條運輸路線?

取貨點的數據

Image:扫描法.jpg

掃描法的解“Sweep” Method Solution

Image:扫描法1.jpg

參考文獻

  1. 1.0 1.1 夏新海.物流配送車輛調度優化研究[D].武漢理工大學,2004年
  2. 鄧宇佑.求解醫院運輸部門運輸中心個數最佳化之研究(D).成功大學工業管理研究所碩士論文,1991年
本條目對我有幫助6
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您認為本條目還有待完善,需要補充新內容或修改錯誤內容,請編輯條目

本条目由以下用户参与贡献

Zfj3000,Dan,Tracy.

評論(共0條)

提示:評論內容為網友針對條目"掃描法"展開的討論,與本站觀點立場無關。

發表評論請文明上網,理性發言並遵守有關規定。

MBA智库
打开APP

以上内容根据网友推荐自动排序生成