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

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 TxS 1 kk NGk | k SxO p tsxsxSxT k xSx xsAxSC L , Tx L S xSx L xCxCxx xcx, 禁忌搜索举例：禁忌搜索举例：TSPTSP问题问题 四城市非对称四城市非对称TSP问题问题 初始初始解解x0=(ABCD)，f(x0)=4，邻域映射为两个城市顺序对，邻域映射为两个城市顺序对 换的换的2opt，始、终点都是，始、终点都是A城

5、市。城市。1 禁忌搜索举例：禁忌搜索举例：TSPTSP问题问题 ABCD BCD A B C 对换评价值 CD4.5 BC7.5 BD8 第第1步步 解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解 f(x0)=4 第第2步步 A B D C BCD A B C3 对换评价值 CD4.5 BC3.5 BD4.5 f(x1)=4.5 禁忌搜索举例：禁忌搜索举例：TSPTSP问题问题 第第3步步 解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解 f(x0)=3.5 第第4步步 f(x1)=7.5 A C D B BCD A B3 C2 对换评价值 CD8 BC4.5 BD7

6、.5 A C B D BCD A B23 C1 对换评价值 CD4.5 BC4.5 BD3.5 禁忌搜索举例：禁忌搜索举例：TSPTSP问题问题 第第5步步 解的形式解的形式 禁忌对象及长度禁忌对象及长度 候选解候选解 f(x0)=4.5 第第6步步 f(x1)=8 A D B C BCD A B01 C2 对换评价值 CD7.5 BC8 BD4.5 A D C B BCD A B30 C1 对换评价值 CD3.5 BC4.5 BD4 禁忌对象禁忌对象 解的简单变化解的简单变化 解向量分量的变化解向量分量的变化 目标值变化目标值变化 情况情况1：禁忌对象为简单的解变化：禁忌对象为简单的解变化

7、xnow=(ABCDE)，f(xnow)=45，H=(ABCDE;45) Can_N(xnow)=(ACBDE;43)，(ABCDE;45)，(ADCBE;45)， (ABEDC;59)，(ABCED;44) xnext=(ACBDE ) 情况情况2：禁忌对象为分量变化：禁忌对象为分量变化 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)

8、，f(xnow)=45，H=45 Can_N(xnow)=(ABCDE;45)，(ACBDE;43)，(ADCBE;45)， (ABEDC;59)，(ABCED;44) xnext=(ACBDE) 特赦原则特赦原则 基于评价值的规则，若出现基于评价值的规则，若出现 一个解的目标值好于前面任一个解的目标值好于前面任 何一个最佳候选解，可特赦；何一个最佳候选解，可特赦； 基于最小错误的规则，若所基于最小错误的规则，若所 有对象都被禁忌，特赦一个有对象都被禁忌，特赦一个 评价值最小的解；评价值最小的解； 基于影响力的规则，可以特基于影响力的规则，可以特 赦对目标值影响大的对象。赦对目标值影响大的对象

9、。 其它原则其它原则 禁忌长度与评价函数禁忌长度与评价函数 （1）t可以为常数，易于实现；可以为常数，易于实现； （2） ，t是可以变化的数，是可以变化的数，tmin和和tmax是确定的。是确定的。 tmin和和tmax根据问题的规模确定，根据问题的规模确定，t的大小主要依据实际问题的大小主要依据实际问题 实验和设计者的经验。实验和设计者的经验。 （3） tmin和和tmax的动态选择。的动态选择。 minmax ,ttt 评价函数评价函数 （1）直接评价函数，通过目标函数的运算得到评价函数；）直接评价函数，通过目标函数的运算得到评价函数； （2）间接评价函数，构造其他评价函数替代目标函数，）

10、间接评价函数，构造其他评价函数替代目标函数， 应反映目标函数的特性，减少计算复杂性。应反映目标函数的特性，减少计算复杂性。 禁忌长度禁忌长度 记忆频率信息和终止规则记忆频率信息和终止规则 n记忆频率信息记忆频率信息 （1）静态频率信息：解、对换或目标值在计算中出现的频率；）静态频率信息：解、对换或目标值在计算中出现的频率； （2）动态频率信息：从一个解、对换或目标值到另一个解、对换）动态频率信息：从一个解、对换或目标值到另一个解、对换 或目标值的变化趋势。或目标值的变化趋势。 n终止规则终止规则 （1）确定步数终止，无法保证解的效果，应记录当前最优解；）确定步数终止，无法保证解的效果，应记录当

