Routing relatively few customers per route

This paper presents a modification of the well-known Solomon (1987) sequential insertion heuristic I1 for the Vehicle Routing Problem with Time Windows (VRPTW). VRPTW involves servicing customers within a pre-specified service time window by homogeneously capacitated vehicles from a single depot. By using two new measures for the additional time needed to insert a customer in the route, significantly better solutions are obtained for relatively short routes compared to the original Solomon (1987) sequential insertion heuristic I1. Because high-quality initial heuristics often allow local searches and metaheuristics to achieve better solutions more quickly, the new approach is likely to help generating better solutions to practical routing problems.     

Parametric enhancements of the Esau–Williams heuristic for the capacitated minimum spanning tree problem

The Capacitated Minimum Spanning Tree Problem is NP-hard and several heuristic solution methods have been proposed. They can be classified as classical ones and metaheuristics. Recent developments have shown that metaheuristics outperform classical heuristics. However, they require long computation times and there are difficulties in their parameter calibration and coding phases. This explains the popularity of the Esau–Williams (EW) heuristic in practice, and its use in many successful metaheuristics and second-order greedy methods. In this work, we are concerned with the EW heuristic and we propose simple new enhancements. Based on our computational experiments, we can say that they considerably improve its accuracy with minor increase in computation time, and without harming its simplicity.     

Scatter search for the vehicle routing problem with time windows

In this paper we use a scatter search framework to solve the vehicle routing problem with time windows (VRPTW). Our objective is to achieve effective solutions and to investigate the effects of reference set design parameters pertaining to size, quality and diversity. Both a common arc method and an optimization-based set covering model are used to combine vehicle routing solutions. A reactive tabu search metaheuristic and a tabu search with an advanced recovery feature, together with a set covering procedure are used for solution improvement. Our approach led to a robust solution method, generating solution quality that is competitive with the current best metaheuristics.     

A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time Windows

Vehicle routing problem with time windows (VRPTW) involves the routing of a set of vehicles with limited capacity from a central depot to a set of geographically dispersed customers with known demands and predefined time windows. The problem is solved by optimizing routes for the vehicles so as to meet all given constraints as well as to minimize the objectives of traveling distance and number of vehicles. This paper proposes a hybrid multiobjective evolutionary algorithm (HMOEA) that incorporates various heuristics for local exploitation in the evolutionary search and the concept of Pareto's optimality for solving multiobjective optimization in VRPTW. The proposed HMOEA is featured with specialized genetic operators and variable-length chromosome representation to accommodate the sequence-oriented optimization in VRPTW. Unlike existing VRPTW approaches that often aggregate multiple criteria and constraints into a compromise function, the proposed HMOEA optimizes all routing constraints and objectives simultaneously, which improves the routing solutions in many aspects, such as lower routing cost, wider scattering area and better convergence trace. The HMOEA is applied to solve the benchmark Solomon's 56 VRPTW 100-customer instances, which yields 20 routing solutions better than or competitive as compared to the best solutions published in literature.     

Hyper-heuristic approaches for the response time variability problem

We propose two classes for the implementation of hyper-heuristic algorithms. The first is based on constructive heuristics, whereas the second uses improvement methods. Within the latter class, a general framework is designed for the use of local search procedures and metaheuristics as low-level heuristics. A dynamic scheme to guide the use of these approaches is also devised. These ideas are tested on an NP-hard scheduling problem known as the response time variability problem (RTVP). An intensive computational experiment shows, especially in the second class where the new best results are found, the effectiveness of the proposed hyper-heuristics.     

Binary Accelerated Particle Swarm Algorithm (BAPSA) for discrete optimization problems

The majority of Combinatorial Optimization Problems (COPs) are defined in the discrete space. Hence, proposing an efficient algorithm to solve the problems has become an attractive subject in recent years. In this paper, a meta-heuristic algorithm based on Binary Particle Swarm Algorithm (BPSO) and the governing Newtonian motion laws, so-called Binary Accelerated Particle Swarm Algorithm (BAPSA) is offered for discrete search spaces. The method is presented in two global and local topologies and evaluated on the 0–1 Multidimensional Knapsack Problem (MKP) as a famous problem in the class of COPs and NP-hard problems. Besides, the results are compared with BPSO for both global and local topologies as well as Genetic Algorithm (GA). We applied three methods of Penalty Function (PF) technique, Check-and-Drop (CD) and Improved Check-and-Repair Operator (ICRO) algorithms to solve the problem of infeasible solutions in the 0–1 MKP. Experimental results show that the proposed methods have better performance than BPSO and GA especially when ICRO algorithm is applied to convert infeasible solutions to feasible ones.     

