论文部分内容阅读
[摘要] MAX—MIN蚁群算法是一种改进蚁群算法，文本构造了求解VRPTW的最大最小蚁群算法，将仿真结果与其他经典算法进行比较，结果证明该算法性能优良。
[关键词] MAX-MIN蚁群算法时间窗车辆路径问题优化
一、VRPTW模型的建立
带有时间窗口的车辆路径问题是典型的多目标组合优化NP-hard问题,因此需要通过合理的构造数学模型来安排车辆配送路线，达到提高配送效率同时又能够产生巨大的社会和经济效益的目的。
VRPTW包括一些客户和仓库，每个客户有一定的需求和时间窗口。每个客户只能由一辆车一次服务完成，还要保证每个客户只能被精确的访问一次，同时不能违背时间窗口约束。其目的是要找到一个可行解使得车辆数最少并且总行程最小。
二、最大最小蚁群算法
为克服在Ant．Q中可能出现的停滞现象,Thomas Stutzle等提出了MMAS算法。该算法具有比基本蚁群算法更贪婪的搜索模式，其主要的改进有以下几点:首先,MMAS在运行期间更多的利用最优解信息，即每次迭代后仅允许一只最优的蚂蚁增加信息素。其次,该算法限定了信息素浓度的上下限，有效避免了在搜索中过早收敛于非全局最优解。
将m只蚂蚁随机放到n个客户中，为t时刻支路(i,j)上的信息素强度，每只蚂蚁都可认为是根据状态转移策略来选择下一个客户，并遵循信息素全局更新规则和信息素限制规则。
1.状态转移策略
针对VRPTW自身的特点，我们定义其状态转移概率为:
其中h∈allowedk={n-tabuk};ηij为启发信息;α(α≥0)代表信息素的权重，β(β≥0)代表启发信息的权重;μij=di0+dj0-dij为节约值; δij为紧迫性因子。
2.信息素更新规则
在MMAS中，只允许其中的最优路径更新信息素，其更新规则为:
其中，为该次迭代sib或全局最优路径sgb的目标函数。
3.信息素限制规则
为了降低算法搜索中的早期停滞问题，该算法限定了信息素浓度允许值的上下限，即
。若，则;若，则。
在搜索过程中,当得到最优解时,按下式便得到一个动态变化的:
为了提高算法的收敛性，我们一般先给定一个Pbest，然后根据下式来选定一个 ：
三、算例分析及结论
设某仓库使用完全相同的车辆把货物运往8个客户，车辆的载重能力为8吨，车速为50公里每小时，客户所需货物的重量，服务时间及访问时间窗口的具体要求由Tab.1给出。客户之间的距离如Tab.2所示。问题是寻找合适的路径，使得车辆运行总成本最小。
实验开始，将每个客户都放置一只蚂蚁，蚂蚁的个数与客户数相同。取α=1，β=3，γ=3，λ=1，ρ=0.8，θ=10。采用本文的算法，得到的最优解为:第一辆车：0-2-7-4-0;第二辆车：0-3-1-0;第三辆车：0-8-5-6-0。
将求解的结果与Clarke-Wright算法和遗传算法比较,从Tab.3中可以看出MMAS不失为带时间窗车辆路径问题的一个较优解。
四、结语
本文将MMAS算法应用于VRPTW问题中，充分发挥了其超强的贪婪搜索能力，获得了较为满意的实验效果。这次成功尝试再次表明了该算法在组合优化领域中是具有强大竞争力的，同时也证明了用这种方法解决具有一定的理论参考价值和实际意义。
参考文献:
[1]吴启迪汪 镭:智能蚁群算法及应用[M].上海科技出版社，2004，4
[2]刘云忠宣慧玉:动态蚁群算法在带时间窗车辆路径问题中的应用[J].中国科学工程,2005,12(7):35－40
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
[关键词] MAX-MIN蚁群算法时间窗车辆路径问题优化
一、VRPTW模型的建立
带有时间窗口的车辆路径问题是典型的多目标组合优化NP-hard问题,因此需要通过合理的构造数学模型来安排车辆配送路线，达到提高配送效率同时又能够产生巨大的社会和经济效益的目的。
VRPTW包括一些客户和仓库，每个客户有一定的需求和时间窗口。每个客户只能由一辆车一次服务完成，还要保证每个客户只能被精确的访问一次，同时不能违背时间窗口约束。其目的是要找到一个可行解使得车辆数最少并且总行程最小。
二、最大最小蚁群算法
为克服在Ant．Q中可能出现的停滞现象,Thomas Stutzle等提出了MMAS算法。该算法具有比基本蚁群算法更贪婪的搜索模式，其主要的改进有以下几点:首先,MMAS在运行期间更多的利用最优解信息，即每次迭代后仅允许一只最优的蚂蚁增加信息素。其次,该算法限定了信息素浓度的上下限，有效避免了在搜索中过早收敛于非全局最优解。
将m只蚂蚁随机放到n个客户中，为t时刻支路(i,j)上的信息素强度，每只蚂蚁都可认为是根据状态转移策略来选择下一个客户，并遵循信息素全局更新规则和信息素限制规则。
1.状态转移策略
针对VRPTW自身的特点，我们定义其状态转移概率为:
其中h∈allowedk={n-tabuk};ηij为启发信息;α(α≥0)代表信息素的权重，β(β≥0)代表启发信息的权重;μij=di0+dj0-dij为节约值; δij为紧迫性因子。
2.信息素更新规则
在MMAS中，只允许其中的最优路径更新信息素，其更新规则为:
其中，为该次迭代sib或全局最优路径sgb的目标函数。
3.信息素限制规则
为了降低算法搜索中的早期停滞问题，该算法限定了信息素浓度允许值的上下限，即
。若，则;若，则。
在搜索过程中,当得到最优解时,按下式便得到一个动态变化的:
为了提高算法的收敛性，我们一般先给定一个Pbest，然后根据下式来选定一个 ：
三、算例分析及结论
设某仓库使用完全相同的车辆把货物运往8个客户，车辆的载重能力为8吨，车速为50公里每小时，客户所需货物的重量，服务时间及访问时间窗口的具体要求由Tab.1给出。客户之间的距离如Tab.2所示。问题是寻找合适的路径，使得车辆运行总成本最小。
实验开始，将每个客户都放置一只蚂蚁，蚂蚁的个数与客户数相同。取α=1，β=3，γ=3，λ=1，ρ=0.8，θ=10。采用本文的算法，得到的最优解为:第一辆车：0-2-7-4-0;第二辆车：0-3-1-0;第三辆车：0-8-5-6-0。
将求解的结果与Clarke-Wright算法和遗传算法比较,从Tab.3中可以看出MMAS不失为带时间窗车辆路径问题的一个较优解。
四、结语
本文将MMAS算法应用于VRPTW问题中，充分发挥了其超强的贪婪搜索能力，获得了较为满意的实验效果。这次成功尝试再次表明了该算法在组合优化领域中是具有强大竞争力的，同时也证明了用这种方法解决具有一定的理论参考价值和实际意义。
参考文献:
[1]吴启迪汪 镭:智能蚁群算法及应用[M].上海科技出版社，2004，4
[2]刘云忠宣慧玉:动态蚁群算法在带时间窗车辆路径问题中的应用[J].中国科学工程,2005,12(7):35－40
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。