Approximation algorithms for inventory problems with submodular or routing costs

DOI10.1007/S10107-016-0981-YMaRDI QIDQ344939zbMATH OpenOpenAlexFDO

Authors Viswanath Nagarajan, Cong Shi

Publication date 25 November 2016

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.06560

zbMATH Keywords

approximation algorithmssubmodular functioninventory managementjoint replenishment probleminventory routing problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Inventory, storage, reservoirs (90B05) Transportation, logistics and supply chain management (90B06) Production models (90B30)

Abstract: We consider the following two deterministic inventory optimization problems over a finite planning horizon $T$ with non-stationary demands. (a) Submodular Joint Replenishment Problem: This involves multiple item types and a single retailer who faces demands. In each time step, any subset of item-types can be ordered incurring a joint ordering cost which is submodular. Moreover, items can be held in inventory while incurring a holding cost. The objective is find a sequence of orders that satisfies all demands and minimizes the total ordering and holding costs. (b) Inventory Routing Problem: This involves a single depot that stocks items, and multiple retailer locations facing demands. In each time step, any subset of locations can be visited using a vehicle originating from the depot. There is also cost incurred for holding items at any retailer. The objective here is to satisfy all demands while minimizing the sum of routing and holding costs. We present a unified approach that yields $mathcalOleft(fraclogTloglogTight)$-factor approximation algorithms for both problems when the holding costs are polynomial functions. A special case is the classic linear holding cost model, wherein this is the first sub-logarithmic approximation ratio for either problem.

Recommendations

• Improved approximation algorithms for inventory problems
• The submodular joint replenishment problem
• Primal-Dual Algorithms for Deterministic Inventory Problems
• Better Approximation Bounds for the Joint Replenishment Problem
• Deliver or Hold: Approximation Algorithms for the Periodic Inventory Routing Problem

Cites work

• A Combined Vehicle Routing and Inventory Allocation Problem
• A constant approximation algorithm for the one-warehouse multiretailer problem
• A new algorithm for minimizing convex functions over convex sets
• A threshold of ln n for approximating set cover
• An Integrated Inventory Allocation and Vehicle Routing Problem
• An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
• An efficient polynomial-time approximation scheme for the joint replenishment problem
• Analysis of Direct Shipping Policies in an Inventory-Routing Problem with Discrete Shipping Times
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
• Better Approximation Bounds for the Joint Replenishment Problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computational complexity of uncapacitated multi-echelon production planning problems
• Deliver or Hold: Approximation Algorithms for the Periodic Inventory Routing Problem
• Distribution Strategies that Minimize Transportation and Inventory Costs
• Dynamic version of the economic lot size model
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Heuristic analysis, linear programming and branch and bound
• Integrating Routing and Inventory Decisions in One-Warehouse Multiretailer Multiproduct Distribution Systems
• Multistage Lot Sizing Problems via Randomized Rounding
• On maximizing welfare when utility functions are subadditive
• One Warehouse Multiple Retailer Systems with Vehicle Routing Costs
• Primal-Dual Algorithms for Deterministic Inventory Problems
• Probabilistic analyses and practical algorithms for inventory-routing models
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
• The Joint Replenishment Problem with General Joint Cost Structures
• The Joint Replenishment Problem: New Heuristics and Worst Case Performance Bounds
• The submodular joint replenishment problem
• Two-Echelon Distribution Systems with Vehicle Routing Costs and Central Inventories

Cited in

(10)

• The subdivision-constrained routing requests problem
• Improved approximation algorithms for inventory problems
• Primal-Dual Algorithms for Deterministic Inventory Problems
• Concave connection cost facility location and the star inventory routing problem
• Combinatorial heuristics for inventory routing problems
• Deliver or Hold: Approximation Algorithms for the Periodic Inventory Routing Problem
• Recent challenges in Routing and Inventory Routing: E‐commerce and last‐mile delivery
• Decomposing inventory routing problems with approximate value functions
• The submodular joint replenishment problem
• <scp>Decomposition‐based</scp> approximation algorithms for the <scp>one‐warehouse multi‐retailer</scp> problem with concave batch order costs

This page was built for publication: Approximation algorithms for inventory problems with submodular or routing costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344939)