A lower bound for the Node,Edge, and Arc Routing Problem

The Node, Edge, and Arc Routing Problem (NEARP) was defined by Prins and Bouchenoua in 2004, although similar problems have been studied before. This problem, also called the Mixed Capacitated General Routing Problem (MCGRP), generalizes the classical Capacitated Vehicle Routing Problem (CVRP), the Capacitated Arc Routing Problem (CARP), and the General Routing Problem. It captures important aspects of real-life routing problems that were not adequately modeled in previous Vehicle Routing Problem (VRP) variants. The authors also proposed a memetic algorithm procedure and defined a set of test instances called the CBMix benchmark. The NEARP definition and investigation contribute to the development of rich VRPs. In this paper we present the first lower bound procedure for the NEARP. It is a further development of lower bounds for the CARP. We also define two novel sets of test instances to complement the CBMix benchmark. The first is based on well-known CARP instances; the second consists of real life cases of newspaper delivery routing. We provide numerical results in the form of lower and best known upper bounds for all instances of all three benchmarks. For three of the instances, the gap between the upper and lower bound is closed. The average gap is 25.1%. As the lower bound procedure is based on a high quality lower bound procedure for the CARP, and there has been limited work on approximate solution methods for the NEARP, we suspect that a main reason for the rather large gaps is the quality of the upper bound. This fact, and the high industrial relevance of the NEARP, should motivate more research on approximate and exact methods for this important problem.     

An extended Akers graphical method with a biased random‐key genetic algorithm for job‐shop scheduling

This paper presents a local search, based on a new neighborhood for the job‐shop scheduling problem, and its application within a biased random‐key genetic algorithm. Schedules are constructed by decoding the chromosome supplied by the genetic algorithm with a procedure that generates active schedules. After an initial schedule is obtained, a local search heuristic, based on an extension of the 1956 graphical method of Akers, is applied to improve the solution. The new heuristic is tested on a set of 205 standard instances taken from the job‐shop scheduling literature and compared with results obtained by other approaches. The new algorithm improved the best‐known solution values for 57 instances.     

A GRASP/VND heuristic for the phylogeny problem using a new neighborhood structure

A phylogeny is a tree that relates taxonomic units, based on their similarity over a set of characters. The phylogeny problem consists in finding a phylogeny with the minimum number of evolutionary steps. We propose a new neighborhood structure for the phylogeny problem. A greedy randomized adaptive search procedure heuristic based on this neighborhood structure and using variable neighborhood descent for local search is described. Computational results on randomly generated and benchmark instances are reported, showing that the new heuristic is quite robust and outperforms the other algorithms in the literature in terms of solution quality and time‐to‐target value.     

Variable neighborhood search algorithms for the vehicle routing problem with two‐dimensional loading constraints and mixed linehauls and backhauls

In this paper, we explore a vehicle routing problem with two‐dimensional loading constraints and mixed linehauls and backhauls. The addressed problem belongs to a subclass of general pickup and delivery problems. Two‐dimensional loading constraints are also considered. These constraints arise in many real‐world situations and can improve efficiency since backhaul customers do not need to be delayed in a route when it is possible to load their items earlier and without rearrangements of the items. To tackle this problem, we report extensive computational experiments to assess the performance of different variants of the variable neighborhood search approaches. The initial solution relies on an insertion heuristic. Both shaking and local search phases resort to 10 neighborhood structures. Some of those structures were specially developed for this problem. The feasibility of routes is heuristically obtained with a classical bottom‐left based method to tackle the explicit consideration of loading constraints. All the strategies were implemented and exhaustively tested on instances adapted from the literature. The results of this computational study are discussed at the end of this paper.     

An evolutionary implicit enumeration procedure for solving the resource‐constrained project scheduling problem

This paper presents a procedure for solving the resource‐constrained project scheduling problem. It consists of an implicit enumeration module and a genetic algorithm. If the procedure is provided access to all of its required computational resources of the problem at hand, it guarantees the optimality of the produced solution. In contrast, and in the case of limited access to computational resources, the procedure gradually moves the root of the search‐tree downward, and consequently prunes part of the search space, trading speed with precision effectively. In the cases where speed has been traded with precision, and the guarantee of optimality has been lost, the final schedule created by the implicit enumeration module is used as a template whose modified instances fill an initial pool of a genetic algorithm to improve the proposed solution. The procedure has been applied to 2040 benchmark instances. The results are promising; whereas for all small‐ and some medium‐sized instances, the procedure has found and guaranteed optimal solutions, for other instances, whose optimal solutions cannot be guaranteed within the limit of computational resources, it has produced high‐quality solutions.     

