关于线性二层规划分枝定界方法的探讨

对求解线性二层规划的分枝定界方法进行了探讨.给出的一个例子表明,目前的分枝定界方法不能很好地解决上层带有任意线性形式约束的线性二层规划问题,进而在线性二层规划新定义的基础上提出了求解线性二层规划的扩展分枝定界方法.算例表明扩展分枝定界方法可以有效解决原分枝定界方法的不足.     

基于分支定界算法的物流配送网络优化研究

为进一步提高物流配送网络的运行效率,以配送总里程最短为目标,建立了单配送中心的配送优化模型,提出了一种基于分枝定界法的混合求解策略。该策略能有效地避免智能启发式算法的不稳定性和传统优化算法的指数爆炸问题,对现代配送网络的建设具有一定的理论和实践意义。     

基于资源受限广义指派问题的分解启发式算法

资源受限广义指派问题(RGAP)是NP-难的,对RGAP问题给出一个分解启发式算法.通过分解目标函数及约束条件,把原问题分解成子问题的集合,并设计分解启发式算法找到该问题的满意解.最后,通过算例说明算法的有效性.     

旅行商问题的交叉粒子群优化算法

本文将粒子群优化算法(PSO)应用于求解旅行商问题(TSP),结合遗传算法的交叉算子,建立了求解此问题的交叉粒子群优化算法,数值模拟结果表明了该算法的有效性.     

求解旅行商问题的搜寻者遗传算法

针对简单遗传算法易陷入局部最优及收敛速度慢的不足,提出一种改进遗传算法-基于启发式策略的搜寻者遗传算法.首先将搜寻者优化算法中的模糊思想和近邻策略相结合改进变异算子,增强种群多样性,避免陷入局部最优;然后针对路径优化问题基于启发式策略设计反转算子,使得路径中不存在交叉边,加快收敛速度;最后将改进遗传算法用于求解旅行商问题.结果表明,改进遗传算法的求解精度和求解效率明显优于基本遗传算法.     

基于半定规划松弛的凸二层规划问题算法研究

提出使用凸松弛的方法求解二层规划问题,通过对一般带有二次约束的二次规划问题的半定规划松弛的探讨,研究了使用半定规划(SDP)松弛结合传统的分枝定界法求解带有凸二次下层问题的二层二次规划问题,相比常用的线性松弛方法,半定规划松弛方法可快速缩小分枝节点的上下界间隙,从而比以往的分枝定界法能够更快地获得问题的全局最优解.     

求解TSP的子空间遗传算法

为避免遗传算法在计算过程中搜索冗余空间而耗费不必要的资源及时间，本提出了一种以经费遗传算法为基础，通过分析问题的特殊解集，以找出原问题解空间的区域特征从而构造出缩小算法搜索空间的子空间遗传算法，并用它求解TSP。结果表明，该算法实施起来非常有效。     

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

针对采用自然编码的遗传算法在求解旅行商问题(TSP)过程中初始群体设置过于复杂的问题,采用了Grefenstette编码设置初始群体,有效保证了初始群体的随机性和多样性.同时,在遗传算法实施过程中采用了自然编码,吸取边重组交叉算子和简单交叉算子的优点,提出一种新的交叉算子.这种处理解决了Grefenstette编码在遗传算法的交叉和变异过程中只能部分遗传父代的优良特性的问题.对TSP试算结果表明,采用这种遗传算法策略有利于问题的求解.这种实施的策略可以大量用于加工领域和交通领域以及其他规划领域的路径规划中.     

一类非凸不可微规划的算法

讨论一类带非凸不可微函数约束的非凸不可微规划的求解．提出一种基于分枝定界技巧的算法,该算法具有全局收敛性。     

TSP的量子蚂蚁算法求解

在分析量子算法的基本概念的基础上,提出了一种新的算法——量子蚂蚁算法。量子蚂蚁算法结合了量子计算中量子旋转门的量子信息和蚂蚁寻优的特点,为解决实际问题提供的一种新的优化方法。本文将量子蚂蚁算法应用于TSP问题的研究,通过选取国际通用的TSP实例库中多个实例进行测试,表明了新算法具有很好的精确度和鲁棒性,即使对于大规模问题,也能以很小的种群和不长的时间求得相对误差较小的满意解。     

用遗传算法求解分组旅行推销员问题

在遗传算法能够有效解决TSP问题的基础上，根据遗传算法——通过搜索大规模，多样化的种群，在种群间交换个体所携带的遗传信息，保留种群中个体的优越遗传信息——的思想，设计了求解分组TSP问题的遗传算法。算法中染色体表示、评价函数的构造、杂交变异算子的设计经过实例计算的检验被证明较为可靠；算法运算速度快，容易获得有效解。     