11、前最优解； （2）频率控制原则，当某一个解、目标值或元素序列的频率）频率控制原则，当某一个解、目标值或元素序列的频率 超过一个给定值时，终止计算；超过一个给定值时，终止计算； （3）目标控制原则，如果在一个给定步数内，当前最优值没）目标控制原则，如果在一个给定步数内，当前最优值没 有变化，可终止计算。有变化，可终止计算。 论文阅读论文阅读 带软时间窗的集货与送货多带软时间窗的集货与送货多 车辆路径问题节约算法车辆路径问题节约算法 祁文祥祁文祥 陆志强陆志强 孙小明孙小明 交通运输工程学报交通运输工程学报2010 关键词关键词：多车辆路径问题、集货与送货、启发式节约算法、软时间窗多车辆路径问题、

12、集货与送货、启发式节约算法、软时间窗 背景介绍背景介绍 随着第三方物流的兴起,很多企业为降低物流成本, 越来越倾向于把原来由自己承担的运输任务外包给 第三方物流企业,而多批次、小批量的送货模式也成多批次、小批量的送货模式也成 为各企业降低库存风险的重要手段为各企业降低库存风险的重要手段。另一方面,第三 方物流企业出于自身运营成本考虑,在满足客户运输在满足客户运输 要求的前提下需要采取有效的路径优化方案要求的前提下需要采取有效的路径优化方案,才能实才能实 现自身利益的最大化现自身利益的最大化 问题描述问题描述 物流配送网络物流配送网络( ,)GV A 集货需求点集集货需求点集P 配货需求点集配货

13、需求点集D 所有需求点集所有需求点集NPD 任务集任务集1,2,.,Tm 租用货车的费用租用货车的费用 货车的运输费用货车的运输费用 时间惩罚费用时间惩罚费用 变量定义变量定义 客户客户j 的集货需求量的集货需求量 j M j N 第第m个任务要求货物送到的时间窗个任务要求货物送到的时间窗 , mm ijij ab 货车货车 k 执行第执行第 m 个任务从客户个任务从客户 i 的出发时间，的出发时间， 该任务配送货物至该任务配送货物至 j 点点 m ijk s 货车货车 k 执行第执行第 m 个任务到达客户个任务到达客户 j 的时间，该的时间，该 任务从任务从 i 点点 出发出发 m ijk

14、r 客户客户j 的送货需求量的送货需求量 变量定义变量定义 单个车辆的租赁费用单个车辆的租赁费用f mk P 早到晚到时间惩罚系数早到晚到时间惩罚系数 , a b 装货时间装货时间 U 卸货时间卸货时间 W 货车货车k 在执行任务在执行任务m 时的时间惩罚值时的时间惩罚值 车辆最大装载量车辆最大装载量L 车辆最大行驶距离车辆最大行驶距离D 单个车辆的租赁费用单个车辆的租赁费用 g 变量定义变量定义 节点节点 i 和节点和节点 j 之间的距离之间的距离 ij d ijk w 0-1变量，货车变量，货车k 完成任务完成任务m取取1，否则，否则0 mk x mnk y 0-1 变量，货车变量，货车k

15、 从客户从客户 i 行驶到客户行驶到客户 j 则取则取1，否则，否则0 决策变量决策变量 0-1变量，货车变量，货车k 完成任务完成任务m及任务及任务 n 取取1，否则，否则0 VRPPDTW数学模型数学模型 min ijijkmk k Kk K i V j Vk K m T zfkgdwP （1） ijkjhk i V k Kh V k K ww S.T. （2） 00 1 i kjk i Vk K ww （3） jj j Vj V MNJ （4） VRPPDTW数学模型数学模型 jijkjj i V k K NwNM （5） jjhkjj h V k K MwNM （6） ijkij i

16、V j V w dD （7） jj j Vj V MNJ （8） m ijijk i V k K qLw （9） VRPPDTW数学模型数学模型 0.5() mnkmknk yxx （9） 0.5()0.5 mknkmnk xxy （10） mm ijkijijk rts （11） / ijij tdv （12） , , ,kK i j hV m nT mn （13） 启发式节约算法启发式节约算法 本研究模型在传统VRP问题上进行了扩展,增加 了集货和送货任务的时间窗要求以及多辆车可 供配置的条件,因此,对于任意访问节点,需要将 运输成本的节省值、时间惩罚费用、租车费用 综合考虑才能构造有效可

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

