Approximation algorithms for inventory problems with submodular or routing costs

DOI10.1007/S10107-016-0981-YzbMATH Open1349.90039arXiv1504.06560OpenAlexW1622454718MaRDI QIDQ344939FDOQ344939

Authors: Viswanath Nagarajan, Cong Shi 

Publication date: 25 November 2016

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

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.

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

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

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)

Cites Work

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

Cited In (10)

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

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)