Article Preview
Top1. Introduction
Third party logistics (3PL) is more than a 150-billion-dollar sector within the U.S. that has been witnessing a steady growth rate exceeding 5.7% since 2010 (“3PL market analysis,” 2015). The growth in online shopping is expected to fuel this market further and has caused a revival of interest in finding better solutions to the large-scale, in-transit freight consolidation problem, which allows the 3PL to cut costs by using economies of scale and reduction in package count (Xiaomin 2017). For a 3PL provider, the consolidation problem requires determining what shipments to consolidate at an intermediate gateway or terminal versus what to ship directly to a customer such that the overall shipment costs are minimized while the delivery time windows are honored. This paper and the solutions herein are motivated by our involvement with a major 3PL provider. We studied their problem of in-transit consolidation of products being shipped from 
geographically disperse shippers to a single business customer via 
consolidation points. Each product has a predefined delivery time window that cannot be violated, and each product is shipped to the intermediate consolidation point (called gateway) before being shipped to the destination. The decision involves choosing which gateway should receive the products and whether to consolidate the shipments into larger containers before shipping them to their end destination.
Typically, a business or corporate customer that employs 3PL have standing orders from multiple suppliers for multiple products across a planning horizon, where each product has a prespecified shipment date and delivery time window. The 3PL providers pick up the products from the suppliers on given shipment dates and deliver to the customer within delivery time windows. All picked up products are first shipped to intermediate gateways before being forwarded to the customer. A 3PL company usually has more than one gateway that provides flexibility pertaining to shipment costs and consolidation options. The routing decisions therefore need to be made for two legs: from suppliers to gateways and from gateways to the final customer. The first leg decision involves assigning the shipment to a particular gateway and selection of the transportation mode. The consolidation-related decisions are made at the gateway. In the second leg, the carrier ships the products—either as consolidated shipments or as is so as to minimize shipment costs without violating the constraints set by the delivery time windows. When a shipment is not consolidated into a container, it is forwarded to the customer as an individual shipment, which is typically more expensive.
We formulated the in-transit freight consolidation problem just described as a mixed-integer programming (MIP) problem, and our key contribution is the development of a Benders decomposition-based solution approach that provides a significant scale-up in the performance of the solver. The decomposition replaces a large number of integer freight-consolidation variables by a small number of continuous variables that reduce the size of the problem in terms of both the number of variables and constraint without impacting the optimality. Using our approach, we can solve to optimality a large-scale case with more than 27.5 million variables and 9.2 million constraints.
The remaining paper is organized into the following sections. In section 2, we present a brief literature review on the freight consolidation problem. There are several useful research outputs reported in the literature on both the in-transit freight consolidation problem as well as Benders decomposition, and we point the reader to the relevant reviews. The proposed MIP model is presented in third section, and the Benders decomposition based reformulation of our model is presented in the fourth section. Finally, the fifth section provides a detailed case study elucidating the efficacy of the decomposition approach for solving large-scale, in-transit freight consolidation problem with the conclusions and potential extensions discussed in the last two sections.