The Freight Transportation Network Scheduling Problem: An Integer Programming-Based Column Generation Algorithm

We consider the optimization problem of determining schedules for shipments on known paths within a freight transportation network in order to minimize vehicle transportation costs. We refer to this problem as the freight transportation network scheduling problem and present two mixed integer programming formulations of that problem. The first is based on the classical idea of a time-expanded network. The second formulation is based on sets of shipment consolidations. We show both analytically and computationally that the consolidation-based formulation is the superior of the two when all consolidations can be enumerated. However, we also show computationally that its enumerative nature renders it ineffective for instances with large numbers of shipments. Thus, we also present a column generation-based algorithm for solving the consolidation-based formulation that relies on solving relaxations that are integer programs. We demonstrate the superior performance of this algorithm with a computational study wherein we compare it against applications of state-of-the-art approaches from the literature. We also perform a detailed computational analysis of the performance of the algorithm in different settings. History: Accepted by Russel Bent, Area Editor for Network Optimization: Algorithms & Applications. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0435 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0435 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .