×

zbMATH — the first resource for mathematics

A hybrid heuristic for an inventory routing problem. (English) Zbl 06599258
Summary: We consider an inventory routing problem in discrete time where a supplier has to serve a set of customers over a multiperiod horizon. A capacity constraint for the inventory is given for each customer, and the service cannot cause any stockout situation. Two different replenishment policies are considered: the order-up-to-level and the maximum-level policies. A single vehicle with a given capacity is available. The transportation cost is proportional to the distance traveled, whereas the inventory holding cost is proportional to the level of the inventory at the customers and at the supplier. The objective is the minimization of the sum of the inventory and transportation costs. We present a heuristic that combines a tabu search scheme with ad hoc designed mixed-integer programming models. The effectiveness of the heuristic is proved over a set of benchmark instances for which the optimal solution is known.

MSC:
90 Operations research, mathematical programming
Software:
Tabu search
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Archetti C., Bertazzi L., Laporte G., Speranza M. G.A branch-and-cut algorithm for a vendor-managed inventory routing problem. Transportation Sci. (2007) 41(3):382-391Link
[2] Bell W. J., Dalberto L. M., Fisher M. L., Greenfield A. J., Jaikumar R. G., Kedia P., Mack R. G., Prutzman P. J.Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer. Interfaces (1983) 13(6):4-23Link
[3] Bertazzi L., Paletta G., Speranza M. G.Deterministic order-up-to level policies in an inventory routing problem. Transportation Sci. (2002) 36(1):119-132Link · Zbl 1065.90500
[4] Bertazzi L., Speranza M. G., Savelsbergh M. W. P., Golden B., Raghavan R., Wasil E.Inventory routing. The Vehicle Routing Problem: Latest Advances and New Challenges (2008) (Springer, New York) 49-72CrossRef · Zbl 1187.90039
[5] Blumenfeld D. E., Burns L. D., Diltz J. D., Daganzo C. F.Analyzing trade-offs between transportation, inventory and production costs on freight networks. Transportation Res. B (1985) 19(5):361-380CrossRef
[6] Campbell A. M., Clarke L., Kleywegt A., Savelsbergh M. W. P., Crainic T. G., Laporte G.The inventory routing problem. Fleet Management and Logistics (1998) (Kluwer Academic Publishers, Boston) 95-113CrossRef · Zbl 0972.90500
[7] Cordeau J.-F., Laporte G., Savelsbergh M. W. P., Vigo D., Barnhart C., Laporte G.Vehicle routing. Handbooks in Operations Research and Management Science: Transportation (2009) 14(North-Holland, Amsterdam) 367-428
[8] Dror M., Ball M., Golden B.A computational comparison of algorithms for the inventory routing problem. Ann. Oper. Res. (1985) 4(1):1-23CrossRef
[9] Federgruen A., Simchi-Levi D., Ball M. O., Magnanti T. L., Monma C. L., Nemhauser G. L.Analysis of vehicle routing and inventory-routing problems. Handbooks in Operations Research and Management Science: Network Routing (1995) 8(North-Holland, Amsterdam) 297-373 · Zbl 0870.90057
[10] Federgruen A., Zipkin P.A combined vehicle routing and inventory allocation problem. Oper. Res. (1984) 32(5):1019-1032Link · Zbl 0552.90026
[11] Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman & Company, New York)
[12] Gendreau M., Hertz A., Laporte G.A tabu search heuristic for the vehicle routing problem. Management Sci. (1994) 40(10):1276-1290Link · Zbl 0822.90053
[13] Glover F.Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. (1986) 13(5):533-549CrossRef · Zbl 0615.90083
[14] Glover F., Laguna M.Tabu Search (1997) (Kluwer Academic Publishers, Dordrecht, The Netherlands) CrossRef
[15] Golden B., Assad A., Dahl R.Analysis of a large scale vehicle routing problem with an inventory component. Large Scale Systems (1984) 7(2-3):181-190 · Zbl 0551.90018
[16] Kellerer H., Pferschy U., Pisinger D.Knapsack Problems (2004) (Springer-Verlag, Berlin) CrossRef
[17] Lin S., Kernighan B. W.An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. (1973) 21(2):498-516Link · Zbl 0256.90038
[18] Martello S., Toth P.Knapsack Problems: Algorithms and Computer Implementations (1990) (John Wiley & Sons, New York)
[19] Taillard E.Robust taboo search for the QAP. Parallel Comput. (1991) 17(4-5):443-455CrossRef
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.