A Model for Multiperiod Route Planning and a Tabu Search Method for Daily Log Truck Scheduling
Independent thesis Basic level (professional degree)Student thesis
The transportation cost of logs from forest to customers is a large part of the overall cost for the Swedish forestry industry. Finding good routes from harvesting points to saw and pulp mills is a complex task, where the total number of feasible routes is extremely high. In this thesis we present two methods for log truck scheduling.
The first is to, from a given set of routes, find the most valuable subset that fulfils the customers demand. We use a model that is similar to the set partitioning problem and a method that is referred to as a composite pricing coupled with Branch and Bound. The composite pricing based method prices the routes (columns) and chooses the most valuable ones that are then added to the LP relaxation. Once an LP optimum is found, the Branch and Bound method is used to find an integer optimum solution. We have tested this on a case of realistic size.
The second method is a tabu search heuristic. Here, the purpose is to create efficient and qualitative routes from a given number of trips (referred to as predefined trips). From a start solution tabu search systematically generates new solutions. This method was tested on a small problem and on a five times larger problem to study how the size of the problem affected the result. It was also tested and compared on two cases in which the backhauling possibilities (i.e. instead of traveling empty the truck picks up another load on the return trip) had and had not been studied. The composite pricing based method and the tabu search method proved to be very useful for this kind of scheduling.
Place, publisher, year, edition, pages
Matematiska institutionen , 2004.
Mathematical optimization, systems theory, Composite Pricing, Forestry, Log Truck Scheduling, Multiperiod Route Planning, Optimization, Predefined Trips, Tabu Search, Transportation
IdentifiersURN: urn:nbn:se:liu:diva-2147ISRN: LITH-MAT-EX--04/01--SEOAI: oai:DiVA.org:liu-2147DiVA: diva2:19477