基于多目标混合启发式算法的协同无冲突4D航迹规划

为促进基于航迹运行的框架下未来空中交通管理系统的协同决策,本文提出了一种协同无冲突4D航迹规划方法。首先以提高航班效率和航空公司间的公平性为目标,以无冲突为约束构建了一个多目标整数线性优化模型。其次,提出了一种基于基尼系数的指标以量化航空公司间的成本分配公平性。为了提高问题求解效率,采用了基于网格的探测方法以加速冲突检测,并设计了一种多目标混合启发式算法(Multi-objective hybrid-meta-heuristic optimization algorithm,MHMOA),通过结合模拟退火(Simulated annealing,SA)和爬山局部搜索算法来近似最优的非支配解。最后,利用实际航班计划和航路网络数据比较和分析了MHMOA、SA和两种常规多目标优化算法的优化结果。结果表明,MHMOA所获得的非支配解的质量更高、延误更低且航空公司间公平性更优,在3个多目标优化性能指标方面表现优异,可为空中交通管理员提供更详细的决策支持。

求解卸装一体化的车辆路径问题的混合启发式算法

提出一种结合蚁群系统（Ant Colony System,ACS）和变邻域下降搜索（Variable Neighborhood Descent,VND）的混合启发式算法ACS_VND,求解卸装一体化车辆路径问题.利用基于插入的ACS解构造方法产生多个弱可行解,再逐个转换成强可行解,并选择其中最好的作为VND的初始解.在VND过程中使用三种不同的邻域结构：插入、交换和2-opt依次对解进行迭代优化.对55个规模为22~199的benchmark算例的求解结果表明,算法ACS_VND能在较短时间内获得52个算例的已知最好解,并且更新了其中44个算例的已知最好解,求解性能优于现有算法.

自动化制造单元最小完工时间调度问题的混合启发式算法

自动化制造单元最小完工时间调度问题属于NP-hard难题,目前尚缺乏有效的调度方法。为此,提出基于遗传和禁忌搜索的混合启发式算法,用以搜索一组最满意的机器人搬运作业排序。以遗传算法为基本结构,在初始种群产生和交叉、变异操作中引入禁忌搜索技术,以提高优化质量。基于搬运作业规则的初始种群构造算法和两阶段交叉、变异算子克服了传统算子对可行搬运作业排序的破坏,而邻域移动算子则保证了禁忌搜索的多样性和集中性。最后,随机实验结果验证了算法的有效性。

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

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

求解一类并行多机调度问题的混合启发式算法

该文研究了一类工件具有不同释放时间的并行多机调度问题 ,调度目标为使总流程时间最小。针对该类调度问题具有强NP -hard的特点 ,首先构造了的一种启发式算法 ,该算法能够在很短的时间内找到次优解。由于通常启发式算法会随着问题规模的扩大导致求解的质量有所下降 ,结合遗传算法的全局搜索能力 ,提出了一种混合启发式算法进一步改善解的质量。仿真结果表明该算法很好地结合了启发式算法和遗传算法的特点 ,能够在较短的时间内求解较大规模的调度问题 ,算法的计算量小 。

多车型开放式车辆路线问题的混合启发式算法

多车型开放式车辆路线问题,是物流配送优化中不可缺少的环节。针对标准遗传算法存在收敛速度慢,局部搜索能力差,易早熟的缺点,采用混合启发式算法进行优化求解。采用实数序列编码,使问题变得更简洁;有针对性地构建初始解,提高了解的可行性;用基于排序的选择与最佳保留相结合策略,保证群体的多样性;引入部分算术交叉算子,加强染色体的全局搜索能力;利用模拟退火算法的Boltzmann机制,控制遗传算法的交叉、变异操作,提高了算法的收敛速度和搜索效率。仿真结果表明混合启发式算法在求解质量和计算效率上好于标准遗传算法。

双层车辆路径问题的混合启发式算法

