最优化算法案例学习(禁忌搜索,混合算法)

1、大作业汇报Shanghai Maritime University禁忌搜索案例学习禁忌搜索案例学习目录目录小组分工禁忌搜索算法带软时间窗的集货与送货多车辆路径问题节约算法考虑碳排放的开环取送货路径优化问题 数值实验禁忌搜索算法禁忌搜索算法Fred Glover禁忌搜索禁忌搜索(Tabu Search)是局部邻域搜索算法的推是局部邻域搜索算法的推广广,Fred Glover在在1986年提出这个概念年提出这个概念,进而形成进而形成一套完整算法一套完整算法. 人类在选择过程中具有人类在选择过程中具有记忆功能记忆功能，比如走迷宫时，比如走迷宫时，当发现有可能又回到某个地点的时候总会有意识当发现有可能

2、又回到某个地点的时候总会有意识地避开先前选择的方向而选择其他的可能性，这地避开先前选择的方向而选择其他的可能性，这样就可以确定性的样就可以确定性的避开迂回搜索避开迂回搜索。禁忌搜索算法禁忌搜索算法只进不退的原则只进不退的原则用用TabuTabu表锁住退路，将表锁住退路，将近期历史搜索过程存放在禁忌表中，防止算近期历史搜索过程存放在禁忌表中，防止算法迂回搜索。法迂回搜索。不以局部最优作为停止准则，算法接受劣解，不以局部最优作为停止准则，算法接受劣解，只要不在禁忌表的较好解都可作为下一次迭只要不在禁忌表的较好解都可作为下一次迭代的初始解。代的初始解。邻域选优的规则模拟了人类的记忆功能，找邻域选优的

3、规则模拟了人类的记忆功能，找过的地方都记下来，不再找第二次。一定迭过的地方都记下来，不再找第二次。一定迭代次数后，早期进入禁忌表解被解禁退出代次数后，早期进入禁忌表解被解禁退出核心思想禁忌搜索算法禁忌搜索算法步骤第一步 选定一个初始解xnow;令禁忌表 ;第二步 若满足终止准则,转第四步; 否则,在xnow的邻域N(xnow)中选出满足禁忌要求的候选集C-N(xnow) ,转第三步;第三步 在C-N(xnow)中选一个评价值最好的解xbest,令xnow=xbest,更新禁忌表H,转第二步;第四步 输出计算结果,停止.概念禁忌表：为避免迂回搜索，记录之前搜索过的解或状态的表禁忌对象：禁忌表中被

4、禁的那些变化元素禁忌长度：禁忌的步数特赦原则：对一些显著提高解质量而处于禁忌的操作解禁H 禁忌搜索算法禁忌搜索算法Xx T0k TxS1 kkNGk |kSxO p tsxsxSxTkxSx xsAxSCL, TxLS xSxL xCxCxxxcx,禁忌搜索举例：禁忌搜索举例：TSPTSP问题问题四城市非对称四城市非对称TSP问题问题 初始初始解解x0=(ABCD)，f(x0)=4，邻域映射为两个城市顺序对，邻域映射为两个城市顺序对换的换的2opt，始、终点都是，始、终点都是A城市。城市。1禁忌搜索举例：禁忌搜索举例：TSPTSP问题问题ABCDBCDABC对换评价值CD4.5BC7.5BD8

5、第第1步步解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解f(x0)=4第第2步步A B D CBCDABC3对换评价值CD4.5BC3.5BD4.5 f(x1)=4.5禁忌搜索举例：禁忌搜索举例：TSPTSP问题问题第第3步步解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解f(x0)=3.5第第4步步 f(x1)=7.5A C D BBCDAB3C2对换评价值CD8BC4.5BD7.5A C B DBCDAB23C1对换评价值CD4.5BC4.5BD3.5禁忌搜索举例：禁忌搜索举例：TSPTSP问题问题第第5步步解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候

