From Monge to modern optimisation of transport flows

  • Anna A. Koroleva Belarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, Belarus

Abstract

The article is devoted to the analysis of flow optimisation methods in transport logistics. The historical review and analysis of the current state are given with a focus on easily solvable cases that generalise the well-known Monge property of cost matrices.

Author Biography

Anna A. Koroleva, Belarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, Belarus

PhD (physics and mathematics), docent; dean of the faculty of economics

References

  1. Monge G. Mémoire sur la théorie des déblais et des remblais. In: Mémoires de l’Academie. Paris: De l’Imprimerie Royale; 1781. p. 666–704.
  2. Tolstoi AN. [Methods of finding the total mileage when planning transportation in space]. Planirovanie perevozok. 1930;1:23–55. Russian.
  3. Kantorovich LV. On the displacement of masses. USSR Academy of Sciences. 1942;32(3):227–229. Russian.
  4. Kantorovich LV, Gavurin MK. [Application of mathematical methods in the analysis of cargo flows]. In: Zvonkov VV, editor. Problemy povysheniya effektivnosti raboty transporta [Problems of improving the efficiency of transport]. Moscow: AN SSSR; 1949. p. 110–138. Russian.
  5. Hitchcock FL. The distribution of a product from several sources to numerous localities. Journal of Mathematics and Physics. 1941;20(1–4):224–230. DOI: 10.1002/sapm1941201224.
  6. Koopmans TC. Optimum utilisation of the transportation system. Econometrica. 1949:17(supplement):136–146. DOI: 10.2307/1907301.
  7. Dantzig G. Application of the simplex method to a transportation problem. In: Koopmans TC, editor. Activity analysis of production and allocation. New York: John Wiley and Sons; 1951. p. 359–377.
  8. Ford L, Fulkerson D. Flows in networks. Princeton: Princeton University Press; 1962. 194 p.
  9. Emelichev VA, Kovalev MM, Kravtsov MK. Mnogogranniki, grafy, optimizatsiya [Polytopes, graphs and optimisation]. Moscow: Nauka; 1981. 344 p. Russian.
  10. Yemelichev VA, Kovalev MM, Kravtsov MK. Polytopes, graphs and optimisation. Cambridge: Cambridge University Press; 1984. 423 p. Russian.
  11. Bogachev VN, Kolesnikov AV. [The task of Monge – Kantorovich: achievements, connections and prospects]. Uspekhi matematicheskikh nauk. 2012;67(5):3–110. Russian. DOI: 10.4213/rm9490.
  12. Hoffman A. On simple linear programming problems. In: Klee V, editor. Convexity: proceedings of the seventh symposium in pure mathematics AMS; 1961 June 13–15; Washington, USA. Volume 7. Providence: American Mathematical Society; 1963. p. 317–327.
  13. Kovalev M. Matroidy v diskretnoi optimizatsii [Matroids in discrete optimisation]. Minsk: Universitetskoe; 1987. 220 p. Russian.
  14. Bein W, Brucker P, Hoffman A. Series parallel composition of greedy linear programming problems. Mathematical Programming. 1993;62:1–14. DOI: 10.1007/BF01585157.
  15. Bein WW, Brucker P, Park J, Pathak P. A Monge property for the d-dimensional transportation problem. Discrete Applied Mathematics. 1995;58:97–109.
  16. Dietrich BL. Monge sequences, antimatroids, and the transportation problem with forbidden arcs. Linear Algebra and its Applications. 1990;139:133–145. DOI: 10.1016/0024-3795(90)90393-Q.
  17. Shamir R. A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs. Discrete Mathematics. 1993;114(1–3):435–444. DOI: 10.1016/0012-365X(93)90382-4.
  18. Adler I, Hoffman A, Schamir R. Monge and feasibility sequences in general flow problems. Discrete Applied Mathematics. 1993;44(1–3):21–38. DOI: 10.1016/0166-218X(93)90220-I.
  19. Park JK. A special case of the n-vertex traveling-salesman problem that can be solved in O(n) time. Informating Processiong Letters. 1991;40(5):247–254. DOI: 10.1016/0020-0190(91)90118-2.
  20. Beresnev VL, Gimadi EKh, Dement’ev VT. Ekstremal’nye zadachi standartizatsii [Extreme problems of standardisation]. Novosibirsk: Nauka; 1978. 333 p. Russian.
  21. Trubin V. [Effective algorithm for determining the location in a tree network]. Doklady AN USSR. 1976;231:547–550. Russian.
  22. Eisenstatt V, Kravchuk D. [Algorithm for finding the extremum of a linear form on a set of cycles in a special case]. Doklady AN BSSR. 1968;12:401– 404. Russian.
  23. Demidenko V. [The problem of a traveling salesman with symmetric matrices]. Izvestiya Natsional’noi akademii nauk Belarusi. Seriya fiziko-tekhnicheskikh nauk. 1978;1:29–35. Russian.
  24. Trubin V. [Two classes of location determination problems in tree networks]. Kibernetika. 1983;4:84–87. Russian.
  25. Gimadi EKh. [An effective algorithm for solving the problem of determining the location with the service area associated with an acyclic network]. Upravlyaemye sistemy. 1979;19:3–13. Russian.
  26. Aggarwal A, Bar-Noy A, Khuller S, Kravets D, Schieber B. Efficient minimum cost matching using quadrangle inequality. In: Proceedings of 33rd annual symposium on foundations of computer science; 1992 October 24–27; Pittsburgh, USA. Washington: Institute of Electrical and Electronics Engineers; p. 583–592. 1992. DOI: 10.1109/SFCS.1992.267793.
  27. Girlich E, Kovalev M, Moshchensky A. Conventy and Monge arrays. Magdeburg University [Preprint]. 1993;12:[22].
  28. Girlich E, Kovalev M, Zaporozhets A. Subcones of submodular functions. Otto von Guericke Universität Magdeburg [Preprint]. 1994;29:[28].
  29. Demidenko VM. [Conic characterisation of Monge matrices]. Kibernetika i sistemnyi analiz. 2004;4:87–98. Russian.
  30. Grishukhin V. Ekstremal’nye luchi konusa submodulyarnoi funktsii [Extremal rays of the cone of a submodular function]. CEMI of the Academy of Sciences of the Ukrainian SSR [Preprint]; 1982. [66 p.]. Russian.
  31. Rudolf R, Woeginger GJ. The cone of Monge matrices: extremal rays and applications. Zeitschrift für Operations Research. 1995;42:161–168. DOI: 10.1007/BF01415751.
  32. Burkard RE, Klinz B, Rudolf R. Perspectives of Monge properties in optimization. Discrete Applied Mathematics. 1996; 70(2):95–161. DOI: 10.1016/0166-218X(95)00103-X.
  33. Deineko V, Filonenko V. [On the reconstruction of special structured matrices]. In: Chernyshenko VM, editor. Aktual’nye problemy EVM i programmirovaniya [Actual problems of computers, programming]. Dnepropetrovsk: Dnipropetrovsk Humanitarian University; 1979. p. 43– 45. Russian.
  34. Deineko V, Woeginger G. Some problems around travelling salesmen, dartboards, and euro-coins. Bulletin of the European Association for Theoretical Computer Science. 2006;90:43–52.
  35. Pisaruk NN. Modeli i metody smeshanno-tselochislennogo programmirovaniya [Models and methods of mixed-integer programming]. Minsk: Belarusian State University; 2010. 230 p. Russian.
  36. Meindl B, Templ M. Analysis of commercial and free and open source solvers for linear optimization problems. Wien: Technische Universität Wien; 2012. 15 p.
  37. Brodetskii GL, Gusev DA. Ekonomiko-matematicheskie metody i modeli v logistike: protsedury optimizatsii [Economic and mathematical methods and models in logistics: optimisation procedures]. Moscow: Akademiya; 2012. 195 p. Russian.
  38. Gasnikov AV, editor. Vvedenie v matematicheskie modelirovanie transportnykh potokov [Introduction to mathematical modeling of transport flows]. 2nd edition. Moscow: Moscow Centre for Continuous Mathematical Education; 2013. 428 p. Russian.
  39. Samoilenko NI, Kobets AA. Transportnye sistemy bol’shoi razmernosti [Transport systems of large dimension]. Kharkiv: NTMT; 2010. 214 p. Russian.
Published
2021-07-30
Keywords: transportation problem, optimisation in logistics, Monge property, the convexity of the matrix
How to Cite
Koroleva, A. A. (2021). From Monge to modern optimisation of transport flows. Journal of the Belarusian State University. Economics, 1, 26-36. Retrieved from https://journals.bsu.by/index.php/economy/article/view/3762
Issue
No 1 (2021): Journal of the Belarusian State University. Economics
Section
C. Mathematical and Quantitative Methods

Copyright (c) 2021 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.)