写在前面
垃圾运输问题可以看作是一个NP完全问题，但很遗憾的是，目前我们所掌握的数学知识并不足以让我们找到一个有效找到NP完全问题全局最优解的算法，甚至，在数学界中还无法确定NP完全问题是否真的存在找到全局最优解的有效算法。在本问题中，我选择通过遍历和迭代来寻找最优解，当然，我会给出一些约束条件来对其做出限制，以此来限制遍历的方向，加快遍历的速度。
问题
其实这个作业一共有3问，但本文着重介绍第1个问题的解决方法，因此只将第1个问题截图出来。
在本问题中，我们可以知道：
- 每个垃圾站的编号，横坐标，纵坐标以及垃圾量
- 运输车的装载量为6t
- 运输车的速度为40km/h
- 运输车只能工作4h
- 运输车空载时费用为0.4元/公里
- 运输车运载时的费用为1.8元/吨公里
- 运输车每次装垃圾需要花费10min，即1/6h
问：需要多少辆运输车，每辆运输车的路径以及总费用
问题分析
从问题中，我们得出了许多关于运输车的约束条件：
运输车的装载量仅有6t，这就约束了运输车在选点规划路线时，经过的路线垃圾总量必须小于6t，一旦装完第n个点，在找n+1个点时，发现地图上剩余点的垃圾量都超过了运输车还剩下的装载量，则垃圾车必须返回垃圾处理厂，即(0,0)点。
运输车只能工作4h，也就是说，虽然运输车的装载量约束了一辆车一趟仅能装多少垃圾，但是如果装完回来卸货后，如有剩余时间，则可以继续出发。
运输车的速度以及装垃圾所花费的时间都是约束运输车的工作时间。
运输车的运载费用分为两部分，一部分是空载时，0.4元/公里。另一部分是装有垃圾时，1.8元/吨公里。也就是说，空载时花费的费用最少，一旦装有垃圾，则装的越多，花费越多，例如：当我经过第1点时（假设我已经知道最优路线），我需要将第1点的垃圾装入，则，我从第1点到第2点之间的花费为：
其中：表示第1个点的垃圾量（吨），表示第1点到第2点之间的距离。
因为垃圾量随着经过的站点增加而增加，因此在路途中的花费几乎是越来越大。如果是第n个点到第n+1个点之间的花费，则将上式中的“1”改为“n”，“2”改为“n+1”即可。
因此，我们可以约定：让费用越低的状态走越长的路，让费用越高的状态走越短的路，在路线中，最后的点应该最接近垃圾处理厂(0,0)，最初的点应该是路线中最远离垃圾处理厂(0,0)。这样一条最优路线中费用就能最大限度地降低。
模型建立
我们可以建立这样的模型：
最小运输费的目标函数为：
其中，这里的下标表示点的编号，而非路线的顺序，例如：0i表示从原点到编号为 i 的点，即：表示从原点到编号为 i 点的距离。表示第 i 点的站的垃圾量
需要注意的是：在本式中 k 并不是顺序数列，而是需要通过约束原则选取出来的无序点的集合。
通过对问题的分析，我们可以给出以下的约束条件：
- 路线的第1个点应该是距离原点最远的点（我们需要空载状态下走最远，而不能让装着垃圾走最远，若装垃圾跑最远，返程时消耗的费用要比空载大）
- 当前点与原点的距离应该比下一点与原点的距离要大，（我们必须先跑到最远点，然后往回运垃圾）
- 当前点与下一点的距离应该是所有可选点中最短的（一样的原因，我们不能装着垃圾跑太远）
- 下一点的垃圾量应该小于运输车剩余装载量
- 下一点为可选点，即下一点尚未经过，垃圾未被装走
其中，表示第 i 站是否已经被选择过了，0表示还未选择，1表示已经被选择过了。D已经在上面阐述过，此处不再赘述
满足以上条件的点，则是我们选择的点，当一条路线中，其余可选点都不满足条件，则该路线的车之间从路线的最后一个点上返回原点即可。
可以看到，我并没有对时间进行约束，这是因为，在数据预处理时，我粗略地计算了运输车在规定时间内能经过很多点，但装载量却不能承受特别多的点，因此装载量的对路线的约束很大，而时间对路线的约束可以忽略。
这样，我们就确定了一条最优路线，当然，在题目中，一条最优路线是不能经过全部的点的，所以我们需要不断遍历：
- 通过上述的约束条件找到最优路线
- 将路线中经过的点标记为不可选择
- 判断是否还剩可选择的点，若有，则返回1，若无则说明全部点都遍历完，退出遍历
这样，我们就能找到多条最优路线，将所有的点都按照约束条件遍历完成，只需要在编程时，一旦选择一点，则将该点的编号记录保存在路线矩阵中，每一条路线的点的编号都记录下来，只需要算出路线的费用，就是最小费用，计算出路线的时间，判断车辆能否通过，若能通过，还剩多少时间，能否再走一条路，这样我们就能选择派出多少辆车。
Matlab代码
clear, clc, close
%% 生成数据
%x，y表示垃圾集中点坐标，m表示垃圾量，N表示坐标
x=[3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 17 25 9 9 30 0];
y=[2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 18 12 16 7 20 20 12 0];
t=[1.5 1.5 0.55 1.2 0.85 1.3 1.2 2.3 1.4 1.5 1.1 2.7 1.8 1.8 0.6 1.5 0.8 1.5 0.8 1.4 1.2 1.8 1.4 1.6 1.6 1.0 2.0 ...
1.0 2.1 1.2 1.9 1.3 1.6 1.2 1.5 1.3 0.0];
a = 1:37;
N = 1:37;
dots=[N;x;y;t;a];%N为编号，x为横坐标，y为纵坐标，t为垃圾量，a为0-1变量，0表示该点尚未经过，1表示该点已经经过了
%画图
plot(dots(2,:),dots(3,:),'r*')
dots(5,:)=0;
jg = zeros(12,12); %选择路线矩阵，(i,j)=k 表示第i条路线的第j个经过的点为编号 k 的点
%% 寻找最优路线
for i=1:20%遍历20次，寻找20条路线
sum=0;
j1=1;
s=0;
m=37;
i3=37;
for j=1:36%第一次循环，找初始点，即最远的节点
if(sqrt(dots(2,j)^2+dots(3,j)^2)>s&&dots(5,j)==0) %满足：1.该点是所有未经过点中的最远点 2.该点并未经过 则：
s=sqrt(dots(2,j)^2+dots(3,j)^2);%记录该点到起始点的距离
jg(i,j1)=dots(1,j);%将该点记录为第i条路线的第1个点
sum=dots(4,j);%垃圾量
m=j;%找到最远的节点，并把标号赋值给m
else continue;%若不满足条件，则进入下一次循环，判断下一个点
end
end
dots(5,m)=1;%最远的节点更改为已选取的状态
j1=j1+1;
while 1
js=0;%初始化纳入路线的点的判断
q=1000;%初始化点间距离
for k=1:36
%若满足以下条件则进入if：
%1.此点与上一点之间距离比其他点与上一点的距离更短
%2.距离原点的距离小于上一点（防止拖着更多垃圾跑得更远，费用更多）
%3.该点垃圾量小于剩余装载量
%4.该点尚未经过
if(q>sqrt((dots(2,m)-dots(2,k))^2+(dots(3,m)-dots(3,k))^2)&&(dots(2,m)^2+dots(3,m)^2)>(dots(2,k)^2+dots(3,k)^2)&&(6-sum)>dots(4,k)&&dots(5,k)==0)
q=sqrt((dots(2,m)-dots(2,k))^2+(dots(3,m)-dots(3,k))^2);%两点之间的距离
js=1;%标记为存在符合条件的点
jg(i,j1)=dots(1,k);%将该点编号放入第i条路线的第j1个点
i3=k;%记录编号
else continue;%如果此点不符合条件，则判断下一个点
end
end
dots(5,i3)=1;%将此点标记为已经过
sum=sum+dots(4,i3); %第i条路线目前为止的垃圾总量
j1=j1+1;%该路线增加一个点
m=i3;%将该点标为上一点，进入下一次循环
if(dots(2,i3)==0&&dots(3,i3)==0||js==0)%若没有任何点满足条件，即唯一符合条件的只有上一个点本身，则说明该路线以达到最优，该路线规划完成，退出循环
break;
end
end
end
%% 计算费用
kcost=0;%第1个点的花费
zcost=0;%除第1个点外其它点的总花费
allcost=0;%总花费
n=0;%初始化编号
nl=0;%初始化第1个点的编号
nn=0;%初始化
sum=0;%初始化垃圾装载量
%路线矩阵遍历：第u1路线的第u2个点
for u1=1:12
sum=0;
nl=jg(u1,1);%获取第1个点的编号
if(nl~=0)%若编号不为0.则说明路线存在
kcost=kcost+0.4*sqrt(dots(2,nl)^2+dots(3,nl)^2);%计算当前路线的第1个点的花费
else continue%若不存在该路线，则进入下一次循环
end
for u2=2:12
if jg(u1,u2)~=0%若此点不为0，则该路线还未走完
nn=jg(u1,u2);%获取第u1路线的第u2点的编号
else continue;%若路线走完了，则进入下一条路线
end
sum=sum+dots(4,nl);%记录经过当前垃圾站的垃圾吨数
zcost=zcost+sum*1.8*sqrt((dots(2,nn)-dots(2,nl))^2+(dots(3,nn)-dots(3,nl))^2);%计算除第1个点外其它点的花费
nl=nn;%将当前点作为上一节点
end
sum=sum+dots(4,nl);
zcost=zcost+sum*1.8*sqrt(dots(2,nl)^2+dots(3,nl)^2);%返回垃圾处理场的花费
end
allcost=zcost+kcost;%总花费
zcost
kcost
%% 计算路线所花费的时间
i=1:12;
time=[i];%建立时间矩阵
time(1,:)=0;%初始化时间矩阵
n1=0;
n2=0;
n3=0;
for i=1:12
if(jg(i,1)~=0)
n3=jg(i,1);
time(1,i)=sqrt(dots(2,n3)^2+dots(3,n3)^2)/40+(1/6); % 第i条路线，从原点到第1个点的时间花费
n2=n2+1;
else continue
end
for j=2:12
if(jg(i,j)~=0)
n1=jg(i,j);
n2=n2+1;
else continue
end
time(1,i)=time(1,i)+sqrt((dots(2,n1)-dots(2,n3))^2+(dots(3,n1)-dots(3,n3))^2)/40+(1/6); %第i条路线，当前点到下一个点的时间花费
n3=n1;%令n1的点为当前点
end
time(1,i)=time(1,i)+sqrt(dots(2,n3)^2+dots(3,n3)^2)/40;%返回垃圾处理厂的时间
end
代码分析：
代码前面输入点的信息将其存储起来，我将点的信息画了个图表示出来
代码核心分为三个部分：
第一部分是选择最优路线，在该部分中，按照模型建立时所说的约束条件来进行遍历，距离取两点之间的线段作为距离，假设运输车不发生转弯等情况。一共遍历20次，这个值可以自己定，但尽量别太小，因为太小时可能走不完所有的点。
jg为路线矩阵，最终路线矩阵数据如下：
该图中，第1条路线为：37-30-29-27-15-37，因0表示没有点，因此我用37号点表示垃圾处理厂(0,0)，其它点同理。
第二部分是根据路线矩阵，计算运输费用：
计算得：
第三部分是根据路线矩阵，计算每条路线的时间花费：
可以看到，没有一条路线的时间超过运输车工作的4h，所以每条路线都是可行路线，其实在一开始进行数据预处理时就粗略地计算了以下，运输车的时间很充裕，对其约束性很小，关键是运输车的载量，对路线的约束更大。因此我们在讨论约束条件时只讨论了载量限制，现在才讨论时间限制。
根据计算，第9条路线与第10条路线时间相加小于4h，其余路线不可相加，因此我们需要9辆运输车，因为运输车的启动并不需要消耗费用，因此，我想选9辆车还是10辆车出发都可以，嘿嘿。
结语
至此，该问题就解决啦。如果你看到这里，非常感谢！也希望我的博客能够帮助到你。文章来源：https://www.toymoban.com/news/detail-402368.html
本人是一名大三学生，文章质量还是解法都不是最优的，也许我解出来的并不是最优解，还有大神能够解出费用比我更低，希望能够一起讨论，若文章中有什么看不懂或错误地方，请批评指正！文章来源地址https://www.toymoban.com/news/detail-402368.html
到了这里，关于数学模型——垃圾运输问题，运输车的路径以及数量选择（含matlab代码）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