6、选解f(x0)=4.5第第6步步 f(x1)=8A D B CBCDAB01C2对换评价值CD7.5BC8BD4.5A D C BBCDAB30C1对换评价值CD3.5BC4.5BD4禁忌对象禁忌对象解的简单变化解的简单变化 解向量分量的变化解向量分量的变化目标值变化目标值变化 情况情况1：禁忌对象为简单的解变化：禁忌对象为简单的解变化xnow=(ABCDE)，f(xnow)=45，H=(ABCDE;45) Can_N(xnow)=(ACBDE;43)，(ABCDE;45)，(ADCBE;45)，(ABEDC;59)，(ABCED;44) xnext=(ACBDE )情况情况2：禁忌对象为分量

7、变化：禁忌对象为分量变化xnow=(ACBDE)，f(xnow)=43，H=(B,C) Can_N(xnow)=(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)，(AEBDC;59) xnext=(ACBED) 情况情况3：禁忌对象为目标值变化：禁忌对象为目标值变化xnow=(ABCDE)，f(xnow)=45，H=45 Can_N(xnow)=(ABCDE;45)，(ACBDE;43)，(ADCBE;45)，(ABEDC;59)，(ABCED;44) xnext=(ACBDE)特赦原则特赦原则基于评价值的规则，若出现基于评价值的规则，若出现一个解的目标值

8、好于前面任一个解的目标值好于前面任何一个最佳候选解，可特赦；何一个最佳候选解，可特赦；基于最小错误的规则，若所基于最小错误的规则，若所有对象都被禁忌，特赦一个有对象都被禁忌，特赦一个评价值最小的解；评价值最小的解；基于影响力的规则，可以特基于影响力的规则，可以特赦对目标值影响大的对象。赦对目标值影响大的对象。其它原则其它原则禁忌长度与评价函数禁忌长度与评价函数（1）t可以为常数，易于实现；可以为常数，易于实现；（2） ，t是可以变化的数，是可以变化的数，tmin和和tmax是确定的。是确定的。 tmin和和tmax根据问题的规模确定，根据问题的规模确定，t的大小主要依据实际问题的大小主要依据实

9、际问题实验和设计者的经验。实验和设计者的经验。（3） tmin和和tmax的动态选择。的动态选择。minmax,ttt评价函数评价函数 （1）直接评价函数，通过目标函数的运算得到评价函数；）直接评价函数，通过目标函数的运算得到评价函数； （2）间接评价函数，构造其他评价函数替代目标函数，）间接评价函数，构造其他评价函数替代目标函数，应反映目标函数的特性，减少计算复杂性。应反映目标函数的特性，减少计算复杂性。禁忌长度禁忌长度记忆频率信息和终止规则记忆频率信息和终止规则n记忆频率信息记忆频率信息（1）静态频率信息：解、对换或目标值在计算中出现的频率；）静态频率信息：解、对换或目标值在计算中出现的频

10、率；（2）动态频率信息：从一个解、对换或目标值到另一个解、对换）动态频率信息：从一个解、对换或目标值到另一个解、对换或目标值的变化趋势。或目标值的变化趋势。n终止规则终止规则 （1）确定步数终止，无法保证解的效果，应记录当前最优解；）确定步数终止，无法保证解的效果，应记录当前最优解； （2）频率控制原则，当某一个解、目标值或元素序列的频率）频率控制原则，当某一个解、目标值或元素序列的频率超过一个给定值时，终止计算；超过一个给定值时，终止计算； （3）目标控制原则，如果在一个给定步数内，当前最优值没）目标控制原则，如果在一个给定步数内，当前最优值没有变化，可终止计算。有变化，可终止计算。论文阅读

