多中心联合配送模式下集货需求随机的VRPSDP问题

针对多中心联合配送模式下集货需求随机的同时配集货车辆路径问题(MDVRPSDDSPJD), 构建了两阶段MDVRPSDDSPJD模型. 预优化阶段基于随机机会约束机制以及车载量约束为客户分配车辆, 生成预优化方案; 重优化阶段采用失败点重优化策略对服务失败点重新规划路径. 根据问题特征, 设计了自适应变邻域文化基因算法(Adaptive memetic algorithm and variable neighborhood search, AMAVNS), 针对文化基因算法易早熟、局部搜索能力弱等缺陷, 将变邻域搜索算法的深度搜索能力运用到文化基因算法的局部搜索策略中, 增强算法的局部搜索能力; 提出自适应邻域搜索次数策略和自适应劣解接受机制平衡种群进化所需的广度和深度. 通过多组算例验证了提出模型及算法的有效性. 研究成果不仅深化和拓展了VRP (Vehicle routing problem)相关理论研究, 也为物流企业制定车辆调度计划提供一种科学合理的方法.     

Improving the quality of heuristic solutions for the capacitated vertex p-center problem through iterated greedy local search with variable neighborhood descent

The capacitated vertex p-center problem is a location problem that consists of placing p facilities and assigning customers to each of these facilities so as to minimize the largest distance between any customer and its assigned facility, subject to demand capacity constraints for each facility. In this work, a metaheuristic for this location problem that integrates several components such as greedy randomized construction with adaptive probabilistic sampling and iterated greedy local search with variable neighborhood descent is presented. Empirical evidence over a widely used set of benchmark data sets on location literature reveals the positive impact of each of the developed components. Furthermore, it is found empirically that the proposed heuristic outperforms the best existing heuristic for this problem in terms of solution quality, running time, and reliability on finding feasible solutions for hard instances.     

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.     

SOLVING THE OPEN SHOP SCHEDULING PROBLEM VIA A HYBRID GENETIC-VARIABLE NEIGHBORHOOD SEARCH ALGORITHM

In this article, a hybrid metaheuristic method for solving the open shop scheduling problem (OSSP) is proposed. The optimization criterion is the minimization of makespan and the solution method consists of four components: a randomized initial population generation, a heuristic solution included in the initial population acquired by a Nawaz-Enscore-Ham (NEH)-based heuristic for the flow shop scheduling problem, and two interconnected metaheuristic algorithms: a variable neighborhood search and a genetic algorithm. To our knowledge, this is the first hybrid application of genetic algorithm (GA) and variable neighborhood search (VNS) for the open shop scheduling problem. Computational experiments on benchmark data sets demonstrate that the proposed hybrid metaheuristic reaches a high quality solution in short computational times. Moreover, 12 new hard, large-scale open shop benchmark instances are proposed that simulate realistic industrial cases.     

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

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

A hybrid metaheuristic approach for the capacitated p-median problem

The capacitated p-median problem (CPMP) seeks to obtain the optimal location of p medians considering distances and capacities for the services to be given by each median. This paper presents an efficient hybrid metaheuristic algorithm by combining a proposed cutting-plane neighborhood structure and a tabu search metaheuristic for the CPMP. In the proposed neighborhood structure to move from the current solution to a neighbor solution, an open median is selected and closed. Then, a linear programming (LP) model is generated by relaxing binary constraints and adding new constraints. The generated LP solution is improved using cutting-plane inequalities. The solution of this strong LP is considered as a new neighbor solution. In order to select an open median to be closed, several strategies are proposed. The neighborhood structure is combined with a tabu search algorithm in the proposed approach. The parameters of the proposed hybrid algorithm are tuned using design of experiments approach. The proposed algorithm is tested on several sets of benchmark instances. The statistical analysis shows efficiency and effectiveness of the hybrid algorithm in comparison with the best approach found in the literature.     

Solving large <Emphasis Type="Italic">p</Emphasis>-median clustering problems by primal–dual variable neighborhood search

Data clustering methods are used extensively in the data mining literature to detect important patterns in large datasets in the form of densely populated regions in a multi-dimensional Euclidean space. Due to the complexity of the problem and the size of the dataset, obtaining quality solutions within reasonable CPU time and memory requirements becomes the central challenge. In this paper, we solve the clustering problem as a large scale p-median model, using a new approach based on the variable neighborhood search (VNS) metaheuristic. Using a highly efficient data structure and local updating procedure taken from the OR literature, our VNS procedure is able to tackle large datasets directly without the need for data reduction or sampling as employed in certain popular methods. Computational results demonstrate that our VNS heuristic outperforms other local search based methods such as CLARA and CLARANS even after upgrading these procedures with the same efficient data structures and local search. We also obtain a bound on the quality of the solutions by solving heuristically a dual relaxation of the problem, thus introducing an important capability to the solution process.     

Variable neighborhood search and local branching

