Abstract
In-transit merging operations involve efficient scheduling of the delivery of shipments from a list of origin points to one or more destinations. It focuses on optimizing the way that individual loads are aggregated so that total transportation and handling costs are minimized, while ensuring that each of the delivery-time requirements are met. The success of in-transit merging operations is critical for competitive advantage for third party logistics (3PL) companies who compete in transportation and handling costs. An effective consolidation strategy helps carriers offer better prices for their customers without hampering their profits. One important factor in transshipment planning is whether the shipment orders can be broken into pieces that are then scheduled separately in terms of both routing and timing. In such cases, the shipments are referred to as “divisible” shipments and typically allow for more consolidation opportunities. In other cases, the shipments are “nondivisible,” where the carrier is required to transport a shipment order as one parcel throughout the network. In this study, we consider both cases, and propose models and efficient solution methods for the in-transit freight consolidation problems, which are typically quite difficult to solve optimally, due to computational complexity and size. Motivated by our collaborations with a major global 3PL company, we tackle three versions of the general problem that differ from each other in cost structure, in addition to the shipments’ divisibility. In all cases, we consider a three-echelon network that involves suppliers, consolidation points (referred to as terminals or gateways), and the customer. For each version of the problem we develop a mixed-integer programming (MIP) formulation that involves transshipments of multiple products using multiple transportation modes over a planning horizon. The first version tackles the problem with divisible shipments, where we propose a redesigned Benders decomposition approach that significantly speeds up the computational performance. In the second part, we modify our model for nondivisible shipments. With the understanding that Benders decomposition does not provide the same effect for the nondivisible case, we develop a novel decomposition based on LP relaxations and valid cuts. In the third part, we introduce cost breaks for shipment amounts, which result in piecewise linear objective function. We show that our decomposition method for this case always leads to optimality. We demonstrate the computational competence of our solution methods using real-life case studies. We also conduct sensitivity analysis to investigate the impact of problem parameters on computational performance.