ЭВОЛЮЦИОННЫЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ

V. A. Tenenev; A. S. Shaura; D. S. Shaura

doi:10.22213/2410-9304-2019-4-143-148

Authors

V. A. Tenenev
A. S. Shaura
D. S. Shaura

DOI:

https://doi.org/10.22213/2410-9304-2019-4-143-148

Keywords:

vehicle routing problem, genetic algorithm, fuzzy clustering, C-means, constrained discrete optimization

Abstract

In this paper we consider the vehicles routing problem, that is a generalization of the salesman problem. There are several basic routing models, each of which is characterized by additional constraints (vehicles capacity, transport fleet, delivery time, number of depot, etc.) and describes a group of real transport logistics tasks. This problem belongs to the class of NP-hard ones, and the presence of additional constraints makes its solution even more difficult.

The paper describes a two-step approach to optimal routing: at the first stage, all delivery points are distributed to geographic areas using fuzzy clustering methods, and at the second stage an optimal route is calculated using a genetic algorithm for each region and each vehicle. All constraints are taken into account when calculating fitness function and determine the feasibility and fitness of individuals of the population.

In practice, it is necessary to have a balanced distribution of consumers between different routes to evenly load the transport fleet and reduce the total delivery time, so in the presented algorithm after a preliminary assessment of duration of all routes, an additional procedure for cluster alignment is provided.

The implemented algorithm was successfully used to solve a routing problem in a real urban transport network.

References

Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

Applegate D.L., Bixby R.B., Chav´atal V. and Cook W.J. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006.

Pouya Baniasadi, Vladimir Ejov, Michael Haythorpe, and Serguei Rossomakhine. A new benchmark set for Traveling salesman problem and Hamiltonian cycle problem. 2018.

TSPLIB. library of sample instances for the TSP (and re-lated problems) from various sources and of various types. https://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/.

Dunn J. C. A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters, Journal of Cybernetics 3: 32-57, 1973.

Bezdek J. C. Pattern Recognition with Fuzzy Objective Function Algoritms, Plenum Press, New York. 1981.

Uzay Kaimak, Magne Setnes. Extended Fuzzy Clustering Algorithms. ERIM report series ERS-2000-51-LIS. Rotterdam, Netherlands, November 2000, 24 pp.

Akhand M. A. H., Sultana T, Shuvo M. I. R, Al-Mahmud. Constructive and Clustering Methods to Solve Capacitated Vehicle Routing Problem. Orient. J. Comp. Sci. and Technol;10 (3). 2017. DOI: http://dx.doi.org/10.13005/ojcst/10.03.02.

Благодатский Г. А., Тененев В. А., Шаура А. С. Численная реализация алгоритма управления запасами при длительных сроках поставки комплектующих в условиях «узких» мест производственного цикла // Интеллектуальные системы в производстве. 2016. № 4 (31). С. 40–44. DOI: 10.22213/2410-9304-2016-4-40-44.

Abdoun Otman, Jaafar Abouchabaka, Chakir Tajani. Analyzing the Performance of Mutation Operators to Solve the Travelling Salesman Problem. Int. J. Emerg. Sci. 2. 2012.

Батищев Д. И., Неймарк Е. А., Старостин Н. В. Применение генетических алгоритмов к решению задач дискретной оптимизации. Н. Новгород, 2007. 88 с.