IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v267y2018i2p555-569.html
   My bibliography  Save this article

A stochastic multi-stage fixed charge transportation problem: Worst-case analysis of the rolling horizon approach

Author

Listed:
  • Bertazzi, Luca
  • Maggioni, Francesca

Abstract

We introduce a stochastic multi-stage fixed charge transportation problem, in which a producer has to satisfy an uncertain demand within a deadline. At each time period, a fixed transportation cost can be paid to buy a transportation capacity. If the transportation capacity is used, the supplier also pays an uncertain unit transportation cost. A unit inventory cost is charged for the unsatisfied demand. The aim is to determine the transportation capacities to buy and the quantity to send at each time period in order to minimize the expected total cost. We prove that this problem is NP-hard, we propose a multi-stage stochastic optimization model formulation, and we determine optimal policies for particular cases, with deterministic unit transportation costs or demand and zero fixed costs. Furthermore, we provide the worst–case analysis of the rolling horizon approach, a classical heuristic approach for solving multi-stage stochastic programming models, applied to this NP-hard problem and to polynomially solvable particular cases. Worst–case results show that the rolling horizon approach can be very suboptimal. We also provide experimental results.

Suggested Citation

  • Bertazzi, Luca & Maggioni, Francesca, 2018. "A stochastic multi-stage fixed charge transportation problem: Worst-case analysis of the rolling horizon approach," European Journal of Operational Research, Elsevier, vol. 267(2), pages 555-569.
  • Handle: RePEc:eee:ejores:v:267:y:2018:i:2:p:555-569
    DOI: 10.1016/j.ejor.2017.12.004
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722171731086X
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Paraskevopoulos, Dimitris C. & Bektaş, Tolga & Crainic, Teodor Gabriel & Potts, Chris N., 2016. "A cycle-based evolutionary algorithm for the fixed-charge capacitated multi-commodity network design problem," European Journal of Operational Research, Elsevier, vol. 253(2), pages 265-279.
    2. Marida Bertocchi & Vittorio Moriggia & Jitka Dupačová, 2006. "Horizon and stages in applications of stochastic programming in finance," Annals of Operations Research, Springer, vol. 142(1), pages 63-78, February.
    3. Jawahar, N. & Balaji, A.N., 2009. "A genetic algorithm for the two-stage supply chain distribution problem associated with a fixed charge," European Journal of Operational Research, Elsevier, vol. 194(2), pages 496-537, April.
    4. Jeff Kennington & Ed Unger, 1976. "A New Branch-and-Bound Algorithm for the Fixed-Charge Transportation Problem," Management Science, INFORMS, vol. 22(10), pages 1116-1126, June.
    5. Andreas Stenger & Daniele Vigo & Steffen Enz & Michael Schwind, 2013. "An Adaptive Variable Neighborhood Search Algorithm for a Vehicle Routing Problem Arising in Small Package Shipping," Transportation Science, INFORMS, vol. 47(1), pages 64-80, February.
    6. Guglielmo Lulli & Suvrajeet Sen, 2004. "A Branch-and-Price Algorithm for Multistage Stochastic Integer Programming with Application to Stochastic Batch-Sizing Problems," Management Science, INFORMS, vol. 50(6), pages 786-796, June.
    7. Adlakha, Veena & Kowalski, Krzysztof & Lev, Benjamin, 2010. "A branching method for the fixed charge transportation problem," Omega, Elsevier, vol. 38(5), pages 393-397, October.
    8. Yogesh Agarwal & Yash Aneja, 2012. "Fixed-Charge Transportation Problem: Facets of the Projection Polyhedron," Operations Research, INFORMS, vol. 60(3), pages 638-654, June.
    9. Christian Valente & Gautam Mitra & Mustapha Sadki & Robert Fourer, 2009. "Extending Algebraic Modelling Languages for Stochastic Programming," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 107-122, February.
    10. Dimitri J. Papageorgiou & Alejandro Toriello & George L. Nemhauser & Martin W. P. Savelsbergh, 2012. "Fixed-Charge Transportation with Product Blending," Transportation Science, INFORMS, vol. 46(2), pages 281-295, May.
    11. Yossi Sheffi, 2004. "Combinatorial Auctions in the Procurement of Transportation Services," Interfaces, INFORMS, vol. 34(4), pages 245-252, August.
    12. Francesca Maggioni & Michal Kaut & Luca Bertazzi, 2009. "Stochastic optimization models for a single-sink transportation problem," Computational Management Science, Springer, vol. 6(2), pages 251-267, May.
    13. Francesca Maggioni & Elisabetta Allevi & Marida Bertocchi, 2016. "Monotonic bounds in multistage mixed-integer stochastic programming," Computational Management Science, Springer, vol. 13(3), pages 423-457, July.
    14. Kouwenberg, Roy, 2001. "Scenario generation and stochastic programming models for asset liability management," European Journal of Operational Research, Elsevier, vol. 134(2), pages 279-292, October.
    15. Gyana R. Parija & Shabbir Ahmed & Alan J. King, 2004. "On Bridging the Gap Between Stochastic Integer Programming and MIP Solver Technologies," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 73-83, February.
    16. Willem Klein Haneveld & Maarten van der Vlerk, 1999. "Stochastic integer programming:General models and algorithms," Annals of Operations Research, Springer, vol. 85(0), pages 39-57, January.
    17. Tue R. L. Christensen & Kim Allan Andersen & Andreas Klose, 2013. "Solving the Single-Sink, Fixed-Charge, Multiple-Choice Transportation Problem by Dynamic Programming," Transportation Science, INFORMS, vol. 47(3), pages 428-438, August.
    18. Côté, Jean-François & Potvin, Jean-Yves, 2009. "A tabu search heuristic for the vehicle routing problem with private fleet and common carrier," European Journal of Operational Research, Elsevier, vol. 198(2), pages 464-469, October.
    19. Ellis L. Johnson & George L. Nemhauser & Martin W.P. Savelsbergh, 2000. "Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition," INFORMS Journal on Computing, INFORMS, vol. 12(1), pages 2-23, February.
    20. John R. Birge, 1997. "State-of-the-Art-Survey---Stochastic Programming: Computation and Applications," INFORMS Journal on Computing, INFORMS, vol. 9(2), pages 111-133, May.
    21. Y. T. Herer & M. J. Rosenblatt & I. Hefter, 1996. "Fast Algorithms for Single-Sink Fixed Charge Transportation Problems with Applications to Manufacturing and Transportation," Transportation Science, INFORMS, vol. 30(4), pages 276-290, November.
    22. Giovanni Pantuso & Kjetil Fagerholt & Stein W. Wallace, 2015. "Solving Hierarchical Stochastic Programs: Application to the Maritime Fleet Renewal Problem," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 89-102, February.
    23. Suresh Chand & Vernon Ning Hsu & Suresh Sethi, 2002. "Forecast, Solution, and Rolling Horizons in Operations Management Problems: A Classified Bibliography," Manufacturing & Service Operations Management, INFORMS, vol. 4(1), pages 25-43, September.
    24. Paul Gray, 1971. "Technical Note—Exact Solution of the Fixed-Charge Transportation Problem," Operations Research, INFORMS, vol. 19(6), pages 1529-1538, October.
    25. M-C Bolduc & J Renaud & F Boctor & G Laporte, 2008. "A perturbation metaheuristic for the vehicle routing problem with private fleet and common carriers," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(6), pages 776-787, June.
    26. M. I. Kusy & W. T. Ziemba, 1986. "A Bank Asset and Liability Management Model," Operations Research, INFORMS, vol. 34(3), pages 356-376, June.
    27. Guigues, Vincent & Sagastizábal, Claudia, 2012. "The value of rolling-horizon policies for risk-averse hydro-thermal planning," European Journal of Operational Research, Elsevier, vol. 217(1), pages 129-140.
    28. Chu, Ching-Wu, 2005. "A heuristic algorithm for the truckload and less-than-truckload problem," European Journal of Operational Research, Elsevier, vol. 165(3), pages 657-667, September.
    29. Erika Buson & Roberto Roberti & Paolo Toth, 2014. "A Reduced-Cost Iterated Local Search Heuristic for the Fixed-Charge Transportation Problem," Operations Research, INFORMS, vol. 62(5), pages 1095-1106, October.
    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. Huang, Kai & An, Kun & Correia, Gonçalo Homem de Almeida, 2020. "Planning station capacity and fleet size of one-way electric carsharing systems with continuous state of charge functions," European Journal of Operational Research, Elsevier, vol. 287(3), pages 1075-1091.
    2. Gambella, Claudio & Maggioni, Francesca & Vigo, Daniele, 2019. "A stochastic programming model for a tactical solid waste management problem," European Journal of Operational Research, Elsevier, vol. 273(2), pages 684-694.

    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:eee:ejores:v:267:y:2018:i:2:p:555-569. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Haili He). General contact details of provider: http://www.elsevier.com/locate/eor .

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

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.