A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem

The heterogeneous fleet vehicle routing problem is investigated using some adaptations of the variable neighborhood search (VNS). The initial solution is obtained by Dijkstra’s algorithm based on a cost network constructed by the sweep algorithm and the 2-opt. Our VNS algorithm uses several neighborhoods which are adapted for this problem. In addition, a number of local search methods together with a diversification procedure are used. Two VNS variants, which differ in the order the diversification and Dijkstra’s algorithm are used, are implemented. Both variants appear to be competitive and produce new best results when tested on the data sets from the literature. We also constructed larger data sets for which benchmarking results are provided for future comparison.     

Serial-batching group scheduling with release times and the combined effects of deterioration and truncated job-dependent learning

This paper investigates a single machine serial-batching scheduling problem considering release times, setup time, and group scheduling, with the combined effects of deterioration and truncated job-dependent learning. The objective of the studied problem is to minimize the makespan. Firstly, we analyze the special case where all groups have the same arrival time, and propose the optimal structural properties on jobs sequencing, jobs batching, batches sequencing, and groups sequencing. Next, the corresponding batching rule and algorithm are developed. Based on these properties and the scheduling algorithm, we develop a hybrid VNS–ASHLO algorithm incorporating variable neighborhood search (VNS) and adaptive simplified human learning optimization (ASHLO) algorithms to solve the general case of the studied problem. Computational experiments on randomly generated instances are conducted to compare the proposed VNS–ASHLO with the algorithms of VNS, ASHLO, Simulated Annealing (SA), and Particle Swarm Optimization (PSO). The results based on instances of different scales show the effectiveness and efficiency of the proposed algorithm.     

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

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

Metaheuristics for scheduling jobs with incompatible families on parallel batching machines

In this paper, we discuss the scheduling of jobs with incompatible families on parallel batching machines. The performance measure is total weighted tardiness. This research is motivated by a scheduling problem found in the diffusion and oxidation areas of semiconductor wafer fabrication where the machines can be modelled as parallel batch processors. Given that this scheduling problem is NP-hard, we suggest an ant colony optimization (ACO) and a variable neighbourhood search (VNS) approach. Both metaheuristics are hybridized with a decomposition heuristic and a local search scheme. We compare the performance of the two algorithms with that of a genetic algorithm (GA) based on extensive computational experiments. The VNS approach outperforms the ACO and GA approach with respect to time and solution quality.     

Nonsmooth optimization through Mesh Adaptive Direct Search and Variable Neighborhood Search

This paper proposes a way to combine the Mesh Adaptive Direct Search (MADS) algorithm, which extends the Generalized Pattern Search (GPS) algorithm, with the Variable Neighborhood Search (VNS) metaheuristic, for nonsmooth constrained optimization. The resulting algorithm retains the convergence properties of MADS, and allows the far reaching exploration features of VNS to move away from local solutions. The paper also proposes a generic way to use surrogate functions in the VNS search. Numerical results illustrate advantages and limitations of this method.     

A variable neighbourhood search for hybrid flow-shop scheduling problem with rework and set-up times

This paper deals with hybrid flow-shop scheduling problem with rework. In this problem, jobs are inspected at the last stage, and poorly processed jobs were returned and processed again. Thus, a job may visit a stage more than once, and we have a hybrid flow-shop with re-entrant flow. This kind of a shop may occur in many industries, such as final inspection system in automotive manufacturing. The criterion is to minimize the makespan of the system. We developed a 0–1 mixed-integer program of the problem. Since the hybrid flow-shop scheduling problem is NP-hard, an algorithm for finding an optimal solution in polynomial time does not exist. So we generalized some heuristic methods based on several basic dispatching rules and proposed a variable neighbourhood search (VNS) for the problem with sequence-dependent set-up times and unrelated parallel machines. The computational experiments show that VNS provides better solutions than heuristic methods.     

Combining variable neighborhood search and estimation of distribution algorithms in the protein side chain placement problem

The aim of this work is to introduce several proposals for combining two metaheuristics: variable neighborhood search (VNS) and estimation of distribution algorithms (EDAs). Although each of these metaheuristics has been previously hybridized in several ways, this paper constitutes the first attempt to combine both optimization methods. The different ways of combining VNS and EDAs will be classified into three groups. In the first group, we will consider combinations where the philosophy underlying VNS is embedded in EDAs. Considering different neighborhood spaces (points, populations or probability distributions), we will obtain instantiations for the approaches in this group. The second group of algorithms is obtained when probabilistic models (or any other machine learning paradigm) are used in order to exploit the good and bad shakes of the randomly generated solutions in a reduced variable neighborhood search. The last group of algorithms contains the results of alternating VNS and EDAs. An application of the first approach is presented in the protein side chain placement problem. The results obtained show the superiority of the hybrid algorithm in comparison with EDAs and VNS.     

