求解多车型校车路径问题的混合集合划分的GRASP算法

针对不同规划场景下具有不同优化目标的多车型校车路径问题(HSBRP),提出一种混合集合划分(SP)的贪婪随机自适应(Greedy Randomized Adaptive Search Procedure,GRASP)算法。根据GRASP算法寻优过程中产生的路径信息构建SP模型,然后使用CPLEX精确优化器对SP模型进行求解。为了适应不同类型的HSBRP问题,改进GRASP的初始解构造函数得到一个可行解,并将其对应的路径放入路径池;在局部搜索过程中应用多种邻域结构和可变邻域下降(VND)来提升解的质量,同时在路径池中记录在搜索过程中得到提升的路径和在每次迭代中得到局部最好解的路径信息。使用基准测试案例进行测试,实验结果表明在GRASP算法中,混合SP能够有效地提高算法的求解性能和稳定性,并且该算法能适应不同优化目标下车型混合和车辆数限制两类HSBRP的求解;与现有算法的比较结果再次验证了所提算法的有效性。     

车辆数限制的多车型校车路径问题模型及算法研究

为适应校车路径规划中校车有多种车型且每种车型数量受限的需求,建立车辆数限制的多车型校车路径问题(HFSBRP)的数学模型,并提出一种迭代局部搜索算法进行求解。该算法借助邻域随机选择的变邻域下降搜索(VND)算法完成局部提升。局部提升过程中,首先调整车型,然后再混合使用缩减路径数和提高车辆利用率的邻域解接受策略以提高算法的寻优能力,为保证解的多样性,允许接受一定偏差范围内的邻域解。此外,为避免算法过早陷入局部最优,设计了多点交换和移动的扰动规则。基于国际基准测试案例进行模型验证和算法测试,实验结果表明了模型的正确性和算法的有效性。     

校车路径问题的改进迭代局部搜索算法

针对考虑站点服务时间、学生最大乘车时间约束的校车路径问题(SBRP),提出一种改进迭代局部搜索(ILS)算法以提升求解质量。该算法使用大规模邻域搜索(LNS)算法作为扰动算子;在解的破坏过程中,设计一组解的破坏因子并赋以一定的选择概率,每隔若干次迭代后根据解的质量自适应更改破坏因子的选择概率,进而调整解的破坏程度。为提升ILS解的多样性,算法采用了基于偏差系数的邻域解接受准则。在国际基准测试案例上进行了测试,测试结果表明在ILS算法中使用自适应调整破坏程度的LNS扰动比常规扰动和其他破坏扰动的求解质量有大幅提升;与蚁群算法的比较结果进一步验证了改进算法的有效性。     

一种求解多校多车型校车路径问题的元启发算法

针对多种车型可用的多校校车路径问题(SBRP),建立数学模型,并提出了一种迭代局部搜索(ILS)元启发算法进行求解。该算法引入并改进了带时间窗的装卸一体化问题(PDPTW)求解中的点对邻域算子,并使用可变邻域下降搜索(VND)完成局部提升。局部提升过程中,设计一种基于路径段的车型调整策略,尽可能地调整车型,降低成本,并允许接受一定偏差范围内的邻域解以保证搜索的多样性。对于局部提升得到的最好解,使用多点移动方法对其进行扰动,以避免算法过早陷入局部最优。在国际基准测试案例上分别测试多校混载和不混载模式下算法的性能,实验结果验证了设计算法的有效性。进一步使用提出的算法求解单车型多校SBRP问题,并与后启发算法、模拟退火算法和记录更新法等算法进行比较,实验结果表明该算法仍然能够获得较好的优化效果。     

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

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

需求可拆分校车路径问题的元启发式算法

校车路径规划中,允许站点乘车需求拆分通常能有效地降低校车服务成本。将该问题定义为需求可拆分校车路径问题(SDSBRP)进行求解。由于校车服务中要顾及学生最大乘车时间,且优化目标要兼顾所需校车数量和校车行驶距离,经典SDVRP算法难以直接应用于SDSBRP。因此分析了该问题的解特征,首次构建双目标SDSBRP数学模型,并首次设计针对该问题的元启发式求解算法。该算法首先构造初始可行解,然后在模拟退火算法框架下,引入站点需求拆分的邻域搜索算子进行迭代搜索,逐步改善解的质量。邻域搜索中,设计了多目标问题的邻域接受准则来引导邻域解的搜索方向,并引入破坏重建机制来增加解的多样性。使用已有的测试案例集和改造的测试案例进行算法测试,实验结果表明所提算法收敛性好,能够显著降低校车服务成本。     

基于局部视觉感知及语义联想的图像理解模型

对一个区域内多所学校进行校车路径规划时,允许校车混载不同学校的学生能显著地减少校车数量,从而降低运营成本。已有学者针对允许混载的校车路径问题(SBRP)提出了启发式算法,但这些算法对邻域解的搜索不够全面,在缩减路径方面仍有较大的提升空间。提出了一种以记录更新法(record-to-record travel,RRT)为基础的启发式算法。该算法从初始解出发,利用求解有时间窗装卸问题(PDPTW)时使用的算子搜索邻域解,逐步优化校车路径数目。与现有算法相比,该算法扩展了求解混载SBRP的启发策略,能够在全局范围内对校车路径进行优化,从而获得所需校车较少的路径规划方案。实验结果验证了该算法的有效性。     

基于搜索信息反馈策略的MaxSAT非完备求解算法

MaxSAT问题是SAT可满足性问题的优化形式，具有NP难度．本文分析了传统的MaxSAT局部搜索求解器对工业算例求解存在的局限性，并基于此分析提出了新的初始解构造算法ASIF.ASIF是一个基于树形赋值的初始解构造算法，其中包含了一个全局信息反馈策略.该算法选取并定义了构造过程中有意义的统计量，使用这些量设计了一个全局搜索信息更新反馈机制，对初始解构造过程中的经验进行积累并为后续解的构造提供指导信息，再根据后续解的构造情况对全局经验进行反馈和更新，从而有效利用了解构造过程中的经验和信息.进一步地，将ASIF作为初始解构造算法，结合IPBMR算法中的路径截断（PB）策略，提出了新的算法PB-ASIF.实验设计与比较共分为三个阶段.第一阶段，将ASIF在300秒内首次找到的可行解与IPBMR求解300秒的结果进行对比.ASIF初始可行解更优的数量是IPBMR在300秒内求解的可行解更优数量的两倍多，其中非加权偏类算例更优解数量上前者更是后者的3.68倍.该阶段的实验结果表明，ASIF算法能快速构造优质的初始可行解.第二阶段，将PB-ASIF与IPBMR进行对比实验，在300秒求解时间内，...     

面向动态车辆路径的改进变邻域搜索算法

为了切实求解带时间窗的车辆动态路径问题,提出一种改进变邻域搜索算法,并建立了相应数学模型。算法运用聚类方法完成客户分配和路线规划的初始解构建。插入一交换混合算子实现抖动过程,提出后优化过程改进解空间,并采用最佳改进策略实现算法在求解质量和运行时间上的最佳平衡,引入模拟退火思想控制新解接受、地理位置分布等,并对路径选择进行了分析。通过与其他算法的实验结果比较表明该算法的可行性和高效性。     

基于带随机需求的限量弧路径规划概率型邻域搜索算法

针对带随机需求的限量弧路径规划( CARPSD)问题,建立基于期望与方差的数学模型,设计一种概率型邻域搜索算法。采用随机路径扫描产生初始种群,构建最优解集。根据影响解的质量的4个关键指标,构建4种领域结构。应用算法的概率机制,计算邻域搜索的强度,进行大小邻域结构的转化,指导邻域搜索。通过Restart策略,扩大解空间的范围。实验结果表明,该算法可有效解决CARPSD问题,比自适应较大的邻域算法具有更强的寻优能力。     

A GRASP with evolutionary path relinking for the truck and trailer routing problem

In the truck and trailer routing problem (TTRP) a heterogeneous fleet composed of trucks and trailers has to serve a set of customers, some only accessible by truck and others accessible with a truck pulling a trailer. This problem is solved using a route-first, cluster-second procedure embedded within a hybrid metaheuristic based on a greedy randomized adaptive search procedure (GRASP), a variable neighborhood search (VNS) and a path relinking (PR). We test PR as a post-optimization procedure, as an intensification mechanism, and within evolutionary path relinking (EvPR). Numerical experiments show that all the variants of the proposed GRASP with path relinking outperform all previously published methods. Remarkably, GRASP with EvPR obtains average gaps to best-known solutions of less than 1% and provides several new best solutions.     

GRASP with evolutionary path-relinking for the capacitated arc routing problem

