遗传算法求解旅行商问题

本文提出一种新的遗传算法，用以求解著名的组合优化难题－旅行商问题。引用原始的文献数据，对城市数为10、30、50的试例均求得公布的最优解，对城市数为75的试例，每次结果均好于公布的最优解。用此算法求解中国旅行商问题，以20％的概率得到已知最优解1540km。或次最优解15409km，而所得最差与最好结果的相对距离为0．69％（即所得最长路径为15510km)。在COMPAQ／DX／25MH微机上每得到一个优化解平均历时150s左右。本算法与传统求解TSP问题的方法相比，具有简单、强壮、高效、高速的特点，它原则上对任何规模的对称欧几里德平面TSP具有通用性。     

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

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

用动态搜索算法求解时间依赖型旅行商问题

为解决基于时段的时间依赖型旅行商问题（time-dependent traveling salesman problem,TDTSP）,提出处理跨时段的方法,并建立了相应的数学模型．用动态搜索算法ds-k-opt（k=2,2．5,3）分别求解该问题．仿真算例表明,动态搜索算法中部分ds-2．5-opt解和绝大部分ds-3-opt解优于动态规划启发式算法。且能求解更大规模的TDTSP问题,动态搜索算法的解随k的增大而更优,但运算时间也更长。     

用改进的人工鱼群算法求解TSP问题

针对人工鱼群算法在寻优过程中存在的不足,结合嗅觉在自然界鱼类捕食过程中的重要作用,在基本人工鱼群算法的基础上,提出了具有嗅觉特征的人工鱼群算法。最后,利用改进的人工鱼群算法成功解决了旅行商问题,并且通过比较基本人工鱼群算法与改进人工鱼群算法的实验结果,得出结论,改进后的人工鱼群算法在算法搜索时间、全局最优值精确度方面都有了显著的提高。     

时间多项式进化算法在旅行商问题中的研究

提出了一种模拟生物遗传的进化算法，并将该算法应用于旅行商问题得到了较好的结果，根据达尔文进化论的优化过程，结合自然选择原则提出了启发式算法，该算法的时间复杂性与快速排序策略相当。在文中利用该算法求解中国旅行商问题得到目前的最佳结果。     

求解TSP问题的一种启发式遗传算法

TSP问题是著名的NPC问题，在组合优化中有许多应用。讨论如何应用启发式遗传算法求解此问题，并设计一种启发式交叉算子和换位变异算子，主要特点是给出算子在程序中的实现技巧，提高搜索的速度。经实例分析，算法性能较好，能较快得到问题的满意解。     

求解FDP问题的演化算法

影片递送问题（简称FDP）是组合优化的一个新问题,它比旅行商问题（简称TSP）复杂得多,介绍了一种新的演化算法,这种算法首先将FDP问题转换成TSP问题,然后基于次序杂交算子（OX）和反转变异算子获得最佳解,该算法不仅易于实现,而且计算的结果精确、快速。     

一种求解线性规划问题的新方法

提出了一种求解线性规划问题的新方法:利用K-T条件及KS函数的凝聚特性,将多约束线性规划问题凝聚为单约束优化问题进行求解.最后给出了二维及三维线性规划问题的实例及相应的几何解释.     

一种求解线性规划问题的新方法

提出了一种求解线性规划问题的新方法：利用K-T条件及阳函数的凝聚特性，将多约束线性规划问题凝聚为单约束优化问题进行求解．最后给出了二维及三维线性规划问题的实例及相应的几何解释。     

有时间约束施行商问题的启发式遗传算法

有时间约束的施行商问题作为施行商问题的拓展，是一个重要的NP难题，深入研究这一问题具有重要的理论和实践意义。将时间窗约束转化为目标约束，采用序列编码设计了基于启发式规则的可同时处理软、硬时间约束的遗传算法－2－交换变异的遗传算法和3－交换变异的遗传算法。实验表明HGA1优于简单遗传算法（SGA），HGA2优于HGA1。     

解TSP的有序遗传算法

根据生物进化原理，提出了一种求解ＴＳＰ的有序遗传算法。利用有序编码规则，通过有序交叉算子和有序变异算子的作用，保证该算法不仅能获得ＴＳＰ的有效解，而且能可靠地获得全局最优解。计算机模拟实验表明，该算法具有收敛速度快，易获得最优解等特点。     

有时间约束旅行商问题的启发式遗传算法

有时间约束的旅行商问题作为旅行商问题的拓展,是一个重要的NP难题,深入研究这一问题具有重要的理论和实践意义。将时间窗约束转化为目标约束,采用序列编码设计了基于启发式规则的可同时处理软、硬时间约束的遗传算法——2-交换变异的遗传算法和3-交换变异的遗传算法。实验表明HGA1优于简单遗传算法(SGA),HGA2优于HGA1。     

基于多旅行商问题的应急设施服务区划分模型

基于多旅行商问题,增设集散中心需求及应急服务设施资源容量约束条件,以最小化遍历区域内全部集散中心的综合旅行时间成本为优化目标,构建一种应急设施服务区划分模型,确定各应急设施的服务区范围.设计一种复合算法求解模型,首先基于P-中值选址模型的优化理念,形成初始方案;继而加入禁忌搜索算法,结合LKH求解器对模型进行迭代优化求得最优解.基于宁波市北仑区实际拓扑网络进行案例分析,验证了模型和求解方法的有效性.     

基于多旅行商问题的应急设施服务区划分模型

基于多旅行商问题,增设集散中心需求及应急服务设施资源容量约束条件,以最小化遍历区域内全部集散中心的综合旅行时间成本为优化目标,构建一种应急设施服务区划分模型,确定各应急设施的服务区范围.设计一种复合算法求解模型,首先基于P-中值选址模型的优化理念,形成初始方案;继而加入禁忌搜索算法,结合LKH求解器对模型进行迭代优化求得最优解.基于宁波市北仑区实际拓扑网络进行案例分析,验证了模型和求解方法的有效性.     

Novel Local Search Method for the Traveling Salesman Problem

A new local search method for the traveling salesman problem based on an original greedy representation of solution space and neighborhood structure is proposed. First, a partial closed route that only consists of three cities is given; then other cities are added to this route by a greedy procedure successively. Implemented on a personal computer, this algorithm finds optimal solutions for 24 out of 27 standard benchmarks, and outperforms the Full Subpath Ejection Algorithm (F-SEC) proposed by Rego in 1998.     

基于改进遗传算法的旅行商问题的求解

用遗传算法解决旅行商问题(TSP)时,经常面临过早收敛和遗传漂移等问题.文章分析了产生此类问题的原因,并针对其主要原因对经典遗传算法的选择、交叉和变异算子做了改进,使得改进后的算法可以有效保持种群多样性,从而提高了算法的稳定性和准确性;通过编程测试将改进后的算法和经典算法做了对比.