Premium
A solution approach for log truck scheduling based on composite pricing and branch and bound
Author(s) -
Palmgren Myrna,
Rönnqvist Mikael,
Värbrand Peter
Publication year - 2003
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/1475-3995.00420
Subject(s) - truck , column generation , scheduling (production processes) , computer science , mathematical optimization , branch and price , vehicle routing problem , integer programming , job shop scheduling , operations research , branch and bound , routing (electronic design automation) , mathematics , engineering , automotive engineering , computer network
The logging truck scheduling problem is one of the most complex routing problems where both pick‐up and delivery operations are included. It consists in finding one feasible route for each vehicle in order to satisfy the demands of the customers and in such a way that the total transport cost is minimized. We use a mathematical formulation of the log truck scheduling problem where each column represents a feasible route. We generate a large pool of columns based on solving a transportation problem. Then we apply a composite pricing algorithm, which mainly consists of pricing the pool of columns and maintain an active set of these, for solving the LP relaxed model. A branch and price approach is used to obtain integer solutions in which we apply composite pricing to generate new columns. Numerical results from case studies at Swedish forestry companies are presented.