A compact model and tight bounds for a combined location-routing problem

This paper considers a combined location-routing problem. We define an auxiliary network and give a compact formulation of the problem in terms of finding a set of paths in the auxiliary network that fulfill additional constraints. The LP solution to the considered model provides an initial lower bound and is also used in a rounding procedure that provides the initial solution for a Tabu search heuristic. Additionally, we propose a different lower bound based on the structure of the problem. The results of computational testing on a set of randomly generated instances are promising.     

A hybrid VNS approach for the short-term production planning and scheduling: A case study in the pulp and paper industry

Mathematical formulations for production planning are increasing complexity, in order to improve their realism. In short-term planning, the desirable level of detail is particularly high. Exact solvers fail to generate good quality solutions for those complex models on medium- and large-sized instances within feasible time. Motivated by a real-world case study in the pulp and paper industry, this paper provides an efficient solution method to tackle the short-term production planning and scheduling in an integrated mill. Decisions on the paper machine setup pattern and on the production rate of the pulp digester (which is constrained to a maximum variation) complicate the problem. The approach is built on top of a mixed integer programming (MIP) formulation derived from the multi-stage general lotsizing and scheduling problem. It combines a Variable Neighbourhood Search procedure which manages the setup-related variables, a specific heuristic to determine the digester's production speeds and an exact method to optimize the production and flow movement decisions. Different strategies are explored to speed-up the solution procedure and alternative variants of the algorithm are tested on instances based on real data from the case study. The algorithm is benchmarked against exact procedures.     

Exact methods and a heuristic for the optimization of an integrated replenishment-storage planning problem

In this paper we study the coordination of different activities in a supply chain issued from a real case. Multiple suppliers send raw materials (RMs) to a distribution center (DC) that delivers them to a unique plant where the storage of the RMs and the finished goods is not possible. Then, the finished goods are directly shipped to multiple customers having just‐in‐time (JIT) demands. Under these hypotheses, we show that the problem can be reduced to multiple suppliers and one DC. Afterwards, we analyze two cases; in the first, we consider an uncapacitated storage at DC, and in the second, we analyze the capacitated storage case. For the first case, we show that the problem is NP‐hard in the ordinary sense using the Knapsack decision problem. We then propose two exact methods: a mixed integer linear program (MILP) and a pseudopolynomial dynamic program. A classical dynamic program and an improved one using the idea of Shaw and Wagelmans are given. With numerical tests we show that the dynamic program gives the optimal solution in reasonable time for quite large instances compared with the MILP. For the second case, the capacity limitation in DC is assumed, which makes the problem solving more challenging. We propose an MILP and a dynamic programming‐based heuristic that provides solutions close to the optimal solution in very short times.     

A branch‐and‐bound algorithm for scheduling of new product development projects

In this paper, we consider scheduling problem in a new product development project. Each research and development project consists of a set of activities in which each activity may be executed in several ways. Each way of execution of an activity is a different technology, called an alternative technology, which may fail due to technical risks. In this work, we focus on alternative technologies for scheduling activities to maximize the expected net present value. We assume that the activity payoff is obtained as soon as any single technology is completed successfully. Therefore, we analyze the problem and develop a two‐phase solution procedure, consisting of a branch‐and‐bound algorithm and a recursive search procedure. The efficiency of the proposed algorithm has been evaluated on a set of randomly generated test instances.     

Algorithms for the circular two‐dimensional open dimension problem

In this paper, we propose three heuristics for the circular two‐dimensional open dimension problem, also known as the circular strip cutting/packing problem. We first propose an open strip generation solution procedure that uses the best local position rule into the open strip. Second, we propose a simple augmented version of the first heuristic by introducing an exchange‐order strategy. Third, we propose a hybrid heuristic that combines beam search and a series of target values belonging to a predetermined interval search. We evaluate the performance of these heuristics on several instances varying from small to large ones. Encouraging results have been obtained.     

Heuristic approaches for the family traveling salesman problem