In this paper we develop a variable neighborhood search (VNS) heuristic for solving mixed-integer programs (MIPs). It uses CPLEX, the general-purpose MIP solver, as a black-box. Neighborhoods around the incumbent solution are defined by adding constraints to the original problem, as suggested in the recent local branching (LB) method of Fischetti and Lodi (Mathematical Programming Series B 2003;98:23–47). Both LB and VNS use the same tools: CPLEX and the same definition of the neighborhoods around the incumbent. However, our VNS is simpler and more systematic in neighborhood exploration. Consequently, within the same time limit, we were able to improve 14 times the best known solution from the set of 29 hard problem instances used to test LB.     

Improving simulated annealing with variable neighborhood search to solve the resource-constrained scheduling problem

The purpose of this paper is to improve the simulated annealing method with a variable neighborhood search to solve the resource-constrained scheduling problem. We also compare numerically this method with other neighborhood search (local search) techniques: threshold accepting methods and tabu search. Furthermore, we combine these techniques with multistart diversification strategies and with the variable neighborhood search technique. A thorough numerical study is completed to set the parameters of the different methods and to compare the quality of the solutions that they generate. The numerical results indicate that the simulated annealing method improved with a variable neighborhood search technique is indeed the best solution method. This research was supported by NSERC grant (OGP 0008312) the first author received a FCAR fellowship during her M.Sc. studies.     

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.     

Metaheuristic approaches to grouping problems in high-throughput cryopreservation operations for fish sperm

High-throughput cryopreservation operations of fish sperm is a technology being developed by researchers today. This paper first formulates a grouping problem in high-throughput cryopreservation operations of fish sperm and then develops a heuristic and four metaheuristic algorithms for its solution. The heuristic is modified from one originally proposed for the assembly line balancing problem. The four metaheuristic algorithms include simulated annealing (SA), tabu search (TS), ant colony optimization (ACO), and a hybrid differential evolution (hDE). For each metaheuristic algorithm, four different initialization methods were used. For both SA and TS, five different neighborhood solution generation methods were also studied. Real world data collected from a high-throughput cryopreservation operation was used to test the effectiveness of algorithms with different initialization and neighborhood solution generation methods. For comparison, a base line of grouping by processing order was also established. The results indicate that: (i) all algorithms performed better than the base line; (ii) using the result of the modified heuristic as the initial solution of metaheuristic algorithms lead to a better solution; the amount of improvement varied from algorithm to algorithm; (iii) among the five neighborhood solution generation operators, insertion operator was the best; (iv) among all algorithms tested, the hybrid differential evolution is the best, followed by tabu search in terms of average objective value.     

An MO‐GVNS algorithm for solving a multiobjective hybrid flow shop scheduling problem

This paper addresses the multiobjective hybrid flow shop (MOHFS) scheduling problem. In the MOHFS problem considered here, we have a set of jobs that must be performed in a set of stages. At each stage, we have a set of unrelated parallel machines. Some jobs may skip stages. The evaluation criteria are the minimizations of makespan, the weighted sum of the tardiness, and the weighted sum of the earliness. For solving it, an algorithm based on the multiobjective general variable neighborhood search (MO‐GVNS) metaheuristic, named adapted MO‐GVNS, is proposed. This work also presents and compares the results obtained by the adapted MO‐GVNS with those of four other algorithms: multiobjective reduced variable neighborhood search, nondominated sorting genetic algorithm II (NSGA‐II), and NSGA‐III, and another MO‐GVNS from the literature. The results were evaluated based on the Hypervolume, Epsilon, and Spacing metrics, and statistically validated by the Levene test and confidence interval charts. The results showed the efficiency of the proposed algorithm for solving the MOHFS problem.     

Discrete sizing/layout/topology optimization of truss structures with an advanced Jaya algorithm

Discrete optimization of truss structures is a hard computing problem with many local minima. Metaheuristic algorithms are naturally suited for discrete optimization problems as they do not require gradient information. A recently developed method called Jaya algorithm (JA) has proven itself very efficient in continuous engineering problems. Remarkably, JA has a very simple formulation and does not utilize algorithm-specific parameters. This study presents a novel JA formulation for discrete optimization of truss structures under stress and displacement constraints. The new algorithm, denoted as discrete advanced JA (DAJA), implements efficient search mechanisms for generating new trial designs including discrete sizing, layout and topology optimization variables. Besides the JA’s basic concept of moving towards the best design of the population and moving away from the worst design, DAJA tries to form a set of descent directions in the neighborhood of each candidate designs thus generating high quality trial designs that are very likely to improve current population. Results collected in seven benchmark problems clearly demonstrate the superiority of DAJA over other state-of-the-art metaheuristic algorithms and multi-stage continuous–discrete optimization formulations.     

Packing unit spheres into the smallest sphere using VNS and NLP

