Skip to main content
Log in

An Integrated Inventory-Routing System for Multi-item Joint Replenishment with Limited Vehicle Capacity

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. D. Adelman (2003) ArticleTitlePrice-directed replenishment of subsets: methodology and its application to inventory routing Manufacturing and Service Operations Management 5 348–371

    Google Scholar 

  2. 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

    Google Scholar 

  3. 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

    Google Scholar 

  4. 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

    Google Scholar 

  5. 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

    Google Scholar 

  6. 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

    Google Scholar 

  7. R.K. Ahuja J.B Orlin D. Sharma (2000) ArticleTitleVery large scale neighborhood search International Transactions in Operations Research 7 301–317

    Google Scholar 

  8. S Anily A. Federgruen (1990) ArticleTitleOne warehouse multiple retailer systems with vehicle routing costs Management Science 36 IssueID1 92–114

    Google Scholar 

  9. S Anily A. Federgruen (1993) ArticleTitleTwo-echelon distribution systems with vehicle routing costs and central inventories Operations Research 41 IssueID1 37–47

    Google Scholar 

  10. S. Anily (1994) ArticleTitleThe general multi-retailer EOQ problem with vehicle routing costs European Journal of Operational Research 79 451–473

    Google Scholar 

  11. 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

    Google Scholar 

  12. N Ben-Khedher C.A. Yano (1994) ArticleTitleThe multi-item joint replenishment problem with transportation and container effects Transportation Science 28 IssueID1 37–54

    Google Scholar 

  13. L Bertazzi M.G. Speranza (1999) ArticleTitleMinimizing logistic costs in multistage supply chains Naval Research Logistics 46 399–417

    Google Scholar 

  14. J Bramel D. Simchi-Levi (1997) The Logic of Logistics: Theory, Algorithms, and Applications for Logistics Management Springer-Verlag New York

    Google Scholar 

  15. F.P Buffa J.R. Munn (1990) ArticleTitleMulti-item grouping algorithm yielding near-optimal logistics cost Decision Sciences 21 IssueID1 14–34

    Google Scholar 

  16. 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

    Google Scholar 

  17. 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

    Article  Google Scholar 

  18. 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

    Google Scholar 

  19. L.M.A Chan D. Simchi-Levi (1998) ArticleTitleProbabilistic analyses and algorithms for three-level distribution systems Management Science 44 IssueID11 1562–1576

    Google Scholar 

  20. 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

    Google Scholar 

  21. T.W. Chien A Balakrishnan R.T. Wong (1989) ArticleTitleAn integrated inventory allocation and vehicle routing problem Transportation Science 23 IssueID2 67–76

    Google Scholar 

  22. G.A. Croes (1958) ArticleTitleA method for solving traveling-salesman problems Operations Research 6 791–812

    Google Scholar 

  23. M. Dror M Ball B. Golden (1985) ArticleTitleA computational comparison of algorithms for the inventory routing problem Annals of Operations Research 4 3–23

    Google Scholar 

  24. M Dror M. Ball (1987) ArticleTitleInventory/routing: reduction from an annual to a short-period problem Naval Research Logistics 34 891–905

    Google Scholar 

  25. 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

    Google Scholar 

  26. A Federgruen P. Zipkin (1984) ArticleTitleA combined vehicle routing and inventory allocation problem Operations Research 32 IssueID5 1019–1037

    Google Scholar 

  27. 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

    Google Scholar 

  28. 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

    Google Scholar 

  29. 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

    Google Scholar 

  30. 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

    Google Scholar 

  31. 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

    Google Scholar 

  32. S. Lin (1965) ArticleTitleComputer solutions of the traveling salesman problem Bell Systems Technical Journal 44 2245–2269

    Google Scholar 

  33. S Lin B.W. Kernighan (1973) ArticleTitleAn efficient heuristic algorithm for the traveling-salesman problem Operations Research 21 498–516

    Google Scholar 

  34. S Martello P. Toth (1990) Knapsack Problems, Algorithms and Computer Implementations John Wiley Sons New York

    Google Scholar 

  35. 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

    Google Scholar 

  36. 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

    Google Scholar 

  37. M.W.P. Savelsbergh (1997) ArticleTitleA branch-and-price algorithm for the generalized assignment problem Operations Research 6 831–841

    Google Scholar 

  38. Z.J. Shen C Coullard M.S. Daskin (2003) ArticleTitleA joint location-inventory model Transportation Science 37 IssueID1 40–55

    Google Scholar 

  39. E.A. Silver D.F Pyke R. Peterson (1998) Inventory Management and Production Planning and Scheduling John Wiley Sons New York

    Google Scholar 

  40. P.M. Thompson (1988) Local Search Algorithms for Vehicle Routing and Other Combinatorial Problems. Ph.D. Thesis, Operations Research Center MIT, Cambridge Massachusetts

    Google Scholar 

  41. P.M Thompson J.B. Orlin (1989) The Theory of Cyclic Transfers.. Working Paper No. OR 200-89 MIT, Cambridge Massachusetts

    Google Scholar 

  42. P.M Thompson H.N. Psaraftis (1993) ArticleTitleCyclic transfer algorithms for multi-vehicle routing and scheduling problems Operations Research 41 935–946 Occurrence HandleMR1241830

    MathSciNet  Google Scholar 

  43. 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

    Google Scholar 

  44. P Toth D. Vigo (2002) The Vehicle Routing Problem, Society for Industrial and Applied Mathemtics Philadelphia USA

    Google Scholar 

  45. 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

    Google Scholar 

  46. C Yano Y. Gerchak (1989) ArticleTitleTransportation contracts and safety stocks for just-in-time deliveries Manufacturing and Service Operations Management 2 314–330

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Sombat Sindhuchao.

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

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-004-5908-0

Keywords

Navigation