禁忌搜索算法简介
禁忌搜索算法(Tabu Search Algorithm，简称TS)起源于对于人类记忆功能的模仿，是一种亚启发式算法(meta-heuristics)。它从一个初始可行解(initial feasible solution)出发，试探一系列的特定搜索方向(移动)，选择让特定的目标函数值提升最多的移动。为了避免陷入局部最优解，禁忌搜索对已经历过的搜索过程信息进行记录，从而指导下一步的搜索方向。
禁忌搜索是人工智能的一种体现，是局部搜索的一种扩展。禁忌搜索是在邻域搜索(local search)的基础上，通过设置禁忌表(tabu list)来禁忌一些曾经执行过的操作，并利用藐视准则来解禁一些优秀的解。
禁忌搜索算法求解VRPTW
对邻域搜索类算法而言，采取的搜索算子和评价函数至关重要。下面详细介绍代码中针对VRPTW的插入算子和评价函数。
插入算子：
评价函数：
算法概述
```
clear clc %% 用importdata这个函数来读取文件 c208=importdata('c208.txt');
cap=700; %车辆负荷 maxIter=300; %最大迭代次数
E=c208(1,5); %仓库时间窗开始时间 L=c208(1,6); %仓库时间窗结束时间 vertexs=c208(:,2:3); %所有点的坐标x和y customer=vertexs(2:end,:); %顾客坐标 cusnum=size(customer,1); %顾客数 vecnum=cusnum; %车辆数 demands=c208(2:end,4); %需求量 a=c208(2:end,5); %顾客时间窗开始时间[a[i],b[i]] b=c208(2:end,6); %顾客时间窗结束时间[a[i],b[i]] s=c208(2:end,7); %客户点的服务时间 h=pdist(vertexs); dist=squareform(h); %距离矩阵，满足三角关系，暂用距离表示花费c[i][j]=dist[i][j] vehiclescustomer=cell(vecnum,1); %每辆车所经过的顾客 %% CW法构造VRPTW初始解 %输出initvc 每辆车所经过的顾客 %输出initTD 所有车行驶的总距离 %输出initvl 每辆车的装载量 %输出violateINTW 判断是否违背时间窗约束，0代表不违背，1代表违背 [initvc,initTD,initvl,violateINTW] = initTW(c208,L,demands,a,b,s,dist,cap); %% 初始化各个车辆配送路线，每个安装场地由一辆车配送，有d2需求的安装场地在前面加上加工车间用0表示 % [ initvc ] = initroute( vehiclescustomer ); % initTD=traveldistance(initvc,dist); S=initvc; %当前解 eS=minLen(S); %当前解各路径中所经过的最少数目的顾客数 initNV=size(S,1); %所用车辆数目 Sbest=S; %全局最优解 % f=initNV*cusnum+eS; % fBest=initNV*cusnum+eS; f=initNV*cusnum+initTD; fBest=initNV*cusnum+init_TD; TbList=zeros(cusnum,initNV); %禁忌表 TbLength=20; %禁忌长度 NS=neighborhood(S,L,cusnum,demands,a,b,s,dist,cap); %S的邻域 [subNS]=subNeighbor(TbList,NS,fBest); % non-tabu or allowed by aspiration
%% Tabu Search iter=0; count=0; while iter copy]=insert(S,i,j,k,p); if fS copy; S=Scopy; NS=neighborhood(Scopy,L,cusnum,demands,a,b,s,dist,cap); [subNS]=subNeighbor(TbList,NS,fBest); %更新禁忌表 for l=1:cusnum for h=1:initNV if TbList(l,h)~=0 TbList(l,h)=TbList(l,h)-1; end end end if TbList(i,j)==0 TbList(i,j)=TbLength; else TbList(i,j)=0; end
else if TbList(i,j)==0S=S_copy;NS=neighborhood(S,L,cusnum,demands,a,b,s,dist,cap);[subNS]=subNeighbor(TbList,NS,fBest);% 更新禁忌表for l=1:cusnumfor h=1:initNVif TbList(l,h)~=0TbList(l,h)=TbList(l,h)-1;endendendTbList(i,j)=TbLength; endendelsebreakenditer=iter+1;
end Sbest=dealvehiclescustomer(Sbest); bestNV=size(Sbest,1); bestTD=traveldistance(Sbest,dist); DEL=JudgeDel(Sbest); % 检查最优解中是否存在元素丢失的情况 % 计算每辆车配送路线上在各个点开始服务的时间，还计算返回仓库时间 bsv= beginsv(Sbest,a,s,dist ); [ violateTW ] = JudgeTW( Sbest,bsv,b,L ); % 判断是否违背时间窗约束，0代表不违背，1代表违背 ```
