编辑实验 创建词条
人大经济论坛-经管百科

扫描法 发表评论(0) 编辑词条

目录

扫描法(Sweep Algorithm)

什么是扫描法 编辑本段回目录

  Gillett和Miller于1974年所提出的求解车辆路线问题Vehicle Routing Problem,VRP)的方法,此方法属于先分群再排路线的方式[1]。该方法采用极坐标来表示各需求点的区位,然后任取一需求点为起始点,定其角度为零度,以顺时钟或逆时钟方向,以车容量为限制条件进行服务区域之分割,再藉由LinKernighan的交换法进行需求点的排序,建构车辆排程路线。

扫描法的步骤[1] 编辑本段回目录

  扫描法分为两阶段性步骤:

  第一阶段:利用极坐标来表示各需求点的区位,然后任取一需求点为起点,以车辆容量为分群的约束,再以该需求点为零度按顺时针或逆时针的方向,进行顾客的扫描分群。

  第二阶段:依据求解旅行商问题的算法,求解各顾客群的排程。

  Solomon于1983年将此方法应用于求解时窗限制车辆路线问题vehicle routing problems with time windowsVRPTW),与原扫描法不同点在于第二阶段的求解各顾客群排程,其以插入法进行各顾客群的排程,并检查时间可行性,若有顾客点无法满足时间窗的约束,则先排除此顾客点。若所有的顾客群都以排入行程,则所有的顾客点都已被服服务,则完成路线的建构;若有顾客点尚未被服务,则沿原扫描方向,将剩余的尚未服务的顾客点重复进行扫描与插入的步骤,直到所有的顾客点都被服务。

参考文献 编辑本段回目录

  1. 1.0 1.1 夏新海.物流配送车辆调度优化研究[D].武汉理工大学,2004年
  2. 邓宇佑.求解医院运输部门运输中心个数最佳化之研究(D).成功大学工业管理研究所硕士论文,1991年
经管百科已经为您找到更多关于“扫描法”的相关信息,点击查看>>

附件列表

→如果您认为本词条还有待完善,请 编辑词条

词条内容仅供参考,如果您需要解决具体问题
(尤其在法律、医学等领域),建议您咨询相关领域专业人士。
0

标签: 扫描法 VRP VRPTW Vehicle Routing Problem Vehicle routing problems with time windows 插入法 旅行商问题 时窗限制车辆路线问题 武汉理工大学 车辆路线问题 顾客

收藏到: Favorites  

同义词: 暂无同义词

关于本词条的评论 (共0条)发表评论>>