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

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

遗传算法求解旅行商问题

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

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

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

解TSP的有序遗传算法

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

带时间窗车辆路径问题的启发式遗传算法

为了在运输生产中按时间要求合理安排车辆路径, 建立了带时间窗车辆路径问题数学模型, 用启发式遗传算法进行求解。先构造染色体, 产生初始群, 再对其进行优化, 根据个体生存能力的体现进行性能估计, 并计算优化值。运用VisualBasic编写相应计算程序, 设定迭代代数为100, 运算次数为10次, 对有时间窗限制的有1个中心仓库与8个分仓库的实际问题进行求解。模拟结果显示需要3辆车按照3条运输线路进行物流配送服务, 总运行距离为483km, 总运行时间为15.55h, 车辆未出现闲置时间, 且全部仓库得到及时服务。可见启发式遗传算法有效、可行。     

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

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

遗传算法用于TSP问题的研究

本文将遗传算法用于ＴＳＰ问题的求解，并结合爬山搜索法的思想提出了一个新的遗传算子，实验表明效果明显。     

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

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

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

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

有容量约束车辆路径问题的多目标遗传算法

针对有容量约束车辆路径问题,提出了基于Pareto方法的多目标优化遗传算法.该算法引入基于擂台法的Pareto锦标赛选择算子,避免了求解非凸解的困难.采用最邻近算法和扫描算法构造初始种群及引入启发式交叉算子来加快算法的收敛速度.通过E-n30-k3算例实验表明:应用该算法得到的Pareto解集,为决策者提供了多种途径有效解决有容量约束车辆路径问题.     

求解旅行商问题的一种新方法

目前关于旅行商问题的启发式算法主要分为两类:环路构造算法和环路改进算法.通过对两类近似算法的深入研究,提出了一种新的方法――简化模型法来求解旅行商问题.该方法通过排序和选择操作得到原网络图的简化模型,对简化模型中的路径进行重构得到旅行商问题的解.通过测试TSPLIB中的实例,表明用简化模型法求解旅行商问题解的质量高、收敛快,时耗小,该算法是实用的.     

约束优化问题的多参量遗传算法

约束优化问题的传统求解方法是拉格朗日乘子法，函数的可导性和多峰性常常成为求解过程中的难题。遗传算法的并行搜索为这类问题的求解提供了一种新的途径。为了提高计算效率，有学者提出用两级遗传算法分别解决拉格朗日乘子入及优化参数的求解问题。用多参量遗传算法可以同时解决两级优化的遗传算法，把分级优化的参数同时编码，就把两级优化转化为一级优化。经试验该算法虽不能使优化算法的计算时间大大降低，却可以使程序设计工作相对简化，同时使遗传算法程序更具通用性。     

带时间窗的随机需求车辆路线问题的模型研究

车辆路线问题是考虑在车队为一些有需求的顾客运送货物时如何安排行驶路线，从而使服务效率达到最高，在原有车辆路线问题的基础上，着重考虑车辆路线问题中顾客需求的随机性及顾客接受服务的时间窗约束，运用机会约束规划的方法，建立了新的随机模型，并用遗传算法进行启发式求解，得到了良好的数值解，为车辆路线问题的进一步研究提供了参考．     

求解软硬时间窗共存配送路径问题的改进遗传算法

探讨用于求解软硬时间窗共存情况下的车辆路径问题的改进遗传算法。对基本遗传算法的交叉、变异操作的交叉概率和变异概率进行改进,使之更加具有自适应性,能根据种群染色体的优劣程度自动进行调整。通过算例证明改进的算法比原算法在计算软硬时间窗共存配送路径问题上更具有效性。     

编组站静态配流的约束传播和启发式回溯算法

为了提高阶段计划的编制效率,针对编组站静态配流字典序多目标累积调度模型,设计了迭代、约束传播和启发式回溯的混合算法.该算法根据多目标的字典序将模型分为3层:第1层为配流成功的出发列车优先级总和最大化,第2层为出发列车车流来源总数最少化,第3层为车辆平均停留时间最短化.每层先通过约束传播算法化简模型、缩小解空间,再通过启发式回溯算法和约束传播技术联合快速求解.上一层的最优解作为下一层的初始解,并动态增加避免上一层目标退化的约束,迭代求解每层的最优解.通过某编组站实际数据验证表明,本算法耗时小于20 s,满足现场对阶段计划编制的实时性要求,且求得的配流方案优于其他算法.      

二维平行放位装车问题的布局约束启发式算法

在分析二给平行入位货物装车问题的基础上，对货物装车问题设定了布局约束，构造了布局约束启发式算法。实验结果表明，此算法可以有效求得问题的优化或近似优化解，是求解此类问题的一个较好的方案。     

带硬时间窗车辆路线问题的混合遗传启发式算法

为了提高物流配送效率, 建立了集货和配送一体化的带硬时间窗的车辆路线问题的数学模型, 提出了混合遗传启发式算法, 并对模型进行了求解。采用改进节约法与随机法相结合的手段构造了初始解群体以增加解的多样性, 对遗传算法中较优的一部分染色体进行了禁忌搜索以使搜索更容易跳出局部最优, 同时加快搜索初期的搜索速度。仿真计算结果表明: 混合遗传启发式算法具有更好的适应性, 采用改进交叉算子使解的精度提高11.0%;在宽时间窗情形下采用倒位变异可使解的精度提高11.6%。     

带模糊预约时间的动态VRP的插入启发式算法

为有效解决动态环境下考虑顾客偏好的车辆路径优化问题,在对反映顾客偏好的模糊预约时间以及具有模糊预约时间的动态车辆路径问题进行简单描述的基础上,给出了该问题的求解思路,即当新顾客出现时,在保证车辆运载能力和服务时间的可行性的前提下,由最佳车辆在最合适的时间为该新顾客服务.基于此思路,设计了由前后双向可推的推-碰过程确定最佳服务时间的插入启发式算法.在该算法中,通过对顾客的服务时间的前推或后推,确定能使所有顾客的综合满意度达到最大的服务时间调整方案.同时,通过综合考虑顾客满意度、车辆行驶距离和车辆等待时间等因素,使由于新顾客的加入而引起的综合成本增加值得以优化.最后,给出了一个算例,以说明该插入启发式算法求解考虑顾客偏好的动态车辆路径问题的有效性.     

有交通条件约束与软时间窗约束的配送配载模型算法研究

由于配送中客户的时间窗限制和车辆在运行过程中的交通条件约束，给配送中心的运营调度工作增加了新的难题，为此建立了在该约束条件下的车辆配送配载模型。通过在路径选择时考虑交通条件约束、在建立目标函数时以阈值的形式引入时间窗约束，对原始模型进行了拓展，并构造了该问题的遗传算法。