扫描算法-------最邻近算法、最近插入法、CW节约法

扫描算法-------最邻近算法、最近插入法、CW节约法

三、程序设计思想

（一）、扫描算法+最邻近算法。

扫描算法采用极坐标来表示各需求点的区位，然后任取一需求点为起始点，定其角度为零度，以顺时钟或逆时钟方向，以车容量为限制条件进行服务区域之分割，再建构车辆排程路线。

最邻近算法，任取一点作为线路的起点，寻求与上一次加进线路中点的距离最近的点，把此点加到路线中去，然后重复上一步，直到所有的点都已经加进去。

第一步，以配送中心为原点，建立坐标轴，然后对所有的客户需求点的位置进行坐标系的变换，使其散落在以配送中心为原点的坐标轴里，并按在此坐标轴里客户需求所在的极限进行分组（以客户点位置与原点形成的正切值为标准），并且把在y轴上的点单独分组。然后统计出在第一，二，三，四象限以及y轴正半轴和负半轴的点的个数。

第二步，对分组好的需求点用起泡法分别按正切值从小到大排列，按逆时针方向合并成一个数组。在这个数组中，根据需求量的限制进行分配区域，并统计各个区需求点个数。

第三步，用最邻近法求各区的总距离。在数组中设置零一变量（作用：当为0时说明未被取过，为1说明已被取过），来求得各区的距离，最后把各区的总距离相加得最后方案的总距离。

（二）、扫描算法+CW节约法。

扫描法同上。

C-W节约算法选取起点，将起点与其它各点连接，得到n –1条线路，对不违背限制条件的所有可连接点计算节约值，节约值越大使总费用减少越多，总距离越小。

第一步，扫描分组同上。

第二步，对分组好的需求点用起泡法分别按正切值从小到大排列，按逆时针方向合并成一个数组。在这个数组中，根据需求量的限制进行分配区域，并统计各个区需求点个数。

第三步，在分配好的服务区域中，将起点与其它各点连接，得到n –1条线路，对不违背限制条件的所有可连接点计算节约值，用起泡法对节约值进行排序。

第四步，设置变量，使每个点只能被取不超过2次，避免回路。根据节约值选好路径，然后算好各区的总距离，加总得到最后方案的总距离

（三）、扫描法+最近插入法。

扫描法同上。

最近插入法关键是依序选择最合适的未分配的节点在路线中进行最佳位置的插入,以构建配送路线,直至不存在可行插入节点时新增一条初始路线。

第一步：扫描法分区组同上。

第二步：以原点为起点，先选一条离其最近的点连接，形成一个往返式子回路。

第三步：在剩下的节点中，寻找一个离子回路中最近的节点，加入子回路中。并设置变量，使每个点只能被取不超过2次，避免回路。

第四步：剩下的点中找一点，再在子回路中找到一个弧，使弧的两端节点到该点的距离之和减去弧长的值最小，去掉该弧，加入新点连接的弧。其余点重复第四步，直到所有的节点都加入到子回路中。

第五步：根据插入法选好路径，然后算好各区的总距离，加总得到最后方案的总距离。