Manufacturing Technology 2021, 21(4):422-433 | DOI: 10.21062/mft.2021.054

Ant Colony Algorithms For The Vehicle Routing Problem With Time Window, Period And Multiple Depots

Anita Agárdi ORCID...1, László Kovács ORCID...2, Tamás Bányai ORCID...3
1 Institute of Informatics, University of Miskolc, Egyetemváros H-3515 Miskolc, Hungary
2 Institute of Informatics, University of Miskolc, Egyetemváros H-3515 Miskolc, Hungary
3 Institute of Logistics, University of Miskolc, Egyetemváros H-3515 Miskolc, Hungary

Vehicle Routing Problem is a common problem in logistics, which can simulate in-plant and out-plant material handling. In the article, we demonstrate a Vehicle Routing Problem, which contains period, time window and multiple depots. In this case, customers must be served from several depots. The position of the nodes (depots and customers), the demand and time window of the customers are known in advance. The number and capacity constraint of vehicles are predefined. The vehicles leave from one depot, visit some customers and then return to the depot. The above-described vehicle routing is solved with construction algorithms and Ant Colony algorithms. The Ant Colony algorithms are used to improve random solutions and solutions generated with construction algorithms. According to the test results the Elitist Strategy Ant System and the Rank-Based Version of Ant System algorithms gave the best solutions.

Keywords: vehicle routing problem, ant colony algorithms, improvement algorithms, construction algorithms

Received: January 4, 2021; Revised: April 16, 2021; Accepted: May 5, 2021; Prepublished online: July 4, 2021; Published: September 18, 2021  Show citation

