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

Abstract

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