文档介绍：Add the author and the accompanying title
《最优化算法案例学习禁忌搜索混合算法》
大作业汇报
Shanghai Maritime University
禁忌搜索案例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)，f(xnow)=45，H={45}
Can_N(xnow)={(ABCDE;45)，(ACBDE;43)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)} xnext=(ACBDE)
特赦原则
基于评价值的规则，若出现一个解的目标值好于前面任何一个最佳候选解，可特赦；
基于最小错误的规则，若所有对象都被禁忌，特赦一个评价值最小的解；
基于影响力的规则，可以特赦对目标值影响大的对象。
其它原则
禁忌长度与评价函数
（1）t可以为常数，易于实现；
（2） ，t是可以变化的数，tmin和tmax是确定的。 tmin和tmax根据问题的规模确定，t的大小主要依据实际问题实验和设计者的经验。
（3） tmin和tmax的动态选择。
评价函数
（1）直接评价函数，通过目标函数的运算得到评价函数；
（2）间接评价函数，构造其他评价函数替代目标函数，应反映目标函数的特性，减少计算复杂性。
禁忌长度
记忆频率信息和终止规则
记忆频率信息
（1）静态频率信息：解、对换或目标值在计算中出现的频率；
（2）动态频率信息：从一个解、对换或目标值到另一个解、对换或目标值的变化趋势。
终止规则
（1）确定步数终止，无法保证解的效果，应记录当前最优解；
（2）频率控制原则，当某一个解、目标值或元素序列的频率超过一个给定值时，终止计算；
（3）目标控制原则，如果在一个给定步数内，当前最优值没有变化，可终止计算。
论文阅读
带软时间窗的集货与送货多车辆路径问题节约算法
祁文祥 陆志强 孙小明
《交通运输工程学报》2010
关键词：
多车辆路径问题、集货与送货、启发式节约算法、软时间窗
背景介绍
随着第三方物流的兴起,很多企业为降低物流成本,越来越倾向于把原来由自己承担的运输任务外包给第三方物流企业,而多批次、小批量的送货模式也成为各企业降低库存风险的重要手段。另一方面,第三方物流企业出于自身运营成本考虑,在满足客户运输要求的前提下需要采取有效的路径优化方案,才能实现自身利益的最大化
问题描述
物流配送网络
集货需求点集
配货需求点集
所有需求点集
任务集
租用货车的费用
货车的运输费用
时间惩罚费用
变量定义
客户j 的集货需求量
第m个任务要求货物送到的时间窗
货车 k 执行第 m 个任务从客户 i 的出发时间，该任务配送货物至 j 点
货车 k 执行第 m 个任务到达客户 j 的时间，该任务从 i 点 出发
客户j 的送货需求量
变量定义
单个车辆的租赁费用
早到晚到时间惩罚系数
装货时间
卸货时间
货车k 在执行任务m 时的时间惩罚值
车辆最大装载量
车辆最大行驶距离
单个车辆的租赁费用
变量定义
节点 i 和节点 j 之间的距离
0-1变量，货车k 完成任务m取1，否则0
0-1 变量，货车k 从客户 i 行驶到客户 j 则取1，否则0
决策变量
0-1变量，货车k 完成任务m及任务 n 取1，否则0
VRPPDTW数学模型
（1）
.
（2）
（3）
（4）
VRPPDTW数学模型
（5）
（6）
（7）
（8）
（9）
VRPPDTW数学模型
（9）
（10）
（11）
（12）
（13）
启发式节约算法
本研究模型在传统VRP问题上进行了扩展,增加了集货和送货任务的时间窗要求以及多辆车可供配置的条件,