IDEAS home Printed from https://ideas.repec.org/a/gam/jsusta/v12y2020i9p3666-d353063.html
   My bibliography  Save this article

An Adapted Version of the Water Wave Optimization Algorithm for the Capacitated Vehicle Routing Problem with Time Windows with Application to a Real Case Using Probe Data

Author

Listed:
  • Letizia Tebaldi

    (Department of Engineering and Architecture, University of Parma, viale delle Scienze 181/A, 43124 Parma, Italy)

  • Teresa Murino

    (Department of Chemical, Materials and Industrial Production Engineering, University of Naples “Federico II”, Piazzale Tecchio 80, 80125 Napoli, Italy)

  • Eleonora Bottani

    (Department of Engineering and Architecture, University of Parma, viale delle Scienze 181/A, 43124 Parma, Italy)

Abstract

Customers’ habits, as far as shipping requests are concerned, have changed in the last decade, due to the fast spread of e-commerce and business to consumer (B2C) systems, thus generating more and more vehicles on the road, traffic congestion and, consequently, more pollution. Trying to partially solve this problem, the operational research field dedicates part of its research to possible ways to optimize transports in terms of costs, travel times, full loads etc., with the aim of reducing inefficiencies and impacts on profit, planet and people, i.e., the well-known triple bottom line approach to sustainability, also thanks to new technologies able to instantly provide probe data, which can detail information as far as the vehicle behavior. In line with this, an adapted version of the metaheuristic water wave optimization algorithm is here presented and applied to the context of the capacitated vehicle routing problem with time windows. This latter one is a particular case of the vehicle routing problem, whose aim is to define the best route in terms of travel time for visiting a set of customers, given the vehicles capacity and time constraints in which some customers need to be visited. The algorithm is then tested on a real case study of an express courier operating in the South of Italy. A nearest neighbor heuristic is applied, as well, to the same set of data, to test the effectiveness and accuracy of the algorithm. Results show a better performance of the proposed metaheuristic, which could improve the journeys by reducing the travel time by up to 23.64%.

