节约里程法—单配送中心CVRP求解

发布时间：2024-11-30 13:49

无人机配送正在逐步解决配送过程中的货物损坏问题 #生活知识# #科技生活# #科技改变生活# #无人机配送#

众所周知，节约里程法是一种贪婪算法，虽然求解质量比不上蚁群或者遗传算法，但是在求解精度要求不高的情况下，却可以快速求解得到一个接近最优的满意解。正因为如此，节约里程法很多情况下和其他启发式算法进行结合，由节约里程法快速计算得到的可行解作为启发式算法的初始解。

下面由我来详细讲解节约里程法的算法思想和求解思路

一、算法思想

节约里程法，顾名思义，是根据里程的节约值的大小来规划线路的。假设有一个单配送中心以及10个客户节点构成的配送系统，在满足载重约束的情况下，计算最少的车辆数和最短的总路径长度，如果用节约里程法进行求解，其算法思想解析如下：

1、首先将10个点分别和配送中心连线构成一个环路，计算从配送中心出发到达该点并回到配送中心的总里程。

2、然后，从任意点开始，做节点的合并，即将相邻的两个点的两条子路径合并成一条子路径，合并后的环路的总里程一定比原来两条子路径的总里程之和要少，计算减少的里程数。其实也就是得到10个点中任意两个点合并成一条子路径后的节约里程表。

3、对得到的节约里程表按照节约值降序排列，然后进行节点的合并和约束判断。

4、优先合并节约值大的两点，合并完一对点之后就要对节约里程表进行修订，去掉已合并的点和对应的节约值，重新降序排列，继续合并剩余的未合并的节点，注意，在合并的时候要分辨是在节点的左边还是右边进行插入，另外，考虑到载重约束，某一条子路径的总的转载量达到载重要求时就立即回到配送中心，停止加入新的节点。

5、如此，按照步骤4不断操作，等所有的节点都被合并之后，就完成了节约里程法的cvrp的求解了。

插入核心的合并过程的代码，如下图中代码所示：

for i=(ii+1):size(svt)

if (svt(i,2)==solut(1,1))&&(isempty(find(svt(i,3)==solut))==1)&&((A(3,(svt(i,3)+1))+zhuang)<=rong); %从最大的小于初始解对应的最大节约值对应的坐标判断（左坐标等于最优解的左坐标，并且右坐标不等于最优解的右坐标，并且容量不超）

solut=[svt(i,3),solut]; %如满足条件，将右坐标加到路径的左侧

sv=sv+svt(i,1);

zhuang=A(3,(svt(i,3)+1))+zhuang;

elseif (svt(i,2)==solut(1,length(solut)))&&(isempty(find(svt(i,3)==solut))==1)&&((A(3,(svt(i,3)+1))+zhuang)<=rong);

solut=[solut,svt(i,3)];%如满足条件，将右坐标加到路径的右侧

sv=sv+svt(i,1);

zhuang=A(3,(svt(i,3)+1))+zhuang;

elseif (svt(i,3)==solut(1,1))&&(isempty(find(svt(i,2)==solut))==1)&&((A(3,(svt(i,2)+1))+zhuang)<=rong);

solut=[svt(i,2),solut];

sv=sv+svt(i,1);

zhuang=A(3,(svt(i,2)+1))+zhuang;

elseif (svt(i,3)==solut(1,length(solut)))&&(isempty(find(svt(i,2)==solut))==1)&&((A(3,(svt(i,2)+1))+zhuang)<=rong);