{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/143005"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/143005","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"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).","abstract_html":"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).","abstract_has_math":false,"creators":["Kulkarni, Kartik Giridhar"],"institution":"Virginia Tech","degree_name":"Doctor of Philosophy","degree_level":"doctoral","degree_discipline":"Industrial and Systems Engineering","degree_department":"Industrial and Systems Engineering","school":null,"contributors":[],"advisors":[],"committee_chairs":["Bansal, Manish"],"committee_members":["Ellis, Kimberly P.","Murali, T. M.","Sarin, Subhash C."],"year":2026,"date_issued":"2026-04-14","date_published":"2026-04-14","updated_at":"2026-07-24T05:56:39Z","subjects":["polynomial algorithms","lot-sizing"],"languages":["en"],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["vt_gsexam:46069"],"render_values":[{"text":"vt_gsexam:46069","href":null,"code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/10919/143005","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeechair","label":"Committee Chair","values":["Bansal, Manish"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Ellis, Kimberly P.","Murali, T. M.","Sarin, Subhash C."]},{"key":"dc:contributor.department","label":"Department","values":["Industrial and Systems Engineering"]},{"key":"dc:creator","label":"Author","values":["Kulkarni, Kartik Giridhar"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2026-04-15T08:00:16Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2026-04-15T08:00:16Z"]},{"key":"dc:date.issued","label":"Date","values":["2026-04-14"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial and Systems Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["polynomial algorithms","lot-sizing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["vt_gsexam:46069"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10919/143005"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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)."]},{"key":"dc:description.abstractgeneral","label":"General Abstract","values":["Many planning problems in manufacturing and supply chains involve deciding how much to produce, transport, or store over time under limited capacity. In practice, this capacity often comes from multiple heterogeneous resources, such as machines in a factory or vehicles in a transportation fleet, each with different capabilities and costs. Coordinating these resources efficiently is particularly challenging when costs exhibit economies of scale and decisions are coupled over time. In this dissertation, we study new generalizations of the classical capacitated lot-sizing problem in which the available capacity in each period is generated by a collection of heterogeneous modules (machines or vehicles). We show that, although these problems are NP-hard in general, they become tractable when the number of modules is fixed. Specifically, we develop exact fixed-parameter tractable algorithms that solve these problems in polynomial time for any fixed number of modules, thereby resolving a long-standing open question in the literature. We also extend this research in several important directions. First, we consider models with piecewise concave cost functions that capture economies of scale and develop improved dynamic programming algorithms with significantly reduced computational complexity. Second, we study multi-echelon supply chain settings, where goods move from suppliers to warehouses and then to retailers under capacity constraints at each stage. For these problems, we provide new polynomial-time exact algorithms, generalizing several classical results that were previously limited to single-resource settings. To evaluate practical performance, we implement our algorithms and compare them with state-of-the-art commercial solvers. The computational results show that our methods are not only theoretically efficient but also highly competitive in practice, often outperforming commercial software in both speed and robustness."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Doctor of Philosophy"]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["ETD"]},{"key":"dc:title","label":"Title","values":["Polynomial Time Algorithms for Transportation and Inventory Management in Serial Supply Chain with Multi-Module Capacitated Vehicles"]}]}],"canonical_facts":{"dc:contributor.committeechair":["Bansal, Manish"],"dc:contributor.committeemember":["Ellis, Kimberly P.","Murali, T. M.","Sarin, Subhash C."],"dc:contributor.department":["Industrial and Systems Engineering"],"dc:creator":["Kulkarni, Kartik Giridhar"],"dc:date.accessioned":["2026-04-15T08:00:16Z"],"dc:date.available":["2026-04-15T08:00:16Z"],"dc:date.issued":["2026-04-14"],"dc:description.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)."],"dc:description.abstractgeneral":["Many planning problems in manufacturing and supply chains involve deciding how much to produce, transport, or store over time under limited capacity. In practice, this capacity often comes from multiple heterogeneous resources, such as machines in a factory or vehicles in a transportation fleet, each with different capabilities and costs. Coordinating these resources efficiently is particularly challenging when costs exhibit economies of scale and decisions are coupled over time. In this dissertation, we study new generalizations of the classical capacitated lot-sizing problem in which the available capacity in each period is generated by a collection of heterogeneous modules (machines or vehicles). We show that, although these problems are NP-hard in general, they become tractable when the number of modules is fixed. Specifically, we develop exact fixed-parameter tractable algorithms that solve these problems in polynomial time for any fixed number of modules, thereby resolving a long-standing open question in the literature. We also extend this research in several important directions. First, we consider models with piecewise concave cost functions that capture economies of scale and develop improved dynamic programming algorithms with significantly reduced computational complexity. Second, we study multi-echelon supply chain settings, where goods move from suppliers to warehouses and then to retailers under capacity constraints at each stage. For these problems, we provide new polynomial-time exact algorithms, generalizing several classical results that were previously limited to single-resource settings. To evaluate practical performance, we implement our algorithms and compare them with state-of-the-art commercial solvers. The computational results show that our methods are not only theoretically efficient but also highly competitive in practice, often outperforming commercial software in both speed and robustness."],"dc:description.degree":["Doctor of Philosophy"],"dc:format.medium":["ETD"],"dc:identifier.other":["vt_gsexam:46069"],"dc:identifier.uri":["https://hdl.handle.net/10919/143005"],"dc:language.iso":["en"],"dc:publisher":["Virginia Tech"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:subject":["polynomial algorithms","lot-sizing"],"dc:title":["Polynomial Time Algorithms for Transportation and Inventory Management in Serial Supply Chain with Multi-Module Capacitated Vehicles"],"dc:type":["Dissertation"],"thesis:degree_discipline":["Industrial and Systems Engineering"],"thesis:degree_level":["doctoral"],"thesis:degree_name":["Doctor of Philosophy"],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-24T05:56:39Z"}