Suggested Citation

  • Letizia Tebaldi & Teresa Murino & Eleonora Bottani, 2020. "An Adapted Version of the Water Wave Optimization Algorithm for the Capacitated Vehicle Routing Problem with Time Windows with Application to a Real Case Using Probe Data," Sustainability, MDPI, vol. 12(9), pages 1-13, May.
    • Handle: RePEc:gam:jsusta:v:12:y:2020:i:9:p:3666-:d:353063
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2071-1050/12/9/3666/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2071-1050/12/9/3666/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Richard Pomfret, 2011. "Trade and Transport in Central Asia," Book Chapters, in: Werner Hermann & Johannes F. Linn (ed.), Central Asia and the Caucasus: At the Crossroads of Eurasia in the 21st Century, chapter 3, pages 43–62, Emerging Markets Forum.
    2. Mishchenko S. P., 2011. "Economic security of rail transport," Вісник економіки транспорту і промисловості, CyberLeninka;Украинская государственная академия железнодорожного транспорта, issue 34, pages 206-209.
    3. 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.
    4. Kalinichenko L. L., 2011. "Innovation policy railway transport of Ukraine," Вісник економіки транспорту і промисловості, CyberLeninka;Украинская государственная академия железнодорожного транспорта, issue 36, pages 314-318.
    5. Itf, 2011. "Meeting Society's Transport Needs under Tight Budgets," International Transport Forum Discussion Papers 2011/10, OECD Publishing.
    6. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    7. Kucheruk G. Y., 2011. "Place of transportation services in logistics systems," Вісник економіки транспорту і промисловості, CyberLeninka;Украинская государственная академия железнодорожного транспорта, issue 36, pages 66-71.
    8. Todd Litman & David Burwell, 2006. "Issues in sustainable transportation," International Journal of Global Environmental Issues, Inderscience Enterprises Ltd, vol. 6(4), pages 331-347.
    9. Baldacci, Roberto & Mingozzi, Aristide & Roberti, Roberto, 2012. "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints," European Journal of Operational Research, Elsevier, vol. 218(1), pages 1-6.
    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. Diana Puspita Sari & Nur Aini Masruroh & Anna Maria Sri Asih, 2021. "Extended Maximal Covering Location and Vehicle Routing Problems in Designing Smartphone Waste Collection Channels: A Case Study of Yogyakarta Province, Indonesia," Sustainability, MDPI, vol. 13(16), pages 1-23, August.
    2. Andrej David & Peter Mako & Jan Lizbetin & Patrik Bohm, 2021. "The Impact of an Environmental Way of Customer’s Thinking on a Range of Choice from Transport Routes in Maritime Transport," Sustainability, MDPI, vol. 13(3), pages 1-23, January.

    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. Achillas, Ch. & Aidonis, D. & Vlachokostas, Ch. & Moussiopoulos, N. & Banias, G. & Triantafillou, D., 2012. "A multi-objective decision-making model to select waste electrical and electronic equipment transportation media," Resources, Conservation & Recycling, Elsevier, vol. 66(C), pages 76-84.
    2. Runfeng Yu & Lifen Yun & Chen Chen & Yuanjie Tang & Hongqiang Fan & Yi Qin, 2023. "Vehicle Routing Optimization for Vaccine Distribution Considering Reducing Energy Consumption," Sustainability, MDPI, vol. 15(2), pages 1-24, January.
    3. Gilbert Laporte, 2016. "Scheduling issues in vehicle routing," Annals of Operations Research, Springer, vol. 236(2), pages 463-474, January.
    4. Aderemi Oluyinka Adewumi & Olawale Joshua Adeleke, 2018. "A survey of recent advances in vehicle routing problems," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 9(1), pages 155-172, February.
    5. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    6. Gilbert Laporte, 2016. "Scheduling issues in vehicle routing," Annals of Operations Research, Springer, vol. 236(2), pages 463-474, January.
    7. Yu Zhang & Zhenzhen Zhang & Andrew Lim & Melvyn Sim, 2021. "Robust Data-Driven Vehicle Routing with Time Windows," Operations Research, INFORMS, vol. 69(2), pages 469-485, March.
    8. Çetinkaya, Cihan & Karaoglan, Ismail & Gökçen, Hadi, 2013. "Two-stage vehicle routing problem with arc time windows: A mixed integer programming formulation and a heuristic approach," European Journal of Operational Research, Elsevier, vol. 230(3), pages 539-550.
    9. Débora P. Ronconi & João L. V. Manguino, 2025. "GRASP and VNS approaches for a vehicle routing problem with step cost functions," Annals of Operations Research, Springer, vol. 350(1), pages 37-62, July.
    10. Babagolzadeh, Mahla & Zhang, Yahua & Abbasi, Babak & Shrestha, Anup & Zhang, Anming, 2022. "Promoting Australian regional airports with subsidy schemes: Optimised downstream logistics using vehicle routing problem," Transport Policy, Elsevier, vol. 128(C), pages 38-51.
    11. Pradhananga, Rojee & Taniguchi, Eiichi & Yamada, Tadashi & Qureshi, Ali Gul, 2014. "Bi-objective decision support system for routing and scheduling of hazardous materials," Socio-Economic Planning Sciences, Elsevier, vol. 48(2), pages 135-148.
    12. Qi, Mingyao & Lin, Wei-Hua & Li, Nan & Miao, Lixin, 2012. "A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 248-257.
    13. Zhiping Zuo & Yanhui Li & Jing Fu & Jianlin Wu, 2019. "Human Resource Scheduling Model and Algorithm with Time Windows and Multi-Skill Constraints," Mathematics, MDPI, vol. 7(7), pages 1-18, July.
    14. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    15. Müller, Juliane, 2010. "Approximative solutions to the bicriterion Vehicle Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 202(1), pages 223-231, April.
    16. Racha El-Hajj & Rym Nesrine Guibadj & Aziz Moukrim & Mehdi Serairi, 2020. "A PSO based algorithm with an efficient optimal split procedure for the multiperiod vehicle routing problem with profit," Annals of Operations Research, Springer, vol. 291(1), pages 281-316, August.
    17. Liu, Yiming & Yu, Yang & Baldacci, Roberto & Tang, Jiafu & Sun, Wei, 2025. "Optimizing carbon emissions in green logistics for time-dependent routing," Transportation Research Part B: Methodological, Elsevier, vol. 192(C).
    18. 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.
    19. Ehmke, Jan Fabian & Campbell, Ann Melissa, 2014. "Customer acceptance mechanisms for home deliveries in metropolitan areas," European Journal of Operational Research, Elsevier, vol. 233(1), pages 193-207.
    20. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;

    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:gam:jsusta:v:12:y:2020:i:9:p:3666-:d:353063. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.