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.