Acta Univ. Agric. Silvic. Mendelianae Brun. 2013, 61(7), 2393-2401 | DOI: 10.11118/actaun201361072393

Contribution of simple heuristics for the vehicle routing problem - A case study of a small brewery

Petr Kučera, Igor Krejčí
Department of Systems Engineering, Faculty of Economics and Management, Czech University of Life Sciences Prague, Kamýcká 129, 165 21 Praha, Czech Republic

This paper presents a case study of a local brewery situated near to Prague. Even though its management already has the software which solves the vehicle routing problem by Mayer and Branch and Bound methods, it is still favourable to implement more approximation methods. The basic reason is that the Branch and Bound algorithm is complicated and software overflows may occur during its run in case of more cities in the cycle. The aim of this paper is to solve the real transportations using other methods that satisfy basic requirements of practicability.
Transportation, which the brewery carried out during the selected week, provided data which were then analyzed using both the modifications of "classical" approximation methods (such as by Clark and Wright, Habr, and Mayer). Three types of the combination of these methods were also applied. The computed results were compared with the routes actually used by the brewery and with results from already implemented software. They showed that the brewery can save approximately 50,000 CZK (2,000 EUR) per year. Furthermore, the application of these methods needs neither any special technical equipment nor much time for the computation.

Keywords: vehicle routing problem, case study, Mayer method, savings method, Habr frequencies, methods crossing

Received: August 28, 2013; Published: December 24, 2013  Show citation

