IDEAS home Printed from https://ideas.repec.org/a/wly/jnddns/v2016y2016i1n2804525.html

An Inverse Robust Optimisation Approach for a Class of Vehicle Routing Problems under Uncertainty

Author

Listed:
  • Liang Sun
  • Bing Wang

Abstract

There is a trade‐off between the total penalty paid to customers (TPC) and the total transportation cost (TTC) in depot for vehicle routing problems under uncertainty (VRPU). The trade‐off refers to the fact that the TTC in depot inevitably increases when the TPC decreases and vice versa. With respect to this issue, the vehicle routing problem (VRP) with uncertain customer demand and travel time was studied to optimise the TPC and the TTC in depot. In addition, an inverse robust optimisation approach was proposed to solve this kind of VRPU by combining the ideas of inverse optimisation and robust optimisation so as to improve both the TPC and the TTC in depot. The method aimed to improve the corresponding TTC of the robust optimisation solution under the minimum TPC through minimising the adjustment of benchmark road transportation cost. According to the characteristics of the inverse robust optimisation model, a genetic algorithm (GA) and column generation algorithm are combined to solve the problem. Moreover, 39 test problems are solved by using an inverse robust optimisation approach: the results show that both the TPC and TTC obtained by using the inverse robust optimisation approach are less than those calculated using a robust optimisation approach.

