SENSITIVITY ANALYSIS FOR SYMMETRICAL 2-PERIPATETIC SALESMAN PROBLEMS

作     者：DEKORT, JBJM 

作者机构：Insttitute of Actuarial Science and Econometrics Operations Research Group Faculty of Economics and Econometrics University of Amsterdam Amsterdam Netherlands 

出 版 物：《OPERATIONS RESEARCH LETTERS》 (运筹学快报)

年 卷 期：1993年第13卷第2期

页      面：79-84页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：GRAPHS SENSITIVITY ANALYSIS TRAVELING SALESMAN PROBLEM TREE ALGORITHMS 

摘      要：A greedy approach can be applied to find 2 edge-disjoint 1-trees or spanning trees (if they exist) of minimum total length in a graph with n vertices and m edges. A greedy algorithm to solve the tree problem contains a routine that tests whether 2 edge-disjoint forests can be augmented with a given edge. Two test routines are discussed with different worst-case running times. The most efficient one is utilized to derive in O(m log m + n2) operations a lower bound solution to the 2-Peripatetic Salesman Problem (2-PSP), which requires 2 edge-disjoint Hamiltonian cycles of minimum total length. Then the other test routine executes in O(n2) operations a sensitivity analysis for all relevant edges. Computational results illustrate the impact of the sensitivity analysis.