18、数租车数量租车数量/辆辆总费用总费用/元元计算时间计算时间/s货车平均利用率货车平均利用率%平局有效运输时间比平局有效运输时间比 102147813.293.287.6 208478067.591.482.9 30137872163.288.385.4 401610290266.485.388.5 502213753475.681.684.8 算例结果 论文改进论文改进 考虑碳排放的开环取送货路考虑碳排放的开环取送货路 径优化问题径优化问题 关键词关键词：车辆路径优化、集货与送货、碳排放、禁忌搜索、蚁群算法车辆路径优化、集货与送货、碳排放、禁忌搜索、蚁群算法 论文改进论文改进 创新点：创新点：

19、 将车辆在集货配货中碳排放成本加入到模型中将车辆在集货配货中碳排放成本加入到模型中 建立了开环模式下的路径优化问题建立了开环模式下的路径优化问题 对比了禁忌搜索、蚁群算法对本问题的求解效果对比了禁忌搜索、蚁群算法对本问题的求解效果 提出了蚁群紧急搜索混合搜索算法，数值实验表明该算提出了蚁群紧急搜索混合搜索算法，数值实验表明该算 法求得的解质量最高法求得的解质量最高 论文改进论文改进 1 2 3 4 5 6 每个客户的需求量较小 违反时间窗产生惩罚费用 假设路上交通状况良好 先取货后配货 需求确定不可拆分 开环路径 考虑碳排放的开环考虑碳排放的开环 取送货路径优化问题取送货路径优化问题 假设条件

20、：假设条件： 论文改进论文改进 标号含义 客户集货点集合， 客户配送点集合 默认由1配送给N+1 网络图节点集合， 0表示车库 所有弧的集合， 顾客i 的需求量， （若 则 ，若 ，则 ） 1,2,3,., PN 1,2,.,2 DNNN 0VPD ( , )| ,Ai ji jV ij i q iP0 i qiD 0 i q P D V A 论文改进论文改进 标号含义 车辆 k 的最大装载量 车辆 k 的集合 辆 k 车 最大行驶里程 顾客 i 时间窗起始时间， 顾客 i 时间窗起始时间， i L T K k L i E T k Q iV iV 论文改进论文改进 标号含义 单位时间延迟成本

21、单位时间等待成本 单位超标碳排放的惩罚成本 节点 i 的等待时间 节点 i 延迟时间 i w p c p i w d p iV iV 论文改进论文改进 标号含义 车辆 k 经过弧（i,j）的碳排放量 弧（i,j）的运输成本，与运输距离成正比 最大允许碳排放量，若超过此值则按超过量惩罚 燃油转换系数 车辆k 的的燃油消耗系数 , kk ab i j c W k i j W 论文改进论文改进 表示节点之间是否有配送关系的变量，如有 则该值为1，否则为0； 决策变量含义 0-1变量，当车辆 k 经过弧（i，j）则为1 ，否则为0 0-1变量，当任务i被指派给k 时为1，否则为0 k i y k i

22、j x i j MIPMIP模型模型 2222 0 1110111 22 101 min () KNKNNNN kk jijijwidi kjkijii KNN k cij kij Ffxx cpwp pWW 0 11 NK k j jk xK （1）式为目标函数，最小化运营成本，其中第一项为车辆的启用成本， 第二项为车辆的行驶成本，第三项为车辆的等待成本，第四项为车辆的惩 罚成本，第五项为车辆的碳排放成本； （2）式表示车辆数限制 （1） （2） MIPMIP模型模型 2 1 i,jV,ij, N k ijik j xykK 2 0 i,jV,ij, N k ijjk i xykK （3）表示 与 的函数关系 k i j x k i y （4）表示 与 的函数关系 k i j x k j y 1 1 /0 K ik k yiV （5）式表示一个客户点的配送或集货需 求只能由一辆车来完成 ,/0,=1, ikjkij yyi jVkK （6）表示每一对取送货点须同一车辆完成 （3） （4） （5） （6） MIPMIP模型模型 2 11