A comprehensive review and evaluation of permutation flowshop heuristics

In this work we present a review and comparative evaluation of heuristics and metaheuristics for the well-known permutation flowshop problem with the makespan criterion. A number of reviews and evaluations have already been proposed. However, the evaluations do not include the latest heuristics available and there is still no comparison of metaheuristics. Furthermore, since no common benchmarks and computing platforms are used, the results cannot be generalised. We propose a comparison of 25 methods, ranging from the classical Johnson's algorithm or dispatching rules to the most recent metaheuristics, including tabu search, simulated annealing, genetic algorithms, iterated local search and hybrid techniques. For the evaluation we use the standard test of Taillard [Eur. J. Operation. Res. 64 (1993) 278] composed of 120 instances of different sizes. In the evaluations we use the experimental design approach to obtain valid conclusions on the effectiveness and efficiency of the different methods tested.     

A Robust Genetic Algorithm for Resource Allocation in Project Scheduling

Genetic algorithms have been applied to many different optimization problems and they are one of the most promising metaheuristics. However, there are few published studies concerning the design of efficient genetic algorithms for resource allocation in project scheduling. In this work we present a robust genetic algorithm for the single-mode resource constrained project scheduling problem. We propose a new representation for the solutions, based on the standard activity list representation and develop new crossover techniques with good performance in a wide sample of projects. Through an extensive computational experiment, using standard sets of project instances, we evaluate our genetic algorithm and demonstrate that our approach outperforms the best algorithms appearing in the literature.     

时间窗约束下的车辆路径问题多目标优化算法

讨论了带时间窗约束的车辆路径问题(VRPTW)其数学模型,分析了以遗传算法求解该类问题时的染色体表示和有关遗传操作,将VRPTw视为一个多目标优化问题,用Pareto评等技术来求解最优解,并以Solomen基准问题为例验证了该方法的有效性.结果表明:该方法与以往文献中的最好结果具有竞争性.     

DVRP: a hard dynamic combinatorial optimisation problem tackled by an evolutionary hyper-heuristic

In this paper we propose and evaluate an evolutionary-based hyper-heuristic approach, called EH-DVRP, for solving hard instances of the dynamic vehicle routing problem. A hyper-heuristic is a high-level algorithm, which generates or chooses a set of low-level heuristics in a common framework, to solve the problem at hand. In our collaborative framework, we have included three different types of low-level heuristics: constructive, perturbative, and noise heuristics. Basically, the hyper-heuristic manages and evolves a sophisticated sequence of combinations of these low-level heuristics, which are sequentially applied in order to construct and improve partial solutions, i.e., partial routes. In presenting some design considerations, we have taken into account the allowance of a proper cooperation and communication among low-level heuristics, and as a result, find the most promising sequence to tackle partial states of the (dynamic) problem. Our approach has been evaluated using the Kilby’s benchmarks, which comprise a large number of instances with different topologies and degrees of dynamism, and we have compared it with some well-known methods proposed in the literature. The experimental results have shown that, due to the dynamic nature of the hyper-heuristic, our proposed approach is able to adapt to dynamic scenarios more naturally than low-level heuristics. Furthermore, the hyper-heuristic can obtain high-quality solutions when compared with other (meta) heuristic-based methods. Therefore, the findings of this contribution justify the employment of hyper-heuristic techniques in such changing environments, and we believe that further contributions could be successfully proposed in related dynamic problems.     

Using Genetic Algorithms and Heuristics for Job Shop Scheduling with Sequence-Dependent Setup Times

In this work a new heuristic solution technique for the Resource-Constrained Project Scheduling Problem (RCPSP) is proposed. This technique is a hybrid multi-pass method that combines random sampling procedures with a backward–forward method. The impact of each component of the algorithm is evaluated through a step-wise computational analysis which in addition permits the value of their parameters to be specified. Furthermore, the performance of the new technique is evaluated against the best currently available heuristics using a well known set of instances. The results obtained point out that the new technique greatly outperforms both the heuristics and metaheuristics currently available for the RCPSP being thus competitive with the best heuristic solution techniques for this problem.     

A Tabu-Search Hyperheuristic for Timetabling and Rostering

