Pyramidal tours and multiple objectives

被引：7

作者：

Ozpeynirci, Ozgur ^{[1
]}

Koksalan, Murat ^{[2
]}

机构：

[1] Izmir Univ Econ, Dept Logist Management, TR-35330 Izmir, Turkey

[2] Middle E Tech Univ, Dept Ind Engn, TR-06531 Ankara, Turkey

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 2010年 / 48卷 / 04期

关键词：

Keywords Pyramidal tour; Polynomially solvable; Multiple objectives; TSP; BTSP; TRAVELING SALESMAN PROBLEM; TSP; VAN;

D O I：

10.1007/s10898-009-9505-0

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this study, we work on the traveling salesperson problems and bottleneck traveling salesperson problems that have special matrix structures and lead to polynomially solvable cases. We extend the problems to multiple objectives and investigate the properties of the nondominated points. We develop a pseudo-polynomial time algorithm to find a nondominated point for any number of objectives. Finally, we propose an approach to generate all nondominated points for the biobjective case.

引用

页码：569 / 582

页数：14

共 16 条

[1] BICRITERIA TRANSPORTATION PROBLEM
ANEJA, YP
NAIR, KPK
[J]. MANAGEMENT SCIENCE, 1979, 25 (01) : 73 - 78
[2] A new asymmetric pyramidally solvable class of the traveling salesman problem
Baki, Mohammed Fazle
[J]. OPERATIONS RESEARCH LETTERS, 2006, 34 (06) : 613 - 620
[3] Perspectives of Monge properties in optimization
Burkard, RE
Klinz, B
Rudolf, R
[J]. DISCRETE APPLIED MATHEMATICS, 1996, 70 (02) : 95 - 161
[4] On the Euclidean TSP with a permuted Van der Veen matrix
Burkard, RE
Deineko, VG
[J]. INFORMATION PROCESSING LETTERS, 2004, 91 (06) : 259 - 262
[5] EFFICIENTLY SOLVABLE SPECIAL CASES OF BOTTLENECK TRAVELING SALESMAN PROBLEMS
BURKARD, RE
SANDHOLZER, W
[J]. DISCRETE APPLIED MATHEMATICS, 1991, 32 (01) : 61 - 76
[6] Well-solvable special cases of the traveling salesman problem: A survey
Burkard, RE
Deineko, VG
Van Dal, R
Van der Veen, JAA
Woeginger, GJ
[J]. SIAM REVIEW, 1998, 40 (03) : 496 - 546
[7] Ehrgott M., 2002, Multiobjective Combinatorial OptimizationTheory, Methodology, and Applications, P369, DOI [10.1007/b101915, DOI 10.1007/B101915]
[8] Gilmore R. C., 1985, TRAVELING SALESMAN P, P87
[9] Gutin G., 2002, COMB OPT (SER), P223
[10] Kabadi S., 2002, COMB OPT (SER), P489

← 1 2 →