In this article, we address the family traveling salesman problem (FTSP), an NP‐hard problem that may be seen as a generalization of the traveling salesman problem. In the FTSP, the set of cities is partitioned into several families and one wants to find the minimum cost route that visits a given number of cities in each family. We propose two metaheuristics, a population‐based method and a local search method, and a hybrid algorithm, which combines a branch‐and‐cut algorithm with a local search procedure. All the proposed methods improve the best known upper bounds from the literature. The local search method and the hybrid algorithm improve the best known upper bounds for all the benchmark instances with unknown optimal value, while the population‐based method improves the best known upper bounds for all instances, except two. Furthermore, we developed an instance generator to create additional test instances with different visit patterns. These newly generated instances were considered in the computational experiment and, thus, we provide optimal values or upper bounds for each instance. Additionally, we created a website dedicated to the FTSP, where this information is made available to the scientific community ( http://familytsp.rd.ciencias.ulisboa.pt/ ).     

An efficient procedure for finding best compromise solutions to the multi-objective assignment problem

In this paper, we consider the problem of determining a best compromise solution for the multi-objective assignment problem. Such a solution minimizes a scalarizing function, such as the weighted Tchebychev norm or reference point achievement functions. To solve this problem, we resort to a ranking (or k-best) algorithm which enumerates feasible solutions according to an appropriate weighted sum until a condition, ensuring that an optimal solution has been found, is met. The ranking algorithm is based on a branch and bound scheme. We study how to implement efficiently this procedure by considering different algorithmic variants within the procedure: choice of the weighted sum, branching and bounding schemes. We present an experimental analysis that enables us to point out the best variants, and we provide experimental results showing the remarkable efficiency of the procedure, even for large size instances.     

Approximation algorithms and heuristics for task scheduling in data‐intensive distributed systems

In this work, we are interested in the problem of task scheduling on large‐scale data‐intensive computing systems. In order to achieve good performance, one must construct not only good task schedules but also good data allocation across nodes on the system, since before a task can be executed, it must have access to data distributed on the system. In this article, we present a general formulation of a static problem that combines both scheduling and replication problems in data‐intensive distributed systems. We show that this problem does not admit an approximation algorithm. However, considering a restricted version of the problem that considers some practical constraints, an approximation algorithm can be designed. From a practical perspective, we introduce a novel heuristic for the problem that is based on nodes clustering. We compare the heuristic with two adapted approaches from other works in the literature by computational simulations using an extensive set of instances based on real computer grids. We show that our heuristic often obtains the best solutions and also runs faster than other approaches.     

Parallel island based Memetic Algorithm with Lin–Kernighan local search for a real-life Two-Echelon Heterogeneous Vehicle Routing Problem based on Brazilian wholesale companies

This paper deals with a Two-Echelon Fixed Fleet Heterogeneous Vehicle Routing Problem (2E-HVRP) faced by Brazilian wholesale companies. Vehicle routing problems with more than one phase are known as Multi-Echelon VRP and consider situations in which freight is moved through some intermediate facilities (e.g., cross-docks or distribution centers) before reaching its destination. The first phase of the problem dealt here is to choose a first-level vehicle, from an heterogeneous set, that will leave a depot and reach an intermediate uncapacitated facility (satellite) to serve a set of second-level vehicles. After that, it is necessary to define routes for smaller vehicles, also from an heterogeneous set, that will visit a set of customers departing from and returning to a satellite. The solution proposed here is an efficient island based memetic algorithm with a local search procedure based on Lin–Kernighan heuristic (IBMA-LK). In order to attest the algorithm’s efficiency, first it was tested in single echelon HVRP benchmark instances. After that the instances were adapted for two-echelon context and used for 2E-HVRP validation and, finally, it was tested on 2E-HVRP instances created using real world normalized data. Localsolver tool was also executed for comparison purposes. Promising results (which corroborate results obtained on the real problem) and future works are presented and discussed.     

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.     

An exact method for the double TSP with multiple stacks

The double travelling salesman problem (TSP) with multiple stacks (DTSPMS) is a pickup and delivery problem in which all pickups must be completed before any deliveries can be made. The problem originates from a real‐life application where a 40‐foot container (configured as 11 rows of three columns) is used to transport 33 pallets from a set of pickup customers to a set of delivery customers. The pickups and deliveries are performed in two separate trips, where each trip starts and ends at a depot and visits a number of customers. The aim of the problem is to produce a packing plan for the pallets that minimizes the total transportation cost given that the container cannot be repacked at any stage. In this paper we present an exact solution method based on matching k‐best tours to each of the separate pickup and delivery TSPs. The approach is shown to outperform the only known previous exact method for this problem in that solutions can be obtained faster and previously unsolved instances containing as many as 18 customers can now be solved to optimality.     

Using iterated local search for solving the flow‐shop problem: Parallelization,parametrization, and randomization issues

Iterated local search (ILS) is a powerful framework for developing efficient algorithms for the permutation flow‐shop problem (PFSP). These algorithms are relatively simple to implement and use very few parameters, which facilitates the associated fine‐tuning process. Therefore, they constitute an attractive solution for real‐life applications. In this paper, we discuss some parallelization, parametrization, and randomization issues related to ILS‐based algorithms for solving the PFSP. In particular, the following research questions are analyzed: (a) Is it possible to simplify even more the parameter setting in an ILS framework without affecting performance? (b) How do parallelized versions of these algorithms behave as we simultaneously vary the number of different runs and the computation time? (c) For a parallelized version of these algorithms, is it worthwhile to randomize the initial solution so that different starting points are considered? (d) Are these algorithms affected by the use of a “good‐quality” pseudorandom number generator? In this paper, we introduce the new ILS‐ESP (where ESP is efficient, simple, and parallelizable) algorithm that is specifically designed to take advantage of parallel computing, allowing us to obtain competitive results in “real time” for all tested instances. The ILS‐ESP also uses “natural” parameters, which simplifies the calibration process. An extensive set of computational experiments has been carried out in order to answer the aforementioned research questions.     

An ILS heuristic for the ship scheduling problem: application in the oil industry

This paper addresses a real‐life rescheduling problem of a pipe‐laying support vessel (PLSV) fleet in charge of subsea oil well connections. The short‐term schedule of these vessels is subject to uncertainties inherent to its operations, resulting in ships idleness or delays in oil production. The objective of this study is to develop methods to support a Brazilian oil and gas company in overcoming impacts caused by operational disruptions, while reaching its planned production level. The PLSV rescheduling problem was treated as an identical parallel machine scheduling problem, where the machines represent the vessels and the jobs are the activities for the subsea well connections. We propose a mathematical programming model and a method based on the iterated local search (ILS) metaheuristic to solve the problem. This paper contributes to this by considering simultaneously setup times, machine eligibility, release dates, due dates, and machine availability. Both methods were applied on 10 instances based on real PLSV data. Taking into account an objective function that measures the operational impact on schedules, the ILS provided an average improvement above 91% in schedules when compared to the initial solution provided by the studied company. The ILS outperformed a mathematical programming model for the problem, in eight instances, within a 30‐minute execution time limit, fitting to the company process.     

Optimizing multiship routing and scheduling with constraints on inventory levels in a Brazilian oil company

This study addresses a real‐life multiship routing and scheduling application with inventory constraints that arises in pickup and delivery operations of different types of crude oil from various offshore oil rigs (platforms) to coastal terminals. Oil transportation largely results from the need to maintain inventories at each supply point (platform) between minimum and maximum levels, considering production rates in these operational points, and to meet demands of different oils in the terminals within the planning time horizon. Routing and scheduling of the available fleet aims to obtain solutions of minimum total costs, subject to various constraints such as the maximum volume of cargo carried on each ship, simultaneous cargo unloading in some terminals, conditions that rule ship docking in offshore platforms and terminal berths, among others. In this research, we modify and extend inventory constrained maritime routing and scheduling models to appropriately represent the problem of a case study at a Brazilian company and to solve small‐to‐moderate instances based on real data. We also present a matheuristic to deal with larger problem instances. Solution evaluation by company experts indicates that the model and this hybrid heuristic properly represent the problem and highlights the potential of their application in practice.     

A tabu search based hybrid evolutionary algorithm for the max-cut problem

This paper presents a tabu search based hybrid evolutionary algorithm (TSHEA) for solving the max-cut problem. The proposed algorithm integrates a distance-and-quality based solution combination operator and a tabu search procedure based on neighborhood combination of one-flip and constrained exchange moves. Comparisons with leading reference algorithms from the literature disclose that the proposed algorithm discovers new best solutions for 15 out of 91 instances, while matching the best known solutions on all but 4 instances. Analysis indicates that the neighborhood combination and the solution combination operator play key roles to the effectiveness of the proposed algorithm.