嵌套分割算法在旅行商问题上的应用

嵌套分割算法是近年来提出的一种求解大规模优化问题的新型全局优化方法。介绍了嵌套分割算法(NPM)的基本思想,将其应用于求解旅行商问题。首先对嵌套分割算法各个算子的策略进行了分析和比较,在局部搜索中引入2-opt算法,并对初始最可能域加以改良,最后提出算法的并行化实现方法。实验证明嵌套分割算法在解决TSP问题时可以获得高质量的解,并且具有良好的时间性能。     

解旅行商问题的混沌蚁群算法

利用混沌运动的遍历性、随机性和规律性等特点,提出了一种求解旅行商问题的混沌蚁群(CACO)算法.该算法的思想是采用混沌初始化进行改善个体质量和利用混沌扰动避免搜索过程陷入局部极值.与模拟退火算法、标准遗传算法进行比较,仿真结果表明该方法是一种简单有效的算法.     

一类多旅行商问题的计算及仿真分析

旅行售货商问题(TSP)是组合优化领域的经典问题之一,而考虑多个旅行商的多旅行商问题(MTSP)是经典的旅行商问题的扩展.多旅行商问题的特点使其符合许多实际问题,并且通过对多旅行商问题加入约束条件可以使其转化为车辆选择问题(VRPs).针对一类特殊的MTSP问题采用Lin-Kernighan算法进行求解分析,并在此基础之上针对访问城市数目均衡的多旅行商问题采用两阶段方法进行求解,计算仿真结果是令人满意的.     

求解配送＼收集旅行商问题的模拟退火算法

配送＼收集旅行商问题(TSPD)是一类重要的组合优化问题,与车辆路径问题等有着密切的联系.但与传统的旅行商问题(TSP)相比,人们对该问题的研究有限,而且大多假定必须在完成所有的配送需求后,才服务收集需求.文中放松这一约束条件,在扩展Metropolis接受准则的基础上,运用模拟退火算法求得该问题较好的结果.     

旅行商问题的遗传算法

旅行商问题属于ＮＰ问题，现在还没有找到有效的解法。本文应用遗传算法对解决此类问题的有效性作了探讨。文中对遗传算子的应用，编码，参数选择及其对收敛的影响等问题作了分析与探讨。     

基于差分进化算法的多旅行商问题优化

针对所有旅行商路径最大值最小的多旅行商问题,提出改进的差分进化算法优化.在该优化方法中,编码采用实数编码;改进的差分进化算法采用轮盘赌选择;根据旅行商问题的特点,在差分进化算法中增加邻域搜索算子.该方法适于距离对称和非对称的多旅行商问题求解.以距离非对称的多旅行商问题的实例进行了仿真和比较,可以看出所提出的改进差分用来解决多旅行商这类离散组合优化问题是有效的.     

时变网络环境下旅行商问题研究

对时变旅行商问题进行描述,提出处理一般跨时段的新方法,并建立数学模型.在求解方法上构造动态搜索优化算法ds-k-opt(k=2,2.5,3)求解该问题.通过实验仿真,大部分动态搜索优化算法解质量优于动态规划启发式算法,且求解规模更大.动态搜索优化算法解随k值增大而更优,算法运行时间也随之增加.     

解旅行商问题的一个新的遗传算法

对旅行商(TSP)问题设计了一个新的遗传算法.首先,对n个城市的旅行商问题设计了一个新的编码方法,并且对这种编码方法,给出了简便的解码方法.其次,针对编码的特点,设计了一种新的、有效的杂交算子和变异算子,这些算子均能直接产生可行的后代.为提高杂交算子的搜索能力,结合了一个局部搜索技术来改进杂交算子.在此基础上,提出了求解TSP的一个新的遗传算法,并证明了其全局收敛性.为了验证算法的有效性,对10个国际标准算例(城市规模从14到1000)进行了计算机仿真,结果表明算法是有效的.     

基因重组算法设计及多目标旅行商问题求解

遗传算法等启发式算法在求解旅行商问题时,存在收敛速度较慢、容易出现过早收敛及算法计算效率较低的问题。在模式理论基础上,提出一种新的基因重组算法。根据优良基因模式,设计模式重组算子,运用重构及进化规划的思想设计算法的个体重构算子和个体选择算子。建立一个多目标旅行商问题模型,分析每一轮计算旅行路线适应度值的差异性,采用熵值法确定路程和费用权重。系列实验表明,基因重组算法在求解多目标旅行商问题时,计算效率远高于比较的算法,收敛速度和求解精度也较一般启发式算法有明显改善。     

求解多旅行商问题的新混合遗传算法:以应急物资配送为例