针对与城市物流密切相关的双层车辆路径问题(2E-VRP),提出了一种用来求解的混合启发式算法。该算法利用贪心算法的快速性、蚁群算法的搜索多样性以及邻域搜索算法较强的局部寻优能力来提高求解质量,加速算法的收敛性。把该算法应用于22个测试算例和3个大规模的算例,并与同类研究进行了比较。实验结果表明,混合启发式算法不仅能保证较高的精确性,而且具有很高的效率;与精确性最高的同类算法相比,虽然在解的质量方面稍逊,但在求解速度方面表现出了明显的优势。实验结果还显示了构建双层城市物流系统的潜在收益,中转站的设置能够在一定条件下显著提高城市物流效率。

多车型多品种货物配装优化问题的混合启发式算法

为满足客户多样化和个性化的需求,建立能充分、均衡利用装载工具的载重和容积的多品种、多车型货物配装模型,并从全局、整体最优上设计混合启发式算法求解。首先,采用实数序列编码,使问题变得更简洁;基于容重比平衡法构建初始解,提高了解的可行性;用基于排序的选择与最佳保留相结合策略,保证群体的多样性;采用改进的非一致变异,加强染色体的局部搜索能力;其次,对遗传算法求得的精英种群再进行禁忌搜索,提高了搜索效率;最后,通过实例计算证明了上述模型和算法的有效性,并为大规模解决实际问题提供思路。

基于混合启发式算法的设备混合布局问题

构建了基于设备单元布局集成求解的设备混合布局多目标优化模型,提出了遗传免疫蚁群混合启发式算法进行模型求解,该算法设计了带"保险柜"的自适应免疫蚁群算法选择操作,有力地维护了群体的多样性,提高了解的质量。最后,通过算例验证了模型及算法的有效性和优越性。

三层物流网络选址—路径优化及混合启发式算法研究

为同时解决转运、分配、选址和车辆路径问题,在考虑车辆载重和行驶距离约束、配送中心处理能力约束的基础上,构建了一个多产品三层物流网络选址—路径模型,以总成本最小为目标,提出一种基于贪婪随机自适应搜索算法和里程节约算法的混合启发式算法,给出了该算法的步骤和伪代码。实验结果表明,该算法具有可行性,并且与其他算法比较而言,算法具有高效性。

混合启发式算法的多产品正向/逆向物流网络设计

文章探讨了一个多产品的二阶段的正向/逆向物流配送网络设计问题,即在有配送量限制的各个生产企业地址已知、客户地址已知、客户需求量与回收量不确定的条件下来确定配送/回收中心地址与规模,使该物流网络总费用最小。并设计了混合启发式算法与二阶段转载算法来解决该问题。计算结果表明该算法的具有很好的效果。

面向有约束TSP的一种混合启发式算法

为了克服传统算法求解有约束TSP的早熟收敛缺陷,提出混合启发式算法。采用基于遍历城市顺序的染色体编码,结合随机法与贪心法生成较优初始种群,执行优先保留交叉和平移变异操作,引入局部邻域及混沌搜索,设计特定的适应度函数,给出最优解判据,最后证实该算法的有效性。

混合启发式算法在汽车调度中的应用

将蚁群优化和变邻域下降搜索VND相结合,形成一种混合启发式算法ACS_VND,应用于客运公司的汽车调度,求解车辆需求数和最佳路径。该算法充分利用了2种不同算法的优点。实验结果表明,算法ACS_VND能在较短时间内获得比单个算法更好的车辆调度路径。

混合启发式算法求解多配送人员车辆路径问题

为解决带时间窗和多配送人员的车辆路径问题,本文采用混合启发式算法对其进行求解。该算法主要由整数规划重组、局部搜索算法和模拟退火算法三部分组成。在算法中,整数规划重组有效提高了解的质量,局部搜索算法和模拟退火算法保证了算法搜索的深入性和广泛性。通过与CPLEX和禁忌搜索算法进行对比,证实了混合启发式算法实用价值更高,求解效果更好。

一种基于Voronoi图求解车辆路径问题的混合启发式算法

