Optimality Conditions to the Acyclic Travelling Salesman Problem

被引：0
作者：
O. E. Charles-Owaba
机构：
[1] University of Ibadan,Department of Industrial and Production Engineering
来源：
OPSEARCH | 2001年 / 38卷 / 5期
关键词：
Travelling Salesman Problem; Element Elimination; Optimality Condition; Lower bound;
D O I：
10.1007/BF03398656
中图分类号：
学科分类号：
摘要：
This paper views an optimal solution (tour) of the n-station acyclic Travelling Selesman problem as consisting of n−1 elements of the distance matrix. Considering lower bound for elements a theoretical basis for identifying and eliminating non-optimal elements was suggested. This concept of element elimination was then used to define optimality conditions. Finally, an iterative algorithm which converges at the optimal sequence, was proposed and applied to some numerical examples.
引用
收藏
页码：531 / 542
页数：11
相关论文
共 32 条
[1]  
Archelus FJ(1983)On n/F set-up Time Dependent problems Engineering optimization 7 59-67
[2]  
Chandra R(1989)Large Travelling Salesman Problems. Arising From Experiments in X-ray Chrystallography; A Preliminary Report on Computation Operations Research Letters 8 125-128
[3]  
Bland R G(1997)TRAVEL: An Interactive TSP Package for IBM Personal Computer Operations Research Letters 63 141-144
[4]  
Shallcross D F(1993)Minimizing Total Completion Time On a Batch Processing Machine with Job Families Operations Research Letters 13 61-65
[5]  
Bond S C(1996)Genetic Algorithms and Travelling Salesman Problems European Journal of Operations Research 93 490-510
[6]  
Pulley Blank W R(1996)Modelling set-up Times, Process Batches and Transfer Batches Using Activity Network Logic European Journal of Operational Research 89 355-365
[7]  
Comuejols G(1983)Set-up Time in Cyclic and Acyclic Group Scheduling Systems International Journal of Production Research 21 63-73
[8]  
Chandru V(1965)Three Heuristic Rules for Sequencing Jobs to a Single Production Facility Management Science 11 B-166–B-176
[9]  
Lee C(1963)An Algorithm for the Travelling Salesman Problem Operations Research Journal 11 972-989
[10]  
Uzsoy R(1993)A Modified Lin-Kemighan Travelling Salesman Heuristic Operations Research letters 13 127-132
1234