扫描法
出自 MBA智库百科(https://wiki.mbalib.com/)
扫描法(Sweep Algorithm)
目录 |
扫描法是指Gillett和Miller于1974年所提出的求解车辆路线问题(Vehicle Routing Problem,VRP)的方法,此方法属于先分群再排路线的方式[1]。该方法采用极坐标来表示各需求点的区位,然后任取一需求点为起始点,定其角度为零度,以顺时钟或逆时钟方向,以车容量为限制条件进行服务区域之分割,再藉由Lin与Kernighan的交换法进行需求点的排序,建构车辆排程路线[2]。简单地理解,就是在地图或方格图中确定所有站点(含仓库)的位置;自仓库始沿任一方向向外划一条直线。沿顺时针或逆时针方向旋转该直线到与某站点相交。继续旋转,直到最大容量使得排定各路线上每个站点的顺序使行车距离最短。排序时可以使用“水滴”法或求解“流动推销员”问题的任何算法。
扫描法的步骤[1]
扫描法分为两阶段性步骤:
第一阶段:利用极坐标来表示各需求点的区位,然后任取一需求点为起点,以车辆容量为分群的约束,再以该需求点为零度按顺时针或逆时针的方向,进行顾客的扫描分群。
第二阶段:依据求解旅行商问题的算法,求解各顾客群的排程。
Solomon于1983年将此方法应用于求解时窗限制车辆路线问题(vehicle routing problems with time windows,VRPTW),与原扫描法不同点在于第二阶段的求解各顾客群排程,其以插入法进行各顾客群的排程,并检查时间可行性,若有顾客点无法满足时间窗的约束,则先排除此顾客点。若所有的顾客群都以排入行程,则所有的顾客点都已被服服务,则完成路线的建构;若有顾客点尚未被服务,则沿原扫描方向,将剩余的尚未服务的顾客点重复进行扫描与插入的步骤,直到所有的顾客点都被服务。
一个卡车公司,厢式货车的载货量是10000件,完成所有取货任务一般需要整整一天的时间。需要多少条运输路线?
取货点的数据
扫描法的解“Sweep” Method Solution