【CVRP】基于matlab节约算法求解带容量的VRP问题【含Matalb源码 157期】
一、简介
VRP问题描述：
假设在一个供求关系系统中，车辆从货源取货，配送到对应的若干配送点。车辆存在最大载货量，且配送可能有时间限制。需要合理安排取货时间，组织适当的行车路线，使用户需求得到满足，同时使某个代价函数最小，比如总工作时间最少、路径最短等。
可以看出TSP问题是VRP问题的一种简单特殊形式。因此，VRP也是一种NP hard 问题。
带有容量约束的车辆路径问题(CVRP)
该模型很难拓展到VRP的其他场景,并且不知道具体车辆的执行路径，因此对其模型继续改进。
C-W节约算法：
基本思想是把各点单独与货源相连，构成若干条仅含一个配送点的线路，总费用为两倍从原点到各点的距离费用；然后计算将点 i 和点 j 连接在一条线路上费用节约值：
S(i,j)=Coi+Cio+Coj+Cjo−(Coi+Cij+Cjo)=Coi+Coj+CijS(i,j)=Coi+Cio+Coj+Cjo−(Coi+Cij+Cjo)=Coi+Coj+Cij
具体步骤：
（1）计算节约值S(i,j)，按从大到小排序
（2）考虑表格中最大元素 Smax（i,j）Smax（i,j），对应点i和j，按条件进行操作：
[*]若i和j均不在构成线路上，则得到线路 o -> i ->j ->o，转到（3）
[*]若i或j在已构成线路上，但不是内点 0 -> i ->o，则可连接，转到（3）
[*]若i和j位于已构成不同线路上，且均不是内点，则连接得到线路，转到（3）
[*]若i和j位于已构成的同一线路，则不连接，转到（3）
（3）划去第i行和第j列，即i点不能再到其他点，j点也不能由其他店到达
（4）若所有元素均被划去，则得到完整线路，算法终止；否则，在没有划去的元素中选最大元素，转至（2）。
遗传算法（GA）：
基本思想是种群仿照生物遗传进化，通过基因交叉、突变繁衍出子代，形成新的种群，然后根据种群中每个个体的适应值，淘汰代价较高的个体，余下个体继续繁衍。在VRP问题中具体步骤如下：
（1）设定种群大小，设定繁衍代数，对所有的配送点编号，每个个体对应于所有配送点的一种排序，初始化得到初始种群；
（2）通过交叉、变异操作，形成子代，与原来的父代形成新的种群；
（3）根据载货量限制，确定何时回货源取货，再结合代价标准，对种群中的每个个体计算适应值；
（4）根据适应值，淘汰代价高的父代子代，余下个体形成新的种群，繁衍代数增加1；
（5）若繁衍代数达到（1）中设定的初值，停止繁衍，返回代价最小的个体，即最为最佳的配送次序；否则，返回（2）
三、源代码
clear
clc
tic
%% 用importdata这个函数来读取文件
rc208=importdata('rc208.txt');
cap=1000;
%% 提取数据信息
vertexs=rc208(:,2:3); %所有点的坐标x和y
customer=vertexs(2:end,:); %顾客坐标
cusnum=size(customer,1); %顾客数
demands=rc208(2:end,4); %需求量
h=pdist(vertexs);
dist=squareform(h); %距离矩阵，满足三角关系，暂用距离表示花费c=dist
%% CW法构造CVRP初始解
=init_CVRP(rc208,cap);
initNV=size(init_vc,1);
str1=['车辆行驶总距离 =' num2str(init_TD)];
disp(str1)
str2=['车辆使用数目 =' num2str(initNV)];
disp(str2)
%% 判断最优解是否满足时间窗约束和载重量约束，0表示违反约束，1表示满足全部约束
flag=Judge(init_vc,cap,demands);
%% 检查最优解中是否存在元素丢失的情况，丢失元素，如果没有则为空
DEL=Judge_Del(init_vc);
%% 画出配送路线图
vertexs=rc208(:,2:3); %所有点的坐标x和y
draw_Best(init_vc,vertexs);
toc
三、运行结果
四、备注
版本：2014a
页:
[1]