11、论文阅读带软时间窗的集货与送货多带软时间窗的集货与送货多车辆路径问题节约算法车辆路径问题节约算法祁文祥祁文祥 陆志强陆志强 孙小明孙小明交通运输工程学报交通运输工程学报2010关键词关键词：多车辆路径问题、集货与送货、启发式节约算法、软时间窗多车辆路径问题、集货与送货、启发式节约算法、软时间窗背景介绍背景介绍随着第三方物流的兴起,很多企业为降低物流成本,越来越倾向于把原来由自己承担的运输任务外包给第三方物流企业,而多批次、小批量的送货模式也成多批次、小批量的送货模式也成为各企业降低库存风险的重要手段为各企业降低库存风险的重要手段。另一方面,第三方物流企业出于自身运营成本考虑,在满足客户运输在满

12、足客户运输要求的前提下需要采取有效的路径优化方案要求的前提下需要采取有效的路径优化方案,才能实才能实现自身利益的最大化现自身利益的最大化问题描述问题描述物流配送网络物流配送网络( ,)GV A集货需求点集集货需求点集P配货需求点集配货需求点集D所有需求点集所有需求点集NPD任务集任务集1,2,.,Tm租用货车的费用租用货车的费用货车的运输费用货车的运输费用时间惩罚费用时间惩罚费用变量定义变量定义客户客户j 的集货需求量的集货需求量jMjN第第m个任务要求货物送到的时间窗个任务要求货物送到的时间窗,mmijijab货车货车 k 执行第执行第 m 个任务从客户个任务从客户 i 的出发时间，的出发时

13、间，该任务配送货物至该任务配送货物至 j 点点mijks货车货车 k 执行第执行第 m 个任务到达客户个任务到达客户 j 的时间，该的时间，该任务从任务从 i 点点 出发出发mijkr客户客户j 的送货需求量的送货需求量变量定义变量定义单个车辆的租赁费用单个车辆的租赁费用fmkP早到晚到时间惩罚系数早到晚到时间惩罚系数, a b装货时间装货时间U卸货时间卸货时间W货车货车k 在执行任务在执行任务m 时的时间惩罚值时的时间惩罚值车辆最大装载量车辆最大装载量L车辆最大行驶距离车辆最大行驶距离D单个车辆的租赁费用单个车辆的租赁费用g变量定义变量定义节点节点 i 和节点和节点 j 之间的距离之间的距离

14、ijdijkw0-1变量，货车变量，货车k 完成任务完成任务m取取1，否则，否则0mkxmnky0-1 变量，货车变量，货车k 从客户从客户 i 行驶到客户行驶到客户 j 则取则取1，否则，否则0决策变量决策变量0-1变量，货车变量，货车k 完成任务完成任务m及任务及任务 n 取取1，否则，否则0VRPPDTW数学模型数学模型minijijkmkk Kk K i V j Vk K m TzfkgdwP（1）ijkjhki V k Kh V k KwwS.T.（2）001i kjki Vk Kww（3）jjj Vj VMNJ（4）VRPPDTW数学模型数学模型jijkjji V k KNwNM（

15、5）jjhkjjh V k KMwNM（6）ijkiji V j Vw dD（7）jjj Vj VMNJ（8）mijijki V k KqLw（9）VRPPDTW数学模型数学模型0.5()mnkmknkyxx（9）0.5()0.5mknkmnkxxy（10）mmijkijijkrts（11）/ijijtdv（12）, , ,kK i j hV m nT mn（13）启发式节约算法启发式节约算法本研究模型在传统VRP问题上进行了扩展,增加了集货和送货任务的时间窗要求以及多辆车可供配置的条件,因此,对于任意访问节点,需要将运输成本的节省值、时间惩罚费用、租车费用综合考虑才能构造有效可行的启发式节约

16、算法。( , )ixyis i jcc( , )mks i jP启发式节约算法启发式节约算法单车完成 i 到 j 的总任务：mkijPc多车完成 i 到 j 的总任务：0 jijixfccc0mkjixPfcc求解结果求解结果最大载货量/t10货车最多可调用数量10n速度/(kmkm-1)40每辆车的固定租车费用/元300最大行驶距离/km240每公里运输费用/(元km-1)2固定装货时间/h0.5时间窗上界惩罚系数/(元h-1)200固定卸货时间/h0.5时间窗下界惩罚系数/(元h-1)300参数设置求解结果求解结果任务数任务数租车数量租车数量/辆辆总费用总费用/元元计算时间计算时间/s货车

