Strategic Design and Analysis of a Relay Network in Truckload Transportation

The truckload industry in the US faces a serious and chronic problem of high driver turnover rate -- typically more than 100% --with staggering associated costs. Among the major causes of this problem are extended on-the-road times where drivers handle several truckload pick-up and deliveries successively, non-regular schedules and get-home rates, and low utilization, i.e., less mileage/unit-time per driver, which leads to low pay.

We consider the strategic design of a relay network which may potentially help to alleviate this problem by providing an efficient underlying network that facilitates an assignment of drivers to home-bases and generation of more predictable schedules with continuity and higher get-home rates. In relay network design, we are interested in determining a number of relay point locations, assigning network nodes to these relay points (i.e., defining domiciles), and determining the actual route (from the origin to the destination) for each truckload in the network. In doing so, we explicitly consider driver tour lengths, load imbalance at relay points, and the percentage circuity constraints.

We develop an efficient Benders decomposition based algorithm that is significantly enhanced via strengthened Benders cuts, cut disaggregation schemes, heuristics for improved upper bounds, and surrogate constraints. Our approach provides the ability to solve large size instances within reasonable solution times and very small optimality gaps as we illustrate with an extensive computational study. Furthermore, in our experiments, we also examine the effects of changes in the problem parameters on the performance of solution algorithm. Finally, we provide analysis of various performance measures obtained via a relay network and alternative multi-zone and point-to-point dispatching methods.