A bi-objective vehicle routing problem with time windows: A real case in Tenerife

This work is motivated by a real problem posed to the authors by a company in Tenerife, Spain. Given a fleet of vehicles, daily routes have to be designed in order to minimize the total traveled distance while balancing the workload of drivers. This balance has been defined in relation to the length of the routes, regarding to the required time. A bi-objective mixed-integer linear model for the problem is proposed and a solution approach, based on the scatter search metaheuristic, is developed. An extensive computational experience is carried out, using benchmark instances with 25, 50 and 100 customers, to test several components of the proposed method. Comparisons with the exact Pareto fronts for instances up to 25 customers show that the proposed methods obtain good approximations. For comparison purposes, an NSGA-II algorithm has also been implemented. Results obtained on a real case instance are also discussed. In this case, the solution provided by the method proposed in this paper improves the solution implemented by the company.     

New heuristic algorithms for the windy rural postman problem

In this paper we deal with the windy rural postman problem. This problem generalizes several important arc routing problems and has interesting real-life applications. Here, we present several heuristics whose study has lead to the design of a scatter search algorithm for the windy rural postman problem. Extensive computational experiments over different sets of instances, with sizes up to 988 nodes and 3952 edges, are also presented.     

Flowshop-scheduling problems with makespan criterion: a review

This paper is a complete survey of flowshop-scheduling problems and contributions from early works of Johnson of 1954 Johnson, SM. 1954. Optimal two- and three-stage production schedules with set-up times included. Naval Res. Logist. Quart., 1: 61–68.   to recent approaches of metaheuristics of 2004. It mainly considers a flowshop problem with a makespan criterion and it surveys some exact methods (for small size problems), constructive heuristics and developed improving metaheuristic and evolutionary approaches as well as some well-known properties and rules for this problem. Each part has a brief literature review of the contributions and a glimpse of that approach before discussing the implementation for a flowshop problem. Moreover, in the first section, a complete literature review of flowshop-related scheduling problems with different assumptions as well as contributions in solving these other aspects is considered. This paper can be seen as a reference to past contributions (particularly in n/m/p/c _max or equivalently F/prmu/c _max) for future research needs of improving and developing better approaches to flowshop-related scheduling problems.     

A simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles

In this paper we address the problem of simultaneous scheduling of machines and vehicles in flexible manufacturing systems. The studied problem is a job shop where the jobs have to be transported between the machines by automatic guided vehicles. In addition to the processing of jobs, we consider the transportation aspect as an integral part of the optimization process. To deal with this problem, we propose a new solution representation based on vehicles rather than machines. Each solution can thus be evaluated using a discrete event approach. An efficient neighbouring system is then described and implemented into three different metaheuristics: iterated local search, simulated annealing and their hybridisation. Computational results are presented for a benchmark of 40 literature instances. New upper bounds are found for 11 of them, showing the effectiveness of the presented approach.     

Solving generalized Nash equilibrium problems through stochastic global optimization

Generalized Nash equilibrium problems address extensions of the well-known standard Nash equilibrium concept, making it possible to model and study more general settings. The main difference lies in that they allow both objective functions and constraints of each player to depend on the strategies of other players. The study of such problems has numerous applications in many fields, including engineering, economics, or management science, for instance. In this work we introduce a solution algorithm based on the Fuzzy Adaptive Simulated Annealing global optimization method (Fuzzy ASA, for short), demonstrating that it is possible to transform the original task into a constrained global optimization problem, which can be solved, in principle, by any effective global optimization algorithm, but in this paper our main tool will be the cited paradigm (Fuzzy ASA). We believe that the main merit of the proposed approach is to offer a simpler alternative for solving this important class of problems, in a less restrictive way in the sense of not demanding very strong conditions on the defining functions. Several case studies are presented for the sake of exemplifying the proposal's efficacy.     

A local search based approach for solving the Travelling Thief Problem: The pros and cons

