Exact and heuristic methods for a full-load, multi-terminal, vehicle scheduling problem with backhauling and time windows

Abstract

The problem considered is the full-load pickup and delivery problem with time windows (PDPTW), and heterogeneous products and vehicles, where the assignment of pickup points to requests is not predetermined. The problem is first formulated as a 0-1 LP, then a hybrid algorithm is developed, which chooses dynamically between a Greedy heuristic and one based on Regret costs. A multi-level constructive heuristic that consists of three post-optimizers is presented. Two lower bounds are used to evaluate the performance of the proposed heuristics when tested on random instances and selected data from a construction company.

Keywords:

• distribution
• heuristics
• multi-depots
• full load

Acknowledgements

We thank EPSRC for a grant to the first author. We also thank both referees for their very useful comments on an earlier version of this paper.