№63-13

Solving the vehicle routing problem at the enterprise

T. Khomyak¹, N. Kokhanchyk¹, A. Malienko¹

¹ Dnipro University of Technology, Dnipro, Ukraine

Coll.res.pap.nat.min.univ. 2020, 63:145-155

https://doi.org/10.33271/crpnmu/63.145

Full text (PDF)

ABSTRACT

The purpose of the research is to solve the vehicle routing problem at the company LLC «Light» in order to find optimal routes for the transportation of goods to customers.

Research methods. To solve the problem, the Clark-Wright algorithm is used, which allows to effectively find a solution in thevehicle routing problem. It belongs to the number of approximate, iterative methods and can be used for the computer solution of the vehicle routing problem, the error of the solution does not exceed, on average, 5-10%. The advantages of the method are its simplicity, reliability and flexibility, which allows to take into account a number of additional factors that affect the final solution of the problem. This algorithm is based on ranking the sections of the path according to "kilometer gains" and then adding these sections to the final route. This allows to minimize the final distance of the route and, accordingly, the time for the delivery of goods.

The results. The work carried out a systematic analysis of the activities of the enterprise, identified the target tasks, the functional activities of each of the divisions of the enterprise and the interaction between them, information flows within the divisions and between them, objects external to the enterprise and external information influences, as well as regulatory and reference documentation, data according to the means and automation systems available at the enterprise. The formulation of the vehicle routing problemat the enterprise has beenformulated, a matrix of distances between customer cities has beenpresented, and three final routes wereobtained.

Scientific novelty. A mathematical model of the vehicle routing problem at the enterprise was obtained, the Clark-Wright algorithm was used to solve the problem, and software has beendeveloped.

The practical significance. The solution of the vehicle routing problem and the developed software according to the Clark-Wright algorithm allow finding the optimal routes for the delivery of goods to customers, which significantly reduces the material costs of the enterprise, as well as the time spent on transportation,and contributes to more efficient operation of the enterprise.

Keywords: system analysis, vehicle routing problem, Clark and Wright method.

References:

1. Alesinskaya, T.V. (2005). Osnovy logistiki. Obshchie voprosy logisticheskogo upravleniya: Uchebnoe posobie. Izd-vo TRTU.
2. Golden, B. ,Raghavan, S. , & Wasil, E. (2008).The vehicle routing problem: latest advances and new challenges.Springer.
3. Lonnie, D.(2007).Systems Analysis and Design for the Global Enterprise 7th Edition.McGraw-Hill.
4. Khomyak, T. V., Malienko, A. V., & Simonets, H. V. (2019). Application of smoothing methods for forecasting production volume. Bulletin of National Technical University “KhPI”. Series: System Analysis, Control and Information Technologies, 1, 8–12.
   https://doi.org/10.20998/2079-0023.2019.01.02
5. Khomyak, T., Malienko, A., & Fishbach, K. (2019). Developing support and decision-making system to select activity of the enterprise. Collection of Research Papers of the National Mining University, 59, 132–142.
   https://doi.org/10.33271/crpnmu/59.132
6. Shankar, R. B. S., Reddy, K. D., & Venkataramaiah, P. (2018). Solution to a capacitated vehicle routing problem using heuristics and firefly algorithm. International Journal of Applied Engineering Research, 13(21), 15247-15254.
7. Altınel, İ. K., & Öncan, T. (2005). A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem. Journal of the Operational Research Society, 56(8), 954–961.
   https://doi.org/10.1057/palgrave.jors.2601916