Tabu search heuristics for the order batching problem in manual order picking systems

In a manual order picking system, order pickers walk or ride through a distribution warehouse in order to collect items requested by (internal or external) customers. In order to perform these operations efficiently, it is usually required that customer orders be combined into (more substantial) picking orders that are limited in size. The order batching problem considered in this paper deals with the question of how a given set of customer orders should be combined into picking orders such that the total length of all picker tours necessary for all of the requested items to be collected is minimized. For the solution of this problem the authors suggest two approaches based on the tabu search principle. The first is a (classic) tabu search (TS), and the second is the attribute-based hill climber (ABHC). In a series of extensive numerical experiments, these approaches are benchmarked against other solution methods put forward in the current literature. It is demonstrated that the proposed methods are superior to the existing methods and provide solutions which may allow distribution warehouses to operate more efficiently.     

A hybrid tabu search/branch & bound approach to solving the generalized assignment problem

A new approach for solving the generalized assignment problem (GAP) is proposed that combines the exact branch & bound approach with the heuristic strategy of tabu search (TS) to produce a hybrid algorithm for solving GAP. The algorithm described uses commercial software to solve sub-problems generated by the TS guiding strategy. The TS approach makes use of the concept of referent domain optimisation and introduces novel add/drop strategies. In addition, the linear programming relaxation of GAP that forms part of the branch & bound approach is itself helpful in suggesting which variables might take binary values. Computational results on benchmark test instances are presented and compared with results obtained by the standard branch & bound approach and also several other heuristic approaches from the literature. The results show the new algorithm performs competitively against the alternatives and is able to find some new best solutions for several benchmark instances.     

Lagrangian relaxation guided problem space search heuristics for generalized assignment problems

We develop and test a heuristic based on Lagrangian relaxation and problem space search to solve the generalized assignment problem (GAP). The heuristic combines the iterative search capability of subgradient optimization used to solve the Lagrangian relaxation of the GAP formulation and the perturbation scheme of problem space search to obtain high-quality solutions to the GAP. We test the heuristic using different upper bound generation routines developed within the overall mechanism. Using the existing problem data sets of various levels of difficulty and sizes, including the challenging largest instances, we observe that the heuristic with a specific version of the upper bound routine works well on most of the benchmark instances known and provides high-quality solutions quickly. An advantage of the approach is its generic nature, simplicity, and implementation flexibility.     

Tabu search for solving the black-and-white travelling salesman problem

The black-and-white travelling salesman problem (BWTSP) is an extension to the well-known TSP by partitioning the set of vertices into black and white vertices, and imposing cardinality and length constraints between two consecutive black vertices in a Hamiltonian tour. BWTSP has various applications in aircraft routing, telecommunication network design and logistics. In this paper, we develop several tabu search (TS) heuristics for solving the BWTSP. Our TS is built upon a new efficient neighbourhood structure, which exploits both the permutation and knapsack features of BWTSP. We also embed our TS as a heuristic procedure to improve the upper bound in a mixed-integer linear programming method. Extensive computational experiment on both benchmark and randomly generated instances shows effectiveness and efficiency of our algorithms. Our algorithms are able to obtain optimal and near optimal solutions to small instances in seconds, and find feasible solutions to large instances that have not been solved by the existing methods in the literature.     

A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem

We present a variable neighborhood search approach for solving the one-commodity pickup-and-delivery travelling salesman problem. It is characterized by a set of customers such that each of the customers either supplies (pickup customers) or demands (delivery customers) a given amount of a single product, and by a vehicle, whose given capacity must not be exceeded, that starts at the depot and must visit each customer only once. The objective is to minimize the total length of the tour. Thus, the considered problem includes checking the existence of a feasible travelling salesman’s tour and designing the optimal travelling salesman’s tour, which are both NP-hard problems. We adapt a collection of neighborhood structures, k-opt, double-bridge and insertion operators mainly used for solving the classical travelling salesman problem. A binary indexed tree data structure is used, which enables efficient feasibility checking and updating of solutions in these neighborhoods. Our extensive computational analysis shows that the proposed variable neighborhood search based heuristics outperforms the best-known algorithms in terms of both the solution quality and computational efforts. Moreover, we improve the best-known solutions of all benchmark instances from the literature (with 200 to 500 customers). We are also able to solve instances with up to 1000 customers.     

A tabu search heuristic for the vehicle routing problem with private fleet and common carrier

This paper describes a tabu search heuristic for a vehicle routing problem where the owner of a private fleet can either visit a customer with one of his vehicles or assign the customer to a common carrier. The owner’s objective is to minimize the variable and fixed costs for operating his fleet plus the total costs charged by the common carrier. The proposed tabu search is shown to outperform the best approach reported in the literature on 34 benchmark instances with a homogeneous fleet.     

Diversified local search strategy under scatter search framework for the probabilistic traveling salesman problem

