车辆路径问题的禁忌搜索算法研究

论文在对车辆路径问题进行简单描述的基础上,通过设计一种新的解的表示方法构造了求解该问题的一种新的禁忌搜索算法,并进行了实验计算。计算结果表明,用本文设计的禁忌搜索算法求解车辆路径问题,不仅可以取得很好的计算结果,而且算法的计算效率较高,收敛速度较快,计算结果也较稳定。     

基于改进蚁群算法的低碳车辆路径问题研究

全球气候恶化危及人类生存环境,物流运输过程中产生的大量温室气体则是祸源之一。本文考虑带有碳排放约束的车辆路径问题（VRP）,以车辆行驶里程最短和碳排放量最小为目标,构建了多目标的VRP非线性规划模型。提出了一种改进的蚁群系统算法对该模型进行求解,算法在更新路径上的蚂蚁信息素时引入了混沌扰动机制,此举能降低算法运行时陷入局部最优解的概率并有效提高算法的适应性。同时,对启发因子、状态转移概率、信息素更新等环节进行了优化设计,提高了最优路径的搜索效率。最后,数值仿真实验证明了该算法的求解表现优于同类研究常用的遗传算法和禁忌搜索算法,具有较强的全局寻优能力。在灵敏性和有效性的保证下,本研究所设计的改进蚁群算法能够较好地处理低碳车辆路径问题（LCVRP）。     

同时集散货物的开放式车辆路径问题研究

本文研究了车辆工作时间限制下同时集散货物的多配送中心开放式车辆路径问题,以车辆数和运输里程最小为目标,建立了多目标规划模型,提出了基于拉格朗日松弛技术和禁忌搜索算法的混合求解算法。 该算法首先求出最优解的最大下界,然后采用客户点的分配和调整策略实现解的可行化,其中禁忌搜索引入了4种领域搜索方法,采用了随机变领域搜索方法和重起策略。算例分析表明,该算法能有效地找到满意解,且采用开放式安排路线比闭合式安排路线更加经济合理。     

禁忌搜索算法在单分配多枢纽轴辐式物流网络中的应用

随着经济的发展,轴辐式网络因有提高运输效率,优化资源配置,产生范围经济等作用越来越多的受到各方面学者的关注。本文对轴辐式网络进行优化分析,改进轴辐式网络的多重分配多枢纽中位问题模型,得到无容量限制的单分配多枢纽中位问题模型(USApHLP)的混合整数线性规划模型,并采用改进的禁忌搜索智能算法来求解,通过算例验证了禁忌搜索算法可以有效的求解单分配多枢纽中位问题。     

环状区域的车辆路径方案生成系统及优化模型

针对顾客满足环状区域分布的车辆路径问题(VRP),以大幅度地缩减问题求解的状态空间为突破口,引入人工智能和运筹学理论,提出求解这类特殊车辆路径问题的两阶段方法.第1阶段考虑行车时间和车载容量,提出带有控制策略的深度优先搜索算法自动生成备选的车辆路径方案集合.第2阶段将此备选方案集合归结为整数规划模型.采用VB6.0编程语言构建了车辆路径方案生成系统,并实现该系统与运筹学求解软件lindo的集成.通过案例验证了上述方法及自动求解系统的有效性.该项研究为解决环状配送区域的车辆路径问题这一难题提供了新方法.     

免疫遗传算子改进单亲遗传算法的研究

比较传统遗传算法(TGA)和单亲遗传算法(PGA)的异同,进而论述了PGA主要算子的实施方法和现存问题即由于PGA各算子的随机性过强,难以避免算法的"早熟".为此引入具有强收敛性的免疫遗传算子(IG0),测试表明结合算法IGO-PGA改进了PGA的性能.根据对TSPLIB中3个TSP问题的求解精度和运行时间的比较得出结论TGA性能低于PGA和IGO-PGA;PGA运行时间短、但求解精度一般;IG0-PGA与PGA时间复杂度相似,而求解精度在3个算法中表现最高,解决130个点的TSP问题(chl30)求解误差低于O.05,生成的路径图具有研究应用价值.     

平行机作业环境下的订单分配与排序

针对一类平行机作业环境下的订单分配与排序问题,从整体的角度协同优化供应链中的订单分配、生产调度和分批运输调度。以完成所有订单的总订货提前期与生产运输总成本的加权和最小化为目标,构建了问题的数学模型。将基于向量组编码结构的禁忌搜索算法与基于动态规划方法的启发式算法相结合,设计了一种混合优化算法以求解问题。对不同策略和不同算法进行比较,数据实验结果显示了订单分配与排序策略的优越性及所提算法的有效性。     

自动化立体仓库中的储位分配及存取路径优化

储位分配和存取作业路径优化是仓储管理中的两个重要决策问题。本文研究如何在自动化立体仓库中对这两个问题进行同时决策。提出了一个混合整数规划模型对该问题进行优化建模,设计开发了一个基于有向连接图的两阶段优化算法对问题求初始解,并利用禁忌搜索算法对所求得的解进行改进。算法第一阶段解决储位分配问题,在此基础上第二阶段利用Hungarian算法对堆垛机的存取作业路径优化问题进行求解。最后利用实例对算法效率和精度进行分析评价,计算结果验证了算法的有效性。     

基于实时信息的游客行程动态规划研究

