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

Authors

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

Keywords:

e-commerce logistics, k travelling salesman problem, branch and boundary method, ant algorithm, greedy algorithm, cluster algorithm

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.

Downloads

Issue

No. 2 (2023): Journal of the Belarusian State University. Economics

Section

C. Mathematical and Quantitative Methods

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.)

How to Cite

[1]
Dutin, .S.R. 2023. Network model and methods for solving the k travelling salesman problem for optimisation of delivery routes. Journal of the Belarusian State University. Economics. 2 (Dec. 2023), 20–24.