IDEAS home Printed from https://ideas.repec.org/a/wly/jnljam/v2013y2013i1n672078.html

Dynamic Vehicle Routing Using an Improved Variable Neighborhood Search Algorithm

Author

Listed:
  • Yingcheng Xu
  • Li Wang
  • Yuexiang Yang

Abstract

In order to effectively solve the dynamic vehicle routing problem with time windows, the mathematical model is established and an improved variable neighborhood search algorithm is proposed. In the algorithm, allocation customers and planning routes for the initial solution are completed by the clustering method. Hybrid operators of insert and exchange are used to achieve the shaking process, the later optimization process is presented to improve the solution space, and the best‐improvement strategy is adopted, which make the algorithm can achieve a better balance in the solution quality and running time. The idea of simulated annealing is introduced to take control of the acceptance of new solutions, and the influences of arrival time, distribution of geographical location, and time window range on route selection are analyzed. In the experiment, the proposed algorithm is applied to solve the different sizes′ problems of DVRP. Comparing to other algorithms on the results shows that the algorithm is effective and feasible.

Suggested Citation

  • Yingcheng Xu & Li Wang & Yuexiang Yang, 2013. "Dynamic Vehicle Routing Using an Improved Variable Neighborhood Search Algorithm," Journal of Applied Mathematics, John Wiley & Sons, vol. 2013(1).
    • Handle: RePEc:wly:jnljam:v:2013:y:2013:i:1:n:672078
    DOI: 10.1155/2013/672078
    as

    Download full text from publisher

    File URL: https://doi.org/10.1155/2013/672078
    Download Restriction: no
    File URL: https://libkey.io/10.1155/2013/672078?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. Michel Gendreau & Alain Hertz & Gilbert Laporte & Mihnea Stan, 1998. "A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows," Operations Research, INFORMS, vol. 46(3), pages 330-335, June.
    2. Éric Taillard & Philippe Badeau & Michel Gendreau & François Guertin & Jean-Yves Potvin, 1997. "A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows," Transportation Science, INFORMS, vol. 31(2), pages 170-186, May.
    3. Bernhard Fleischmann & Stefan Gnutzmann & Elke Sandvoß, 2004. "Dynamic Vehicle Routing Based on Online Traffic Information," Transportation Science, INFORMS, vol. 38(4), pages 420-433, November.
    4. Christophe Duhamel & Jean-Yves Potvin & Jean-Marc Rousseau, 1997. "A Tabu Search Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows," Transportation Science, INFORMS, vol. 31(1), pages 49-59, February.
    5. 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.
    6. R. Montemanni & L. M. Gambardella & A. E. Rizzoli & A. V. Donati, 2005. "Ant Colony System for a Dynamic Vehicle Routing Problem," Journal of Combinatorial Optimization, Springer, vol. 10(4), pages 327-343, 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. Yi Han & Ikou Kaku & Jianhu Cai & Yanlai Li & Chao Yang & Lili Deng, 2013. "Shuffled Frog Leaping Algorithm for Preemptive Project Scheduling Problems with Resource Vacations Based on Patterson Set," Journal of Applied Mathematics, John Wiley & Sons, vol. 2013(1).

    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. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    2. Briseida Sarasola & Karl Doerner & Verena Schmid & Enrique Alba, 2016. "Variable neighborhood search for the stochastic and dynamic vehicle routing problem," Annals of Operations Research, Springer, vol. 236(2), pages 425-461, January.
    3. Briseida Sarasola & Karl F. Doerner & Verena Schmid & Enrique Alba, 2016. "Variable neighborhood search for the stochastic and dynamic vehicle routing problem," Annals of Operations Research, Springer, vol. 236(2), pages 425-461, January.
    4. Joaquín Pacheco & Rafael Caballero & Manuel Laguna & Julián Molina, 2013. "Bi-Objective Bus Routing: An Application to School Buses in Rural Areas," Transportation Science, INFORMS, vol. 47(3), pages 397-411, August.
    5. Manuel Ostermeier & Andreas Holzapfel & Heinrich Kuhn & Daniel Schubert, 2022. "Integrated zone picking and vehicle routing operations with restricted intermediate storage," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(3), pages 795-832, September.
    6. Jose Carlos Molina & Ignacio Eguia & Jesus Racero, 2019. "Reducing pollutant emissions in a waste collection vehicle routing problem using a variable neighborhood tabu search algorithm: a case study," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 27(2), pages 253-287, July.
    7. Saint-Guillain, Michael & Paquay, Célia & Limbourg, Sabine, 2021. "Time-dependent stochastic vehicle routing problem with random requests: Application to online police patrol management in Brussels," European Journal of Operational Research, Elsevier, vol. 292(3), pages 869-885.
    8. Ostermeier, Manuel, 2024. "The supply of convenience stores: Challenges of short-distance routing within the constraints of working time regulations," European Journal of Operational Research, Elsevier, vol. 314(3), pages 997-1012.
    9. 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.
    10. Jeroen Beliën & Liesje De Boeck & Jonas Van Ackere, 2014. "Municipal Solid Waste Collection and Management Problems: A Literature Review," Transportation Science, INFORMS, vol. 48(1), pages 78-102, February.
    11. Zhen Wang & Jiazhen Huo & Jasmine Siu Lee Lam, 2025. "The vehicle routing programming of municipal solid waste collection under cognitive uncertainty," Transportation Journal, John Wiley & Sons, vol. 64(1), January.
    12. Maria João Santos & Pedro Amorim & Alexandra Marques & Ana Carvalho & Ana Póvoa, 2020. "The vehicle routing problem with backhauls towards a sustainability perspective: a review," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(2), pages 358-401, July.
    13. Kerscher, Christoph & Minner, Stefan, 2025. "Decompose-route-improve framework for solving large-scale vehicle routing problems with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 204(C).
    14. Campelo, Pedro & Neves-Moreira, Fábio & Amorim, Pedro & Almada-Lobo, Bernardo, 2019. "Consistent vehicle routing problem with service level agreements: A case study in the pharmaceutical distribution sector," European Journal of Operational Research, Elsevier, vol. 273(1), pages 131-145.
    15. Christos D. Tarantilis & Afroditi K. Anagnostopoulou & Panagiotis P. Repoussis, 2013. "Adaptive Path Relinking for Vehicle Routing and Scheduling Problems with Product Returns," Transportation Science, INFORMS, vol. 47(3), pages 356-379, August.
    16. Lagos, Felipe & Pereira, Jordi, 2024. "Multi-armed bandit-based hyper-heuristics for combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 312(1), pages 70-91.
    17. Cruijssen, F. & Braysy, O. & Dullaert, W. & Fleuren, H.A. & Salomon, M., 2006. "Joint Route Planning under Varying Market Conditions," Discussion Paper 2006-49, Tilburg University, Center for Economic Research.
    18. ARNOLD, Florian & SÖRENSEN, Kenneth, 2017. "A simple, deterministic, and efficient knowledge-driven heuristic for the vehicle routing problem," Working Papers 2017012, University of Antwerp, Faculty of Business and Economics.
    19. Olli Bräysy & Wout Dullaert & Geir Hasle & David Mester & Michel Gendreau, 2008. "An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle-Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 42(3), pages 371-386, August.
    20. Nasreddine Ouertani & Hajer Ben-Romdhane & Saoussen Krichen, 2022. "A decision support system for the dynamic hazardous materials vehicle routing problem," Operational Research, Springer, vol. 22(1), pages 551-576, March.

    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:jnljam:v:2013:y:2013:i:1:n:672078. 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/4185 .

    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.