TRUCK BACKHAULING ON NETWORKS WITH MANY TERMINALS

This paper develops a model to help coordinate backhauling between many (more than two) terminals. Two mathematical programming formulations of this backhauling problem are given. One formulates it as a 'matching' problem that leads to a heuristic for solving the very large backhauling problems that arise in practice. Using Lagrangian relaxation, the other formulation allows a very tight bound on the optimal solution to be calculated. The quality of the heuristic solution can be determined by comparison with this bound. A large scale example based on actual truck shipments demonstrates how the model might be used in planning truck backhauling. For this example, the heuristic yields a solution within 1% of optimal.