Search

We present a new algorithm that uses both local branching and Monte Carlo sampling in a multidescent search strategy for solving 0-1 integer stochastic programming problems. This procedure is applied [...]

This paper shows how local branching can be used to accelerate the classical Benders decomposition algorithm. By applying local branching throughout the solution process, one can simultaneously improve both the […]

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2004.12.006 Byline: Michel Gendreau (a)(b), Jean-Yves Potvin (a)(b), Ali Smires (a)(b), Patrick Soriano (a)(c) Keywords: Telecommunications; Local access network; Capacity expansion; Multi-period; Heuristic Abstract: In this paper, we examine a multi-period capacity expansion problem for a local access telecommunications network with a tree topology. Capacity expansion is realized through the installation of concentrators at the nodes and cables on the links of the network. Clearly, the installation of concentrators reduces the need for additional cables, and conversely. The goal is to find the least cost alternative to satisfy the demand. A heuristic approach is proposed to solve this problem, where local installation decisions at each node are propagated in the network. This information is then used to adjust prices that guide the decision process from one iteration to the next, until a fixed point is reached. Numerical results are reported on problem instances based on different cost and demand structures. Author Affiliation: (a) Centre de Recherche sur les Transports, Universite de Montreal, C.P. 6128, Succursale Centre-ville, Montreal, Que., Canada H3C 3J7 (b) Departement d'Informatique et de Recherche Operationnelle, Universite de Montreal, C.P. 6128, Succursale Centre-ville, Montreal, Que., Canada H3C 3J7 (c) Ecole des Hautes Etudes Commerciales, 3000, Chemin de la CA[acute accent]te-Sainte-Catherine, Montreal, Que., Canada H3T 2A7 Article History: Received 19 May 2004; Accepted 13 December 2004

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2004.07.031 Byline: Sophie D. Lapierre (a)(b), Angel Ruiz (a)(c), Patrick Soriano (a)(d) Keywords: Assembly line balancing; Tabu search; Metaheuristic Abstract: Balancing assembly lines is a crucial task for manufacturing companies in order to improve productivity and minimize production costs. Despite some progress in exact methods to solve large scale problems, softwares implementing simple heuristics are still the most commonly used tools in industry. Some metaheuristics have also been proposed and shown to improve on classical heuristics but, to our knowledge, no computational experiments have been performed on real industrial applications to clearly assess their performance as well as their flexibility. Here we present a new tabu search algorithm and discuss its differences with respect to those in the literature. We then evaluate its performance on the Type I assembly line balancing problem. Finally, we test our algorithm on a real industrial data set involving 162 tasks, 264 precedence constraints, and where the assembly is carried out on a sequential line with workstations located on both sides of the conveyor, with two possible conveyor heights and no re-positioning of the product. We discuss the flexibility of the metaheuristic and its ability to solve real industrial cases. Author Affiliation: (a) Centre de recherche sur les transports, Universite de Montreal, CP 6128, Succursale Centre-ville, Montreal (Qc), Canada H3C 3J7 (b) Departement de mathematiques appliquees et genie industriel, Ecole Polytecnique de Montreal, CP 6079, Succursale Centre-ville, Montreal (Qc), Canada H3C 3A7 (c) Departement operations et systemes de decision, Faculte des sciences de l'administration, Universite Laval, Quebec (Qc), Canada G1K 7P4 (d) Service dc I'enseignement des methodes quantitatives de gestion, Ecole des Hautes Etudes Commerciales, 3000 Chemin de la CA[acute accent]te-Sainte-Catherine, Montreal (Qc), Canada H3T 2A7

A tabu search heuristic for the design of self-healing rings (SHRs), to protect the transmission of telecommunication demands, in a zonal network is proposed. This search has demonstrated its efficiency by improving significantly upon the best solutions that could be found with a greedy constructive heuristic over a large set of real and randomly generated instances.

Usage of metaheuristics for development of model for designing telecommunication networks, with minimal costs of installation, is described.

Cet article propose une revue des différents travaux publiés en lien avec le déploiement et le redéploiement des véhicules ambulanciers. Le problème de déploiement consiste à déterminer les différents points d'attente à utiliser pour la localisation des véhicules entre deux affectations. De son côté, le problème de redéploiement consiste plutôt à relocaliser les véhicules disponibles parmi les différents points d'attente potentiels de façon à assurer, en tout temps, une couverture adéquate de la population. Cet article présente les trois principales approches considérées pour modéliser le problème de déploiement, soit la programmation mathématique, la simulation et la théorie des files d'attente, et recense les méthodes développées afin de le résoudre. Il propose également une description des modèles conçus pour le redéploiement des véhicules ambulanciers. Enfin, il discute des règles d'affectation des véhicules aux appels de détresse, puis de différentes avenues de recherche potentielles. [ABSTRACT FROM AUTHOR]

Kraft pulp, the raw material in paper manufacturing, is obtained by exposing pieces of wood to a cooking process. The parameters of this process (temperatures, times, chemicals, etc.) depend strongly on the density of the different woods in the cooker and have an influence on the quality of the pulp that is obtained. In order to optimize both the production process and the pulp quality, one wishes to cook together woods having similar densities. However, given that the harvest areas contain limited quantities of trees and that wood densities vary significantly from one area to another, deciding how harvested wood from different areas should be mixed for processing is a significant operational decision in pulp production planning. This situation is modelled as a scheduling problem where one has to decide which harvested area goes to each available processing units in order to minimize the variance of wood densities within each cooker for each period of the planning horizon. We also present an approximated solution approach based on the formulation proposed. Some results are reported and the efficiency of the method is discussed. [ABSTRACT FROM AUTHOR]

The search for sites to locate stabilised special waste storage facilities (SWSF) falls in the realm of hazardous/non-desirable facility location problems. The implementation of such projects is often difficult given their multi-stakeholder and multi-criteria dimensions. They are frequently disputed or even blocked. In this paper, we present the process developed for the selection of SWSF sites in French-speaking Switzerland. This process, which has been in progress since 1987, is a multidisciplinary iterative approach that incorporates multicriteria decision making techniques like ELECTRE I. The strength and originality of this approach lie in the fact that both the technical and sociopolitical aspects of the problem are taken into account simultaneously. This enables the decision maker to identify the players that have to be consulted and to define over time the type of decisions, both technical and non-technical, that need to be taken as well as the process to be followed for each of them. [ABSTRACT FROM AUTHOR]