Hyperheuristics can be defined to be heuristics which choose between heuristics in order to solve a given optimisation problem. The main motivation behind the development of such approaches is the goal of developing automated scheduling methods which are not restricted to one problem. In this paper we report the investigation of a hyperheuristic approach and evaluate it on various instances of two distinct timetabling and rostering problems. In the framework of our hyperheuristic approach, heuristics compete using rules based on the principles of reinforcement learning. A tabu list of heuristics is also maintained which prevents certain heuristics from being chosen at certain times during the search. We demonstrate that this tabu-search hyperheuristic is an easily re-usable method which can produce solutions of at least acceptable quality across a variety of problems and instances. In effect the proposed method is capable of producing solutions that are competitive with those obtained using state-of-the-art problem-specific techniques for the problems studied here, but is fundamentally more general than those techniques.     

Tabu Search heuristics for the Vehicle Routing Problem with Time Windows

This paper surveys the research on the Tabu Search heuristics for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes for a fleet of vehicles from one depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval; all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. In addition to describing basic features of each method, experimental results for Solomon’s benchmark test problems are presented and analyzed. This work was partially supported by the Emil Aaltonen Foundation, Liikesivistysrahasto Foundation, the Canadian Natural Science and Engineering Research Council and the TOP program funded by the Research Council of Norway. This support is gratefully acknowledged.     

Local search intensified: Very large-scale variable neighborhood search for the multi-resource generalized assignment problem

We introduce a heuristic for the Multi-Resource Generalized Assignment Problem (MRGAP) based on the concepts of Very Large-Scale Neighborhood Search and Variable Neighborhood Search. The heuristic is a simplified version of the Very Large-Scale Variable Neighborhood Search for the Generalized Assignment Problem. Our algorithm can be viewed as a k-exchange heuristic; but unlike traditional k-exchange algorithms, we choose larger values of k resulting in neighborhoods of very large size with high probability. Searching this large neighborhood (approximately) amounts to solving a sequence of smaller MRGAPs either by exact algorithms or by heuristics. Computational results on benchmark test problems are presented. We obtained improved solutions for many instances compared to some of the best known heuristics for the MRGAP within reasonable running time. The central idea of our heuristic can be used to develop efficient heuristics for other hard combinatorial optimization problems as well.     

A comparison of three metaheuristics for the workover rig routing problem

The workover rig routing problem (WRRP) is a variant of the Vehicle Routing Problem with Time Windows (VRPTW) and arises in the operations of onshore oil fields. In this problem, a set of workover rigs located at different positions must service oil wells requesting maintenance as soon as possible. When a well requires maintenance, its production is reduced or stopped for safety reasons and some workover rig must service it within a given deadline. It is therefore important to service the wells in a timely fashion in order to minimize the production loss. Whereas for classical VRPTWs the objective is to minimize route length, in the WRRP the objective is to minimize the total lost production, equal to the sum of arrival times at the wells, multiplied by production loss rates. The WRRP generalizes the Delivery Man Problem with Time Windows by considering multiple open vehicle routes and multiple depots. This paper compares three metaheuristics for the WRRP: an iterated local search, a clustering search, and an Adaptive Large Neighborhood Search (ALNS). All approaches, in particular ALNS, have yielded good solutions for instances derived from a real-life setting.     

Evolutionary Algorithms for the Vehicle Routing Problem with Time Windows

This paper surveys the research on evolutionary algorithms for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes from a single depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval. All routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. The main types of evolutionary algorithms for the VRPTW are genetic algorithms and evolution strategies. In addition to describing the basic features of each method, experimental results for the benchmark test problems of Solomon (1987) and Gehring and Homberger (1999) are presented and analyzed.     

On solving the forward kinematics of 3RPR planar parallel manipulator using hybrid metaheuristics

Hybrid metaheuristics have been applied with success in solving many real-world problems. This work introduces hybrid metaheuristics to the field of kinematics problem, in particular, for solving the forward kinematics of the 3RPR parallel manipulator. It implements a combination of genetic algorithms and simulated annealing into two popular hybrid metaheuristic techniques. They are combined as teamwork and relay collaborative hybrid metaheuristics and compared to the performance of genetic algorithms and simulated annealing alone. The results show that the meta-heuristic approaches give robust and high quality solutions. Genetic algorithms and teamwork collaborative metaheuristics showed better performance than simulated annealing and relay collaborative metaheuristics. The given metaheuristic methods obtain all the unique solutions and comparisons with algebraic methods show promising results.     

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.     

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.