变邻域模拟退火算法求解速度时变的VRPTW问题

本文在经典的带时间窗的车辆路径问题(VRPTW)的基础上,考虑不同时间段车辆行驶速度不同的情况,研究速度时变的带时间窗车辆路径问题(TDVRPTW),使问题更具实际意义。本文用分段函数表示不同时间段下的车辆行驶速度,并解决了速度时变条件下行驶时间计算的问题。针对模拟退火算法(SA)在求解VRPTW问题时易陷入局部最优解,变邻域搜索算法(VNS)在求解VRPTW问题时收敛速度慢的问题,本文将模拟退火算法以一定概率接受非最优解的思想和变邻域搜索算法系统地改变当前解的邻域结构以拓展搜索范围的思想结合起来,提出了一种改进的算法——变邻域模拟退火算法(SAVN),使算法在退火过程中一陷入局部最优解就改变邻域结构,更换搜索范围,以此提升算法跳出局部最优解的能力,加快收敛速度。通过在仿真实验中将SAVN算法的求解结果与VNS算法、SA算法进行对比,验证了SAVN算法确实能显著提升算法跳出局部最优解的能力。     

改进的二进制粒子群算法求解车辆路径问题

设计了一种改进的二进制粒子群优化算法来求解车辆路径问题,算法基于粒子群算法的寻优模式充分考虑粒子之间的导向作用,改进二进制粒子群算法的位取值方式,减小了在进化过程中停滞于局部最优解的概率,并通过构造辅助函数处理优化问题的约束条件,基于分层次实现多个目标的思路来寻优,提高了算法的搜索效率和计算速度.实验测试结果验证了该算法对求解车辆路径问题的适用性和有效性.     

求解带时间窗车辆路径问题的混合Memetic算法

为提高带时间窗车辆路径问题的求解精度和求解效率,设计了一种混合Memetic算法。采用基于时间窗升序排列的混合插入法构造初始种群,提高解质量的同时兼顾多样性,扩大搜索空间;任意选择组成父代种群,以维持搜索空间;运用简化的变邻域搜索进行局部开发,引入邻域半径减少策略提高开发效率,约束放松机制开放局部空间;以弧为对象,增加种群向当前最优解和全局最优解的后学习过程。实验结果表明,所提出的算法具有较好的寻优精度和稳定性,能搜索到更好的路径长度结果,更新了现有研究在最短路径长度的目标函数上的下限。     

求解旅行商问题的基于类Kruskal的混合粒子群算法

本文针对求解旅行商问题的标准粒子群算法所存在的早熟和低效的问题,提出一种基于Greedy Heuristic的初始解与粒子群相结合的混合粒子群算法(SKHPSO)。该算法通过本文给出的类Kruskal算法作为Greedy Heuristic的具体实现手段,产生一个较优的初始可行解,作为粒子群中的一员,然后再用改进的混合粒子群算法进行启发式搜索。SKHPSO的局部搜索借鉴了Lin-Kernighan邻域搜索,而全局搜索结合了遗传算法中的交叉及置换操作。应用该算法对TSPLIB中的典型算例进行了算法测试分析,结果表明:SKHPSO可明显提高求解的质量和效率。     

基于改进粒子群算法的学习路径优化方法

提出一种改进粒子群算法求解在线学习系统中的学习路径优化问题.在建模时综合考虑了学习者的学习目标、知识掌握水平、学习成本和资源相关度等因素;在寻优时采用局部邻域搜索与禁忌搜索相结合的方式,以改进标准粒子群方法的寻优性能.实验结果表明,该方法具有较高的实用性和准确性,是学习路径优化问题的一种有效求解算法.     

基于量子粒子群算法的电力系统负荷多目标优化分配

针对电力系统经济负荷优化分配问题,提出了一种基于量子粒子群的多目标优化算法.该算法通过将改进后的量子进化算法融合到粒子群中,采用量子位对粒子的当前位置进行编码,用量子旋转门实现对粒子最优位置的搜索,用量子非门实现粒子位置的变异以避免早熟收敛.这种搜索机制能够遍历解空间,增强种群的多样性,并能用量子位的概率幅将最优解表述为解空间中的多种表述形式,从而增强全局最优的可能性.最后,通过算例进行仿真分析,结果表明算法的搜索能力和优化效率均优于普通粒子群算法.     

求解柔性作业车间调度的动态群智能优化算法

针对柔性作业车间调度问题,提出一种新型两阶段动态混合群智能优化算法.算法初始阶段采用动态邻域的协同粒子群进行粗搜索,第二阶段提出了基于混沌算子的蜂群进行细搜索,既增强了种群多样性,又提高了算法搜索精度,实现了全局搜索与局部搜索能力的有效平衡.针对柔性作业车间调度问题特点,采用独特的编码方式和位置更新策略来避免不合法解的产生.最后将此算法在不同规模的实例上进行了仿真测试,并与最近提出的其他几种具有代表性的算法进行了比较,验证了算法的有效性和优越性.     

随机混流U型拆卸线平衡排序问题多目标进化算法优化

