liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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
Optimal Truck Scheduling: Mathematical Modeling and Solution by the Column Generation Principle
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
2005 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

We consider the daily transportation problem in forestry which arises when transporting logs from forest sites to customers such as sawmills and pulp and paper mills. Each customer requires a specific amount of a certain assortment, and the deliveries to the customers can be made within time intervals, known as time windows. Further, there are a number of supply points, each with a certain assortment, and a number of vehicles of a given capacity, to be used for transport.

The log truck scheduling problem consists of finding a set of minimal costs routes, one for each vehicle, such that the customers’ demands are satisfied without exceeding the supplies available at the supplies. Each route has to satisfy a number of constraints concerning time windows, truck capacity, timetable of the driver, lunch breaks, et cetera. The model used to describe the log truck scheduling problem is based on the route concept, and each variable, or column, represents one feasible route. Since the number of feasible routes is huge, we work only with restricted versions of this problem, which are similar to restricted master problems in a Dantzig-Wolfe decomposition scheme.

We use three solution methods based on the column generation principle, together with a pool strategy which allows us to deal with the feasible routes outside the restricted master problem. The three methods proposed have a common structure; they use branch-andprice together with a column generator, followed by branch-and-bound. The column generators in the three methods differ. In the first method, the subproblem is based on a cluster-first-route-second strategy. The column generator in the second method involves solving a constrained shortest path problem, and finally, the third method builds on a repeated generation of clusters and routes.

The three methods are tested on real cases from Swedish forestry companies, and the third method has been adapted to a computerised system that utilises the Swedish national road data base, for computing travelling distances. The results obtained show that the optimisation methods succeed in finding significantly better solutions than those obtained by manual planning, and in a reasonable computing time.

Place, publisher, year, edition, pages
Matematiska institutionen , 2005. , 120 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 967
Keyword [en]
optimisation, pickup and delivery problem, transportation, scheduling, column generation, integer programming
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-3590ISBN: 91-85457-17-5 (print)OAI: oai:DiVA.org:liu-3590DiVA: diva2:20408
Public defence
2005-09-16, BL32, Hus B, Campus Valla, Linköping, 10:15 (English)
Opponent
Supervisors
Available from: 2005-09-02 Created: 2005-09-02 Last updated: 2013-08-30

Open Access in DiVA

fulltext(862 kB)11041 downloads
File information
File name FULLTEXT01.pdfFile size 862 kBChecksum SHA-1
9b631682461208198f64771e815f48494e16bc56e3e55c5d1e6ce39ba2b621f3353b5499
Type fulltextMimetype application/pdf

Authority records BETA

Palmgren, Myrna

Search in DiVA

By author/editor
Palmgren, Myrna
By organisation
Optimization The Institute of Technology
Mathematics

Search outside of DiVA

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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 2046 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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