一种改进的蚁群算法及其在TSP中的应用

蚁群算法是一种求解复杂组合优化问题的新的拟生态算法,也是一种基于种群的启发式仿生进化算法,属于随机搜索算法的一种,并用于较好地解决TSP问题.然而此算法也有它自己的缺陷,如易于陷入局部优化、搜索时间长等.通过对基本蚁群算法的介绍及相关因素的分析,提出了一种改进的蚁群算法,用于解决TSPLAB问题的10个问题,并与参考文献中的F-W、NCSOM、ASOM算法进行比较,计算机仿真结果表明了改进算法的有效性.如利用改进的蚁群算法解决lin105问题,其最优解为14382.995933(已知最优解为14379),相对误差是0.0209%,计算出的最小值几乎接近于已知最优解.     

连锁—遗传算法中的一种启发式方法

１引言遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ,简称ＧＡ）是由美国密执安大学教授ＪｏｈｎＨｏｌｌａｎｄ提出的,其依据为达尔文的进化论和盂德尔的遗传学说．该算法效法自然界中各物种的进化过程,是一种随机搜索算法,广泛应用于解决各种优化问题．２生物遗传学中的连锁生物遗传学中的连锁现象是Ｂａｔｅｓｏｎ和Ｐｕｎｎｅｔｔ在１９０６年发现的,他们在研究香豌豆的两对性状的遗传时,观察到同一亲体遗传来的基因较多地联在一起,这就是基因的连锁（ｌｉｎｋａｇｅ）现象．这里应给玉米的例子来说明遗传学上的连锁现象．设基…     

Further Extension of the TSP Assign Neighborhood

We introduce a new extension of Punnen's exponential neighborhood for the traveling salesman problem (TSP). In contrast to an interesting generalization of Punnen's neighborhood by De Franceschi, Fischetti, and Toth (2005), our neighborhood is searchable in polynomial time, a feature that invites exploitation by heuristic and metaheuristic procedures for the TSP and related problems, including those of De Franceschi, Fischetti, and Toth (2005) for the vehicle routing problem. Research of GG was partially supported by Leverhulme Trust and by the IST Programme of the European Community, under the PASCAL Network of Excellence, IST-2002–506778.     

Improved Large-Step Markov Chain Variants for the Symmetric TSP

The large-step Markov chain (LSMC) approach is the most effective known heuristic for large symmetric TSP instances; cf. recent results of [Martin, Otto and Felten, 1991] and [Johnson, 1990]. In this paper, we examine relationships among (i) the underlying local optimization engine within the LSMC approach, (ii) the kick move perturbation that is applied between successive local search descents, and (iii) the resulting LSMC solution quality. We find that the traditional double-bridge kick move is not necessarily optimum: stronger local optimization engines (e.g., Lin-Kernighan) are best matched with stronger kick moves. We also propose use of an adaptive temperature schedule to allow escape from deep basins of attraction; the resulting hierarchical LSMC variant outperforms traditional LSMC implementations that use uniformly zero temperatures. Finally, a population-based LSMC variant is studied, wherein multiple solution paths can interact to achieve improved solution quality.     

A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems

A parallel branch and bound algorithm that solves the asymmetric traveling salesman problem to optimality is described. The algorithm uses an assignment problem based lower bounding technique, subtour elimination branching rules, and a subtour patching algorithm as an upper bounding procedure. The algorithm is organized around a data flow framework for parallel branch and bound. The algorithm begins by converting the cost matrix to a sparser version in such a fashion as to retain the optimality of the final solution. Computational results are presented for three different classes of problem instances: (1) matrix elements drawn from a uniform distribution of integers for instances of size 250 to 10 000 cities, (2) instances of size 250 to 1000 cities that concentrate small elements in the upper left portion of the cost matrix, and (3) instances of size 300 to 3000 cities that are designed to confound neighborhood search heuristics.     

New TSP Construction Heuristics and Their Relationships to the 2-Opt

Correction heuristics for the traveling salesman problem (TSP), with the 2-Opt applied as a postprocess, are studied with respect to their tour lengths and computation times. This study analyzes the 2-Opt dependency, which indicates how the performance of the 2-Opt depends on the initial tours built by the construction heuristics. In accordance with the analysis, we devise a new construction heuristic, the recursive-selection with long-edge preference (RSL) method, which runs faster than the multiple-fragment method and produces a comparable tour when they are combined with the 2-Opt.