Change search
ReferencesLink to record
Permanent link

Direct link
The use of abstractions to solve large scheduling problems
Number of Authors: 1
2000 (English)Report (Refereed)
Abstract [en]

This thesis investigates how abstractions can be used to improve performance in a railroad scheduling system that uses constraint programming. The idea behind abstractions is to solve a large problem in smaller parts and extract information from these parts. That information can then be used when solving the entire problem. Two different types of abstractions are introduced: Relations and Net abstractions. The use of relations builds orders between trips or parts of trips. These orders can be used to reduce the search necessary to find a solution to the scheduling problem. When using net abstraction, the problem is solved in an abstract search space, where it is easier to solve. The solution computed in the abstract search space is then used to reduce search when solving the problem in the original space. It is shown that these two types of abstraction can improve performance in problems with various settings. Relations can successfully be used in problems that have few solutions and are hard to solve. Net abstraction on the other hand works best for problems with many valid solutions.

Place, publisher, year, edition, pages
Kista, Sweden: Swedish Institute of Computer Science , 2000, 1. , 64 p.
SICS Technical Report, ISSN 1100-3154 ; 2000:13
Keyword [en]
Train planning, Hierarchical planning, Vehicle routing and scheduling, Constraint programming, Formal abstraction
National Category
Computer and Information Science
URN: urn:nbn:se:ri:diva-22013OAI: diva2:1041555
Available from: 2016-10-31 Created: 2016-10-31

Open Access in DiVA

fulltext(319 kB)7 downloads
File information
File name FULLTEXT01.pdfFile size 319 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 7 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 3 hits
ReferencesLink to record
Permanent link

Direct link