关于旅行推销员问题的一个启发式算法

给出了解旅行推销员问题的一个启发式算法．     

高速铁路列车运行调整的状态空间模型及算法

列车运行调整的优化属超大规模的组合优化问题，具有因素多、各因素之间关系复杂的特点，很难给出一个简洁、易解的规划模型．基于面向事件的状态空间模型良好的描述能力和具有接近系统自然特性的特点，本文在前人研究的基础上，结合我国高速铁路的特点，建立了行车调整的事件驱动的状态空间模型．针对前人研究中状态转移方程的表达及在冲突确认和疏解上的缺陷，结合算法的求解特点和列车运行的实际可能性，提出了改进方法．特别是冲突确认和疏解的新方法和策略，清除了事件驱动的状态空间模型和与之相应的调整算法在实用时的主要难点之一．仿真表明模型和算法是有效的．     

运输路径问题的一个新启发式算法

在解运输路径问题时常常使用Clarke和Wright提出的启发式算法(下称C.W.算法)。本文对Clarke和Wright算法进行改进。改进算法的计算复杂性虽不如C.W.算法,但计算的数值结果在大多数情况下比C.W.算法的结果更好。     

图论算法复杂性问题(一)

本文论述了图论算法复杂性的基本理论和分析方法。由它的表示式和阶的运算,可以分析一个具体问题的算法复杂性,进而明确某一具体算法的有效性。     

单机总误工问题的分解启发式算法

为了解决单机总误工问题,提出了一种分解启发式算法。该算法是将解决这一问题最好的优化方法(Lawler分解算法)和非常有效的启发式算法(MDD)有机结合,在每一次迭代过程中均利用MDD算法估计Lawler分解算法中不同分解位置对应的误工,确定具有最大加工时间的工件在获得最小总误工的分解位置处加工。从理论上证明了该算法得到的排序结果优于MDD排序,仿真实验也表明该算法得到的结果99%以上为最优排序,而且可以求解多达1000个工件的问题。该算法以较短的时间获得了接近最优排序的结果,算法性能优良。     

并行加工系统中的负荷分配模型及启发式算法

在分析已有负荷分配算法的基础上，提出了关于并行加工系统负荷分配的模型和求解的新算法。模型的优化目标考虑使系统中加工负荷最重的设备的负荷最小，同时使设备负荷之差最小。     

流水作业问题的一个启发式算法

讨论具有延迟时间的流水作业问题,并提出了解决该问题的一种启发算法,证明了其最坏性能比是（m 1）/2,并且上界是紧的,特别当m=2,即两台机器上具有延迟时间的流水作业问题时,其最坏性能比是3/2,最后将所得结论推广到FmID2问题,即加工时间相等且延迟时间只取两上值的流水作业问题,其最坏性能比也是m 1/2。     

求极大元的一个图论算法

给出了一个求优超关系下极大元的多项式算法，该算法能产生可图序列，直接在图上实现。文中给出算法实例。     

列车运行调整问题的分解协调计算模型

针对列车运行调整问题集中式求解方法的不足,构建多目标优化列车运行调整的数学模型,并设计分解协调计算模型来求解.分解协调计算模型将求解过程分为4个层次,分别是将待调整列车分解为子调整列车集的协调分组层,确定子列车集优化目标的目标设定层,完成子调整问题求解的优化计算层和将各子问题解还原为原问题解的结果还原层.该计算模型能适应多种线路条件,也能适应不同列车调度员指挥的习惯偏好,并能快速求出优化解.     

出厂物流调度问题及其启发式算法

针对出厂物流调度问题,建立了一类出厂物流问题的调度理论模型,证明了该问题的强NP-hard特性.基于对问题的特征分析,提出求解问题的近似算法,证明了算法的最坏性能比为3且为紧界,并通过数值仿真验证了该算法的有效性.结果表明,所提出算法对两台流水作业机器的完工时间有一定的优化.     

一种求解翻箱问题的启发式算法

在集装箱堆场,翻箱操作不可避免,为降低翻箱次数,提高作业效率,有必要找到一种有效的方法来解决这一问题.在已知每个集装箱提箱顺序的前提下,如何安排翻箱作业顺序是典型的NP难问题.为此提出了一种启发式算法,并通过算例实验与已有算法的结果进行对比,实验结果表明本文提出的算法较优.     

模糊集值产生式系统的启发式图搜索算法

首先提出了模糊集值产生的系统的概念，然后运用三角范算子，得到了模糊集值产生式系统启发式算法，并对启发式算法的可采纳性给出了证明。     

多年调节水库补偿调节联合运行模型及人机对话算法

结合多年调节水库特点,本文建立了多年调节水库补偿调节联合运行模型,提出了一种基于等出力补偿调节计算、决策者参与的人机对话算法,通过实例计算表明,该算法具有计算速度快、占用内存少、决策者参与计算等优点,是解决多年调节水库联合运行计算的有效途径,具有重要推广、实用价值。     

一种网络仿真实验床映射问题的启发式算法

提出了一种求解网络仿真实验床映射问题的启发式算法．该算法的思想是：为尽量少地占用仿真实验床的网络资源，应尽可能地将实验者要求的逻辑拓扑中连接紧密的结点映射到同一台交换机上．为此，将仿真实验床的物理拓扑以交换机为单位分成若干子图，之后在实验者要求的逻辑拓扑上进行迭代，每次迭代按边和权值选取结点进行子图划分，最终得到的划分图即为逻辑拓扑到仿真实验床物理拓扑的映射结果．实验结果表明，该算法能在较短的时间内求得近优解，并且当结点个数增大时，算法的求解时间远少于遗传算法．     

运行调整系统若干技术难点问题的研究

从我国铁路日常运输组织特点出发，从通用性、实用性和可移植性的角度，采用数据相关法表示技术设备及各种运行参数的特征及关系；提出了运行图无级缩放、任意平移和加快图形处理速度的过滤裁剪算法；研究了适合各种线路结构和技术条件的调度算法的实现方法，较好地解决了实现计算机辅助列车运行调整的技术难点问题。     

集合覆盖问题的一种启发式算法

给出了完备策略的概念，并提出了一个求解集合覆盖问题的启发式算法，对该算法的合理性、时间复杂性以及精度进行了分析。用该方法可以求解其它的NP困难问题。     

定位-车辆路径问题的两阶段混合启发式算法

定位-车辆路径问题(LRP)集成了设施定位分配和车辆路径决策,属于NP-hard难题.为有效求解实际大规模的具有设施容量约束和车辆容量约束的LRP问题,设计了基于禁忌搜索及双种群蚁群算法的两阶段混合启发式算法.算法第1阶段采用禁忌搜索算法确定设施定位及客户分配,算法第2阶段采用双种群蚁群算法优化车辆路径,蚁群间的通信与协调通过信息素共享来实现.通过仿真试验并与其他启发式算法进行对比,结果表明,该算法是可行和有效的.