FURTHER RESULTS ON THE PROBABILISTIC TRAVELING SALESMAN PROBLEM

被引:62
作者
BERTSIMAS, D [1 ]
HOWELL, LH [1 ]
机构
[1] MIT,DEPT MATH,CAMBRIDGE,MA 02139
基金
美国国家科学基金会;
关键词
PROBABILISTIC TRAVELING SALESMAN PROBLEM; PROBABILISTIC ANALYSIS; COMBINATORIAL OPTIMIZATION; HEURISTICS;
D O I
10.1016/0377-2217(93)90145-D
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
In 1985, Jaillet introduced the probabilistic traveling salesman problem (PTSP), a variant of the classical TSP in which only a subset of the nodes may be present in any given instance of the problem. The goal is to find an a priori tour of minimal expected length, with the strategy of visiting the present nodes in a particular instance in the same order as they appear in the a priori tour. In this paper we reexamine the PTSP using a variety of theoretical and computational approaches. We sharpen the best known bounds for the PTSP, derive several asymptotic relations, and compare from various viewpoints the PTSP with the re-optimization strategy, i.e., finding an optimal tour in every problem instance. When a Euclidean metric is used and the nodes are uniformly distributed in the unit square, a heuristic for the PTSP is shown to be very close to the re-optimization strategy. We examine some PTSP heuristics with provable worst-case performance, and address the question of finding constant-guarantee heuristics. Implementations of various heuristics, some based on sorting and some on local optimality, permit us to discuss the qualitative and quantitative properties of computational problems with up to 5000 nodes.
引用
收藏
页码:68 / 95
页数:28
相关论文
共 50 条
  • [41] Traveling salesman problem with backend information processing
    Doganbas, Merve
    Shin, Hayong
    [J]. OPERATIONS RESEARCH LETTERS, 2024, 57
  • [42] Improving local search for the traveling salesman problem
    Misevicius, Alfonsas
    Ostreika, Armantas
    Simaitis, Antanas
    Zilevicius, Vilius
    [J]. INFORMATION TECHNOLOGY AND CONTROL, 2007, 36 (02): : 187 - 195
  • [43] A linear programming formulation of the Traveling Salesman Problem
    Diaby, Moustapha
    [J]. PROCEEDINGS OF THE 11TH WSEAS INTERNATIONAL CONFERENCE ON APPLIED MATHEMATICS (MATH '07), 2007, : 97 - +
  • [44] A fresh look at the Traveling Salesman Problem with a Center
    Luo, Yuchen
    Golden, Bruce
    Poikonen, Stefan
    Zhang, Rui
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2022, 143
  • [45] A heuristic for the pickup and delivery traveling salesman problem
    Renaud, J
    Boctor, FF
    Ouenniche, J
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2000, 27 (09) : 905 - 916
  • [46] Heuristics for the traveling salesman problem with pickup and delivery
    Gendreau, M
    Laporte, G
    Vigo, D
    [J]. COMPUTERS & OPERATIONS RESEARCH, 1999, 26 (07) : 699 - 714
  • [47] Microcanonical optimization applied to the traveling salesman problem
    Linhares, A
    Torreao, JRA
    [J]. INTERNATIONAL JOURNAL OF MODERN PHYSICS C, 1998, 9 (01): : 133 - 146
  • [48] The angular-metric traveling salesman problem
    Aggarwal, A
    Coppersmith, D
    Khanna, S
    Motwani, R
    Schieber, B
    [J]. SIAM JOURNAL ON COMPUTING, 2000, 29 (03) : 697 - 711
  • [49] A BENCHMARK FOR QUANTUM OPTIMIZATION: THE TRAVELING SALESMAN PROBLEM
    Warren, Richard H.
    [J]. QUANTUM INFORMATION & COMPUTATION, 2021, 21 (7-8) : 557 - 562
  • [50] GatedGCN with GraphSage to Solve Traveling Salesman Problem
    Yang, Hua
    [J]. ARTIFICIAL NEURAL NETWORKS AND MACHINE LEARNING, ICANN 2023, PT IV, 2023, 14257 : 377 - 387