An efficient algorithm for the Steiner Tree Problem with revenue,bottleneck and hop objective functions |
| |
| Authors: | Leizer Lima Pinto Gilbert Laporte |
| |
| Affiliation: | 1. Department of Systems Engineering and Computer Science, COPPE/UFRJ – Federal University of Rio de Janeiro, Brazil;2. Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montreal, Que., Canada H3C 3J7;3. Canada Research Chair in Distribution Management, HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montréal, Canada H3T 2A7 |
| |
| Abstract: | This paper considers a tricriteria Steiner Tree Problem arising in the design of telecommunication networks. The objective functions consist of maximizing the revenue and of minimizing the maximal distance between each pair of interconnected nodes, as well as the maximal number of arcs between the root and each node. A polynomial algorithm is developed for the generation of a minimal complete set of Pareto-optimal Steiner trees. Optimality proofs are given and computational experience on a set of randomly generated problems is reported. |
| |
| Keywords: | Steiner tree Multi-objective problem Pareto-optimal solution Bottleneck function |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
