«Automation and Informatization of the fuel and energy complex»

Optimization of a crew routing based on heuristic methods for solving a variation of a traveling salesman problem

UDC: 004.023
DOI: 10.33285/2782-604X-2023-9(602)-34-40

Authors:

¹ National University of Oil and Gas "Gubkin University", Moscow, Russia

Keywords: traveling salesman problem, heuristic algorithm, ant colony optimization, genetic algorithm, simulated annealing algorithm

Annotation:

The article addresses the urgent problem of routing crews for work considering individual restrictions. This task is a specific instance of a traveling salesman problem that cannot be solved by deterministic methods within a reasonable time. Therefore, approximate methods are used which may not necessarily find the best solution but can find a sufficiently good one in a feasible time. The solution of this problem provides the opportunity to automate the management process and organization of optimal path construction, thereby enhancing working process efficiency. To do this, the article conducts a comparatively analyzes three modern meta-heuristic algorithms: the ant colony algorithm, the genetic algorithm, and the simulated annealing algorithm. As a result, the best method for solving this problem has been identified – the ant colony algorithm. The automation of routes formation, which is close to the optimal one and takes into account real constraints, contributes to the reduction of technical downtime and enhances the resource efficiency of the organization.

Bibliography:

1. Tsifrovaya ekonomika neftyanogo proizvodstva / G.I. Shmal', L.I. Grigor'ev, V.Ya. Kershenbaum, D.G. Leonov // Neft. khoz-vo. – 2019. – № 1. – S. 100–103. – DOI: 10.24887/0028-2448-2019-1-100-103
2. Kovalevskiy P.G. Avtomatizatsiya postroeniya kalendarnogo plana provedeniya remontno-vosstanovitel'nykh rabot na lineynoy chasti magistral'nogo gazoprovoda s ispol'zovaniem metodov matematicheskogo programmirovaniya // Avtomatizatsiya i informatizatsiya TEK. – 2023. – № 1(594). – S. 13–19. – DOI: 10.33285/2782-604X-2023-1(594)-13-19
3. Tendentsii razvitiya integrirovannykh avtomatizirovannykh sistem upravleniya v gazodobyche / S.P. Chistikov, V.K. Lavrukhin, L.I. Grigor'ev [i dr.] // Gazovaya prom-st'. – 2006. – № 5. – S. 199–203.
4. Mudrov V.I. Zadacha o kommivoyazhere. – M.: Znanie, 1969. – 64 s.
5. Solomatin A.N. Optimizatsiya strategiy razrabotki gruppy gazovykh mestorozhdeniy // Avtomatizatsiya i informatizatsiya TEK. – 2022. – № 10(591). – S. 45–51. – DOI: 10.33285/2782-604X-2022-10(591)-45-51
6. Shtovba S.D. Murav'inye algoritmy // Exponenta Pro: Matematika v prilozheniyakh. – 2003. – № 4. – S. 70–75.
7. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy: ucheb. posobie. – 2-e izd. – M.: Fizmatlit, 2006. – 320 s.
8. Kirsanov M.N. Grafy v Maple: zadachi, algoritmy, programmy. – M.: Fizmatlit, 2007. – 168 s.