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

Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns

Author

Listed:
  • Tatarakis, A.
  • Minis, I.

Abstract

We study the routing of a single vehicle that delivers multiple products under stochastic demand. Specifically, we investigate two practical variations of this problem: (i) The case in which each product type is stored in its dedicated compartment in the vehicle, and (ii) the case in which all products are stored together in the vehicle's single compartment. Suitable dynamic programming algorithms are proposed to determine the minimum expected (routing) cost for each case. Furthermore, the optimal routing policy is derived by developing appropriate theorems. The efficiency of the algorithms is studied by solving large problem sets.

Suggested Citation

  • Tatarakis, A. & Minis, I., 2009. "Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns," European Journal of Operational Research, Elsevier, vol. 197(2), pages 557-571, September.
    • Handle: RePEc:eee:ejores:v:197:y:2009:i:2:p:557-571
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00502-X
    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. Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
    2. Michel Gendreau & Gilbert Laporte & Alain Hertz, 1997. "An Approximation Algorithm for the Traveling Salesman Problem with Backhauls," Operations Research, INFORMS, vol. 45(4), pages 639-641, August.
    3. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    4. CORNUEJOLS, Gérard & NEMHAUSER, George L., 1978. "Tight bounds for Christofides' traveling salesman heuristic," LIDAM Reprints CORE 327, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    6. Dimitris J. Bertsimas, 1992. "A Vehicle Routing Problem with Stochastic Demand," Operations Research, INFORMS, vol. 40(3), pages 574-585, June.
    7. Nicola Secomandi, 2001. "A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 49(5), pages 796-802, October.
    8. Wen-Huei Yang & Kamlesh Mathur & Ronald H. Ballou, 2000. "Stochastic Vehicle Routing Problem with Restocking," Transportation Science, INFORMS, vol. 34(1), pages 99-112, February.
    9. Pierre Trudeau & Moshe Dror, 1992. "Stochastic Inventory Routing: Route Design with Stockouts and Route Failures," Transportation Science, INFORMS, vol. 26(3), pages 171-184, August.
    10. Moshe Dror & Gilbert Laporte & Pierre Trudeau, 1989. "Vehicle Routing with Stochastic Demands: Properties and Solution Frameworks," Transportation Science, INFORMS, vol. 23(3), pages 166-176, August.
    11. Dror, Moshe, 1993. "Modeling vehicle routing with uncertain demands as a stochastic program: Properties of the corresponding solution," European Journal of Operational Research, Elsevier, vol. 64(3), pages 432-441, February.
    12. Tsirimpas, P. & Tatarakis, A. & Minis, I. & Kyriakidis, E.G., 2008. "Single vehicle routing with a predefined customer sequence and multiple depot returns," European Journal of Operational Research, Elsevier, vol. 187(2), pages 483-495, June.
    13. Laporte, Gilbert & Louveaux, Francois & Mercure, Helene, 1989. "Models and exact solutions for a class of stochastic location-routing problems," European Journal of Operational Research, Elsevier, vol. 39(1), pages 71-78, March.
    14. Stewart, William R. & Golden, Bruce L., 1983. "Stochastic vehicle routing: A comprehensive approach," European Journal of Operational Research, Elsevier, vol. 14(4), pages 371-385, December.
    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. Jin, Ming & Li, Gang & Cheng, T.C.E., 2018. "Buy online and pick up in-store: Design of the service area," European Journal of Operational Research, Elsevier, vol. 268(2), pages 613-623.
    2. Dimitrakos, T.D. & Kyriakidis, E.G., 2015. "A single vehicle routing problem with pickups and deliveries, continuous random demands and predefined customer order," European Journal of Operational Research, Elsevier, vol. 244(3), pages 990-993.
    3. Epaminondas G. Kyriakidis & Theodosis D. Dimitrakos & Constantinos C. Karamatsoukis, 2020. "A Stochastic Single Vehicle Routing Problem with a Predefined Sequence of Customers and Collection of Two Similar Materials," Methodology and Computing in Applied Probability, Springer, vol. 22(4), pages 1559-1582, December.
    4. Zhang, Junlong & Lam, William H.K. & Chen, Bi Yu, 2016. "On-time delivery probabilistic models for the vehicle routing problem with stochastic demands and time windows," European Journal of Operational Research, Elsevier, vol. 249(1), pages 144-154.
    5. Goodson, Justin C., 2015. "A priori policy evaluation and cyclic-order-based simulated annealing for the multi-compartment vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 241(2), pages 361-369.
    6. Florio, Alexandre M. & Hartl, Richard F. & Minner, Stefan, 2020. "Optimal a priori tour and restocking policy for the single-vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 285(1), pages 172-182.
    7. Justin C. Goodson & Barrett W. Thomas & Jeffrey W. Ohlmann, 2016. "Restocking-Based Rollout Policies for the Vehicle Routing Problem with Stochastic Demand and Duration Limits," Transportation Science, INFORMS, vol. 50(2), pages 591-607, May.
    8. Pandelis, D.G. & Kyriakidis, E.G. & Dimitrakos, T.D., 2012. "Single vehicle routing problems with a predefined customer sequence, compartmentalized load and stochastic demands," European Journal of Operational Research, Elsevier, vol. 217(2), pages 324-332.
    9. Kyriakidis, Epaminondas G. & Dimitrakos, Theodosis D. & Karamatsoukis, Constantinos C., 2019. "Optimal delivery of two similar products to N ordered customers with product preferences," International Journal of Production Economics, Elsevier, vol. 209(C), pages 194-204.
    10. Pandelis, D.G. & Karamatsoukis, C.C. & Kyriakidis, E.G., 2013. "Finite and infinite-horizon single vehicle routing problems with a predefined customer sequence and pickup and delivery," European Journal of Operational Research, Elsevier, vol. 231(3), pages 577-586.
    11. Jorge E. Mendoza & Bruno Castanier & Christelle Guéret & Andrés L. Medaglia & Nubia Velasco, 2011. "Constructive Heuristics for the Multicompartment Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 45(3), pages 346-363, August.
    12. Minis, I. & Tatarakis, A., 2011. "Stochastic single vehicle routing problem with delivery and pick up and a predefined customer sequence," European Journal of Operational Research, Elsevier, vol. 213(1), pages 37-51, August.

    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. Prasanna Balaprakash & Mauro Birattari & Thomas Stützle & Marco Dorigo, 2015. "Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers," Computational Optimization and Applications, Springer, vol. 61(2), pages 463-487, June.
    2. Alan L. Erera & Juan C. Morales & Martin Savelsbergh, 2010. "The Vehicle Routing Problem with Stochastic Demand and Duration Constraints," Transportation Science, INFORMS, vol. 44(4), pages 474-492, November.
    3. Florio, Alexandre M. & Hartl, Richard F. & Minner, Stefan, 2020. "Optimal a priori tour and restocking policy for the single-vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 285(1), pages 172-182.
    4. Nicola Secomandi & François Margot, 2009. "Reoptimization Approaches for the Vehicle-Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 57(1), pages 214-230, February.
    5. Novoa, Clara & Storer, Robert, 2009. "An approximate dynamic programming approach for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 196(2), pages 509-515, July.
    6. Ann M. Campbell & Barrett W. Thomas, 2008. "Probabilistic Traveling Salesman Problem with Deadlines," Transportation Science, INFORMS, vol. 42(1), pages 1-21, February.
    7. Bertazzi, Luca & Secomandi, Nicola, 2018. "Faster rollout search for the vehicle routing problem with stochastic demands and restocking," European Journal of Operational Research, Elsevier, vol. 270(2), pages 487-497.
    8. Minis, I. & Tatarakis, A., 2011. "Stochastic single vehicle routing problem with delivery and pick up and a predefined customer sequence," European Journal of Operational Research, Elsevier, vol. 213(1), pages 37-51, August.
    9. Zhang, Junlong & Lam, William H.K. & Chen, Bi Yu, 2016. "On-time delivery probabilistic models for the vehicle routing problem with stochastic demands and time windows," European Journal of Operational Research, Elsevier, vol. 249(1), pages 144-154.
    10. Luo, Zhixing & Qin, Hu & Zhang, Dezhi & Lim, Andrew, 2016. "Adaptive large neighborhood search heuristics for the vehicle routing problem with stochastic demands and weight-related cost," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 85(C), pages 69-89.
    11. Wen-Huei Yang & Kamlesh Mathur & Ronald H. Ballou, 2000. "Stochastic Vehicle Routing Problem with Restocking," Transportation Science, INFORMS, vol. 34(1), pages 99-112, February.
    12. Astrid S. Kenyon & David P. Morton, 2003. "Stochastic Vehicle Routing with Random Travel Times," Transportation Science, INFORMS, vol. 37(1), pages 69-82, February.
    13. Walter Rei & Michel Gendreau & Patrick Soriano, 2010. "A Hybrid Monte Carlo Local Branching Algorithm for the Single Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 44(1), pages 136-146, February.
    14. Krishna Chepuri & Tito Homem-de-Mello, 2005. "Solving the Vehicle Routing Problem with Stochastic Demands using the Cross-Entropy Method," Annals of Operations Research, Springer, vol. 134(1), pages 153-181, February.
    15. F. Hooshmand Khaligh & S.A. MirHassani, 2016. "A mathematical model for vehicle routing problem under endogenous uncertainty," International Journal of Production Research, Taylor & Francis Journals, vol. 54(2), pages 579-590, January.
    16. Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
    17. Nicola Secomandi, 2001. "A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 49(5), pages 796-802, October.
    18. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2017. "The stochastic vehicle routing problem, a literature review, Part II: solution methods," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 349-388, December.
    19. Shahparvari, Shahrooz & Abbasi, Babak & Chhetri, Prem, 2017. "Possibilistic scheduling routing for short-notice bushfire emergency evacuation under uncertainties: An Australian case study," Omega, Elsevier, vol. 72(C), pages 96-117.
    20. Aykagan Ak & Alan L. Erera, 2007. "A Paired-Vehicle Recourse Strategy for the Vehicle-Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 41(2), pages 222-237, May.

    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:197:y:2009:i:2:p:557-571. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.