一个物流配送优化算法

分析并描述了终端物流配送体系 ,建立了终端物流配送优化模型。该模型是一个复杂的带约束的多旅行商问题 ,属于非确定性多项式 (NP)完全问题。基于集合分划、启发式贪心策略和边缘交换算法给出一种可行的优化算法。

基于隶属云模型蚁群算法与LK搜索的TSP求解

提出一种求解TSP的算法,采用"问题无关的进化算法与问题相关的局部搜索相结合"的策略。采用基于云模型的蚁群算法来产生足够好的解;改进传统的LK算法,新加入5种搜索删除集与添加集元素的准则,以此细化搜索。将该算法用于求解TSPLIB中不同类型、城市数从48到33810内变化的TSP,比较该学派与其他学派算法的偏离率与运行时间,结果均显示该算法更优,有效求解了TSPLIB中的非对称TSP、哈密尔顿圈问题。

基于MTSP的机车周转图编制模型与算法

为了提高机车的工作效率,探讨了机车周转图编制模型与算法.对于给定的列车运行图,综合考虑机车使用台数最少和图形均衡性,提出了一种编制机车周转图的新算法.将机车周转图编制问题转化为多旅行商问题(MTSP)并建立数学模型,从而求得问题的最优解.最后,用列车运行图实际数据进行了验证,证明了该算法的有效性.

基于不同检修能力的动车组运用计划研究

以动车组接续时间、接续地点、动车组定检里程、检修点分级检修能力为约束条件,以需要的动车组数量最少和动车组总检修时间最小为目标函数,建立动车组运用计划优化模型,用改进的蚂蚁算法进行求解。以京津城际铁路为例的计算结果表明,采用给出的模型和算法能够得到优化的动车组运用计划,并能够确定检修点的分级检修能力。

一种改进的基于隶属云模型的蚁群算法

为了解决传统蚁群算法的收敛速度慢和易陷入局部最优等缺陷,做出如下改进:首先采用云模型来自适应控制蚂蚁的随机性;其次缩小了后继城市的搜索范围;最后引入2-opt局部搜索策略。对城市规模从50到高达1000的TSP问题进行仿真,并与先前提出的改进蚁群算法进行对比,结果表明,该算法不仅偏离率更小,而且运行时间短。随着城市规模的增大,优势更明显。

基于和声搜索和模拟退火的混合算法解决TSP问题

和声搜索是一种新的启发式优化算法,算法模拟了音乐创作中乐师们凭借自己的记忆,通过反复地调整乐队中各乐器的音调,最终能达到一个美妙的和声状态的过程。针对和声搜索算法容易陷入局部最优的缺陷,将其与模拟退火算法结合,得到了两种混合算法。实验表明混合算法针对TSP问题具有较高的求解质量。

考虑工作量平衡的多旅行商问题及其求解

根据多旅行商问题(MTSP)特点,针对最小化各旅行商最长路线这一优化目标,提出改进蚁群算法(IACO)。最小化各旅行商最长路线考虑各旅行商的工作量平衡,更具实际应用意义。算法中信息素更新与限制遵循最大最小蚁群算法(MMAS)框架,为提高算法性能设计混合局域搜索算法。利用文献中标准算例进行检验,结果表明,所设计蚁群算法与三种遗传算法相比表现出较强竞争性。

神经网络方法在解多路旅行商问题中的应用

本文提出了把ＭＴＳＰ转化成标准ＴＳＰ的方法，讨论了用神经网络的原理和方法解决它，计算机模拟结果表明该方法十分有效．

神经网络求解 MTSP 的应用研究

对多路旅行商问题（ＭＴＳＰ）根据出发城市的不同和返回情况分成了四个子问题，建立了各问题的神经网络计算能量函数和迭代公式，提出了智能化的优化方法，并用中国３１个直辖市、省会和自治区首府为例对ＭＴＳＰ进行了计算机模拟，说明了神经网络用于求解组合优化问题是十分有效的。

神经网络方法在解多路旅行商问题中的应用

本文对多路旅行商问题根据出发城市和返回情况分成了四个子问题，建立了各问题的神经网络计算能量函数和迭代公式，提出了智能化的优化方法．并用中国31个城市进行了模拟分析，结果表明神经网络对求解多路旅行商问题十分有效。

AGV作业调度模型及改进的DE算法研究

AGV作业调度问题的求解结果对AS/RS的运行效率具有重要影响。通过必要的简化,建立了AGV作业调度问题的静态优化模型。可知静态AGV作业调度问题实质是一种带约束的多重TSP问题,属于典型的NP完全问题,目前还不存在可在多项式时间内求解的确定算法。提出了一种改进的差分演化算法用于求解该问题。为了适应AGV作业调度问题的特点,新算法设计了新的两段编码方法,对多个DE算子进行了改造。还提出了基于生存时间的种群多样性增强机制,用于增强算法的搜索能力,避免陷入局部最优。仿真实验显示,该算法可以有效提高AGV作业调度的效率,验证了相关改进机制的有效性。