The Travelling Thief Problem (TTP) is a novel problem that aims to provide a benchmark model of combinatorial optimization problems with multiple interdependent components. The TTP combines two other well known benchmark problems: the Travelling Salesman Problem (TSP) and the Knapsack Problem (KP). The aim of this paper is to study the interdependence between the TTP's components, and how it makes solving each sub-problem independently from the other useless for solving the overall problem. A local search approach is proposed to solve the TTP. Two simple iterative neighborhood algorithms based on our approach are presented, analyzed, and compared to other algorithms. Initialization strategies are empirically investigated. The experimental results confirm that our approach was able to find new better solutions for many TTP instances.     

A great deluge and tabu search hybrid with two-stage memory support for quadratic assignment problem

A two-stage memory architecture is maintained within the framework of great deluge algorithm for the solution of single-objective quadratic assignment problem. Search operators exploiting the accumulated experience in memory are also implemented to direct the search towards more promising regions of the solution space. The level-based acceptance criterion of the great deluge algorithm is applied for each best solution extracted in a particular iteration. The use of short- and long-term memory-based search supported by effective move operators resulted in a powerful combinatorial optimization algorithm. A successful variant of tabu search is employed as the local search method that is only applied over a few randomly selected memory elements when the second stage memory is updated. The success of the presented approach is illustrated using sets of well-known benchmark problems and evaluated in comparison to well-known combinatorial optimization algorithms. Experimental evaluations clearly demonstrate that the presented approach is a competitive and powerful alternative for solving quadratic assignment problems.     

Water cycle algorithm with evaporation rate for solving constrained and unconstrained optimization problems

This paper presents a modified version of the water cycle algorithm (WCA). The fundamental concepts and ideas which underlie the WCA are inspired based on the observation of water cycle process and how rivers and streams flow to the sea. New concept of evaporation rate for different rivers and streams is defined so called evaporation rate based WCA (ER-WCA), which offers improvement in search. Furthermore, the evaporation condition is also applied for streams that directly flow to sea based on the new approach. The ER-WCA shows a better balance between exploration and exploitation phases compared to the standard WCA. It is shown that the ER-WCA offers high potential in finding all global optima of multimodal and benchmark functions. The WCA and ER-WCA are tested using several multimodal benchmark functions and the obtained optimization results show that in most cases the ER-WCA converges to the global solution faster and offers more accurate results than the WCA and other considered optimizers. Based on the performance of ER-WCA on a number of well-known benchmark functions, the efficiency of the proposed method with respect to the number of function evaluations (computational effort) and accuracy of function value are represented.     

Multistart Simulated Annealing applied to a Reduced Scale Thermo-Hydraulic Loop of a Pressurized Water Reactor core

In this paper we investigate the reduced scale design of a third generation Pressurized Water Reactor core, with single phase flow under natural circulation, based on the Loss-of-Fluid Test facility. Recent works approach this issue applying metaheuristics such as Genetic Algorithms and Particle Swarm Optimization. Both approaches have, as a drawback, the high computational time to obtain an acceptable solution. Here, we propose an alternative method when computational time is critical. We approach the problem applying a Multistart Simulated Annealing method in order to obtain an acceptable solution in a lower computational time. Our results indicate a 98.7% computational time improvement over the state-of-the-art Particle Swarm Optimization method. Moreover, the Multistart Simulated Annealing results are 1.36% better than state-of-the-art Particle Swarm Optimization method. Thus, Multistart SA shows promising results and is a suitable method when time is critical.     

Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery

The location routing problem with simultaneous pickup and delivery (LRPSPD) is a new variant of the location routing problem (LRP). The objective of LRPSPD is to minimize the total cost of a distribution system including vehicle traveling cost, depot opening cost, and vehicle fixed cost by locating the depots and determining the vehicle routes to simultaneously satisfy the pickup and the delivery demands of each customer. LRPSPD is NP-hard since its special case, LRP, is NP-hard. Thus, this study proposes a multi-start simulated annealing (MSA) algorithm for solving LRPSPD which incorporates multi-start hill climbing strategy into simulated annealing framework. The MSA algorithm is tested on 360 benchmark instances to verify its performance. Results indicate that the multi-start strategy can significantly enhance the performance of traditional single-start simulated annealing algorithm. Our MSA algorithm is very effective in solving LRPSPD compared to existing solution approaches. It obtained 206 best solutions out of the 360 benchmark instances, including 126 new best solutions.