An efficient two-phase exact algorithm for the automated truck freight transportation problem

- An automated truck freight transportation planning problem via lane reservation is studied.
- Improved formulation is provided and several special cases of the problem are investigated.
- An efficient two-phase exact algorithm based on problem properties is developed.
- Computational results confirm the efficiency of the proposed model and algorithm.

A recent study has developed an integer linear program and an exact algorithm for the automated truck transportation freight problem with lane reservation. However, due to its NP-hard nature, their proposed method becomes difficult to solve large-size problems within acceptable time. In this paper, we firstly present an improved integer linear program by adding valid inequalities and identify that its several special cases are classical combinatorial optimization problems. Based on analyzed properties, a new efficient two-phase exact algorithm is developed. Computational results on benchmark and new larger-size instances with up to 700 nodes and 55 tasks show that the new algorithm outperforms very favorably the state-of-the-art one.