Let <i>G = (V,E,w)</i> be a graph with vertex and edge sets <i>V</i> and <i>E</i>, respectively, and <i>w : E</i> <img src="/cgi-bin/mimetex.cgi?\rightarrow"...

The Team Orienteering Problem (TOP) is the generalization to the case of mul- tiple tours of the Orienteering Problem, known also as Selective Traveling Sal...

We consider a crew scheduling problem with preferential bidding in the airline industry. We propose a new methodology based on a graph coloring model and a ...

It is well known that each tree metric <i>M</i> has a unique realization as a tree, and that this realization minimizes the total length of the edges among ...

Nous décrivons les méta-heuristiques couramment utilisées en optimisation, avec pour objectif de guider toute personne désirant adapter une méta-heuristique...

This article reviews some of the best metaheuristics proposed in recent years for the Vehicle Routing Problem. These are based on local search, on populatio...

In the present paper we review the method of augmenting graphs, which is a general approach to solve the maximum independent set problem. Our objective is th...

The problem retained for the ROADEF'2001 international challenge was a frequency assignment problem with polarization constraints (FAPP). This NP-hard probl...

<i>Tabucol</i>&nbsp; is a tabu search algorithm that tries to determine whether the vertices of a given graph can be colored with a &#64257;xed number <i>k</...

This paper presents algorithms to find vertex-critical and edge-critical subgraphs in a given graph <i>G</i>, and demonstrates how these critical subgraphs ...

Let <i>G</i>=(<i>V,E</i>) be a graph with vertex set <i>V</i> and edge set <i>E</i>. The <i>k</i>-colouring problem is to assign a colour (a number chosen ...

The augmenting chain technique has been applied to solve the maximum stable set problem in the class of line graphs (which coincides with the maximum matchin...

Given a finite set <i>E</i> and a family <i>F</i>={<i>E</i>₁,...,<i>E_m</i>} of subsets of <i>E</i> such that <i>F</i> covers <i>E</i>...

We describe a tabu search algorithm for the vehicle routing problem with split deliveries. At each iteration, a neighbour solution is obtained by removing a ...

The 18^th EURO Summer/Winter Institute (ESWI XVIII) took place during the spring 2000 in Switzerland. The topic of ESWI XVIII, "Meta-heuristics in ...

Arc routing problems (ARPs) arise naturally in several applications where streets require maintenance, or customers located along road must be serviced. The ...

Finding augmenting chains is in the heart of the maximum matching problem, which is equivalent to the maximum stable set problem in the class of line graphs...

The complexity status of the maximum stable set problem in the class of <i>P</i>₅-free graphs is unknown. In this paper, we first propose a chara...

The maximum stable set problem is NP-hard, even when restricted to <i>banner</i>-free graphs. In this paper, we use the augmenting graph approach to attack ...

This article reports on some recent algorithmic development for the <i>Rural Postman Problem</i> (CPP) and for the <i>Capacitated Arc Routing Problem</i> (C...