ɨ跨 - 管理知识

ɨ跨

外汇网2021-06-22 14:26:47 53

什么是扫描法

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

扫描法的步骤^[1]

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

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

第二阶段：根据求解旅游商困难的算法，求解各顾客群的排程。

Solomon于1983年将此方法应用于求解时窗制约车辆路线困难（vehicle routing problems with time windows，VRPTW），与原扫描法不同点在于第二阶段的求解各顾客群排程，其以插入法执行各顾客群的排程，并检查时间可行性，若有顾客点无法满足时间窗的约束，则先消除此顾客点。若所有的顾客群都以排入行程，则所有的顾客点都已被服服务，则完成路线的建构；若有顾客点仍未被服务，则沿原扫描方向，将余下的仍未服务的顾客点重复执行扫描与插入的步骤，直到所有的顾客点都被服务。

参考文献

↑ ^1.0^1.1 夏新海.物流配送车辆调度优化研究[D].武汉理工大学,2004年

↑ 邓宇佑.求解医院运输部门运输中心个数最佳化之研究(D).成功大学工业治理研究所硕士论文,1991年

ɨ跨

推荐文章

热门文章

推荐文章

热门文章