A solution approach for log truck scheduling based on composite pricing and branch and bound

The log 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 a fleet 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 and constant branching. Numerical results from case studies at Swedish forestry companies are presented.