Abstract
In this paper, we develop a mathematical programming approach for coordinating inventory and transportation decisions in an inbound commodity collection system. In particular, we consider a system that consists of a set of geographically dispersed suppliers that manufacture one or more non-identical items, and a central warehouse that stocks these items. The warehouse faces a constant and deterministic demand for the items from outside retailers. The items are collected by a fleet of vehicles that are dispatched from the central warehouse. The vehicles are capacitated, and must also satisfy a frequency constraint. Adopting a policy in which each vehicle always collects the same set of items, we formulate the inventory-routing problem of minimizing the long-run average inventory and transportation costs as a set partitioning problem. We employ a column generation approach to determine a lower bound on the total costs, and develop a branch-and-price algorithm that finds the optimal assignment of items to vehicles. We also propose greedy constructive heuristics, and develop a very large-scale neighborhood (VLSN) search algorithm to find near-optimal solutions for the problem. Computational tests are performed on a set of randomly generated problem instances.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
D. Adelman (2003) ArticleTitlePrice-directed replenishment of subsets: methodology and its application to inventory routing Manufacturing and Service Operations Management 5 348–371
R.K. Ahuja N Boland I. Dumitrescu (2001) Exact and heuristic algorithms for the subset disjoint minimum cost cycle problem. Working paper, Department of Industrial and Systems Engineering University of Florida Gainesville, Florida
R.K. Ahuja O. Ergun J.B Orlin A. Punnen (2002) ArticleTitleA survey of very large scale neighborhood search techniques Discrete Applied Mathematics 123 75–102
R.K. Ahuja W. Huang H.E Romeijn D. Romero Morales (2002) A heuristic approach to the multi-period single-sourcing problem with production and inventory capacities and perishability constraints. Research Report 2002-2, Department of Industrial and Systems Engineering University of Florida Gainesville, Florida
R.K. Ahuja J.B Orlin D. Sharma (2001) ArticleTitleA composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem Operations Research Letters 31 185–194
R.K. Ahuja J.B Orlin D. Sharma (2001) ArticleTitleMulti-exchange neighborhood structures for the capacitated minimum spanning tree problem Mathematical Programming 91 IssueID1 71–97
R.K. Ahuja J.B Orlin D. Sharma (2000) ArticleTitleVery large scale neighborhood search International Transactions in Operations Research 7 301–317
S Anily A. Federgruen (1990) ArticleTitleOne warehouse multiple retailer systems with vehicle routing costs Management Science 36 IssueID1 92–114
S Anily A. Federgruen (1993) ArticleTitleTwo-echelon distribution systems with vehicle routing costs and central inventories Operations Research 41 IssueID1 37–47
S. Anily (1994) ArticleTitleThe general multi-retailer EOQ problem with vehicle routing costs European Journal of Operational Research 79 451–473
C. Barnhart E.L. Johnson G.L. Nemhauser M.W.P Savelsbergh P. Vance (1998) ArticleTitleBranch-and-Price: column generation for solving huge integer programs Operations Research 46 IssueID3 316–329
N Ben-Khedher C.A. Yano (1994) ArticleTitleThe multi-item joint replenishment problem with transportation and container effects Transportation Science 28 IssueID1 37–54
L Bertazzi M.G. Speranza (1999) ArticleTitleMinimizing logistic costs in multistage supply chains Naval Research Logistics 46 399–417
J Bramel D. Simchi-Levi (1997) The Logic of Logistics: Theory, Algorithms, and Applications for Logistics Management Springer-Verlag New York
F.P Buffa J.R. Munn (1990) ArticleTitleMulti-item grouping algorithm yielding near-optimal logistics cost Decision Sciences 21 IssueID1 14–34
L.D. Burns R.W. Hall D.E Blumenfeld C.F. Daganzo (1985) ArticleTitleDistribution strategies that minimize transportation and inventory costs Operations Research 33 IssueID3 469–490
S Çetinkaya C.-Y. Lee (2000) ArticleTitleStock replenishment and shipment scheduling for vendor managed inventory systems Management Science 46 IssueID2 217–232 Occurrence Handle10.1287/mnsc.46.2.217.11923
L.M.A. Chan A Federgruen D. Simchi-Levi (1998) ArticleTitleProbabilistic analyses and practical algorithms for inventory-routing models Operations Research 46 IssueID1 96–106
L.M.A Chan D. Simchi-Levi (1998) ArticleTitleProbabilistic analyses and algorithms for three-level distribution systems Management Science 44 IssueID11 1562–1576
P. Chaovalitwongse H.E Romeijn P.M. Pardalos (2002) A scenario-based heuristic for a capacitated transportation-inventory problem with stochastic demands E. Kontoghiorghes B. Rustem S. Siokos (Eds) Computational Methods in Decision-Making, Economics and Finance Kluwer Academic Publishers Dordrecht, The Netherlands
T.W. Chien A Balakrishnan R.T. Wong (1989) ArticleTitleAn integrated inventory allocation and vehicle routing problem Transportation Science 23 IssueID2 67–76
G.A. Croes (1958) ArticleTitleA method for solving traveling-salesman problems Operations Research 6 791–812
M. Dror M Ball B. Golden (1985) ArticleTitleA computational comparison of algorithms for the inventory routing problem Annals of Operations Research 4 3–23
M Dror M. Ball (1987) ArticleTitleInventory/routing: reduction from an annual to a short-period problem Naval Research Logistics 34 891–905
R Fahrion M. Wrede (1990) ArticleTitleOn a principle of chain exchange for vehicle routing problems (I-VRP) Journal of the Operational Research Society 41 821–827
A Federgruen P. Zipkin (1984) ArticleTitleA combined vehicle routing and inventory allocation problem Operations Research 32 IssueID5 1019–1037
A. Frangioni E Necciari M.G. Scutella (2000) Multi-exchange algorithms for the minimum makespan machine scheduling problem. Technical report, Dipartimento di Informatica University of Pisa, Pisa Italy
R. Freling H.E. Romeijn D Morales A.P.M. Wagelmans (2003) ArticleTitleA branch-and-price algorithm for the multi-period single-sourcing problem Operations Research 51 922–939
G Gallego D. Simchi-Levi (1990) ArticleTitleOn the effectiveness of direct shipping strategy for the one-warehouse multi-retailer R-systems Management Science 36 IssueID2 240–243
M. Gendreau F. Guertin J.-Y Potvin R. Seguin (1998) Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries. CRT Research Report No. CRT-98-10, Centre for Research on Transportation University of Montréal Montréal, Canada
W. Huang H.E Romeijn J. Geunes (2004) The continuous-time single-sourcing problem with capacity expansion opportunities. Technical Report, Department of Industrial and Systems Engineering University of Florida Gainesville, Florida
S. Lin (1965) ArticleTitleComputer solutions of the traveling salesman problem Bell Systems Technical Journal 44 2245–2269
S Lin B.W. Kernighan (1973) ArticleTitleAn efficient heuristic algorithm for the traveling-salesman problem Operations Research 21 498–516
S Martello P. Toth (1990) Knapsack Problems, Algorithms and Computer Implementations John Wiley Sons New York
W.W. Qu J.H Bookbinder P. Iyogun (1999) ArticleTitleAn integrated inventory-transportation system with modified periodic policy for multiple products European Journal of Operational Research 115 254–269
D.J. Rosenkrantz R.E Stearns P.M. Lewis (1977) ArticleTitleAn analysis of several heuristics of traveling salesman problem SIAM Journal of Computing 6 563–581
M.W.P. Savelsbergh (1997) ArticleTitleA branch-and-price algorithm for the generalized assignment problem Operations Research 6 831–841
Z.J. Shen C Coullard M.S. Daskin (2003) ArticleTitleA joint location-inventory model Transportation Science 37 IssueID1 40–55
E.A. Silver D.F Pyke R. Peterson (1998) Inventory Management and Production Planning and Scheduling John Wiley Sons New York
P.M. Thompson (1988) Local Search Algorithms for Vehicle Routing and Other Combinatorial Problems. Ph.D. Thesis, Operations Research Center MIT, Cambridge Massachusetts
P.M Thompson J.B. Orlin (1989) The Theory of Cyclic Transfers.. Working Paper No. OR 200-89 MIT, Cambridge Massachusetts
P.M Thompson H.N. Psaraftis (1993) ArticleTitleCyclic transfer algorithms for multi-vehicle routing and scheduling problems Operations Research 41 935–946 Occurrence HandleMR1241830
A. Toptal S Çetinkaya C.-Y. Lee (2003) ArticleTitleThe buyer-vendor coordination problem: modeling inbound and outbound cargo capacity and costs IIE Transactions on Logistics and Scheduling 35 IssueID11 987–1002
P Toth D. Vigo (2002) The Vehicle Routing Problem, Society for Industrial and Applied Mathemtics Philadelphia USA
S Viswanathan K. Mathur (1997) ArticleTitleIntegrating routing and inventory decisions in one-warehouse multi-retailer multi-product distribution systems Management Science 43 IssueID3 294–312
C Yano Y. Gerchak (1989) ArticleTitleTransportation contracts and safety stocks for just-in-time deliveries Manufacturing and Service Operations Management 2 314–330
Author information
Authors and Affiliations
Corresponding author
Additional information
The work of this author was supported by a scholarship of the Faculty of Engineering of Ubonratchathani University, Ubonratchathani, Thailand., The work of this author was supported in part by the National Science Foundation under Grant No. DMI-0085682.
Rights and permissions
About this article
Cite this article
Sindhuchao, S., Romeijn, H.E., Akçali, E. et al. An Integrated Inventory-Routing System for Multi-item Joint Replenishment with Limited Vehicle Capacity. J Glob Optim 32, 93–118 (2005). https://doi.org/10.1007/s10898-004-5908-0
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10898-004-5908-0