Network model and methods for solving the k travelling salesman problem for optimisation of delivery routes

  • Sergey R. Dutin Belarusian State University, 4 Niezaliezhnasci Avenue, Minsk 220030, Belarus

Abstract

The article formulates a network model of the k travelling salesman problem for optimisation of delivery routes in electronic commerce. Approximate and exact methods of searching for optimal or quasi-optimal routes are proposed for the constructed model. The task of routing delivery is of great practical importance due to the rapid growth of e-commerce and it has not been sufficiently investigated due to the novelty.

Author Biography

Sergey R. Dutin, Belarusian State University, 4 Niezaliezhnasci Avenue, Minsk 220030, Belarus

postgraduate student at the department of analytical economics and econometrics, faculty of economics

References

  1. Little J, Murty D, Sweeny D, Karel C. An algorithm for the traveling salesman problem. Operational Research. 1963;11:972–982.
  2. Gutin G, editor. The traveling salesman problem and its variations. Dorbrecht: Kluwer Academy Publishing; 2002. 830 p.
  3. Kovalev MM. Diskretnaya optimizatsiya: tselochislennoe programmirovanie [Discrete optimisation: integer programming]. Minsk: Belarusian State University; 1977. 192 p. Russian.
  4. Dudnik TA, Bodrov AS, Kolpakova SV, Levshina KV. Solution of the travelling salesman problem with a limited delivery time in the conditions of the development of digital technologies in transport. World of Transport and Technological Machines. 2021;1:64–72. Russian.
  5. Zak YuA. Matematicheskie modeli i algoritmy postroeniya effektivnykh marshrutov dostavki gruzov [Mathematical models and algorithms of construction effective cargo delivery routes]. Moscow: Rusains; 2023. 304 p. Russian.
  6. Solomon MM. Algorithm for tehicle routing and scheduling problems with time window constraints. Operational Research. 1987; 35:254–265.
  7. Gan J, Zhang G. The k-delivery traveling salesman problem: revisited. Lecture Notes in Computer Science. 2019;11949:197–209.
  8. Kovalev MM. Matroidy v diskretnoi optimizatsii [Matroids in discrete optimisation]. Moscow: URSS; 2003. 222 p. Russian.
  9. Dorigo M. Optimisation, learning and natural algorithms. Milano: Politecnico di Milano; 1992. 102 p.
Keywords: e-commerce logistics, k travelling salesman problem, branch and boundary method, ant algorithm, greedy algorithm, cluster algorithm
How to Cite
Dutin, S. R. (1). Network model and methods for solving the k travelling salesman problem for optimisation of delivery routes. Journal of the Belarusian State University. Economics, 2, 20-24. Retrieved from https://journals.bsu.by/index.php/economy/article/view/5827
Issue
No 2 (2023): Journal of the Belarusian State University. Economics
Section
C. Mathematical and Quantitative Methods

Copyright (c) 2023 Journal of the Belarusian State University. Economics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)