Relay Network Design with Capacity and Link-Imbalance Considerations: A Lagrangean Decomposition Algorithm and Analysis
针对卡车运输业司机短缺和高流动率问题，研究接力网络设计，引入链路容量和链路不平衡概念，提出拉格朗日分解算法求解混合整数规划模型，帮助减少司机离家时间并提高运营效率。
High driver turnover and driver shortage are costly problems in the truckload trucking industry. Extended on-the-road times and low quality of life with irregular schedules and low get-home rates for drivers are commonly attributed as the main culprits in both academic and industry literature. The use of a relay network on which the truckloads switch drivers during their transportation can potentially help reduce drivers’ away-from-home times and regularize their schedule without sacrificing the mileage accumulation on which their pay is determined. Relay network design involves the determination of the relay point (RP) locations, their interconnections, assignment of non-RP nodes to RPs, and the routes for truckloads. Recognizing the importance of considering operational realities such as empty mileage and driver availability along with limited resources, we introduce link capacity constraints and the concept of link imbalance in strategic relay network design. The use of link imbalance is motivated by the need to improve operational efficiency via increased ability to return drivers to their home bases and reduce empty backhauls. To solve our mixed-integer programming design model, we develop an efficient Lagrangean decomposition algorithm that can provide solutions to large-size problems with small optimality gaps within reasonable runtimes. We also present computational experiments on the algorithmic performance, trade-offs between imbalance and cost components, effects of capacity, and the relationship between link- and node-imbalance concepts. The online appendix is available at https://doi.org/10.1287/trsc.2016.0704 .