ACS AIP APA ASA Harvard Chicago IEEE ISO690 MLA NLM Turabian Vancouver
Agárdi A, Kovács L, Bányai T. Ant Colony Algorithms For The Vehicle Routing Problem With Time Window, Period And Multiple Depots. Manufacturing Technology. 2021;21(4):422-433. doi: 10.21062/mft.2021.054.
Share...
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    References

    1. TOTH, P., & VIGO, D. (2002). The vehicle routing problem. Society for Industrial and Applied Mathematics Go to original source...
    2. NAGY, G., & SALHI, S. (2005). Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European journal of operational research, 162(1), pp. 126-141 Go to original source...
    3. CREVIER, B., CORDEAU, J. F., & LAPORTE, G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research, 176(2), pp. 756-773 Go to original source...
    4. LI, F., GOLDEN, B., & WASIL, E. (2007). The open vehicle routing problem: Algorithms, large-scale test problems, and computational results. Computers & operations research, 34(10), pp. 2918-2930. Go to original source...
    5. MARINELLI, M., COLOVIC, A., & DELL'ORCO, M. (2018). A novel dynamic programming approach for two-echelon capacitated vehicle routing problem in city logistics with environmental considerations. Transportation research procedia, 30, 147-156. Go to original source...
    6. BRUGLIERI, M., PEZZELLA, F., PISACANE, O., & SURACI, S. (2015). A Variable Neighborhood Search Branching for the Electric Vehicle Routing Problem with Time Windows. Electron. Notes Discret. Math., 47, 221-228. Go to original source...
    7. MIN, H. (1989). The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 23(5), pp. 377-386. Go to original source...
    8. CAMPBELL, A. M., & WILSON, J. H. (2014). Forty years of periodic vehicle routing. Networks, 63(1), 2-15. Go to original source...
    9. LIU, F. H., & SHEN, S. Y. (1999). The fleet size and mix vehicle routing problem with time windows. Journal of the Operational Research society, 50(7), 721-732. Go to original source...
    10. TAŞ, D., DELLAERT, N., VAN WOENSEL, T., & DE KOK, T. (2014). The time-dependent vehicle routing problem with soft time windows and stochastic travel times. Transportation Research Part C: Emerging Technologies, 48, 66-83. Go to original source...
    11. CALVETE, H. I., GALÉ, C., OLIVEROS, M. J., & SÁNCHEZ-VALVERDE, B. (2007). A goal programming approach to vehicle routing problems with soft time windows. European Journal of Operational Research, 177(3), 1720-1733. Go to original source...
    12. BERTSIMAS, D. J. (1992). A vehicle routing problem with stochastic demand. Operations Research, 40(3), 574-585. Go to original source...
    13. CAO, E., & LAI, M. (2010). The open vehicle routing problem with fuzzy demands. Expert Systems with Applications, 37(3), 2405-2411. Go to original source...
    14. NGUEVEU, S. U., PRINS, C., & CALVO, R. W. (2010). An effective memetic algorithm for the cumulative capacitated vehicle routing problem. Computers & Operations Research, 37(11), 1877-1885. Go to original source...
    15. MOUSAVI, S. M., VAHDANI, B., TAVAKKOLI-MOGHADDAM, R., & HASHEMI, H. (2014). Location of cross-docking centers and vehicle routing scheduling under uncertainty: A fuzzy possibilistic-stochastic programming model. Applied Mathematical Modelling, 38(7-8), 2249-2264. Go to original source...
    16. SCHWARZE, S. (2016). Pricing strategies for the site-dependent vehicle routing problem. OR spectrum, 38(1), 137-173. Go to original source...
    17. ARAS, N., AKSEN, D., & TEKIN, M. T. (2011). Selective multi-depot vehicle routing problem with pricing. Transportation Research Part C: Emerging Technologies, 19(5), 866-884. Go to original source...
    18. GRANGIER, P., GENDREAU, M., LEHUÉDÉ, F., & ROUSSEAU, L. M. (2016). An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization. European Journal of Operational Research, 254(1), 80-91. Go to original source...
    19. MAŃDZIUK, J., & ¦WIECHOWSKI, M. (2017). UCT in capacitated vehicle routing problem with traffic jams. Information Sciences, 406, 42-56. Go to original source...
    20. BRUGLIERI, M., PEZZELLA, F., PISACANE, O., & SURACI, S. (2015). A variable neighborhood search branching for the electric vehicle routing problem with time windows. Electronic Notes in Discrete Mathematics, 47, 221-228. Go to original source...
    21. CHEN, H. K., HSUEH, C. F., & CHANG, M. S. (2009). Production scheduling and vehicle routing with time windows for perishable food products. Computers & operations research, 36(7), 2311-2319. Go to original source...
    22. KELLNER, T., KYNCL, J., PITRMUC, Z., BERANEK, L., KANAK, M., & KYNCL, M. (2019). Pro-duction process planning in Additive manufacturing and conventional machining technology manufacturing system. Manufacturing Technology, 19(2), 232-237. Go to original source...
    23. MODROVSKÝ, R. (2019). Optimization of Production Flow through the CRAFT Method. Manufacturing Technology, 19(1), 114-117. Go to original source...
    24. YOSHIZAKI, H. T. Y. (2009). Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil. European Journal of Operational Research, 199(3), 750-758. Go to original source...
    25. PRINS, C., LACOMME, P., & PRODHON, C. (2014). Order-first split-second methods for vehicle routing problems: A review. Transportation Research Part C: Emerging Technologies, 40, 179-200. Go to original source...
    26. KIZILATEŞ, G., & NURIYEVA, F. (2013). On the nearest neighbor algorithms for the traveling salesman problem. In Advances in Computational Science, Engineering and Information Technology, pp. 111-118. Spring-er, Heidelberg. Go to original source...
    27. HAHSLER, M., & HORNIK, K. (2007). TSP-Infrastructure for the traveling salesperson problem. Journal of Statistical Software, 23(2), pp.1-21. Go to original source...
    28. NILSSON, C. (2003). Heuristics for the traveling salesman problem. Linkoping University, pp.1-6.
    29. KANTOR, M., CHALUPA, M., SOUČEK, J., BÍLKOVÁ, E., NOWAK, P. (2020). Application of Genetic Algorithm Methods for Water Turbine Blade Shape Optimization, Manufacturing Technology, 20(4), 453-458. Go to original source...
    30. ZHANG, W., HOU, L., GAN, Y., XU, C., BU, X., LIN, H. (2019). Parallel Optimization of the Balancing and Sequencing for Mixed-model Assembly Lines, Manufacturing Technology, 19(3), 537-544. Go to original source...
    31. STÜTZLE, T., & DORIGO, M. (1999). ACO algorithms for the traveling salesman problem. Evolutionary algorithms in engineering and computer science
    32. BULLNHEIMER, B., HARTL, R. F., & STRAUSS, C. (1997). A new rank based version of the Ant System. A computational study

    This is an open access article distributed under the terms of the Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0), which permits non-comercial use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content