亲爱的MBA智库百科用户:


过去的17年,百科频道一直以免费公益的形式为大家提供知识服务,这是我们团队的荣幸和骄傲。 然而,在目前越来越严峻的经营挑战下,单纯依靠不断增加广告位来维持网站运营支出,必然会越来越影响您的使用体验,这也与我们的初衷背道而驰。 因此,经过审慎地考虑,我们决定推出VIP会员收费制度,以便为您提供更好的服务和更优质的内容。


MBA智库百科VIP会员,您的权益将包括: 1、无广告阅读; 2、免验证复制。


当然,更重要的是长期以来您对百科频道的支持。诚邀您加入MBA智库百科VIP会员,共渡难关,共同见证彼此的成长和进步!



MBA智库百科项目组
2023年8月10日
百科VIP
未登录
无广告阅读
免验证复制
1年VIP
¥ 9.9
支付方式:
微信支付
支付宝
PayPal
购买数量:
1
应付金额:
9.9
汇率换算:
1.32
美元(USD)
  • 美元(USD)
  • 加元(CAD)
  • 日元(JPY)
  • 英镑(GBP)
  • 欧元(EUR)
  • 澳元(AUD)
  • 新台币(TWD)
  • 港元(HKD)
  • 新加坡(SGD)
  • 菲律宾(PHP)
  • 泰铢(THB)

按当月汇率换算,

包含手续费

打开手机微信 扫一扫继续付款
立即开通
PayPal支付后,可能会遇到VIP权益未及时开通的情况,请您耐心等待,或者联系百科微信客服:mbalib888。
温馨提示:当无法进去支付页面时,可刷新后重试或更换浏览器
开通百科会员即视为同意《MBA智库·百科会员服务规则》

支付成功

全球专业中文经管百科,由121,994位网友共同编写而成,共计436,064个条目

扫描法

用手机看条目

出自 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年
本条目对我有帮助13
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您认为本条目还有待完善,需要补充新内容或修改错误内容,请编辑条目投诉举报

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

Zfj3000,Dan,Tracy.

评论(共0条)

提示:评论内容为网友针对条目"扫描法"展开的讨论,与本站观点立场无关。

发表评论请文明上网,理性发言并遵守有关规定。

打开APP

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

官方社群
下载APP
告MBA智库百科用户的一封信
亲爱的MBA智库百科用户: 过去的17年,百科频道一直以免费公益的形式为大家提供知识服务,这是我们团队的荣幸和骄傲。 然而,在目前越来越严峻的经营挑战下,单纯依靠不断增加广告位来维持网站运营支出,必然会越来越影响您的使用体验,这也与我们的初衷背道而驰。 因此,经过审慎地考虑,我们决定推出VIP会员收费制度,以便为您提供更好的服务和更优质的内容。 MBA智库百科VIP会员(9.9元 / 年,点击开通),您的权益将包括: 1、无广告阅读; 2、免验证复制。 当然,更重要的是长期以来您对百科频道的支持。诚邀您加入MBA智库百科VIP会员,共渡难关,共同见证彼此的成长和进步!
MBA智库百科项目组
2023年8月10日

闽公网安备 35020302032707号

添加收藏

    新建收藏夹

    编辑收藏夹

    20