A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal

The scheduling problem in a container terminal is characterized by the coordination of different types of equipment. In this paper, we present an integrated model to schedule the equipment. The objective is to minimize the makespan, or the time it takes to serve a given set of ships. The problem is formulated as a Hybrid Flow Shop Scheduling problem with precedence and Blocking constraints (HFSS-B). A tabu search algorithm is proposed to solve this problem. Certain mechanisms are developed and introduced into the algorithm to assure its quality and efficiency. The performance of the tabu search algorithm is analyzed from the computational point of view.     

Pareto-optimal solutions for a wastewater treatment problem

In this paper we present an application of optimal control theory of partial differential equations combined with multi-objective optimization techniques to formulate and solve an economical-ecological problem related to the management of a wastewater treatment system. The problem is formulated as a parabolic multi-objective optimal control problem, and it is studied from a non-cooperative point of view (looking for a Nash equilibrium), and also from a cooperative point of view (looking for Pareto-optimal solutions “better” than the Nash equilibrium). In both cases we state the existence of solutions, give a useful characterization of them, and propose a numerical algorithm to solve the problem. Finally, a numerical experience for a real world situation in the estuary of Vigo (NW Spain) is presented.     

A max-conflicts based heuristic search for the stable marriage problem with ties and incomplete lists

In this paper, we propose a heuristic search algorithm based on maximum conflicts to find a weakly stable matching of maximum size for the stable marriage problem with ties and incomplete lists. The key idea of our approach is to define a heuristic function based on the information extracted from undominated blocking pairs from the men’s point of view. By choosing a man corresponding to the maximum value of the heuristic function, we aim to not only remove all the blocking pairs formed by the man but also reject as many blocking pairs as possible for an unstable matching from the women’s point of view to obtain a solution of the problem as quickly as possible. Experiments show that our algorithm is efficient in terms of both execution time and solution quality for solving the problem.

     

A Metaheuristic to Solve a Location-Routing Problem with Non-Linear Costs

The paper deals with a location-routing problem with non-linear cost functions. To the best of our knowledge, a mixed integer linear programming formulation for the addressed problem is proposed here for the first time. Since the problem is NP-hard exact algorithms are able to solve only particular cases, thus to solve more general versions heuristics are needed. The algorithm proposed in this paper is a combination of a p-median approach to find an initial feasible solution and a metaheuristic to improve the solution. It is a hybrid metaheuristic merging Variable Neighborhood Search (VNS) and Tabu Search (TS) principles and exploiting the synergies between the two. Computational results and conclusions close the paper.     

The Parallel Variable Neighborhood Search for the p-Median Problem

The Variable Neighborhood Search (VNS) is a recent metaheuristic that combines series of random and improving local searches based on systematically changed neighborhoods. When a local minimum is reached, a shake procedure performs a random search. This determines a new starting point for running an improving search. The use of interchange moves provides a simple implementation of the VNS algorithm for the p-Median Problem. Several strategies for the parallelization of the VNS are considered and coded in C using OpenMP. They are compared in a shared memory machine with large instances.     

Neighborhood structures for the container loading problem: a VNS implementation

This paper presents a Variable Neighborhood Search (VNS) algorithm for the container loading problem. The algorithm combines a constructive procedure based on the concept of maximal-space, with five new movements defined directly on the physical layout of the packed boxes, which involve insertion and deletion strategies. The new algorithm is tested on the complete set of Bischoff and Ratcliff problems, ranging from weakly to strongly heterogeneous instances, and outperforms all the reported algorithms which have used those test instances.     

Integer programming formulations for the minimum weighted maximal matching problem

Given an undirected graph, the problem of finding a maximal matching that has minimum total weight is NP-hard. This problem has been studied extensively from a graph theoretical point of view. Most of the existing literature considers the problem in some restricted classes of graphs and give polynomial time exact or approximation algorithms. On the contrary, we consider the problem on general graphs and approach it from an optimization point of view. In this paper, we develop integer programming formulations for the minimum weighted maximal matching problem and analyze their efficacy on randomly generated graphs. We also compare solutions found by a greedy approximation algorithm, which is based on the literature, against optimal solutions. Our results show that our integer programming formulations are able to solve medium size instances to optimality and suggest further research for improvement.     

Variable neighborhood search: Principles and applications