This paper focuses on introducing a concept of diversified local search strategy under the scatter search framework for the probabilistic traveling salesman problem (PTSP). Different combinations of three commonly used local search methods in the PTSP, i.e., 1-shift, 2-opt, and 3-opt, were used to investigate its effects. A set of numerical experiments were conducted to test the validity of the proposed strategy based on randomly generated test instances. The numerical results and the permutation test showed that the diversified local search strategy, especially by combining 1-shift and 2-opt algorithms, can most effectively solve the homogeneous and heterogeneous PTSP in most of the tested instances in comparison with the single local search strategy under scatter search framework.     

A reactive tabu search for the vehicle routing problem

The classical vehicle routing problem (VRP) involves determining a fleet of homogeneous size vehicles and designing an associated set of routes that minimizes the total cost. Our tabu search (TS) algorithm to solve the VRP is based on reactive tabu search (RTS) with a new escape mechanism, which manipulates different neighbourhood schemes in a very sophisticated way in order to get a balanced intensification and diversification continuously during the search process. We compare our algorithm with the best methods in the literature using different data sets and report results including new best known solutions for several well-known benchmark problems.     

Variable neighbourhood search for bandwidth reduction

The problem of reducing the bandwidth of a matrix consists of finding a permutation of rows and columns of a given matrix which keeps the non-zero elements in a band as close as possible to the main diagonal. This NP-complete problem can also be formulated as a vertex labelling problem on a graph, where each edge represents a non-zero element of the matrix. We propose a variable neighbourhood search based heuristic for reducing the bandwidth of a matrix which successfully combines several recent ideas from the literature. Empirical results for an often used collection of 113 benchmark instances indicate that the proposed heuristic compares favourably to all previous methods. Moreover, with our approach, we improve best solutions in 50% of instances of large benchmark tests.     

A parallel multi-neighborhood cooperative tabu search for capacitated vehicle routing problems

This paper presents a parallel tabu search algorithm that utilizes several different neighborhood structures for solving the capacitated vehicle routing problem. Single neighborhood or neighborhood combinations are encapsulated in tabu search threads and they cooperate through a solution pool for the purpose of exploiting their joint power. The computational experiments on 32 large scale benchmark instances show that the proposed method is highly effective and competitive, providing new best solutions to four instances while the average deviation of all best solutions found from the collective best results reported in the literature is about 0.22%. We are also able to associate the beneficial use of special neighborhoods with some test instance characteristics and uncover some sources of the collective power of multi-neighborhood cooperation.     

The bi-objective Pollution-Routing Problem

The bi-objective Pollution-Routing Problem is an extension of the Pollution-Routing Problem (PRP) which consists of routing a number of vehicles to serve a set of customers, and determining their speed on each route segment. The two objective functions pertaining to minimization of fuel consumption and driving time are conflicting and are thus considered separately. This paper presents an adaptive large neighborhood search algorithm (ALNS), combined with a speed optimization procedure, to solve the bi-objective PRP. Using the ALNS as the search engine, four a posteriori methods, namely the weighting method, the weighting method with normalization, the epsilon-constraint method and a new hybrid method (HM), are tested using a scalarization of the two objective functions. The HM combines adaptive weighting with the epsilon-constraint method. To evaluate the effectiveness of the algorithm, new sets of instances based on real geographic data are generated, and a library of bi-criteria PRP instances is compiled. Results of extensive computational experiments with the four methods are presented and compared with one another by means of the hypervolume and epsilon indicators. The results show that HM is highly effective in finding good-quality non-dominated solutions on PRP instances with 100 nodes.     

An adaptive large neighborhood search algorithm for a selective and periodic inventory routing problem

We study a selective and periodic inventory routing problem (SPIRP) and develop an Adaptive Large Neighborhood Search (ALNS) algorithm for its solution. The problem concerns a biodiesel production facility collecting used vegetable oil from sources, such as restaurants, catering companies and hotels that produce waste vegetable oil in considerable amounts. The facility reuses the collected waste oil as raw material to produce biodiesel. It has to meet certain raw material requirements either from daily collection, or from its inventory, or by purchasing virgin oil. SPIRP involves decisions about which of the present source nodes to include in the collection program, and which periodic (weekly) routing schedule to repeat over an infinite planning horizon. The objective is to minimize the total collection, inventory and purchasing costs while meeting the raw material requirements and operational constraints. A single-commodity flow-based mixed integer linear programming (MILP) model was proposed for this problem in an earlier study. The model was solved with 25 source nodes on a 7-day cyclic planning horizon. In order to tackle larger instances, we develop an ALNS algorithm that is based on a rich neighborhood structure with 11 distinct moves tailored to this problem. We demonstrate the performance of the ALNS, and compare it with the MILP model on test instances containing up to 100 source nodes.     

A library of local search heuristics for the vehicle routing problem

The vehicle routing problem (VRP) is a difficult and well-studied combinatorial optimization problem. Real-world instances of the VRP can contain hundreds and even thousands of customer locations and can involve many complicating constraints, necessitating the use of heuristic methods. We present a software library of local search heuristics that allows one to quickly generate solutions to VRP instances. The code has a logical, object-oriented design and uses efficient data structures to store and modify solutions. The core of the library is the implementation of seven local search operators that share a similar interface and are designed to be extended to handle additional options with minimal code change. The code is well-documented, straightforward to compile, and is freely available online. The code contains several applications that can be used to generate solutions to the capacitated VRP. Computational results indicate that these applications are able to generate solutions that are within about one percent of the best-known solution on benchmark problems.     

