Alain Hertz
RetourCahiers du GERAD
114 résultats — page 5 de 6
The Metric Bridge Partition Problem
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"...
référence BibTeX
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...
référence BibTeX
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 ...
référence BibTeXA Note on Tree Realizations of Matrices
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 ...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
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...
référence BibTeX
The problem retained for the ROADEF'2001 international challenge was a frequency assignment problem with polarization constraints (FAPP). This NP-hard probl...
référence BibTeX
<i>Tabucol</i> is a tabu search algorithm that tries to determine whether the vertices of a given graph can be colored with a fixed number <i>k</...
référence BibTeX
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 ...
référence BibTeX
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 ...
référence BibTeX
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...
référence BibTeX
Given a finite set <i>E</i> and a family <i>F</i>={<i>E</i><sub>1</sub>,...,<i>E<sub>m</sub></i>} of subsets of <i>E</i> such that <i>F</i> covers <i>E</i>...
référence BibTeX
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 ...
référence BibTeX
The 18<sup>th</sup> EURO Summer/Winter Institute (ESWI XVIII) took place during the spring 2000 in Switzerland. The topic of ESWI XVIII, "Meta-heuristics in ...
référence BibTeXRecent Trends in Arc Routing
Arc routing problems (ARPs) arise naturally in several applications where streets require maintenance, or customers located along road must be serviced. The ...
référence BibTeX
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...
référence BibTeX
The complexity status of the maximum stable set problem in the class of <i>P</i><sub>5</sub>-free graphs is unknown. In this paper, we first propose a chara...
référence BibTeX
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 ...
référence BibTeX
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...
référence BibTeX