ACS AIP APA ASA Harvard Chicago IEEE ISO690 MLA NLM Turabian Vancouver
Kučera, P., & Krejčí, I. (2013). Contribution of simple heuristics for the vehicle routing problem - A case study of a small brewery. Acta Universitatis Agriculturae et Silviculturae Mendelianae Brunensis, 61(7), 2393-2401. doi: 10.11118/actaun201361072393
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. APPLEGATE, D. L., BIXBY, R. E., CHVÁTAL, V. COOK, W. J., 2006: The Travelling Salesman Problem: A Computational Study, Princeton: Princeton University Press, 593 s. ISBN 978-0-691-12993-8.
    2. BRAUN, H., 1991: On Solving Travelling Salesman Problems by Genetic Algorithms. Lecture Notes in Computer Science, 496: 129-133. ISSN 0302-9743. DOI: 10.1007/BFb0029743 Go to original source...
    3. BRÄYSY, O., DULLAERT, W., NAKARI, P., 2009: The Potential of Optimization in Communal Routing Problems: Case Studies from Finland. Journal of Transport Geography, 17, 6: 484-490. ISSN 0966-6923. DOI: 10.1016/j.jtrangeo.2008.10.003 Go to original source...
    4. BRÄYSY, O., NAKARI, P., DULLAERT, W., NEITTAANMÄKI, P., 2009: An Optimization Approach for Communal Home Meal Delivery Service: A Case Study. Journal of Computational and Applied Mathematics, 232, 1: 46-53. ISSN 0377-0427. DOI: 10.1016/j.cam.2008.10.038 Go to original source...
    5. CLARKE, G., WRIGHT, J. W., 1964: Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12, 4: 568-581. ISSN 0030-364X. DOI: 10.1287/opre.12.4.568 Go to original source...
    6. EUROPEAN COMMISSION, 2013: What is an SME? - Small and medium sized enterprises (SME) - enterprise and industry, [online] [21. 6. 2013] European Commission, Available: http://ec.europa.eu/enterprise/policies/sme/facts-figures-analysis/sme-definition/index_en.htm.
    7. GILLET, B., MILLER, L. 1974: A Heuristics Algorithm for Vehicle Dispatching Problem. Operations Research, 22: 340-349. ISSN 0030-364X. DOI: 10.1287/opre.22.2.340 Go to original source...
    8. GUTIN, G., PUNNEN, A. P. (eds.), 2007: The Traveling Salesman Problem and Its Variations. New York: Springer, 830 s. ISBN 0-387-44459-9. Go to original source...
    9. HABR, J., 1966: Jednoduché optimalizační metody pro ekonomickou praxi. Prague: SNTL. 196 s.
    10. HADRAVA, J., 2013: Optimalizace dopravních tras mezi firmou a jejími dodavateli a zákazníky. Diploma Thesis. Czech University of Life Sciences Prague.
    11. HASLE, G., KLOSTER O., 2007: Industrial vehicle routing problems, in: G. Hasle, K. A. Lie, E. Quak (Eds.), Geometric Modelling, Numerical Simulation, and Optimization, Springer Verlag, pp. 391-426. ISBN 978-3-540-68783-2.
    12. KUČERA, P., 2012a: Different Versions Of The Savings Method For The Time Limited Vehicle Routing Problem. Acta univ. agric. et silvic. Mendel. Brun., 60, 7: 47-56. ISSN 1211-8516. DOI: 10.11118/actaun201260070171 Go to original source...
    13. KUČERA, P., 2012b: Solution of the Time Limited Vehicle Routing Problem by Different Approximation Methods Depending on the Number of Necessary Vehicles. In: Proceedings of the 30th International Conference on Mathematical Methods in Economics 2012. Karviná: Silesian university Opava, pp. 508-511. ISBN 978-80-7248-779-0.
    14. KUČERA, P., HOUŠKA, M., BERÁNKOVÁ, M., 2006: Methods for the Multipletours Traveling Salesman Problem Making the Final Solution in One Time. In: Proceedings of the 24th International Conference on Mathematical Methods in Economics 2006. Prague: Czech Society for Operations Research, Plzeň: University of West Bohemia, pp. 313-316. ISBN 978-80-7043-480-2.
    15. KUČERA, P., JARKOVSKÁ, M., 2010: The optimization of pastry delivery for NOPEK bakery in Vysoké Mýto. Agris On-line, 2, 4: 65-77. ISSN 1804-1930.
    16. PELIKÁN, J., 2006: A time limited vehicle routing problem. Komunikacie, 7, 3: 9-11. ISSN 1335-4205. Go to original source...
    17. PERZINA, R., 2011: Self-adaptive Genetic Algorithm for Solving Travelling Purchaser Problem. In: Proceedings of the 29th International Conference on Mathematical Methods in Economics 2011. Prague: Professional Publishing, pp. 545-550. ISBN 978-80-7431-058-4.
    18. PLEVNÝ, M., 2003: A Study on Optimization of the Municipal Refuse Collecting System. In: Proceedings of the 21st International Conference on Mathematical Methods in Economics 2003. Prague: Czech University of Life Sciences, pp. 209-213. ISBN 978-80-213-1046-9.
    19. POTVIN, J. Y., DUBE, D., ROBILLARD C., 1996: A hybrid approach to vehicle routing using neural networks and genetic algorithms. Applied Intelligence, 6, 3: 241-252. ISSN 0924-669X. DOI: 10.1007/BF00126629 Go to original source...
    20. ROSENKRANTZ, D. J., STEARNS, R. E., LEWIS, P. M. II., 1977: An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM Journal on Computing, 6: 563-581. ISSN 0097-5397 DOI: 10.1137/0206041 Go to original source...
    21. SOEHODHO, S., PRAMONO, 2003: Proposal of Distribution Route with VRP Method: A Case Study at Pertamina Depot, Plumpang. Proceedings of the Eastern Asia Society for Transportation Studies, 4: 1256-1267. ISSN 1348-5393.
    22. SUTHIKARNNARUNAI, N., 2008: A Sweep Algorithm for the Mix Fleet Vehicle Routing Problem. Proceedings of the International MultiConference of Engineers and Computer Scientists 2008 Vol II: pp. 1914-1919. ISBN 978-988-17012-1-3.
    23. THIELE, J. C., 2008: Beispielhafte Anwendung von Zwei Heuristischen Methoden der Tourenplanung für eine Imaginäres Zellstoffwerk. Allgemeine Forst und Jagdzeitung, 179, 2/3: 33-42. ISSN 0002-5852.
    24. TOTH, P. VIGO, D. (eds.), 2002: The Vehicle Routing Problem. Philadelphia: Society for Industrial and Applied Mathematics, 367 p. ISBN 0-89871-579-2.

    This is an open access article distributed under the terms of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY NC ND 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