Polynomial Time Algorithms for Transportation and Inventory Management in Serial Supply Chain with Multi-Module Capacitated Vehicles

Abstract

We study new generalizations of the classical capacitated lot-sizing problem with concave production (or transportation), holding, and subcontracting cost functions, in which the total capacity available in each time period is the sum of capacities of a subset of n heterogeneous modules (machines or vehicles). We refer to this class of problems as the Multi-module Capacitated Lot-Sizing Problem without and with Subcontracting, denoted by MCLS and MCLS-S, respectively. While these problems are NP-hard when n is part of the input and polynomially solvable for n = 1, the complexity status for fixed n ≥ 2 has remained open. We resolve this question by developing exact fixed-parameter tractable algorithms that solve MCLS and MCLS-S in O(T2n+3) time for any fixed n ≥ 2. Our results generalize the algorithm of Atamtürk and Hochbaum [Management Science 47(8):1081–1100, 2001] for the case n = 1. We further extend our framework to two important generalizations: (i) the lot-sizing problem with piecewise concave production costs (LS-PC-S), for which we propose an O(T2m+3) time algorithm, where m is the number of breakpoints; and (ii) a two-echelon multi-module lot-sizing problem, solved in O(T4n+4) time. Our LS-PC-S algorithm reduces the runtime of the dynamic programming approach of Koca et al. [INFORMS J. on Computing 26(4):767–779, 2014] by up to 93.6%, and our two-echelon results generalize those of van Hoesel et al. [Management Science 51(11):1706–1719, 2005] for the single-module case. Computational experiments demonstrate that our algorithms are both efficient and highly stable compared to Gurobi 9.1, including under parallel implementation. In addition, our results for MCLS-S establish the existence of a polynomial-time algorithm for optimizing a linear function over the n-mixing set, a significant generalization of the classical 1-mixing set. We also investigate single-item discrete multi-module capacitated lot-sizing problems without and with backlogging, where production in each period consists of binary multiples of module capacities. For fixed n ≥ 2, we develop exact fixed-parameter tractable algorithms that generalize the results of van Vyve (2007) for n = 1. These algorithms are embedded within a Lagrangian decomposition framework to solve the corresponding multi-item problems. Computational results show substantial improvements over Gurobi 9.0 in both performance and robustness. Finally, we study serial supply chain models in which goods are transported from a supplier to a warehouse and then to a retailer over a finite planning horizon. These problems fall under the class of two-echelon lot-sizing problems (2-ELS) with capacitated inbound and outbound transportation. We address an open question posed by van Hoesel, Romeijn, Morales, and Wagelmans (2005) concerning the existence of a polynomial-time algorithm for 2-ELS with a single capacitated vehicle in each echelon. We provide polynomial-time exact algorithms for this setting and three further generalizations involving multiple heterogeneous capacitated vehicles, thereby extending the results of Kaminsky and Simchi-Levi (2003) and Sargut and Romeijn (2007).