数模校赛 |
您所在的位置：网站首页 › 车辆行驶路线规划 › 数模校赛 |
数模校赛
|
一、问题描述 杨浦区卫计委通过捐赠和购买组织了一批重达50吨防疫物资需要分发到本区内的各街道（具体分配方案如下表）。假设卫计委雇用了运输公司的一辆载重量为5吨的卡车负责将物资分别从卫计委运送到各街道办事处，请建立数学模型给出详细且最经济的运输方案。已知：卡车的每公里运输成本为: 20元+载货量*10元/吨。综合考虑时间和运输成本, 给出一个最优运输方案。 物资分配方案（单位：吨） 街道 物资量 街道 物资数量 定海路街道 2 殷行街道 3 平凉路街道 3 大桥街道 5 江浦路街道 4 五角场街道 7 四平路街道 5 新江湾城街道 6 控江路街道 3 长海路街道 6 长白新村街道 3 延吉新村街道 3 （不好意思，我不会插入表格…） 二、模型建立 设每个街道的物资需求量为，配送中心的物资需求量；表示到的阻抗；表示当卡车第次从配送中心出发运送物资时，各地的需求量；表示当卡车第次从配送中心出发运送物资时，从到行驶的过程中的载货量。 定义0-1规划决策变量： 三、模型求解——自适应蚁群算法（Matlab） %蚁群算法TSP问题 n = 13; %城市个数（包括配送中心） load D; %城市间距离，自己到自己的距离应设置为eps（后面要取倒数） %种群初始化，参数的设置 m = 75; %蚂蚁数量 alpha = 1; beta = 5; vol = 0.2; Q = 10; Heu_F = 1./D; Tau = ones(n,n); %信息素矩阵 Table = zeros(m,n); Table2 = zeros(m,n);% 用来记录蚂蚁到哪个城市时，返回过出发点（用“1”表示返回出发点） iter = 1; %迭代次数初值 iter_max = 100; %最大迭代次数 Route_best = zeros(iter_max,21); Length_best = zeros(iter_max,1); Length_ave = zeros(iter_max,1); %迭代寻找最佳路径 for iter = 1:iter_max Table(:,1) = 0; %从配送中心（0）出发 %逐个蚂蚁选择 for i = 1:m k = 5; citys_index = 0:12; target = 0; De = [0,2,3,4,5,3,3,3,5,7,6,6,3]; %需求向量 ban_number = 0; %已经被禁止的城市个数 j = 1; Table2(i,1) = 5; ban = zeros(1,13); while(1) if De(target+1) == 0 ban_number = ban_number + 1; ban(ban_number) = target; end if ban_number == 13 Table2(i,j) = 0; break; end if k == 0 k = 5; end allow_index = ~ismember(citys_index,ban); %citys_index中有元素属于禁忌表中元素的时候取1，取反后变成0，产生的是逻辑数组 allow = citys_index(allow_index); %得到还未去过的城市代号 P = allow; %计算城市间转移概率 if Table2(i,j) == 5 && j ~= 1 for g = 1:length(allow) P(g) = Tau(1,allow(g)+1)^alpha * Heu_F(1,allow(g)+1)^beta; end else for g = 1:length(allow) P(g) = Tau(ban(ban_number)+1,allow(g)+1)^alpha * Heu_F(ban(ban_number)+1,allow(g)+1)^beta; end end P = P/sum(P); %轮盘赌法选择下一个访问城市 Pc = cumsum(P); %累加函数，把前几个累加到1 target_index = find(Pc >= rand); target = allow(target_index(1)); %选定的下一个要去的城市 j = j+1; Table(i,j) = target; %确定此时蚂蚁还背着多少吨货物 if k-De(target+1) > 0 k = k-De(target+1); De(target+1) = 0; Table2(i,j) = k-De(target+1); elseif k-De(target+1) == 0 k = k-De(target+1); De(target+1) = 0; Table2(i,j) = 5; else De(target+1) = De(target+1)-k; k = 0; Table2(i,j) = 5; end end end %计算各个蚂蚁的路径要花的钱 Length = zeros(m,1); for i = 1:m Route = Table(i,:);%取出一条路径 Length(i) = Length(i) + D(1,Route(2)+1)*20; j = 2; while (Table2(i,j) ~= 0) if Table2(i,j) == 5 Length(i) = Length(i) + D(Route(j)+1,1)*20 + D(Route(j+1),1)*20; else Length(i) = Length(i) + D(Route(j)+1,Route(j+1)+1)*(20 + Table2(i,j)*10); end j = j+1; end Length(i) = Length(i) + D(Route(j)+1,1)*20; end [min_Length,min_index] = min(Length); %找到最短距离的值的大小和位置 Length_best(iter,:) = min_Length; %此次迭代的路线最小值记录 Route_best(iter,:) = Table(min_index,:); %此次迭代的路线最小值记录 Fuzhu(iter,:) = Table2(min_index,:); %此次迭代的路线最小值记录 Length_ave(iter) = mean(Length); Delta_Tau = zeros(n,n); %逐个蚂蚁计算 for i = 1:m Delta_Tau(Table(i,2)+1,1) = Delta_Tau(Table(i,2)+1,1) + Q/Length(i); Delta_Tau(1,Table(i,2)+1) = Delta_Tau(1,Table(i,2)+1) + Q/Length(i); j = 2; while (Table2(i,j) ~= 0) if Table2(i,j) == 5 Delta_Tau(Table(i,j)+1,1) = Delta_Tau(Table(i,j)+1,1) + Q/Length(i); Delta_Tau(1,Table(i,j)+1) = Delta_Tau(1,Table(i,j)+1) + Q/Length(i); Delta_Tau(Table(i,j+1)+1,1) = Delta_Tau(Table(i,j+1)+1,1) + Q/Length(i); Delta_Tau(1,Table(i,j+1)+1) = Delta_Tau(1,Table(i,j+1)+1) + Q/Length(i); else Delta_Tau(Table(i,j)+1,Table(i,j+1)+1) = Delta_Tau(Table(i,j)+1,Table(i,j+1)+1) + Q/Length(i); Delta_Tau(Table(i,j+1)+1,Table(i,j)+1) = Delta_Tau(Table(i,j+1)+1,Table(i,j)+1) + Q/Length(i); end j = j+1; end Delta_Tau(Table(i,j)+1,1) = Delta_Tau(Table(i,j)+1,1) + Q/Length(i); Delta_Tau(1,Table(i,j)+1) = Delta_Tau(1,Table(i,j)+1) + Q/Length(i); end Tau = (1-vol)*Tau+Delta_Tau; %迭代次数加1，清空路径记录表 iter = iter+1; Table = zeros(m,n); %清空路线表 Table2 = zeros(m,n); end我当时做这个题，参考的是车辆路径规划问题。很多论文中的例题都是有多辆车可以进行配送，虽然我们的这个题目只有一辆车，但是我认为在不带时间窗的情况下，一辆车与多辆车并没有本质区别。 不过，即便是自适应的蚁群算法在求解这个问题的时候，收敛性也非常的差。可视化以后，这个问题尤其明显。我所查阅的论文中并没有将迭代过程可视化的，所以我特别想知道到底是我程序设计的问题，还是说它本来就是收敛性不好的。欢迎大家和我交流鸭~ |
建立数学模型如下： 
(1)式即目标函数，表示运输距离最小且运输成本最小的目标； 其中， 
其中，为卡车从到的运输成本；为，两地之间的距离是一个常数，这里取=2000。 (2)式约束卡车的载重量为5吨,每次运完5吨都会返回配送中心；(3)式表示每次运送物资过程中，每个街道需求的减少量等于本次卡车运往该街道的物资量；(4)式表示卡车每到一个街道，都会尽量用此时的载货量满足其需求量；(5)式表示除必须返回配送中心的情况外，只有当街道j仍有需求且卡车上仍有物资时，卡车才会前往街道；(6),(7)两式表示卡车每次从配送中心出发运送物资时，每个地点最多经过1次。【本文地址】
今日新闻 |
推荐新闻 |