AN EXACT METHOD FOR SOLVING THE BI-OBJECTIVE MINIMUM DIAMETER-COST SPANNING TREE PROBLEM

被引：7

作者：

De Sousa, Ernando Gomes ^{[1
]}

Santos, Andrea Cynthia ^{[2
]}

Aloise, Dario Jose ^{[1
]}

机构：

[1] Univ Estado Rio Grande do Norte, BR-59610210 Mossoro, RN, Brazil

[2] Univ Technol Troyes, ICD LOSI, CS 42060, F-10004 Troyes, France

来源：

RAIRO-OPERATIONS RESEARCH | 2015年 / 49卷 / 01期

关键词：

Spanning trees; multi-objective optimization; Parallel Partitioning Method; FORMULATION; ALGORITHM; PPM;

D O I：

10.1051/ro/2014029

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this work, we propose a procedure to compute Pareto-optimal fronts for the bi-objective Minimum Diameter-Cost Spanning Tree problem (bi-MDCST). The bi-MDCST aims at finding spanning trees with minimum total cost and minimum diameter. Strategic decision problems for high-speed trains infrastructure, as well as tactical and operational optimization problems for network design and transportation can be modeled as bi-MDCST. The proposed exact procedure makes use of components from the multi-objective exact method Parallel Partitioning Method, and Pareto-optimal fronts have been computed for two benchmark instances from the literature. To the best of our knowledge, there are no works dedicated to providing Pareto-optimal fronts for the bi-MDCST.

引用

页码：143 / 160

页数：18

共 35 条

[1]

[Anonymous], LECT NOTES COMPUT SC

[2]

[Anonymous], TRANSPORTATION SCI

[3]

[Anonymous], INT J COMPUT APPL

[4]

[Anonymous], 1994, AUST J COMB

[5]

Arroyo JEC, 2008, ANN OPER RES, V159, P125, DOI [10.1007/s10479-007-0263-4, 10.1007/S10479-007-0263-4]

[6] An exact ε-constraint method for bi-objective combinatorial optimization problems: Application to the Traveling Salesman Problem with Profits [J].

Berube, Jean-Francois ;

Gendreau, Michel ;

Potvin, Jean-Yves .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 194 (01) :39-50

[7] A survey of recent developments in multiobjective optimization [J].

Chinchuluun, Altannar ;

Pardalos, Panos M. .

ANNALS OF OPERATIONS RESEARCH, 2007, 154 (01) :29-50

[8]

Cor men T. H., 2009, Introduction to Algorithms, V3rd

[9]

Deo N, 2000, LECT NOTES COMPUT SC, V1767, P17

[10] IMPROVEMENTS AND EXTENSIONS TO THE MILLER-TUCKER-ZEMLIN SUBTOUR ELIMINATION CONSTRAINTS [J].

DESROCHERS, M ;

LAPORTE, G .

OPERATIONS RESEARCH LETTERS, 1991, 10 (01) :27-36

← 1 2 3 4 →