Article ID: | iaor200942210 |
Country: | United States |
Volume: | 56 |
Issue: | 5 |
Start Page Number: | 1264 |
End Page Number: | 1277 |
Publication Date: | Sep 2008 |
Journal: | Operations Research |
Authors: | Song Haiqing, Hsu Vernon N, Cheung Raymond K |
We study a problem faced by a third–party logistics provider (3PL) who needs to coordinate shipments between suppliers and customers through a consolidation center in a distribution network. Products from a supplier have one release time and are consolidated into a single shipment to the consolidation center. At the center, products to the same destination are also consolidated into a single shipment, and the consolidation time can be as early as possible or as late as possible, depending on the customer requirement and cost structure. The 3PL needs to determine the pickup times from the suppliers, delivery times to the customers, and the transportation options while considering product release times, latest arrival times, different consolidation policies, and the transportation and storage costs involved. In this paper, we formulate this problem as a nonlinear optimization problem, show it is an NP–hard problem, and develop a dual–based solution method for the general problem. Utilizing the problem's special structure, we show that the Lagrangian dual of the general problem can be solved optimally as a linear program, thus allowing us to accelerate the computation of a lower bound to the optimal objective function value. The experimental results show that the dual–based algorithm provides solutions with objective function values, which are on average within 3.24% of optimality. We also consider a version of the problem where each customer orders products from all suppliers, for which we develop a polynomial–time algorithm.