针对混流U型拆卸线平衡排序问题,考虑拆卸时间不确定,建立了该问题最小拆卸线平均闲置率、尽早拆卸危害和高需求零部件、最小化平均方向改变次数的多目标优化模型,并提出一种基于分解和动态邻域搜索的混合多目标进化算法(Hybrid Multi-objective Evolutionary Algorithm Based on Decomposition, HMOEA/D)。该算法通过采用弹性任务分配策略、动态邻域结构和动态调整权重以保证解的可行性并搜索得到分布较好的非劣解集。最后,仿真求解实验设计技术(DOE)生成的测试算例,结果表明HMOEA/D较其它算法能得到更接近Pareto最优、分布更好的近似解集。     

凸二次半定规划一个新的原始对偶路径跟踪算法

本文提出求解凸二次半定规划的一个新的原始对偶路径跟踪算法.在每次迭代中,通过求解一个线性方程组产生搜索方向.在一定条件下证明算法产生的迭代点列落在中心路径的邻域内,且算法至多经■次迭代可得到一个ε-最优解.     

变邻域搜索分布估计算法求解舰载机保障作业调度问题

针对多资源、多约束的资源受限舰载机保障作业调度问题,提出了一种求解该问题的基于变邻域搜索的分布估计算法.首先,建立了考虑站位、设备、作业的优先级和安全性等约束的调度模型,该模型以舰载机保障作业的总完成时间和舰载机移动次数的加权和最小化为目标;其次,结合问题特征分析,提出了最早可用设备规则,对偶站位交换规则等两类启发式规则,定义了基于序置换排列的解的编码方式;再次,提出了分布估计算法(EDA)的概率分布更新模型,以及基于工序插入、交换、反转等邻域操作的变邻域搜索策略,设计了基于变邻域搜索的分布估计算法(EDAVNS);最后,基于单波次8架舰载机保障的仿真结果,验证了所提模型对舰载机保障作业调度问题具有较好的实用性.同时,基于5个不同规模的问题集的分析结果表明:与分布估计算法、变邻域搜索、遗传算法、以及只使用插入、交换、反转等单一邻域操作的EDA算法相比,EDAVNS均取得了最优的结果,验证了EDAVNS能有效地求解该问题,并较好地平衡全局探索与局部搜索.     

Solving the two-echelon location routing problem by a GRASP reinforced by a learning process and path relinking

The two-echelon location-routing problem (LRP-2E) arises from recent transportation applications like city logistics. In this problem, still seldom studied, first-level trips serve from a main depot a set of satellite depots, which must be located, while second-level trips visit customers from these satellites. After a literature review on the LRP-2E, we present four constructive heuristics and a hybrid metaheuristic: A greedy randomized adaptive search procedure (GRASP) complemented by a learning process (LP) and path relinking (PR). The GRASP and learning process involve three greedy randomized heuristics to generate trial solutions and two variable neighbourhood descent (VND) procedures to improve them. The optional path relinking adds a memory mechanism by combining intensification strategy and post-optimization. Numerical tests show that the GRASP with LP and PR outperforms the simple heuristics and an adaptation of a matheuristic initially published for a particular case, the capacitated location-routing problem (CLRP). Additional tests on the CLRP indicate that the best GRASP competes with the best metaheuristics published.     

军事物流系统中定位-运输路线安排模型及算法

考虑到战时物资需求的紧迫性和保障资源的有限性,从决策者的角度出发,以军事物流系统总体供应时间最短为目标,构建了两级军事配送网络的定位-运输路线安排模型,并给出一种启发式算法.算法分为两个阶段,首先利用蚁群算法和线性规划的方法解决运输路线安排问题,然后运用贪婪搜索算法解决军事物流配送中心选址问题.最终,将两种算法结合起来进行逐步搜索,从而得到模型的解,并运用实例说明了算法的有效性和可行性.     

A variable neighborhood search for the network design problem with relays

Given a set of commodities to be routed over a network, the network design problem with relays involves selecting a route for each commodity and determining the location of relays where the commodities must be reprocessed at certain distance intervals. We propose a hybrid approach based on variable neighborhood search. The variable neighborhood algorithm searches for the route for each commodity and the optimal relay locations for a given set of routes are determined by an implicit enumeration algorithm. We show that dynamic programming can be used to determine the optimal relay locations for a single commodity. Dynamic programming is embedded into the implicit enumeration algorithm to solve the relay location problem optimally for multiple commodities. The special structure of the problem is leveraged for computational efficiency. In the variable neighborhood search algorithm, the routes of the current solution are perturbed and reconstructed to generate neighbor solutions using random and greedy construction heuristics. Computational experiments on three sets of problems (80 instances) show that the variable neighborhood search algorithm with optimal relay allocations outperforms all existing algorithms in the literature.     

A Particle Swarm Optimization Algorithm with Path Relinking for the Location Routing Problem

