Improved convergent heuristics for the 0‐1 multidimensional knapsack problem

This study addresses the problem of scheduling the daily assignment of available trucks for delivery of forest products required at different destinations. The products are logs of various types depending on their point of origin, and are defined in terms of length and diameter. Their destinations include sawmills, pulp mills, and other plants, and ports for export abroad. They are available for pickup and delivery by trucks within a previously defined road network during a working day. The trucks' trip times and load capacities are known. An integer linear programming model is developed for minimizing the costs associated with the daily truck transport operations that satisfy each destination's product demand. The model is based on column generation, each column representing a given truck's trip schedule for a working day feasible for that vehicle. The linear relaxation of the model is solved by dynamically generating columns that are attractive for incorporation and then solving the integer model constructed with all the columns so generated. This approach is then applied to instances whose size and degree of difficulty are similar to those actually encountered in the Chilean forest industry. In every case the linear relaxation optimum is 3% below the integer solution, with execution times low enough to be useful in real‐world applications.