IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v39y2005i2p233-248.html
   My bibliography  Save this article

Shipping Multiple Items by Capacitated Vehicles: An Optimal Dynamic Programming Approach

Author

Listed:
  • Shoshana Anily

    (Faculty of Management, Tel Aviv University, Tel Aviv, Israel)

  • Michal Tzur

    (Department of Industrial Engineering, Tel Aviv University, Tel Aviv, Israel)

Abstract

We consider a system in which multiple items are transferred from a warehouse or a plant to a retailer through identical capacitated vehicles, or by identical freight wagons. Any mixture of the items may be loaded onto a vehicle. The retailer is facing dynamic deterministic demand for several items, over a finite planning horizon. A vehicle incurs a fixed cost for each trip made from the warehouse to the retailer. In addition, there exist item-dependent variable shipping costs and inventory holding costs at the retailer, which are both constant over time. The objective is to find a shipment schedule that minimizes the total cost, while satisfying demand on time.We address and partially resolve the question regarding the problem’s complexity by introducing a dynamic programming algorithm whose complexity is polynomial for a fixed number of items, but exponential otherwise. Our dynamic programming formulation is based on properties satisfied by the optimal solution, and uses an innovative way for partitioning the problem into subproblems.

Suggested Citation

  • Shoshana Anily & Michal Tzur, 2005. "Shipping Multiple Items by Capacitated Vehicles: An Optimal Dynamic Programming Approach," Transportation Science, INFORMS, vol. 39(2), pages 233-248, May.
  • Handle: RePEc:inm:ortrsc:v:39:y:2005:i:2:p:233-248
    DOI: 10.1287/trsc.1030.0080
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1030.0080
    Download Restriction: no

    File URL: https://libkey.io/10.1287/trsc.1030.0080?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Steven A. Lippman, 1969. "Optimal Inventory Policy with Multiple Set-Up Costs," Management Science, INFORMS, vol. 16(1), pages 118-138, September.
    2. Michael Florian & Morton Klein, 1971. "Deterministic Production Planning with Concave Costs and Capacity Constraints," Management Science, INFORMS, vol. 18(1), pages 12-20, September.
    3. Miguel Constantino, 1998. "Lower Bounds in Lot-Sizing Models: A Polyhedral Study," Mathematics of Operations Research, INFORMS, vol. 23(1), pages 101-118, February.
    4. Kenneth R. Baker & Paul Dixon & Michael J. Magazine & Edward A. Silver, 1978. "An Algorithm for the Dynamic Lot-Size Problem with Time-Varying Production Capacity Constraints," Management Science, INFORMS, vol. 24(16), pages 1710-1720, December.
    5. Candace A. Yano & Alexandra M. Newman, 2001. "Scheduling Trains and Containers with Due Dates and Dynamic Arrivals," Transportation Science, INFORMS, vol. 35(2), pages 181-191, May.
    6. POCHET, Yves & WOLSEY, Laurence A., 1993. "Lot-sizing with constant batches: formulation and valid inequalities," LIDAM Reprints CORE 1066, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. Yves Pochet & Laurence A. Wolsey, 1993. "Lot-Sizing with Constant Batches: Formulation and Valid Inequalities," Mathematics of Operations Research, INFORMS, vol. 18(4), pages 767-785, November.
    8. M. Florian & J. K. Lenstra & A. H. G. Rinnooy Kan, 1980. "Deterministic Production Planning: Algorithms and Complexity," Management Science, INFORMS, vol. 26(7), pages 669-679, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Engebrethsen, Erna & Dauzère-Pérès, Stéphane, 2019. "Transportation mode selection in inventory models: A literature review," European Journal of Operational Research, Elsevier, vol. 279(1), pages 1-25.
    2. Ulku, M. Ali, 2016. "Keeping Trucking In-House: a Dynamic Multi-Item Shipment Consolidation Model for a Manufacturer-Distributor," 57th Transportation Research Forum (51st CTRF) Joint Conference, Toronto, Ontario, May 1-4, 2016 319305, Transportation Research Forum.
    3. Retsef Levi & Andrea Lodi & Maxim Sviridenko, 2008. "Approximation Algorithms for the Capacitated Multi-Item Lot-Sizing Problem via Flow-Cover Inequalities," Mathematics of Operations Research, INFORMS, vol. 33(2), pages 461-474, May.
    4. ANILY, Shoshana & TZUR, Michal & WOLSEY, Laurence A., 2005. "Multi-item lot-sizing with a joint set-up cost," LIDAM Discussion Papers CORE 2005070, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Martin Grunewald & Thomas Volling & Christoph Müller & Thomas S. Spengler, 2018. "Multi-item single-source ordering with detailed consideration of transportation capacities," Journal of Business Economics, Springer, vol. 88(7), pages 971-1007, September.
    6. Yue Jin & Ana Muriel, 2009. "Single‐warehouse multi‐retailer inventory systems with full truckload shipments," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(5), pages 450-464, August.
    7. Mustafa Çagri Gürbüz & Kamran Moinzadeh & Yong-Pin Zhou, 2007. "Coordinated Replenishment Strategies in Inventory/Distribution Systems," Management Science, INFORMS, vol. 53(2), pages 293-307, February.
    8. Farhat, Mlouka & Akbalik, Ayse & Hadj-Alouane, Atidel B. & Sauer, Nathalie, 2019. "Lot sizing problem with batch ordering under periodic buyback contract and lost sales," International Journal of Production Economics, Elsevier, vol. 208(C), pages 500-511.
    9. Awi Federgruen & Joern Meissner & Michal Tzur, 2007. "Progressive Interval Heuristics for Multi-Item Capacitated Lot-Sizing Problems," Operations Research, INFORMS, vol. 55(3), pages 490-502, June.
    10. Jenny Carolina Saldana Cortés, 2011. "Programación semidefinida aplicada a problemas de cantidad económica de pedido," Documentos CEDE 8735, Universidad de los Andes, Facultad de Economía, CEDE.
    11. Shoshana Anily & Michal Tzur, 2006. "Algorithms for the multi‐item multi‐vehicles dynamic lot sizing problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(2), pages 157-169, March.
    12. Brahimi, Nadjib & Absi, Nabil & Dauzère-Pérès, Stéphane & Nordli, Atle, 2017. "Single-item dynamic lot-sizing problems: An updated survey," European Journal of Operational Research, Elsevier, vol. 263(3), pages 838-863.
    13. Shi Li, 2020. "Constant Approximation Algorithm for Nonuniform Capacitated Multi-Item Lot Sizing via Strong Covering Inequalities," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 947-965, August.
    14. Baller, Annelieke C. & Dabia, Said & Dullaert, Wout E.H. & Vigo, Daniele, 2019. "The Dynamic-Demand Joint Replenishment Problem with Approximated Transportation Costs," European Journal of Operational Research, Elsevier, vol. 276(3), pages 1013-1033.
    15. Weihong Hu & Zhuoting Yu & Alejandro Toriello & Maged M. Dessouky, 2020. "Decomposition‐based approximation algorithms for the one‐warehouse multi‐retailer problem with concave batch order costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(7), pages 503-523, October.
    16. Andersson, Jonas & Malmberg, Filip & Marklund, Johan, 2023. "Exact analysis of One-Warehouse-Multiple-Retailer inventory systems with quantity restricted deliveries," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1161-1172.
    17. Sancak, Emre & Salman, F. Sibel, 2011. "Multi-item dynamic lot-sizing with delayed transportation policy," International Journal of Production Economics, Elsevier, vol. 131(2), pages 595-603, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jans, Raf & Degraeve, Zeger, 2007. "Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1855-1875, March.
    2. C. P. M. van Hoesel & A. P. M. Wagelmans, 2001. "Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems," Mathematics of Operations Research, INFORMS, vol. 26(2), pages 339-357, May.
    3. van Hoesel, C.P.M. & Wagelmans, A., 1997. "Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems," Research Memorandum 029, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    4. Chung-Lun Li & Qingying Li, 2016. "Polynomial-Time Solvability of Dynamic Lot Size Problems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(03), pages 1-20, June.
    5. Hark-Chin Hwang, 2009. "Inventory Replenishment and Inbound Shipment Scheduling Under a Minimum Replenishment Policy," Transportation Science, INFORMS, vol. 43(2), pages 244-264, May.
    6. Alper Atamtürk & Dorit S. Hochbaum, 2001. "Capacity Acquisition, Subcontracting, and Lot Sizing," Management Science, INFORMS, vol. 47(8), pages 1081-1100, August.
    7. Brahimi, Nadjib & Absi, Nabil & Dauzère-Pérès, Stéphane & Nordli, Atle, 2017. "Single-item dynamic lot-sizing problems: An updated survey," European Journal of Operational Research, Elsevier, vol. 263(3), pages 838-863.
    8. van Hoesel, C.P.M. & Wagelmans, A.P.M., 1997. "Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems," Econometric Institute Research Papers EI 9735/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    9. Shoshana Anily & Michal Tzur, 2006. "Algorithms for the multi‐item multi‐vehicles dynamic lot sizing problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(2), pages 157-169, March.
    10. Ayse Akbalik & Bernard Penz & Christophe Rapine, 2015. "Capacitated lot sizing problems with inventory bounds," Annals of Operations Research, Springer, vol. 229(1), pages 1-18, June.
    11. Mathieu Van Vyve, 2007. "Algorithms for Single-Item Lot-Sizing Problems with Constant Batch Size," Mathematics of Operations Research, INFORMS, vol. 32(3), pages 594-613, August.
    12. Ming Zhao & Minjiao Zhang, 2020. "Multiechelon Lot Sizing: New Complexities and Inequalities," Operations Research, INFORMS, vol. 68(2), pages 534-551, March.
    13. Akbalik, Ayse & Penz, Bernard, 2009. "Exact methods for single-item capacitated lot sizing problem with alternative machines and piece-wise linear production costs," International Journal of Production Economics, Elsevier, vol. 119(2), pages 367-379, June.
    14. Hark-Chin Hwang, 2010. "Economic Lot-Sizing for Integrated Production and Transportation," Operations Research, INFORMS, vol. 58(2), pages 428-444, April.
    15. Akbalik, Ayse & Rapine, Christophe, 2013. "The single item uncapacitated lot-sizing problem with time-dependent batch sizes: NP-hard and polynomial cases," European Journal of Operational Research, Elsevier, vol. 229(2), pages 353-363.
    16. Laurence A. Wolsey, 2002. "Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation," Management Science, INFORMS, vol. 48(12), pages 1587-1602, December.
    17. van Hoesel, C.P.M. & Wagelmans, A., 1995. "An O ( T ³) algorithm for the economic lot-sizing problem with constant capacities," Research Memorandum 005, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    18. Akbalik, Ayse & Hadj-Alouane, Atidel B. & Sauer, Nathalie & Ghribi, Houcem, 2017. "NP-hard and polynomial cases for the single-item lot sizing problem with batch ordering under capacity reservation contract," European Journal of Operational Research, Elsevier, vol. 257(2), pages 483-493.
    19. Absi, Nabil & Kedad-Sidhoum, Safia, 2008. "The multi-item capacitated lot-sizing problem with setup times and shortage costs," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1351-1374, March.
    20. Hwang, Hark-Chin & Kang, Jangha, 2016. "Two-phase algorithm for the lot-sizing problem with backlogging for stepwise transportation cost without speculative motives," Omega, Elsevier, vol. 59(PB), pages 238-250.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:39:y:2005:i:2:p:233-248. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.