Suggested Citation

  • Liang Sun & Bing Wang, 2016. "An Inverse Robust Optimisation Approach for a Class of Vehicle Routing Problems under Uncertainty," Discrete Dynamics in Nature and Society, John Wiley & Sons, vol. 2016(1).
    • Handle: RePEc:wly:jnddns:v:2016:y:2016:i:1:n:2804525
    DOI: 10.1155/2016/2804525
    as

    Download full text from publisher

    File URL: https://doi.org/10.1155/2016/2804525
    Download Restriction: no
    File URL: https://libkey.io/10.1155/2016/2804525?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. Tao Yao & Supreet Mandala & Byung Chung, 2009. "Evacuation Transportation Planning Under Uncertainty: A Robust Optimization Approach," Networks and Spatial Economics, Springer, vol. 9(2), pages 171-189, June.
    2. 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.
    3. 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.
    4. Shangyao Yan & Ching-Hui Tang, 2008. "An Integrated Framework for Intercity Bus Scheduling Under Stochastic Bus Travel Times," Transportation Science, INFORMS, vol. 42(3), pages 318-335, August.
    5. R. Montemanni & J. Barta & M. Mastrolilli & L. M. Gambardella, 2007. "The Robust Traveling Salesman Problem with Interval Data," Transportation Science, INFORMS, vol. 41(3), pages 366-381, August.
    6. 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.
    7. John M. Mulvey & Robert J. Vanderbei & Stavros A. Zenios, 1995. "Robust Optimization of Large-Scale Systems," Operations Research, INFORMS, vol. 43(2), pages 264-281, April.
    Full references (including those not matched with items on IDEAS)

    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. Santos, Maria João & Curcio, Eduardo & Mulati, Mauro Henrique & Amorim, Pedro & Miyazawa, Flávio Keidi, 2020. "A robust optimization approach for the vehicle routing problem with selective backhauls," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 136(C).
    3. Tomáš Režnar & Jan Martinovič & Kateřina Slaninová & Ekaterina Grakova & Vít Vondrák, 2017. "Probabilistic time-dependent vehicle routing problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 25(3), pages 545-560, September.
    4. Chen, Lijian & Chiang, Wen-Chyuan & Russell, Robert & Chen, Jun & Sun, Dengfeng, 2018. "The probabilistic vehicle routing problem with service guarantees," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 111(C), pages 149-164.
    5. Archetti, C. & Coelho, L.C. & Speranza, M.G. & Vansteenwegen, P., 2026. "Beyond fifty years of vehicle routing: Insights into the history and the future," European Journal of Operational Research, Elsevier, vol. 330(2), pages 355-372.
    6. Byung Chung & Tao Yao & Chi Xie & Andreas Thorsen, 2011. "Robust Optimization Model for a Dynamic Network Design Problem Under Demand Uncertainty," Networks and Spatial Economics, Springer, vol. 11(2), pages 371-389, June.
    7. Reusken, Meike & Laporte, Gilbert & Rohmer, Sonja U.K. & Cruijssen, Frans, 2024. "Vehicle routing with stochastic demand, service and waiting times — The case of food bank collection problems," European Journal of Operational Research, Elsevier, vol. 317(1), pages 111-127.
    8. Gabrel, Virginie & Murat, Cécile & Thiele, Aurélie, 2014. "Recent advances in robust optimization: An overview," European Journal of Operational Research, Elsevier, vol. 235(3), pages 471-483.
    9. Alexandre M. Florio & Richard F. Hartl & Stefan Minner & Juan-José Salazar-González, 2021. "A Branch-and-Price Algorithm for the Vehicle Routing Problem with Stochastic Demands and Probabilistic Duration Constraints," Transportation Science, INFORMS, vol. 55(1), pages 122-138, 1-2.
    10. Patrick Jaillet & Jin Qi & Melvyn Sim, 2016. "Routing Optimization Under Uncertainty," Operations Research, INFORMS, vol. 64(1), pages 186-200, February.
    11. Ampol Karoonsoontawong & Onwasa Kobkiattawin & Chi Xie, 2019. "Efficient Insertion Heuristic Algorithms for Multi-Trip Inventory Routing Problem with Time Windows, Shift Time Limits and Variable Delivery Time," Networks and Spatial Economics, Springer, vol. 19(2), pages 331-379, June.
    12. Alizadeh, Morteza & Amiri-Aref, Mehdi & Mustafee, Navonil & Matilal, Sumohon, 2019. "A robust stochastic Casualty Collection Points location problem," European Journal of Operational Research, Elsevier, vol. 279(3), pages 965-983.
    13. Biao Yuan & Ran Liu & Zhibin Jiang, 2015. "A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements," International Journal of Production Research, Taylor & Francis Journals, vol. 53(24), pages 7450-7464, December.
    14. Pedro Munari & Alfredo Moreno & Jonathan De La Vega & Douglas Alem & Jacek Gondzio & Reinaldo Morabito, 2019. "The Robust Vehicle Routing Problem with Time Windows: Compact Formulation and Branch-Price-and-Cut Method," Transportation Science, INFORMS, vol. 53(4), pages 1043-1066, July.
    15. Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
    16. 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.
    17. Hua Sun & Ziyou Gao & W. Szeto & Jiancheng Long & Fangxia Zhao, 2014. "A Distributionally Robust Joint Chance Constrained Optimization Model for the Dynamic Network Design Problem under Demand Uncertainty," Networks and Spatial Economics, Springer, vol. 14(3), pages 409-433, December.
    18. Yang Fengmei & Wang Yakun & Yuan Wenyan & Li Jian, 2014. "A Robust VRPHTW Model with Travel Time Uncertainty," Journal of Systems Science and Information, De Gruyter, vol. 2(4), pages 289-300, August.
    19. Zhang, Huili & An, Xuan & Chen, Cong & Wang, Nengmin & Tong, Weitian, 2025. "Data-driven robust two-stage ferry vehicle management at airports," Omega, Elsevier, vol. 133(C).
    20. Zhenzhen Zhang & Yu Zhang & Roberto Baldacci, 2024. "Generalized Riskiness Index in Vehicle Routing Under Uncertain Travel Times: Formulations, Properties, and Exact Solution Framework," Transportation Science, INFORMS, vol. 58(4), pages 761-780, July.

    More about this item

    Statistics

    Access and download statistics

    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:wly:jnddns:v:2016:y:2016:i:1:n:2804525. 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: Wiley Content Delivery (email available below). General contact details of provider: https://onlinelibrary.wiley.com/journal/3059 .

    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.