Systematic change of neighborhood within a possibly randomized local search algorithm yields a simple and effective metaheuristic for combinatorial and global optimization, called variable neighborhood search (VNS). We present a basic scheme for this purpose, which can easily be implemented using any local search algorithm as a subroutine. Its effectiveness is illustrated by solving several classical combinatorial or global optimization problems. Moreover, several extensions are proposed for solving large problem instances: using VNS within the successive approximation method yields a two-level VNS, called variable neighborhood decomposition search (VNDS); modifying the basic scheme to explore easily valleys far from the incumbent solution yields an efficient skewed VNS (SVNS) heuristic. Finally, we show how to stabilize column generation algorithms with help of VNS and discuss various ways to use VNS in graph theory, i.e., to suggest, disprove or give hints on how to prove conjectures, an area where metaheuristics do not appear to have been applied before.     

一种新的求解拟单调变分不等式的压缩投影算法

2020年Liu和Yang提出了求解Hilbert空间中拟单调且Lipschitz连续的变分不等式问题的投影算法,简称LYA。本文在欧氏空间中提出了一种新的求解拟单调变分不等式的压缩投影算法,简称NPCA。新算法削弱了LYA中映射的Lipschitz连续性。在映射连续、拟单调且对偶变分不等式解集非空的条件下得到了NPCA所生成点列的聚点是解的结论。当变分不等式的解集还满足一定条件时,得到了NPCA的全局收敛性。数值实验结果表明NPCA所需的迭代步数少于LYA的迭代步数,NPCA在高维拟单调例子中所需的计算机耗时也更少。     

Concave cost minimization on networks

The paper deals with the problem of finding a minimum cost multicommodity flow on an uncapacitated network with concave link costs. Problems of this type are the optimal design of a network in the presence of scale economies and the telpack problem.Two different definitions of local optimality are given and compared both from the point of view of the computational complexity and from the point of view of the goodness of the solution they may provide.A vertex following algorithm to find a local optimum is proposed. The computational complexity of each iteration of the algorithm is O(n³), where n is the number of nodes of the network, and is independent of the differentiability of the objective function.Experimental results obtained from a set of test problems of size ranging from 11 nodes and 23 arcs to 48 nodes and 174 arcs, with number of commodities up to 5, are given.     

A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems

This paper presents a hybrid multi-objective model that combines integer programming (IP) and variable neighbourhood search (VNS) to deal with highly-constrained nurse rostering problems in modern hospital environments. An IP is first used to solve the subproblem which includes the full set of hard constraints and a subset of soft constrains. A basic VNS then follows as a postprocessing procedure to further improve the IP’s resulting solutions. The satisfaction of the excluded constraints from the preceding IP model is the major focus of the VNS. Very promising results are reported compared with a commercial genetic algorithm and a hybrid VNS approach on real instances arising in a Dutch hospital. The comparison results demonstrate that our hybrid approach combines the advantages of both the IP and the VNS to beat other approaches in solving this type of problems. We also believe that the proposed methodology can be applied to other resource allocation problems with a large number of constraints.     

A TRANSFORMATION PATH ALGORITHM FOR UNCONSTRAINED SIGNOMIAL GEOMETRIC PROGRAMMING

In this paper we present a transformation path algorithm for UnconstrainedSignomial Geometric Programming (USGP). The algorithm is proposed from a newpoint of view based on exploring the characteristics of USGP problem. Firstly by somestable transformations, a particular subproblem is derived which is very easy to solve.Secondly, a special path is formed conveniently. And then the step of the algorithmconsists in finding a “good” point to the current iterate by choosing it along the specialpath and within a trust region. It is proved that the algorithm is globally convergent.     

Exact and heuristic solutions of the global supply chain problem with transfer pricing

We examine the example of a multinational corporation that attempts to maximize its global after tax profits by determining the flow of goods, the transfer prices, and the transportation cost allocation between each of its subsidiaries. Vidal and Goetschalckx [Vidal, C.J., Goetschalckx, M., 2001. A global supply chain model with transfer pricing and transportation cost allocation. European Journal of Operational Research 129 (1), 134–158] proposed a bilinear model of this problem and solved it by an Alternate heuristic. We propose a reformulation of this model reducing the number of bilinear terms and accelerating considerably the exact solution. We also present three other solution methods: an implementation of Variable Neighborhood Search (VNS) designed for any bilinear model, an implementation of VNS specifically designed for the problem considered here and an exact method based on a branch and cut algorithm. The solution methods are tested on artificial instances. These results show that our implementation of VNS outperforms the two other heuristics. The exact method found the optimal solution of all small instances and of 26% of medium instances.