An exact solution framework for a broad class of vehicle routing problems

This paper presents an exact solution framework for solving some variants of the vehicle routing problem (VRP) that can be modeled as set partitioning (SP) problems with additional constraints. The method consists in combining different dual ascent procedures to find a near optimal dual solution of the SP model. Then, a column-and-cut generation algorithm attempts to close the integrality gap left by the dual ascent procedures by adding valid inequalities to the SP formulation. The final dual solution is used to generate a reduced problem containing all optimal integer solutions that is solved by an integer programming solver. In this paper, we describe how this solution framework can be extended to solve different variants of the VRP by tailoring the different bounding procedures to deal with the constraints of the specific variant. We describe how this solution framework has been recently used to derive exact algorithms for a broad class of VRPs such as the capacitated VRP, the VRP with time windows, the pickup and delivery problem with time windows, all types of heterogeneous VRP including the multi depot VRP, and the period VRP. The computational results show that the exact algorithm derived for each of these VRP variants outperforms all other exact methods published so far and can solve several test instances that were previously unsolved.     

Heuristic solutions for the vehicle routing problem with time windows and synchronized visits

We present a simulated annealing based algorithm for a variant of the vehicle routing problem (VRP), in which a time window is associated with each client service and some services require simultaneous visits from different vehicles to be accomplished. The problem is called the VRP with time windows and synchronized visits. The algorithm features a set of local improvement methods to deal with various objectives of the problem. Experiments conducted on the benchmark instances from the literature clearly show that our method is fast and outperforms the existing approaches. It produces all known optimal solutions of the benchmark in very short computational times, and improves the best results for the rest of the instances.     

The linear ordering problem: Instances,search space analysis and algorithms

The linear ordering problem is an NP-hard problem that arises in a variety of applications. Due to its interest in practice, it has received considerable attention and a variety of algorithmic approaches to its solution have been proposed. In this paper we give a detailed search space analysis of available benchmark instance classes that have been used in various researches. The large fitness-distance correlations observed for many of these instances suggest that adaptive restart algorithms like iterated local search or memetic algorithms, which iteratively generate new starting solutions for a local search based on previous search experience, are promising candidates for obtaining high performing algorithms. We therefore experimentally compared two such algorithms and the final experimental results suggest that, in particular, the memetic algorithm is a new state-of-the-art approach to the linear ordering problem.     

A self-tuning heuristic for a multi-objective vehicle routing problem

In this study, a heuristic free from parameter tuning is introduced to solve the vehicle routing problem (VRP) with two conflicting objectives. The problem which has been presented is the designing of optimal routes: minimizing both the number of vehicles and the maximum route length. This problem, even in the case of its single objective form, is NP-hard. The proposed self-tuning heuristic (STH) is based on local search and has two parameters which are updated dynamically throughout the search process. The most important advantage of the algorithm is the application convenience for the end-users. STH is tested on the instances of a multi-objective problem in school bus routing and classical vehicle routing. Computational experiments, when compared with the prior approaches proposed for the multi-objective routing of school buses problem, confirm the effectiveness of STH. STH also finds high-quality solutions for multi-objective VRPs.     

A combined local search and integer programming approach to the traveling tournament problem

The traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances.     

Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem

The unconstrained binary quadratic programming problem (BQP) is known to be NP-hard and has many practical applications. This paper presents a simulated annealing (SA)-based heuristic for the BQP. The new SA heuristic for the BQP is based on a simple (1-opt) local search heuristic and designed with a simple cooling schedule, but the multiple annealing processes are adopted. To show practical performances of the SA, we test on publicly available benchmark instances of large size ranging from 500 to 2500 variables and compare them with other heuristics such as multi-start local search, the previous SA, tabu search, and genetic algorithm incorporating the 1-opt local search. Computational results indicate that our SA leads to high-quality solutions with short times and is more effective than the competitors particularly for the largest benchmark set. Furthermore, the values of new best-known solutions found by the SA for several large instances are also reported.     

BPPLIB: a library for bin packing and cutting stock problems

The bin packing problem (and its variant, the cutting stock problem) is among the most intensively studied combinatorial optimization problems. We present a library of computer codes, benchmark instances, and pointers to relevant articles for these two problems. The library is available at http://or.dei.unibo.it/library/bpplib. The computer code section includes twelve programs: seven are directly downloadable from the library page, while for the remaining five we provide addresses where they can be obtained or downloaded. Some of the codes for which we provide an original C++ implementation need an integer linear programming solver. For such cases, the library provides two versions: one that uses the commercial solver CPLEX, and one that uses the freeware solver SCIP. The benchmark section provides over six thousands instances (partly coming from the literature and partly randomly generated), together with the corresponding solutions. Instances that are difficult to solve to proven optimality are included. The library also includes a BibTeX file of more than 150 references on this topic and an interactive visual tool to manually solve bin packing and cutting stock instances. We conclude this work by reporting the results of new computational experiments on a number of computer codes and benchmark instances.     