基于实时信息的游客行程动态规划问题可适用于城市景点的游客行程规划、主题公园的游客行程规划、博物馆的游客游览路线规划等服务系统的实际场景。本文采用重规划方法将该问题转化为离散时间段上的静态规划子问题,建立了对应的混合线性整数规划模型,并证明了该问题的NP难性质。提出了一种分支定界算法来求解静态子问题的优化模型,并设计了一种变邻域搜索算法来求解对应的大规模问题。通过数值实验验证了所提的模型和算法,并进行了算法参数标定和算法比较分析。数值实验的结果表明,所提分支定界算法和变邻域搜索算法的计算性能都明显优于已有文献的算法。所提的模型和算法可以嵌入到管理信息系统中,对于提升服务系统的工作效率、降低顾客的等待时间、优化服务系统的资源配置等具有实际意义。     

考虑三维装箱约束的车辆路径问题研究

针对实际物流配送问题的特点,建立考虑三维装箱约束的车辆路径问题模型,提出求解该问题的引导式局部搜索算法。采用改进的模糊遗传算法求解车辆路径问题,提出一种新的模糊逻辑控制器,并采用引导式局部搜索算法求解三维装箱问题。通过计算标准算例检验算法性能,试验结果表明引导式局部搜索算法能够在较短时间内得到质量较高的近似最优解。     

An efficient tabu search algorithm for the single- machine mean tardiness problem

In this paper, an efficient tabu search algorithm is prepared for solving the single-machine mean tardiness problem. The proposed implementation of the tabu search approach suggests simple techniques for generating neighbourhoods of a given sequence and a combined scheme for intensification and diversification. The tabu search method is shown to produce results very close to the optimal solution using randomly generated problems with varying degrees of difficulty.     

SEQUENCING AND BATCHING FOR TWO CLASSES OF JOBS WITH DEADLINES AND SETUP TIMES

We formulate a general sequencing problem that includes two classes of jobs with setup times, setup costs, holding costs, and deadlines. The formulation is unique in its explicit recognition of the opportunities to exploit productive capacity increases due to batching. An algorithm based on tabu search is then used as a solution method. Computational results are presented that suggest that the algorithm is effective.     

Multi-start iterated tabu search for the minimum weight vertex cover problem

The minimum weight vertex cover problem (MWVCP) is one of the most popular combinatorial optimization problems with various real-world applications. Given an undirected graph where each vertex is weighted, the MWVCP is to find a subset of the vertices which cover all edges of the graph and has a minimum total weight of these vertices. In this paper, we propose a multi-start iterated tabu search algorithm (MS-ITS) to tackle MWVCP. By incorporating an effective tabu search method, MS-ITS exhibits several distinguishing features, including a novel neighborhood construction procedure and a fast evaluation strategy. Extensive experiments on the set of public benchmark instances show that the proposed heuristic is very competitive with the state-of-the-art algorithms in the literature.     

The permutation flow shop problem with blocking. A tabu search approach

This paper develops a fast tabu search algorithm to minimize makespan in a flow shop problem with blocking. Some properties of the problem associated with the blocks of jobs have been presented and discussed. These properties allow us to propose a specific neighbourhood of algorithms. Also, the multimoves are used that consist in performing several moves simultaneously in a single iteration and guide the search process to more promising areas of the solutions space, where good solutions can be found. It allow us to accelerate the convergence of the algorithm. Besides, a dynamic tabu list is proposed that assists additionally to avoid being trapped at a local optimum. The proposed algorithms are empirically evaluated and found to be relatively more effective in finding better solutions than attained by the leading approaches in a much shorter time. The presented ideas can be applied in many local search procedures.     

Hybrid Evolutionary Algorithms for Graph Coloring

A recent and very promising approach for combinatorial optimization is to embed local search into the framework of evolutionary algorithms. In this paper, we present such hybrid algorithms for the graph coloring problem. These algorithms combine a new class of highly specialized crossover operators and a well-known tabu search algorithm. Experiments of such a hybrid algorithm are carried out on large DIMACS Challenge benchmark graphs. Results prove very competitive with and even better than those of state-of-the-art algorithms. Analysis of the behavior of the algorithm sheds light on ways to further improvement.     

低碳环境下的车辆路径问题及禁忌搜索算法研究

基于节能减排的新视角,本文研究了低碳环境下由第三方提供运输服务的车辆路径问题,在安排车辆路径时,同时考虑了能耗、碳排放和租车费用,而这些费用不仅与距离有关,也与客户点的需求量和车辆速度有关。提出了考虑车辆运量和速度的能耗计算方法,建立了非满载运输方式下的低碳路径模型——LCRP。设计了基于路径划分的禁忌搜索算法RS-TS对问题进行求解,该算法引入了一种新颖的路径编码与解码算法WSS,采用了三种邻域搜索方法。通过基准测试实例验证了算法能有效地找到满意解,并揭示了距离、能耗、行驶时间等参数之间的关系,实验分析表明采用低碳路径安排更加经济环保且选择中低的交通速度更有利于节约能耗和降低碳排放。     

Multi-neighborhood based iterated tabu search for routing and wavelength assignment problem

The routing and wavelength assignment problem (RWA) has shown to be NP-hard if the wavelength continuity constraint and the objective of minimizing the number of wavelengths are considered. This paper introduces a multi-neighborhood based iterated tabu search algorithm (MN-ITS), which consists of three neighborhoods with a unified incremental evaluation method, to solve the min-RWA problem. The proposed MN-ITS algorithm is tested on a set of widely studied real world instances as well as a set of challenging random ones in the literature. Comparison with other reference algorithms shows that the MN-ITS algorithm is able to improve five best upper bounds obtained by other competitive reference algorithms in the literature. This paper also presents an analysis to show the significance of the unified incremental evaluation technique and the combination of multiple neighborhoods.