This paper introduces a new hybrid algorithmic nature inspired approach based on particle swarm optimization, for solving successfully one of the most popular logistics management problems, the location routing problem (LRP). The proposed algorithm for the solution of the location routing problem, the hybrid particle swarm optimization (HybPSO-LRP), combines a particle swarm optimization (PSO) algorithm, the multiple phase neighborhood search – greedy randomized adaptive search procedure (MPNS-GRASP) algorithm, the expanding neighborhood search (ENS) strategy and a path relinking (PR) strategy. The algorithm is tested on a set of benchmark instances. The results of the algorithm are very satisfactory for these instances and for six of them a new best solution has been found.      

A reactive GRASP with path relinking for capacitated clustering

This paper presents a greedy randomized adaptive search procedure (GRASP) coupled with path relinking (PR) to solve the problem of clustering n nodes in a graph into p clusters. The objective is to maximize the sum of the edge weights within each cluster such that the sum of the corresponding node weights does not exceed a fixed capacity. In phase I, both a heaviest weight edge (HWE) algorithm and a constrained minimum cut algorithm are used to select seeds for initializing the p clusters. Feasible solutions are obtained with the help of a self-adjusting restricted candidate list that sequentially guides the assignment of the remaining nodes. At each major GRASP iteration, the list length is randomly set based on a probability density function that is updated dynamically to reflect the solution quality realized in past iterations. In phase II, three neighborhoods, each defined by common edge and node swaps, are explored to attain local optimality. The following exploration strategies are investigated: cyclic neighborhood search, variable neighborhood descent, and randomized variable neighborhood descent (RVND). The best solutions found are stored in an elite pool.     

Solving the flight perturbation problem with meta heuristics

When there is a perturbation in a carefully constructed aircraft schedule, e.g. an aircraft breakdown, it is important to minimize the negative consequences of this disturbance. Here, a tabu search and a simulated annealing approach to the flight perturbation problem are presented. The heuristics use a tree-search algorithm to find new schedules for the aircraft, and utilize a path relinking strategy to explore paths between structurally different solutions. The computational results indicate that the solution strategies, especially the tabu search, can be successfully used to solve the flight perturbation problem.     

Path Relinking, Cycle-Based Neighbourhoods and Capacitated Multicommodity Network Design

In this paper, we propose a path relinking procedure for the fixed-charge capacitated multicommodity network design problem. Cycle-based neighbourhoods are used both to move along paths between elite solutions and to generate the elite candidate set by a tabu-like local search procedure. Several variants of the method are implemented and compared. Extensive computational experiments indicate that the path relinking procedure offers excellent results. It systematically outperforms the cycle-based tabu search method in both solution quality and computational effort and offers the best current meta-heuristic for this difficult class of problems.     

铁路应急设施非概率可靠性选址优化研究

为解决小样本、贫信息下铁路应急资源储备点的可靠性选址问题,创新性地将选址-路径问题与区间非概率可靠性方法结合起来,考虑灾情发生后应急设施点在可接受的时间范围内响应受灾点的需求能力及其稳定程度,采用区间值度量路段阻抗,基于区间非概率可靠性理论及区间运算规则,提出路径的非概率可靠性度量及可靠最短路径选择方法;建立基于区间时间阻抗下可靠最短路径的无容量设施选址模型,提出约束条件限制的Monte Carlo改进算法,确定了铁路资源储备点选址的最优方案。实例表明,本文的优化方案能更好地保证救援的时间可靠性,改进的求解算法具有更小的时间复杂度,有效地缩短了运算时间,改善了解的质量。本文的方法与模型体系对于实现铁路应急设施可靠性选址,为决策者提供决策支持,提高铁路应急响应能力具有重要的指导意义。     

A path relinking algorithm for a multi-depot periodic vehicle routing problem

In this paper, we consider a multi-depot periodic vehicle routing problem which is characterized by the presence of a homogeneous fleet of vehicles, multiple depots, multiple periods, and two types of constraints that are often found in reality, i.e., vehicle capacity and route duration constraints. The objective is to minimize total travel costs. To tackle the problem, we propose an efficient path relinking algorithm whose exploration and exploitation strategies enable the algorithm to address the problem in two different settings: (1) As a stand-alone algorithm, and (2) As a part of a co-operative search algorithm called integrative co-operative search. The performance of the proposed path relinking algorithm is evaluated, in each of the above ways, based on standard benchmark instances. The computational results show that the developed PRA performs well, in both solution quality and computational efficiency.     

Pareto memetic algorithm with path relinking for bi-objective traveling salesperson problem

The paper presents an effective version of the Pareto memetic algorithm with path relinking and efficient local search for multiple objective traveling salesperson problem. In multiple objective Traveling salesperson problem (TSP), multiple costs are associated with each arc (link). The multiple costs may for example correspond to the financial cost of travel along a link, time of travel, or risk in the case of hazardous materials. The algorithm searches for new good solutions along paths in the decision space linking two other good solutions selected for recombination. Instead of a simple local search it uses short runs of tabu search based on the steepest version of the Lin–Kernighan algorithm. The efficiency of local search is further improved by the techniques of candidate moves and locked arcs. In the final step of the algorithm the neighborhood of each potentially Pareto-optimal solution is searched for new solutions that could be added to this set. The algorithm is compared experimentally to the state-of-the-art algorithms for multiple objective TSP.