A diversified Tabu search approach for the open-pit mine production scheduling problem with metal uncertainty

This paper presents a metaheuristic solution approach based on Tabu search for the open-pit mine production scheduling problem with metal uncertainty. To search the feasible domain more extensively, two different diversification strategies are used to generate several initial solutions to be optimized by the Tabu search procedure. The first diversification strategy exploits a long-term memory of the search history. The second one relies on the variable neighborhood search method. Numerical results on realistic large-scale instances are provided to indicate the efficiency of the solution approach to produce very good solutions in relatively short computational times.     

An iterated local search algorithm for the vehicle routing problem with backhauls

The Vehicle Routing Problem with Backhauls (VRPB) is an extension of the VRP that deals with two types of customers: the consumers (linehaul) that request goods from the depot and the suppliers (backhaul) that send goods to the depot. In this paper, we propose a simple yet effective iterated local search algorithm for the VRPB. Its main component is an oscillating local search heuristic that has two main features. First, it explores a broad neighborhood structure at each iteration. This is efficiently done using a data structure that stores information about the set of neighboring solutions. Second, the heuristic performs constant transitions between feasible and infeasible portions of the solution space. These transitions are regulated by a dynamic adjustment of the penalty applied to infeasible solutions. An extensive statistical analysis was carried out in order to identify the most important components of the algorithm and to properly tune the values of their parameters. The results of the computational experiments carried out show that this algorithm is very competitive in comparison to the best metaheuristic algorithms for the VRPB. Additionally, new best solutions have been found for two instances in one of the benchmark sets. These results show that the performance of existing metaheuristic algorithms can be considerably improved by carrying out a thorough statistical analysis of their components. In particular, it shows that by expanding the exploration area and improving the efficiency of the local search heuristic, it is possible to develop simpler and faster metaheuristic algorithms without compromising the quality of the solutions obtained.     

A hybrid evolutionary algorithm for the periodic location-routing problem

The well-known vehicle routing problem (VRP) has been studied in depth over the last decades. Nowadays, generalizations of VRP have been developed for tactical or strategic decision levels of companies but not both. The tactical extension or periodic VRP (PVRP) plans a set of trips over a multiperiod horizon, subject to frequency constraints. The strategic extension is motivated by interdependent depot location and routing decisions in most distribution systems. Low-quality solutions are obtained if depots are located first, regardless of the future routes. In the location-routing problem (LRP), location and routing decisions are tackled simultaneously. Here for the first time, except for some conference papers, the goal is to combine the PVRP and LRP into an even more realistic problem covering all decision levels: the periodic LRP or PLRP. A hybrid evolutionary algorithm is proposed to solve large size instances of the PLRP. First, an individual representing an assignment of customers to combinations of visit days is randomly generated. The evolution operates through an Evolutionary Local Search (ELS) on visit day assignments. The algorithm is hybridized with a heuristic based on the Randomized Extended Clarke and Wright Algorithm (RECWA) to create feasible solutions and stops when a given number of iterations is reached. The method is evaluated over three sets of instances, and solutions are compared to the literature on particular cases such as one-day horizon (LRP) or one depot (PVRP). This metaheuristic outperforms the previous methods for the PLRP.     

A framework for analyzing sub-optimal performance of local search algorithms

This paper presents a framework for analyzing and comparing sub-optimal performance of local search algorithms for hard discrete optimization problems. The β-acceptable solution probability is introduced that captures how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. Using this probability, the necessary conditions for a local search algorithm to converge in probability to β-acceptable solutions are derived. To evaluate and compare the effectiveness of local search algorithms, two estimators for the expected number of iterations to visit a β-acceptable solution are obtained. Computational experiments are reported with simulated annealing and tabu search applied to four small traveling salesman problem instances, and the Lin-Kernighan-Helsgaun algorithm applied to eight medium to large traveling salesman problem instances (all with known optimal solutions), to illustrate the application of these estimators.     

A metaheuristic approach to the dominating tree problem

This paper considers a recently introduced NP-hard problem on graphs, called the dominating tree problem. In order to solve this problem, we develop a variable neighborhood search (VNS) based heuristic. Feasible solutions are obtained by using the set of vertex permutations that allow us to implement standard neighborhood structures and the appropriate local search procedure. Computational experiments include two classes of randomly generated test instances and benchmark test instances from the literature. Optimality of VNS solutions on small size instances is verified with CPLEX.     

Local search heuristics for multi-index assignment problems with decomposable costs

