Solving the traveling tournament problem with iterative-deepening A*

Show simple item record

dc.contributor.author Uthus, DC en
dc.contributor.author Riddle, Patricia en
dc.contributor.author Guesgen, Hans en
dc.date.accessioned 2012-03-14T00:36:48Z en
dc.date.issued 2012 en
dc.identifier.citation Journal of Scheduling 15(5):601-614 en
dc.identifier.issn 1094-6136 en
dc.identifier.uri http://hdl.handle.net/2292/14292 en
dc.description.abstract This work presents an iterative-deepening A∗ (IDA∗) based approach to the traveling tournament problem (TTP). The TTP is a combinatorial optimization problem which abstracts the Major League Baseball schedule. IDA∗ is able to find optimal solutions to this problem, with performance improvements coming from the incorporation of various past concepts including disjoint pattern databases, symmetry breaking, and parallelization along with new ideas of subtree skipping, forced deepening, and elite paths to help to reduce the search space. The results of this work show that an IDA∗ based approach can find known optimal solutions to most TTP instances much faster than past approaches. More importantly, it has been able to optimally solve two larger instances that have been unsolved since the problem’s introduction in 2001. In addition, a new problem set called GALAXY is introduced, using a 3D space to create a challenging problem set. en
dc.publisher Springer en
dc.relation.ispartofseries Journal of Scheduling en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. Details obtained from http://www.sherpa.ac.uk/romeo/issn/1094-6136/ en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.title Solving the traveling tournament problem with iterative-deepening A* en
dc.type Journal Article en
dc.identifier.doi 10.1007/s10951-011-0237-x en
pubs.begin-page 1 en
dc.rights.holder Copyright: Springer en
pubs.end-page 14 en
dc.rights.accessrights http://purl.org/eprint/accessRights/RestrictedAccess en
pubs.subtype Article en
pubs.elements-id 210615 en
pubs.org-id Science en
pubs.org-id School of Computer Science en
dc.identifier.eissn 1099-1425 en
pubs.record-created-at-source-date 2012-02-21 en


Files in this item

There are no files associated with this item.

Find Full text

This item appears in the following Collection(s)

Show simple item record

Share

Search ResearchSpace


Browse

Statistics