A large neighborhood search heuristic for the longest common subsequence problem

Given a set S={S ¹,…,S ^k } of finite strings, the k-Longest Common Subsequence Problem (k-LCSP) seeks a string L ^* of maximum length such that L ^* is a subsequence of each S ⁱ for i=1,…,k. This paper presents a large neighborhood search technique that provides quality solutions to large k-LCSP instances. This heuristic runs in linear time in both the length of the sequences and the number of sequences. Some computational results are provided.     

A large neighbourhood search heuristic for the aircraft and passenger recovery problem

This paper introduces a large neighbourhood search heuristic for an airline recovery problem combining fleet assignment, aircraft routing and passenger assignment. Given an initial schedule, a list of disruptions, and a recovery period, the problem consists in constructing aircraft routes and passenger itineraries for the recovery period that allow the resumption of regular operations and minimize operating costs and impacts on passengers. The heuristic alternates between construction, repair and improvement phases, which iteratively destroy and repair parts of the solution. The aim of the first two phases is to produce an initial solution that satisfies a set of operational and functional constraints. The third phase then attempts to identify an improved solution by considering large schedule changes while retaining feasibility. The whole process is iterated by including some randomness in the construction phase so as to diversify the search. This work was initiated in the context of the 2009 ROADEF Challenge, a competition organized jointly by the French Operational Research and Decision Analysis Society and the Spanish firm Amadeus S.A.S., in which our team won the first prize.     

Network flow-based approaches for integrated aircraft fleeting and routing

Given a schedule of flights to be flown, the aircraft fleeting and routing problem (AFRP) consists of determining a minimum-cost route assignment for each aircraft so as to cover each flight by exactly one aircraft while satisfying maintenance requirements and other activity constraints. We investigate network flow-based heuristic approaches for this problem. Computational experiments conducted on real-data given by TunisAir show that the proposed heuristic consistently yields very near-optimal solutions while requiring modest CPU effort.     

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 variable neighborhood search heuristic for periodic routing problems

The aim of this paper is to propose a new heuristic for the Periodic Vehicle Routing Problem (PVRP) without time windows. The PVRP extends the classical Vehicle Routing Problem (VRP) to a planning horizon of several days. Each customer requires a certain number of visits within this time horizon while there is some flexibility on the exact days of the visits. Hence, one has to choose the visit days for each customer and to solve a VRP for each day. Our method is based on Variable Neighborhood Search (VNS). Computational results are presented, that show that our approach is competitive and even outperforms existing solution procedures proposed in the literature. Also considered is the special case of a single vehicle, i.e. the Periodic Traveling Salesman Problem (PTSP). It is shown that slight changes of the proposed VNS procedure is also competitive for the PTSP.     

Hybrid large neighborhood search for the bus rapid transit route design problem

Due to an increasing demand for public transportation and intra-urban mobility, an efficient organization of public transportation has gained significant importance in the last decades. In this paper we present a model formulation for the bus rapid transit route design problem, given a fixed number of routes to be offered. The problem can be tackled using a decomposition strategy, where route design and the determination of frequencies and passenger flows will be dealt with separately. We propose a hybrid metaheuristic based on a combination of Large Neighborhood Search (LNS) and Linear Programming (LP). The algorithm as such is iterative. Decision upon the design of routes will be handled using LNS. The resulting passenger flows and frequencies will be determined by solving a LP. The solution obtained may then be used to guide the exploration of new route designs in the following iterations within LNS. Several problem specific operators are suggested and have been tested. The proposed algorithm compares extremely favorable and is able to obtain high quality solutions within short computational times.     

A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem

Given a set of customer orders and a routing policy, the goal of the order-batching problem?(OBP) is to group customer orders to picking orders (batches) such that the total length of all tours through a rectangular warehouse is minimized. Because order picking is considered the most labor-intensive process in warehousing, effectively batching customer orders can result in considerable savings. The OBP is NP-hard if the number of orders per batch is greater than two, and the exact solution methods proposed in the literature are not able to consistently solve larger instances. To address larger instances, we develop a metaheuristic hybrid based on adaptive large neighborhood search and tabu search, called ALNS/TS. In numerical studies, we conduct an extensive comparison of ALNS/TS to all previously published OBP methods that have used standard benchmark sets to investigate their performance. ALNS/TS outperforms all comparison methods with respect to both average solution quality and run-time. Compared to the state-of-the-art, ALNS/TS shows the clearest advantages on the larger instances of the existing benchmark sets, which assume a higher number of customer orders and higher capacities of the picking device. Finally, ALNS/TS is able to solve newly generated large-scale instances with up to 600 customer orders and six articles per customer order with reasonable run-times and convincing scaling behavior and robustness.     

