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

Direct link
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.
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
URN: urn:nbn:se:liu:diva-3590ISBN: 91-85457-17-5OAI: diva2:20408
Public defence
2005-09-16, BL32, Hus B, Campus Valla, Linköping, 10:15 (English)
Available from: 2005-09-02 Created: 2005-09-02 Last updated: 2013-08-30

Open Access in DiVA

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

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 9302 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: 2008 hits
ReferencesLink to record
Permanent link

Direct link