The Travelling Salesman Problem with Precedence Constraints

The Travelling Salesman Problem with Precedence Constraints (TSP-PC) is the usual Travelling Salesman Problem with the restrictions that the salesman should start from a prescribed node (i.e., a headquarters) and each admissible tour is to satisfy k precedence relations denoted by ir < jr; r=1,2,...

Full description

Saved in:
Bibliographic Details
Published in:Opsearch 2001-06, Vol.38 (3), p.299-318
Main Authors: Ahmed, Zakir Hussain, Pandit, S. N. Narahari
Format: Article
Language:English
Subjects:
Genetic algorithms
Job shops
Operations research
Precedence constraints
Production scheduling
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Travelling Salesman Problem with Precedence Constraints (TSP-PC) is the usual Travelling Salesman Problem with the restrictions that the salesman should start from a prescribed node (i.e., a headquarters) and each admissible tour is to satisfy k precedence relations denoted by ir < jr; r=1,2,...,k. That is the node jr should not be visited unless node ir is already visited. This problem is NP-hard and arises in practical transportation and sequencing problems. In this paper, a lexisearch algorithm has been developed for obtaining exact optimal solution. Also, simple and hybrid genetic algorithms have been developed for obtaining heuristically optimal solution to the problem. The efficiency of the genetic algorithms to the TSP-PC as against lexi-search approach has been examined for a variety of randomly generated test problems.
ISSN:0030-3887
0975-0320
DOI:10.1007/BF03398638