Decomposition and local search based methods for the traveling umpire problem

The Traveling Umpire Problem (TUP) is a challenging combinatorial optimization problem based on scheduling umpires for Major League Baseball. The TUP aims at assigning umpire crews to the games of a fixed tournament, minimizing the travel distance of the umpires. The present paper introduces two complementary heuristic solution approaches for the TUP. A new method called enhanced iterative deepening search with leaf node improvements (IDLI) generates schedules in several stages by subsequently considering parts of the problem. The second approach is a custom iterated local search algorithm (ILS) with a step counting hill climbing acceptance criterion. IDLI generates new best solutions for many small and medium sized benchmark instances. ILS produces significant improvements for the largest benchmark instances. In addition, the article introduces a new decomposition methodology for generating lower bounds, which improves all known lower bounds for the benchmark instances.     

An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem

In this paper we present two major approaches to solve the car sequencing problem, in which the goal is to find an optimal arrangement of commissioned vehicles along a production line with respect to constraints of the form “no more than l_ccars are allowed to require a component c in any subsequence of m_cconsecutive cars”. The first method is an exact one based on integer linear programming (ILP). The second approach is hybrid: it uses ILP techniques within a general variable neighborhood search (VNS) framework for examining large neighborhoods. We tested the two methods on benchmark instances provided by CSP_LIB and the automobile manufacturer RENAULT for the ROADEF Challenge 2005. These tests reveal that our approaches are competitive to previous reported algorithms. For the CSP_LIB instances we were able to shorten the required computation time for reaching and proving optimality. Furthermore, we were able to obtain tight bounds on some of the ROADEF instances. For two of these instances the proposed ILP-method could provide new optimality proofs for already known solutions. For the VNS, the individual contributions of the used neighborhoods are also experimentally analyzed. Results highlight the significant impact of each structure. In particular the large ones examined using ILP techniques enhance the overall performance significantly, so that the hybrid approach clearly outperforms variants including only commonly defined neighborhoods.     

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.     

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.     

Approximating the maximum vertex/edge weighted clique using local search

This paper extends the recently introduced Phased Local Search (PLS) algorithm to more difficult maximum clique problems and also adapts the algorithm to handle maximum vertex/edge weighted clique instances. PLS is a stochastic reactive dynamic local search algorithm that interleaves sub-algorithms which alternate between sequences of iterative improvement, during which suitable vertices are added to the current sub-graph, and plateau search, where vertices of the current sub-graph are swapped with vertices not contained in the current sub-graph. These sub-algorithms differ in firstly their vertex selection techniques in that selection can be solely based on randomly selecting a vertex, randomly selecting within highest vertex degree, or random selecting within vertex penalties that are dynamically adjusted during the search. Secondly, the perturbation mechanism used to overcome search stagnation differs between the sub-algorithms. PLS has no problem instance dependent parameters and achieves state-of-the-art performance for maximum clique and maximum vertex/edge weighted clique problems over a large range of the commonly used DIMACS benchmark instances.     

A two-phase tabu search based evolutionary algorithm for the maximum diversity problem

In this paper, we study the maximum diversity problem (MDP) which is equivalent to the quadratic unconstrained binary optimization (QUBO) problem with cardinality constraint. The MDP aims to select a subset of elements with given cardinality such that the sum of pairwise distances between any two elements in the selected subset is maximized. For solving this computationally challenging problem, we propose a two-phase tabu search based evolutionary algorithm (TPTS/EA), which integrates several distinguishing features to ensure the diversity and the quality of the evolution, such as a two-phase tabu search algorithm which consists of a dynamic candidate list (DCL) strategy-based traditional tabu search in the first phase and a solution-based tabu search procedure to refine the search in the second phase, and two path-relinking based recombination operators to generate new offspring solutions. Tested on three sets of totally 140 public instances in the literature, the study demonstrates the efficacy of the proposed TPTS/EA algorithm in terms of both solution quality and computational efficiency. Specifically, our proposed TPTS/EA algorithm is able to improve the previous best known results for 2 instances, while matching the previous best-known solutions for 130 instances. We also provide experimental evidences to highlight the beneficial effect of several important components in our TPTS/EA algorithm.     

A tabu search algorithm for the single machine total weighted tardiness problem

In this study, a tabu search (TS) approach to the single machine total weighted tardiness problem (SMTWT) is presented. The problem consists of a set of independent jobs with distinct processing times, weights and due dates to be scheduled on a single machine to minimize total weighted tardiness. The theoretical foundation of single machine scheduling with due date related objectives reveal that the problem is NP-hard, rendering it a challenging area for meta-heuristic approaches. This paper presents a totally deterministic TS algorithm with a hybrid neighborhood and dynamic tenure structure, and investigates the strength of several candidate list strategies based on problem specific characteristics in increasing the efficiency of the search. The proposed TS approach yields very high quality results for a set of benchmark problems obtained from the literature.