ERA

Download the full-sized PDF of Solving the Sequential Ordering Problem with Automatically Generated Lower BoundsDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3XP6V500

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

Solving the Sequential Ordering Problem with Automatically Generated Lower Bounds Open Access

Descriptions

Author or creator
Hernadvolgyi, Istvan
Additional contributors
Subject/Keyword
Asymmetric Traveling Salesman Problem
Sequential Ordering Problem
Type of item
Computing Science Technical Report
Computing science technical report ID
TR03-16
Language
English
Place
Time
Description
Technical report TR03-16. The Sequential Ordering Problem (SOP) is a version of the Asymmetric Traveling Salesman Problem (ATSP) where precedence constraints on the vertices must be observed. The SOP has many real life applications and it has proved to be a challenge as there are SOPs of order 40-50 vertices which have not yet been solved optimally with significant computational effort. We use a novel branch&bound search algorithm with lower bounds obtained from homomorphic abstractions of the original state space. Our method is asymptotically optimal. In one instance, it has proved a solution value to be optimal for an open problem while it also has matched best known solutions quickly for many unsolved problems from the TSPLIB. Our method of deriving lower bounds is general and applies to other variants of constrained ATSPs as well.
Date created
2003
DOI
doi:10.7939/R3XP6V500
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-29T18:32:40.514+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 1042064
Last modified: 2015:10:12 16:52:20-06:00
Filename: TR03-16.pdf
Original checksum: 63cde9e6342265522ebfbb14744ea726
Well formed: true
Valid: true
Page count: 30
Activity of users you follow
User Activity Date