• 软件:1158
  • 资讯:38209|
  • 收录网站:95634|

IT精英团

禁忌搜索算法求解带时间窗的车辆路径问题(下 附MATLAB代码)

禁忌搜索算法求解带时间窗的车辆路径问题(下 附MATLAB代码)

浏览次数:
评论次数:
编辑: mb5fd86d8699f84
信息来源: 51CTO博客
更新日期: 2021-03-25 17:10:14
摘要

小编终于把上次剩下的TS求VRPTW代码写完了,由于小编用的只是最简单的邻域结构,禁忌表的设计也比较简单,所以代码的求解结果远不如大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码),但是肯定要比构造启发式方法好很多CW节约算法构造VRPTW初始解(附MATLAB代码),大家做一个简单的参考吧。后期如果小伙伴想进一步改进这个代码,可以考虑更换一些复杂的邻域结构,或

  • 资讯详情


小编终于把上次剩下的TS求VRPTW代码写完了,由于小编用的只是最简单的邻域结构,禁忌表的设计也比较简单,所以代码的求解结果远不如大规模邻域搜索(LNS)求解带时间窗的车辆路径问题(VRPTW)(附MATLAB代码),但是肯定要比构造启发式方法好很多CW节约算法构造VRPTW初始解(附MATLAB代码),大家做一个简单的参考吧。

后期如果小伙伴想进一步改进这个代码,可以考虑更换一些复杂的邻域结构,或者可以考虑给违反约束的解以惩罚

可以参考下面两篇文献:

  1. Taillard, Éric, et al. "A tabu search heuristic for the vehicle routing problem with soft time windows." Transportation science 31.2 (1997): 170-186.

  2. Cordeau, Jean-François, Gilbert Laporte, and Anne Mercier. "A unified tabu search heuristic for vehicle routing problems with time windows." Journal of the Operational research society 52.8 (2001): 928-936.


VRPTW比CVRP问题多了时间窗约束,后台一位小伙伴问我,如何对变量进行约束,其实VRPTW问题中,小编在代码中加了这样一段代码,看不懂没关系,因为只是部分片片段,但小编想强调的是,在邻域结构的设计中,只有满足容量约束和时间窗约束的邻域才被接受


 1%考虑时间窗约束和容量约束,如果不满足,则不能插入到该位置
2Ld=leave_load( route,demands);  %该路径上车辆离开仓库时的载货量
3% 计算该路线上车辆对顾客的开始服务时间,还计算车辆返回仓库的时间
4%bs:车辆对顾客的开始服务时间,back:车辆返回集配中心的时间
5[bs,back]= begin_s( route,a,s,dist);
6%遍历该路径上每个顾客判断是否都满足时间窗约束,flag=1表示顾客都满足时间窗约束,flag=0表示存在不满足时间窗约束的顾客
7flag=1;
8for h=1:lrr
9    if (bs(h)>b(route(h)))||(back>L)
10        flag=0;
11        break
12    end
13end
14%如果容量约束和时间窗约束都满足,则可以把路径j上的顾客i插入到路径k上的位置p
15if (Ld<=cap)&&(flag==1)
16    route_before=vc_copy{j};
17    route_before(route_before==i)=[];             %将顾客i从路径j中移除
18    vc_copy{j}=route_before;
19    route_k=vc_copy{k};
20    vc_copy{k}=route;
21    vc_c=deal_vehicles_customer(vc_copy);
22    %                     e=minLen(vc_c);
23    TD=travel_distance(vc_copy,dist);
24    %                     f=TD;
25    f=size(vc_c,1)*cusnum+TD;
26    NS=[NS;i,j,k,p,f];
27    vc_copy{k}=route_k;
28end


标签: Java
人工鱼群算法求解CVRP问题
« 上一篇
Google Guice之注入方式
下一篇 »
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
你会是第一个来这里评论的人吗?
最近发布资讯
更多