求解旅行商问题的一种混合遗传算法

文章针对组合优化中的旅行商问题,设计了将溶入最近邻算法思想的混合遗传算法。它的特点在于用具有最邻近结构的基因片段完成个体的替代;目的在于修正部分适应度偏低的染色体,提高群体的平均适应度。

提高链式Lin-Kernighan算法性能的一种新策略

在笔者前期工作(王东,吴湘滨.提高链式Lin-Kernighan算法性能的策略.计算机应用,2007,27(11):2826-2829)的基础上,通过对经典旅行商问题(TSP)优化解边集之间交集的特性分析,给出了一种新的Lin-Kernighan算法参照优化边集生成模型。该模型建立的边集中边的数量少于常规方法以及前期研究成果生成边集中边的数量,同时以更高概率保留全局最优解中的边。将该模型应用于Lin-Kernighan算法,在不损失单次调用该算法求解精度的前提下,进一步缩短了算法的执行时间,从而进一步提高了链式Lin-Kernighan算法的求解性能。结合前期研究成果,能进一步提高使用Lin-Kernighan算法作为启发式算法的所有混合算法性能。

提高链式Lin-Kernighan算法性能的策略

Lin-Kernighan算法作为一种高效的组合优化问题优化算法,普遍应用于各种求解组合优化难题的算法中,尤其是旅行商问题的求解。通过对该类问题的可化简性论述,分析并建立了该类问题初始边集的概率化简模型,经实验分析方式确定了模型中的先验性概率值,并建立旅行商化简初始边集的随机算法。将该算法建立的边集作为链式Lin-Kernighan算法的参照优化边集,大幅度提高了链式Lin-Kernighan算法的求解性能,在与多种智能算法结合中取得了较好的收敛效果。

旅行商问题的一种高效近似算法及其排考应用

要为解决现实应用中的类似于小规模旅行商问题的组合优化问题,提出了一种新的近似算法——群体竞争搜索算法(PCS).使用了一种新的局部搜索算子2e/1p-opt,并按照"搜索-选优-变异-搜索"的迭代策略设计了群体竞争搜索算法.与CLK算法进行了比较,对于280城市以下的旅行商问题,在计算速度和计算结果两方面都有较好表现.将高校排考中的场次排序优化问题转化为TSP并用算法求解,能在1秒内得到大幅改进的结果.

热轧调度的数学模型及解法

研究了钢铁厂的热轧调度问题 ,将其转化为带有能力约束的多旅行商问题 ,并对此给出一个启发式算法 .

基于DE算法求解AGV作业调度问题研究

AGV作业调度问题在一定约束条件下可建模为一个NP完全的多重TSP问题。为了优化AGV作业调度的效果,提高AS/RS系统的运行效率,本文提出用差分演化(DE)算法来求解AGV作业调度问题,并针对问题的特点对DE算法进行了若干改进。设计了新的个体两段编码方法,提出了基于生存时间的种群多样性增强机制来提高算法的搜索能力,避免陷入局部最优等。模拟结果显示,提出的算法可以有效求解AGV作业调度问题,获得了高质量的优化解,且收敛速度快。

最大最小目标的多旅行商问题求解

研究一类多旅行商问题,对所有旅行商所走的环路,寻求最大长度最小化.设计了一种新的局部搜索算子,该算子既能进行一条环路的优化,也能对两条环路进行重组优化,与现有的局部搜索算子相比,在计算成本相当的条件下,其寻优能力更好;以该算子为基础,提出了"搜索-选优-变异-搜索"的迭代策略,按此策略设计了竞争搜索算法.在公开的数据集上进行了实验,与近期文献相比,计算结果有所改进.

旅行商问题的一种启发式算法

用一个有向图表示旅行商避开某一城市到1个顶点的所有最短路径,并在每条弧上定义一个线性表,用以记录所有包含该弧的图,从而将判断某条弧和某个顶点是否应该存在于某个子图中的最短路径上的问题转化为线性表的相关操作,进而讨论了图上的弧都在某一最短路径上的充要条件,以及如何顺序产生第1列到第n列的顶点上的图,如何从这些图上搜索出近似最优解的方法.

指针网络改进遗传算法求解旅行商问题

针对遗传算法在求解旅行商问题时,受限于初始种群质量而存在收敛速度慢、易陷入局部最优等问题,提出一种基于指针网络改进遗传算法种群模型。通过经改进指针网络生成初始种群取代原种群,并结合基于汉明距离轮盘赌策略对种群个体进行择优,形成个体质量和种群多样性高的新种群。实验在TSPLIB标准库上多组实例进行测试,并和研究进展种群改进算法和多种主流启发式算法进行多项系数对比。结果表明,经过优化后算法的收敛速度和寻优能力有显著提高,能够有效用于改善遗传算法在旅行商问题上的应用。