针对由多个配送中心和多个客户点组成的物流网络中的车辆路径问题,提出了一种基于"集群第一,路线第二"的路径优化策略,即首先使用Voronoi分割对配送区域进行划分,然后引入综合插入算法和变邻域搜索算法的混合启发式算法求解配送区域内车辆路径问题。通过算例和应用系统的分析与验证表明,该混合算法既能获取质量较优解,同时也具有较好的实时性,能较好地满足实际应用需求。

基于混合启发式算法的集装箱装载优化

针对多约束条件下大规模的集装箱装载问题,以集装箱的空间利用率最大化为目标提出了基于块装载算法的剩余空间启发式算法与模拟退火算法相结合的混合启发式算法。剩余空间启发式算法的核心是在满足多约束条件下,根据块装载算法生成简单块和复合块,有效降低大规模集装箱装载的维度,并且通过剩余空间的分割和合并方法确定块装载的目标空间,利用装载序列优化装载方案中的块选择,得到优化的初始装载方案。模拟退火算法结合剩余空间启发式算法采取领域操作策略优化装载序列寻找最优装载方案。实验结果表明,与混合遗传模拟退火算法相比,混合启发式算法在大规模多约束算例上装载率提高了4.90%,稳定性也得到了提高。

带不相关并行机和有限缓冲MHFS调度的混合启发式算法

研究每阶段含不相关并行机的多阶段混合流水车间问题(MHFSP),工件的加工时间取决于所分配的机器,相邻阶段之间缓冲区能力有限.鉴于直接求解该NP-hard问题较为困难,将其转化为带阻塞和不相关并行机的MHFSP (BMHFSP-UPM),建立整数规划模型,基于遗传算法(GA)和禁忌搜索(TS)提出一种混合启发式算法(HHGA&TS)进行求解.在该算法中,设计基于多阶段并行加工的二维矩阵编码方案,继而基于二维矩阵元胞组的初始解群体表述设计参数自适应策略;引入基于工件位-基因位的单点倒置交叉以及基于机器号的单点变异过程,利用GA求解机制完成解更新过程;设计机器号次序交换(MNE)、工件位置交换(JNE)、工件工序变异(JNM)三种邻域解移动规则,从而完成基于MNE-JNE-JNM的TS二次优化.仿真实验测试了多达120个工件的720组不同规模实例,结果表明,相较于GA、TS及NEH-IGA,所提出的混合启发式算法在解的质量方面表现更佳.

一种求解学区划分问题的混合启发式算法

针对目前求解学区划分问题算法搜索过程缺乏记忆,搜索效率不高,容易陷入局部最优而收敛慢等问题,该文提出一种多启动(M)框架下,迭代禁忌搜索(ITS)算法与模拟退火(SA)算法混合的M-ITS-SA算法。该算法包括构造初始解、禁忌搜索、SA算法优化与求解等。运用K-Medoids模型对学校分组后,采用M-ITS-SA算法对学区进行划分与优化,并从多个分区方案中求解最优分区方案。学区划分实验结果表明:该文提出的M-ITS-SA算法能够保证分区的空间连续性,适用于单校和多校划片,并在入学总距离上与混合元启发算法(M-ILS-SPP)保持相当的同时,大大降低了超额招生人数和总用时,具有良好的寻优能力和收敛性,优于M-ILS-SPP算法。

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

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

一体化集货和配送车辆路径问题的混合遗传启发式算法

为满足电子商务客户多样化和个性化的需求,建立多约束条件的一体化集货和配送车辆调度模型。针对模型特点,采用混合遗传启发式算法求解。首先,采用自然数编码,可以使问题变得更简洁;用最佳保留选择法,以保证群体的多样性;用改进的顺序交叉算子避免优良基因片断在顺序交叉时被破坏,保证算法能够收敛到全局最优;其次,对混合遗传算法求得的精英种群进行禁忌搜索求解。通过实例计算表明,该算法好于单独使用遗传算法或是禁忌搜索算法。