The Capacitated Arc Routing Problem (CARP) is a well-known NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours servicing a subset of required edges under vehicle capacity constraints. There are numerous applications for the CARP, such as street sweeping, garbage collection, mail delivery, school bus routing, and meter reading. A Greedy Randomized Adaptive Search Procedure (GRASP) with Path-Relinking (PR) is proposed and compared with other successful CARP metaheuristics. Some features of this GRASP with PR are (i) reactive parameter tuning, where the parameter value is stochastically selected biased in favor of those values which historically produced the best solutions in average; (ii) a statistical filter, which discard initial solutions if they are unlikely to improve the incumbent best solution; (iii) infeasible local search, where high-quality solutions, though infeasible, are used to explore the feasible/infeasible boundaries of the solution space; (iv) evolutionary PR, a recent trend where the pool of elite solutions is progressively improved by successive relinking of pairs of elite solutions. Computational tests were conducted using a set of 81 instances, and results reveal that the GRASP is very competitive, achieving the best overall deviation from lower bounds and the highest number of best solutions found.     

Skewed general variable neighborhood search for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem (CCVRP) is a relatively new version of the classical capacitated vehicle routing problem, and it is equivalent to a traveling repairman problem with capacity constraints and a homogeneous vehicle fleet, which aims to minimize the total arrival time at customers. Many real‐world applications can be modeled by this problem, such as the important application resulting from the humanitarian aid following a natural disaster. In this paper, two heuristics are proposed. The first one is a constructive heuristic to generate an initial solution and the second is the skewed variable neighborhood search (SVNS) heuristic. The SVNS algorithm starts with the initial solution. At each iteration, the perturbation phase and the local search phase are used to improve the solution of the CCVRP, and the distance function in acceptance criteria phase is used to improve the exploration of faraway valleys. This algorithm is applied to a set of benchmarks, and the comparison results show that the proposed algorithms provide better solutions than those reported in the previous literature on memetic algorithms and adaptive large neighborhood search heuristics.     

A mixed load capacitated rural school bus routing problem with heterogeneous fleet: Algorithms for the Brazilian context

A capacitated rural school bus routing problem featuring mixed loads, a heterogeneous fleet, and the same school starting time is here addressed. This is an important problem of the routing literature which has been attracting the attention of many researchers recently. The mixed load feature allows students from different schools to ride the same bus at the same time. Five meta-heuristic based algorithms were devised to solve the problem, and evaluated on solving four different datasets, one of them being based on a real case from Brazil. Four traditional local search neighborhood structures for vehicle routing problems were adapted and specialized to handle mixed loads and a heterogeneous fleet simultaneously. To the best of the authors knowledge, it is the first time that both features are treated jointly within an algorithm, and not as a post processing optimization step. The attained cost savings and reduction of fleet sizes suggest the suitability of a mixed load, heterogeneous fleet approach for sparsely populated rural areas. Moreover the devised framework has been embedded into a decision support system which is assisting several municipalities of the state of Minas Gerais, Brazil, to better plan their routes and reduce transportation costs.     

An efficient variable neighborhood search heuristic for very large scale vehicle routing problems

In this paper, we present an efficient variable neighborhood search heuristic for the capacitated vehicle routing problem. The objective is to design least cost routes for a fleet of identically capacitated vehicles to service geographically scattered customers with known demands. The variable neighborhood search procedure is used to guide a set of standard improvement heuristics. In addition, a strategy reminiscent of the guided local search metaheuristic is used to help escape local minima. The developed solution method is specifically aimed at solving very large scale real-life vehicle routing problems. To speed up the method and cut down memory usage, new implementation concepts are used. Computational experiments on 32 existing large scale benchmarks, as well as on 20 new very large scale problem instances, demonstrate that the proposed method is fast, competitive and able to find high-quality solutions for problem instances with up to 20,000 customers within reasonable CPU times.     

The fixed set search applied to the power dominating set problem

In this article, we focus on solving the power dominating set problem and its connected version. These problems are frequently used for finding optimal placements of phasor measurement units in power systems. We present an improved integer linear program (ILP) for both problems. In addition, a greedy constructive algorithm and a local search are developed. A greedy randomised adaptive search procedure (GRASP) algorithm is created to find near optimal solutions for large scale problem instances. The performance of the GRASP is further enhanced by extending it to the novel fixed set search (FSS) metaheuristic. Our computational results show that the proposed ILP has a significantly lower computational cost than existing ILPs for both versions of the problem. The proposed FSS algorithm manages to find all the optimal solutions that have been acquired using the ILP. In the last group of tests, it is shown that the FSS can significantly outperform the GRASP in both solution quality and computational cost.