The multi-index assignment problem (MIAP) with decomposable costs is a natural generalization of the well-known assignment problem. Applications of the MIAP arise, for instance, in the field of multi-target multi-sensor tracking. We describe an (exponentially sized) neighbourhood for a solution of the MIAP with decomposable costs, and show that one can find a best solution in this neighbourhood in polynomial time. Based on this neighbourhood, we propose a local search algorithm. We empirically test the performance of published constructive heuristics and the local search algorithm on random instances; a straightforward iterated local search algorithm is also tested. Finally, we compute lower bounds to our problem, which enable us to assess the quality of the solutions found.     

Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning

Mathematical Programming - Graph partitioning is an intractable problem that arises in many practical applications. Heuristics such as local search generate good (though suboptimal) solutions in...     

A new hybrid genetic algorithm for the capacitated vehicle routing problem

Recently proved successful for variants of the vehicle routing problem (VRP) involving time windows, genetic algorithms have not yet shown to compete or challenge current best search techniques in solving the classical capacitated VRP. A new hybrid genetic algorithm to address the capacitated VRP is proposed. The basic scheme consists in concurrently evolving two populations of solutions to minimize total travelled distance using genetic operators combining variations of key concepts inspired from routing techniques and search strategies used for a time variant of the problem to further provide search guidance while balancing intensification and diversification. Results from a computational experiment over common benchmark problems report the proposed approach to be very competitive with the best-known methods.     

A proposal for a hybrid meta-strategy for combinatorial optimization problems

In this paper, we propose an algorithm named BDS (Bound-Driven Search) that combines features of exact and approximate methods. The proposed procedure may be seen as a local search algorithm that systematically explores (in a branch-and bound sense) the most promising nodes, thus preventing solutions from being reevaluated. Additionally, it can be regarded as an exact method as it may be able to guarantee that the solution found is optimal. We present the application of this new algorithm to a specific problem domain: the permutation flow shop scheduling problem with makespan objective. The subsequent computational experiments are encouraging, as the algorithm is able to yield exact or near exact solutions to most instances of the problem. Furthermore, the algorithm outperforms one of the best state-of-the-art algorithms for the problem.     

Minimizing cyclic cutwidth of graphs using a memetic algorithm

Cyclic cutwidth minimization problem (CCMP) consists of embedding a graph onto a circle such that the maximum cutwidth in a region is minimized. It is an NP-complete problem and for some classes of graphs, exact results of cyclic cutwidth have been proved in literature. However, no algorithm has been reported for general graphs. In this paper, a memetic algorithm is proposed for CCMP in which we have designed six construction heuristics in order to generate a good initial population and also local search is employed to improve the solutions in each generational phase. The algorithm achieves optimal results for the classes of graphs with known exact results. Extensive experiments have also been conducted on some classes of graphs for which exact results are not known such as the complete split graph, join of hypercubes, toroidal meshes, cone graph and some instances of Harwell-Boeing graphs which are a subset of public domain Matrix Market library. Trends observed in the experimental results for some of the classes of graphs have led to conjectures for cyclic cutwidth.     

A Tabu Search Algorithm for the Quadratic Assignment Problem

Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). One of the most important features of our tabu search implementation is an efficient use of mutations applied to the best solutions found so far. We tested this approach on a number of instances from the library of the QAP instances—QAPLIB. The results obtained from the experiments show that the proposed algorithm belongs to the most efficient heuristics for the QAP. The high efficiency of this algorithm is also demonstrated by the fact that the new best known solutions were found for several QAP instances.     

Heuristics for the lexicographic max-ordering vehicle routing problem

In this paper, we propose fast heuristics for the vehicle routing problem (VRP) with lexicographic max-order objective. A fixed number of vehicles, which are based at a depot, are to serve customers with known demands. The lexicographic max-order objective is introduced by asking to minimize lexicographically the sorted route lengths. Based on a model for this problem, several approaches are studied and new heuristic solution procedures are discussed resulting in the development of a sequential insertion heuristic and a modified savings algorithm in several variants. Comparisons between the algorithms are performed on instances of the VRP library VRPLIB. Finally, based on the results from the computational experiments, conclusions about the applicability and efficiency of the presented algorithms are drawn.     

A two-stage intelligent search algorithm for the two-dimensional strip packing problem

This paper presents a two-stage intelligent search algorithm for a two-dimensional strip packing problem without guillotine constraint. In the first stage, a heuristic algorithm is proposed, which is based on a simple scoring rule that selects one rectangle from all rectangles to be packed, for a given space. In the second stage, a local search and a simulated annealing algorithm are combined to improve solutions of the problem. In particular, a multi-start strategy is designed to enhance the search capability of the simulated annealing algorithm. Extensive computational experiments on a wide range of benchmark problems from zero-waste to non-zero-waste instances are implemented. Computational results obtained in less than 60 seconds of computation time show that the proposed algorithm outperforms the supposedly excellent algorithms reported recently, on average. It performs particularly better for large instances.