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

Satisficing measure approach for vehicle routing problem with time windows under uncertaintyAuthor-Name: Nguyen, V.A

Author

Listed:
  • Jiang, J.
  • Ng, K.M.
  • Teo, K.M.

Abstract

The complexity of evaluating chance constraints makes chance-constrained programming problem difficult to solve. One way to handle this complexity is by devising satisficing measures for the relevant uncertainties. This paper focuses on solving the stochastic vehicle routing problem with time windows (VRPTW) by Satisficing Measure Approach (SMA) that mitigates the dissatisfaction experienced by the customers. Satisficing measures are first proposed for the VRPTW with stochastic demand on various distributions to demonstrate the dependency of customers’ satisfaction towards lack of inventory based on the vehicle's capacity. Similar satisficing measures are extended to VRPTW with stochastic travel times. We integrate the proposed satisficing measures into an existing tabu-search heuristics to solve a set of generalized Solomon instances in a short amount of computation time. Compared with best-known results, the SMA saves the effort to design recourse actions, applicable to many popular probability distributions and produces very competitive results.

Suggested Citation

  • Jiang, J. & Ng, K.M. & Teo, K.M., 2016. "Satisficing measure approach for vehicle routing problem with time windows under uncertaintyAuthor-Name: Nguyen, V.A," European Journal of Operational Research, Elsevier, vol. 248(2), pages 404-414.
    • Handle: RePEc:eee:ejores:v:248:y:2016:i:2:p:404-414
    DOI: 10.1016/j.ejor.2015.07.041
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722171500675X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.07.041?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
    ---><---

    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. Gilbert Laporte & François Louveaux & Hélène Mercure, 1992. "The Vehicle Routing Problem with Stochastic Travel Times," Transportation Science, INFORMS, vol. 26(3), pages 161-170, August.
    3. Van Woensel, T. & Kerbache, L. & Peremans, H. & Vandaele, N., 2008. "Vehicle routing with dynamic travel times: A queueing approach," European Journal of Operational Research, Elsevier, vol. 186(3), pages 990-1007, May.
    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. Haugland, Dag & Ho, Sin C. & Laporte, Gilbert, 2007. "Designing delivery districts for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 180(3), pages 997-1010, August.
    6. Michel Gendreau & Gilbert Laporte & René Séguin, 1995. "An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers," Transportation Science, INFORMS, vol. 29(2), pages 143-155, May.
    7. 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.
    8. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    9. Naoki Ando & Eiichi Taniguchi, 2006. "Travel Time Reliability in Vehicle Routing and Scheduling with Time Windows," Networks and Spatial Economics, Springer, vol. 6(3), pages 293-311, September.
    10. Enrico Diecidue & Jeroen van de Ven, 2008. "Aspiration Level, Probability Of Success And Failure, And Expected Utility," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 49(2), pages 683-700, May.
    11. David B. Brown & Melvyn Sim, 2009. "Satisficing Measures for Analysis of Risky Positions," Management Science, INFORMS, vol. 55(1), pages 71-84, January.
    12. Laoucine Kerbache & T. van Woensel & N. Vandaele & Herbert Peremans, 2008. "Vehicle routing with dynamic travel times: A queueing approach," Post-Print hal-00465127, HAL.
    13. Li, Xiangyong & Tian, Peng & Leung, Stephen C.H., 2010. "Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm," International Journal of Production Economics, Elsevier, vol. 125(1), pages 137-145, May.
    14. 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.
    15. Dror, Moshe & Trudeau, Pierre, 1986. "Stochastic vehicle routing with modified savings algorithm," European Journal of Operational Research, Elsevier, vol. 23(2), pages 228-235, February.
    16. Astrid S. Kenyon & David P. Morton, 2003. "Stochastic Vehicle Routing with Random Travel Times," Transportation Science, INFORMS, vol. 37(1), pages 69-82, February.
    17. Frank A. Tillman, 1969. "The Multiple Terminal Delivery Problem with Probabilistic Demands," Transportation Science, INFORMS, vol. 3(3), pages 192-204, August.
    18. Lau, Hoong Chuin & Sim, Melvyn & Teo, Kwong Meng, 2003. "Vehicle routing problem with time windows and a limited number of vehicles," European Journal of Operational Research, Elsevier, vol. 148(3), pages 559-569, August.
    19. Michel Gendreau & Gilbert Laporte & René Séguin, 1996. "A Tabu Search Heuristic for the Vehicle Routing Problem with Stochastic Demands and Customers," Operations Research, INFORMS, vol. 44(3), pages 469-477, June.
    20. Gilbert Laporte & FranÇois V. Louveaux & Luc van Hamme, 2002. "An Integer L -Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 50(3), pages 415-423, June.
    21. Martin Branda, 2013. "On relations between chance constrained and penalty function problems under discrete distributions," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 77(2), pages 265-277, April.
    22. John W. Payne & Dan J. Laughhunn & Roy Crum, 1980. "Translation of Gambles and Aspiration Level Effects in Risky Choice Behavior," Management Science, INFORMS, vol. 26(10), pages 1039-1060, 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. 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.
    2. Mojtaba Rajabi-Bahaabadi & Afshin Shariat-Mohaymany & Mohsen Babaei & Daniele Vigo, 2021. "Reliable vehicle routing problem in stochastic networks with correlated travel times," Operational Research, Springer, vol. 21(1), pages 299-330, March.
    3. Guodong Yu & Yu Yang, 2019. "Dynamic routing with real-time traffic information," Operational Research, Springer, vol. 19(4), pages 1033-1058, December.
    4. Cheung, Ka Chun & Yam, Sheung Chi Phillip & Zhang, Yiying, 2022. "Satisficing credibility for heterogeneous risks," European Journal of Operational Research, Elsevier, vol. 298(2), pages 752-768.
    5. 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.

    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. 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.
    2. 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.
    3. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2018. "The stochastic vehicle routing problem, a literature review, part I: models," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 193-221, September.
    4. 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.
    5. Jinil Han & Chungmok Lee & Sungsoo Park, 2014. "A Robust Scenario Approach for the Vehicle Routing Problem with Uncertain Travel Times," Transportation Science, INFORMS, vol. 48(3), pages 373-390, August.
    6. Majid Salavati-Khoshghalb & Michel Gendreau & Ola Jabali & Walter Rei, 2019. "A hybrid recourse policy for the vehicle routing problem with stochastic demands," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 269-298, September.
    7. Mojtaba Rajabi-Bahaabadi & Afshin Shariat-Mohaymany & Mohsen Babaei & Daniele Vigo, 2021. "Reliable vehicle routing problem in stochastic networks with correlated travel times," Operational Research, Springer, vol. 21(1), pages 299-330, March.
    8. Goodson, Justin C. & Ohlmann, Jeffrey W. & Thomas, Barrett W., 2012. "Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand," European Journal of Operational Research, Elsevier, vol. 217(2), pages 312-323.
    9. Majid Salavati-Khoshghalb & Michel Gendreau & Ola Jabali & Walter Rei, 2019. "A Rule-Based Recourse for the Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 53(5), pages 1334-1353, September.
    10. Junlong Zhang & William Lam & Bi Chen, 2013. "A Stochastic Vehicle Routing Problem with Travel Time Uncertainty: Trade-Off Between Cost and Customer Service," Networks and Spatial Economics, Springer, vol. 13(4), pages 471-496, December.
    11. Chrysanthos E. Gounaris & Wolfram Wiesemann & Christodoulos A. Floudas, 2013. "The Robust Capacitated Vehicle Routing Problem Under Demand Uncertainty," Operations Research, INFORMS, vol. 61(3), pages 677-693, June.
    12. 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.
    13. Florent Hernandez & Michel Gendreau & Ola Jabali & Walter Rei, 2019. "A local branching matheuristic for the multi-vehicle routing problem with stochastic demands," Journal of Heuristics, Springer, vol. 25(2), pages 215-245, April.
    14. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    15. Li, Xiangyong & Tian, Peng & Leung, Stephen C.H., 2010. "Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm," International Journal of Production Economics, Elsevier, vol. 125(1), pages 137-145, May.
    16. 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.
    17. Seyedmehdi Mirmohammadsadeghi & Shamsuddin Ahmed, 2015. "Memetic Heuristic Approach for Solving Truck and Trailer Routing Problems with Stochastic Demands and Time Windows," Networks and Spatial Economics, Springer, vol. 15(4), pages 1093-1115, December.
    18. Norlund, Ellen Karoline & Gribkovskaia, Irina & Laporte, Gilbert, 2015. "Supply vessel planning under cost, environment and robustness considerations," Omega, Elsevier, vol. 57(PB), pages 271-281.
    19. F. Errico & G. Desaulniers & M. Gendreau & W. Rei & L.-M. Rousseau, 2018. "The vehicle routing problem with hard time windows and stochastic service times," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 223-251, September.
    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:248:y:2016:i:2:p:404-414. 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.