A Slope Scaling/Lagrangean Perturbation Heuristic with Long-Term Memory for Multicommodity Capacitated Fixed-Charge Network Design |
| |
Authors: | Teodor Gabriel Crainic Bernard Gendron Geneviève Hernu |
| |
Institution: | (1) Département d'informatique et recherche opérationnelle Centre de recherche sur les transports, Université de Montréal, C.P.6128, succursale Centre-ville, Montréal, Canada, H3C 3J7;(2) Département de management et technologie, Université du Québec à Montréal Centre de recherche sur les transports, Université de Montréal, Montréal, Canada |
| |
Abstract: | This paper describes a slope scaling heuristic for solving the multicomodity capacitated fixed-charge network design problem. The heuristic integrates a Lagrangean perturbation scheme and intensification/diversification mechanisms based on a long-term memory. Although the impact of the Lagrangean perturbation mechanism on the performance of the method is minor, the intensification/diversification components of the algorithm are essential for the approach to achieve good performance. The computational results on a large set of randomly generated instances from the literature show that the proposed method is competitive with the best known heuristic approaches for the problem. Moreover, it generally provides better solutions on larger, more difficult, instances. |
| |
Keywords: | slope scaling Lagrangean heuristic long-term memory multicommodity capacitated fixed-charge network design |
本文献已被 SpringerLink 等数据库收录! |
|