Author:
Palmgren, Myrna (Linköping University, Department of Mathematics)
Title:
Optimal Truck Scheduling: Mathematical Modeling and Solution by the Column Generation Principle
Department:
Linköping University, Department of Mathematics
Publication type:
Doctoral thesis, monograph (Other scientific)
Language:
English
Publisher:
Matematiska institutionen
Pages:
120
Series:
Linköping Studies in Science and Technology. Dissertations,ISSN 0345-7524;967
Year of publ.:
2005
URI:
urn:nbn:se:liu:diva-3590
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-3590
ISBN:
91-85457-17-5
Subject category:
MATHEMATICS
Keywords(en) :
optimisation, pickup and delivery problem, transportation, scheduling, column generation, integer programming
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.
Public defence:
2005-09-16, BL32, Hus B, Campus Valla, Linköping, 10:15
Degree:
Doctor of Philosophy (PhD)
Supervisor:
Larsson, Torbjörn, (Linköping University, Department of Mathematics)
Opponent:
Kohl, Niklas (DSB, Planlægning - IT og Optimering, Köpenhamn)
Available from:
2005-09-02
http://ifile.it/irslg5j/266007___mathematical_modeling_and_solution_by_the_column_generation_principle.pdf