A continuous variable neighborhood search heuristic for finding the three-dimensional structure of a molecule

We develop a continuous variable neighborhood search heuristic for minimizing the potential energy function of a molecule. Computing the global minimum of this function is very difficult because it has a large number of local minimizers which grows exponentially with molecule size. Experimental evidence shows that in the great majority of cases the global minimum potential energy of a given molecule corresponds to its three-dimensional structure and this structure is important because it dictates most of the properties of the molecule. Computational results for problems with up to 200 degrees of freedom are presented and favourable compared with other two existing methods from the literature.     

A variable neighborhood search for the capacitated arc routing problem with intermediate facilities

The capacitated arc routing problem (CARP) focuses on servicing edges of an undirected network graph. A wide spectrum of applications like mail delivery, waste collection or street maintenance outlines the relevance of this problem. A realistic variant of the CARP arises from the need of intermediate facilities (IFs) to load up or unload the service vehicle and from tour length restrictions. The proposed Variable Neighborhood Search (VNS) is a simple and robust solution technique which tackles the basic problem as well as its extensions. The VNS shows excellent results on four different benchmark sets. Particularly, for all 120 instances the best known solution could be found and in 71 cases a new best solution was achieved.     

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 deterministic tabu search algorithm for the fleet size and mix vehicle routing problem

The fleet size and mix vehicle routing problem consists of defining the type, the number of vehicles of each type, as well as the order in which to serve the customers with each vehicle when a company has to distribute goods to a set of customers geographically spread, with the objective of minimizing the total costs. In this paper, a heuristic algorithm based on tabu search is proposed and tested on several benchmark instances. The computational results show that the proposed algorithm produces high quality results within a reasonable computing time. Some new best solutions are reported for a set of test problems used in the literature.     

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.     

Combining very large scale and ILP based neighborhoods for a two-level location problem

In this paper we tackle a generalization of the Single Source Capacitated Facility Location Problem in which two sets of facilities, called intermediate level and upper level facilities, have to be located; the dimensioning of the intermediate set, the assignment of clients to intermediate level facilities, and of intermediate level facilities to upper level facilities, must be optimized, as well. Such problem arises, for instance, in telecommunication network design: in fact, in hierarchical networks the traffic arising at client nodes often have to be routed through different kinds of facility nodes, which provide different services. We propose a heuristic approach, based on very large scale neighborhood search to tackle the problem, in which both ad hoc algorithms and general purpose solvers are applied to explore the search space. We report on experimental results using datasets from the capacitated location literature. Such results show that the approach is promising and that Integer Linear Programming based neighborhoods are significantly effective.     

Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph

We consider four conjectures related to the largest eigenvalue of (the adjacency matrix of) a graph (i.e., to the index of the graph). Three of them have been formulated after some experiments with the programming system AutoGraphiX, designed for finding extremal graphs with respect to given properties by the use of variable neighborhood search. The conjectures are related to the maximal value of the irregularity and spectral spread in n-vertex graphs, to a Nordhaus–Gaddum type upper bound for the index, and to the maximal value of the index for graphs with given numbers of vertices and edges. None of the conjectures has been resolved so far. We present partial results and provide some indications that the conjectures are very hard.     

Stability of boundary layer and rarefaction wave to an outflow problem for compressible Navier-Stokes equations under large perturbation

In this paper, we investigate the large-time behavior of solutions to an outflow problem for compressible Navier-Stokes equations. In 2003, Kawashima, Nishibata and Zhu [S. Kawashima, S. Nishibata, P. Zhu, Asymptotic stability of the stationary solution to the compressible Navier-Stokes equations in the half space, Comm. Math. Phys. 240 (2003) 483-500] showed there exists a boundary layer (i.e., stationary solution) to the outflow problem and the boundary layer is nonlinearly stable under small initial perturbation. In the present paper, we show that not only the boundary layer above but also the superposition of a boundary layer and a rarefaction wave are stable under large initial perturbation. The proofs are given by an elementary energy method.