17、平均利用率货车平均利用率%平局有效运输时间比平局有效运输时间比102147813.293.287.6208478067.591.482.930137872163.288.385.4401610290266.485.388.5502213753475.681.684.8算例结果论文改进论文改进考虑碳排放的开环取送货路考虑碳排放的开环取送货路径优化问题径优化问题关键词关键词：车辆路径优化、集货与送货、碳排放、禁忌搜索、蚁群算法车辆路径优化、集货与送货、碳排放、禁忌搜索、蚁群算法论文改进论文改进创新点：创新点：将车辆在集货配货中碳排放成本加入到模型中将车辆在集货配货中碳排放成本加入到模型中建立了开环

18、模式下的路径优化问题建立了开环模式下的路径优化问题对比了禁忌搜索、蚁群算法对本问题的求解效果对比了禁忌搜索、蚁群算法对本问题的求解效果提出了蚁群紧急搜索混合搜索算法，数值实验表明该算提出了蚁群紧急搜索混合搜索算法，数值实验表明该算法求得的解质量最高法求得的解质量最高论文改进论文改进123456每个客户的需求量较小违反时间窗产生惩罚费用假设路上交通状况良好先取货后配货需求确定不可拆分开环路径考虑碳排放的开环考虑碳排放的开环取送货路径优化问题取送货路径优化问题假设条件：假设条件：论文改进论文改进标号含义客户集货点集合， 客户配送点集合默认由1配送给N+1网络图节点集合， 0表示车库所有弧的集合，

19、顾客i 的需求量， （若 则 ，若 ，则 ）1,2,3,., PN1,2,.,2 DNNN0VPD( , )| ,Ai ji jV ijiqiP0iqiD0iqPDVA论文改进论文改进标号含义车辆 k 的最大装载量车辆 k 的集合辆 k 车 最大行驶里程顾客 i 时间窗起始时间， 顾客 i 时间窗起始时间，iL TKkLiE TkQiViV论文改进论文改进标号含义单位时间延迟成本单位时间等待成本单位超标碳排放的惩罚成本节点 i 的等待时间 节点 i 延迟时间iwpcpiwdpiViV论文改进论文改进标号含义车辆 k 经过弧（i,j）的碳排放量弧（i,j）的运输成本，与运输距离成正比最大允许碳排

20、放量，若超过此值则按超过量惩罚燃油转换系数 车辆k 的的燃油消耗系数,kkabi jcWki jW论文改进论文改进表示节点之间是否有配送关系的变量，如有则该值为1，否则为0；决策变量含义0-1变量，当车辆 k 经过弧（i，j）则为1 ，否则为00-1变量，当任务i被指派给k 时为1，否则为0kiyki jxi jMIPMIP模型模型22220111011122101min() KNKNNNNkkjijijwidikjkijiiKNNkcijkijFfxx cpwppWW011 NKkjjkxK（1）式为目标函数，最小化运营成本，其中第一项为车辆的启用成本，第二项为车辆的行驶成本，第三项为车辆的等待成本，第四项为车辆的惩罚成本，第五项为车辆的碳排放成本；（2）式表示车辆数限制（1）（2）MIPMIP模型模型21 i,jV,ij, NkijikjxykK20 i,jV,ij, NkijjkixykK（3）表示 与 的函数关系ki jxkiy（4）表示 与 的函数关系ki jxkjy11 /0 KikkyiV（5）式表示一个客户点的配送或集货需求只能由一辆车来完成 ,/0,=1, ikjkijyyi jVkK（6）表示每一对取送货点须同一车辆完成（3）（4）（5）（6）MIPM