禁忌搜索算法求解带时间窗的车辆路径问题(下 附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