为优化生物反恐条件下的应急物资配送过程,将该环境下的应急物资配送问题构造为一多旅行商问题(MTSP),并从理论上分析了该旅行商回路为最短Hamilton路径。以此问题为背景,针对应用传统遗传算法求解多旅行商问题时存在收敛速度缓慢等问题,提出并设计了一类新的混合遗传算法。该类新遗传算法与传统遗传算法的最主要区别在于,针对多旅行商问题专门设计了一种新的染色体编码规则、排序算子和交叉算子。仿真结果表明,该算法能够快速收敛到问题的近似最优解,并能很好地维持种群的多样性。     

生产流水线上允许返回作业的一维机器配置问题

在现代制造系统中,大量地采用了流水线作业以提高劳动生产率,其中一维机器配置问题在此起着非常重要的作用。本文探讨了生产流水线上允许返回作业的一维机器配置问题。由于该问题是一个NP-完全组合优化问题,随着问题规模的扩大,往往难以求得最优或满意的机器配置方案。本文提出一种新的遗传算法用以求解这种机器配置问题,数值分析表明所构造的遗传算法对求解这类组合优化问题上是有效的。     

品牌推广动态选址问题及其混合算法研究

对品牌推广动态选址问题进行了描述并且建立了数学模型.基于禁忌规则,提出了求解该问题的模拟退火算法.算法采用自然数编码,在状态生成函数中利用两种邻域扩大抽样范围;根据问题的特点,在模拟退火算法抽样过程中加入了禁忌规则.在介绍了算法原理的基础上给出了具有代表性的算例试验结果并且进行了分析.试验结果表明了所提出的混合算法对品牌推广动态选址问题的有效性.     

基于活动-出行超网络的交通流分配模型研究综述

传统基于出行的交通流分配模型未考虑个体的出行需求源于参与活动的需要这一内在驱动力,忽视了出行与出行之间的连贯性。基于活动的交通流分配模型能够弥补传统交通流分配模型的缺点,综合考虑活动时间窗、活动地点、活动性质等活动属性对道路交通流时空分布的影响,从而更准确地为城市道路规划、城市规划提供理论指导。围绕现有文献,首先介绍描述出行者活动-出行行为过程的超网络结构模型;然后,评述基于活动-出行超网络的交通流分配模型研究;最后,分别从决策主体、决策内容与决策情境视角探讨未来的研究内容。     

Inverse Center Location Problem on a Tree

This paper discusses the inverse center location problem restricted on a tree with different costs and bound constraints. The authors first show that the problem can be formulated as a series of combinatorial linear programs, then an O（｜V｜^2 log ｜V｜） time algorithm to solve the problem is presented. For the equal cost case, the authors further give an O（｜V｜） time algorithm.     

易腐物品配送中心连续选址模型及其遗传算法

针对易腐物品的特性和连续选址问题的复杂性 ,建立了一种求解易腐物品配送中心连续选址问题的 CAGA算法 ,此算法为与 ALA法结合而成的遗传算法 .实验结果表明 ,这一启发式算法具有较好的搜索特性 ,不失为求解易腐物品配送中心选址问题的一种好方法 .     

废弃物处理站选址问题及多目标演化算法求解

针对废弃物处理站选址问题,建立了一个总成本最小和负效用最小的双目标规划模型,从而确定建站的位置、处理容量以及分配给处理站的废弃物产生点.利用问题的启发式知识,设计遗传操作,提出了一种混合多目标演化算法.实例分析表明,混合多目标演化算法在求解质量上与约束法非常接近,而求解速度要远好于约束法.     

带有预知信息的在线Homing ATSP问题

针对快递服务网络结构上的非对称性以及可提前获知待服务需求的位置和释放时间的特征,将预知信息引入可返回原点的非对称TSP问题中,提出以服务总成本最小为目标的带有预知信息的在线Homing ATSP问题.分析了该问题竞争比的下界,并且在一般网络图上设计了SSdd(α)算法和PAH-dd算法,分析了算法各自的竞争比.结果表明在线车采取适时等待策略比采取zealous策略更优;并且预知信息越多,在线算法的竞争性能越优.     

解决位置管理问题的混沌混合差分进化算法

位置管理问题是移动计算环境中的一个重要问题.提出了一种解决位置管理问题的混沌混合差分进化算法,给出了将浮点编码的种群个体映射为问题解的方法,给出了解决标准差分进化算法早熟收敛问题的混沌搜索算法.仿真结果表明,混沌混合差分进化算法能有效解决移动计算中的报告小区规划问题,且算法的搜索质量优于遗传算法、禁忌搜索算法、蚁群算法和传统差分进化算法.     

成本与半径优化的设施选址问题

成本与半径优化的服务设施选址问题(CROFL)广泛应用于应急服务、快递、维修网络等领域,其特点是考虑了响应速度与服务价格、成本之间的关系,根据净收益最大化或者成本最小化的原则自动判断是否将偏远的"需求点"纳入服务半径之内,实现服务成本与服务半径的双重优化。建立了CROFL的混合整数规划模型,构造了求解平面CROFL的7.853+ε-近似算法,并提供了求解一般CROFL的Benders分解算法,计算实验显示,Benders分解算法具有非常高的求解效率与求解质量。