This paper addresses the NP hard optimization problem of packing identical spheres of unit radii into the smallest sphere (PSS). It models PSS as a non-linear program (NLP) and approximately solves it using a hybrid heuristic which couples a variable neighborhood search (VNS) with a local search (LS). VNS serves as the diversification mechanism whereas LS acts as the intensification one. VNS investigates the neighborhood of a feasible local minimum u in search for the global minimum, where neighboring solutions are obtained by shaking one or more spheres of u and the size of the neighborhood is varied by changing the number of shaken spheres, the distance and the direction each sphere is moved. LS intensifies the search around a solution u by subjecting its neighbors to a sequential quadratic algorithm with non-monotone line search (as the NLP solver). The computational investigation highlights the role of LS and VNS in identifying (near) global optima, studies their sensitivity to initial solutions, and shows that the proposed hybrid heuristic provides more precise results than existing approaches. Most importantly, it provides computational evidence that the multiple-start strategy of non-linear programming solvers is not sufficient to solve PSS. Finally, it gives new upper bounds for 29 out of 48 benchmark instances of PSS.     

Multi-neighborhood local search optimization for machine reassignment problem

As the topic of the Google ROADEF/EURO Challenge 2012, machine reassignment problem (denoted as MRP) is an important optimization problem in load balance of cloud computing. Given a set of machines and a set of processes running on machines, the MRP aims at finding a best process-machine reassignment to improve the usage of machines while satisfying various hard constraints. In this paper, we present a metaheuristic algorithm based on multi-neighborhood local search (denoted as MNLS) for solving the MRP. Our MNLS algorithm consists of three primary and one auxiliary neighborhood structures, an efficient neighborhood partition search mechanism with respect to the three primary neighborhoods and a dynamic perturbation operator. Computational results tested on 30 benchmark instances of the ROADEF/EURO Challenge 2012 and comparisons with the results in the challenge and the literature demonstrate the efficacy of the proposed MNLS algorithm in terms of both effectiveness and efficiency. Furthermore, several key components of our MNLS algorithm are analyzed to gain an insight into it.     

Particle swarm optimization with expanding neighborhood topology for the permutation flowshop scheduling problem

This paper introduces a new algorithmic nature-inspired approach that uses particle swarm optimization (PSO) with different neighborhood topologies, for successfully solving one of the most computationally complex problems, the permutation flowshop scheduling problem (PFSP). The PFSP belongs to the class of combinatorial optimization problems characterized as NP-hard and, thus, heuristic and metaheuristic techniques have been used in order to find high quality solutions in reasonable computational time. The proposed algorithm for the solution of the PFSP, the PSO with expanding neighborhood topology, combines a PSO algorithm, the variable neighborhood search strategy and a path relinking strategy. As, in general, the structure of the social network affects strongly a PSO algorithm, the proposed method using an expanding neighborhood topology manages to increase the performance of the algorithm. As the algorithm starts from a small size neighborhood and by increasing (expanding) in each iteration the size of the neighborhood, it ends to a neighborhood that includes all the swarm, and it manages to take advantage of the exploration abilities of a global neighborhood structure and of the exploitation abilities of a local neighborhood structure. In order to test the effectiveness and the efficiency of the proposed method, we use a set of benchmark instances of different sizes and compare the proposed method with a number of other PSO algorithms and other algorithms from the literature.     

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

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

Variable neighborhood search based approaches to a vehicle scheduling problem in agriculture

A vehicle scheduling problem (VSP) that arises from sugar beet transportation within minimum working time under the set of constraints reflecting a real‐life situation is considered. A mixed integer quadratically constrained programming (MIQCP) model of the considered VSP and reformulation to a mixed integer linear program (MILP) are proposed and used within the framework of Lingo 17 solver, producing optimal solutions only for small‐sized problem instances. Two variants of the variable neighborhood search (VNS) metaheuristic—basic VNS (BVNS) and skewed VNS (SVNS) are designed to efficiently deal with large‐sized problem instances. The proposed VNS approaches are evaluated and compared against Lingo 17 and each other on the set of real‐life and generated problem instances. Computational results show that both BVNS and SVNS reach all known optimal solutions on small‐sized instances and are comparable on medium‐ and large‐sized instances. In general, SVNS significantly outperforms BVNS in terms of running times.     

Generic Pareto local search metaheuristic for optimization of targeted offers in a bi-objective direct marketing campaign

Cross-selling campaigns seek to offer the right products to the set of customers with the goal of maximizing expected profit, while, at the same time, respecting the purchasing constraints set by investors. In this context, a bi-objective version of this NP-Hard problem is approached in this paper, aiming at maximizing both the promotion campaign total profit and the risk-adjusted return, which is estimated with the reward-to-variability ratio known as Sharpe ratio. Given the combinatorial nature of the problem and the large volume of data, heuristic methods are the most common used techniques. A Greedy Randomized Neighborhood Structure is also designed, including the characteristics of a neighborhood exploration strategy together with a Greedy Randomized Constructive technique, which is embedded in a multi-objective local search metaheuristic. The latter combines the power of neighborhood exploration by using a Pareto Local Search with Variable Neighborhood Search. Sets of non-dominated solutions obtained by the proposed method are described and analyzed for a number of problem instances.