Digitala Vetenskapliga Arkivet

Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The use of abstractions to solve large scheduling problems
RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
2000 (English)Report (Other academic)
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. , p. 64
Series
SICS Technical Report, ISSN 1100-3154 ; T2000:13
Keywords [en]
Train planning, Hierarchical planning, Vehicle routing and scheduling, Constraint programming, Formal abstraction
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:ri:diva-22013OAI: oai:DiVA.org:ri-22013DiVA, id: diva2:1041555
Available from: 2016-10-31 Created: 2016-10-31 Last updated: 2021-12-16Bibliographically approved

Open Access in DiVA

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

By organisation
SICS
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 145 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

urn-nbn

Altmetric score

urn-nbn
Total: 33 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf