Issue №1, 2019

LOGIN      REGISTER

          

Solving some network tasks in Excel

N. V. Katargin, Financial University under the Government of Russian Federation (Moscow, Russia)

Full article 

DOI: 10.34130/2070-4992-2019-1-150-159

P. 150–159.

The aim of this work is to develop methods for solving actual problems of network modeling. Fundamentally, new algorithms for solving two problems in Excel are proposed: the choice of the route in the road network (the traveling salesman problem), the placement and connection to consumers of power substations with the provision of minimizing losses in power grids. The authors know how: «short plan» in the problem of choosing a route, which allows to dramatically reduce the number of variables varied by the computer, non-trivial use of the service Solver using the gradient descent method to vary binary variables, as well as the joint variation of real and binary variables in the problem of placement. The problem of the appearance of «islands» in the problem of choosing a route – nodes that are not connected with the main route is solved. The algorithm is based on the prevention of return on the same way, except in special cases – star routes from some points. The algorithms are implemented in MS Excel, for their use does not require programming, but only filling in the tables of the original data and simple steps: copying and summarizing. Route selection and placement of substations are tested on networks with 15 nodes, which is enough for practice. The optimal routes are laid through the real road network, both without returning to the original point and the ring route, as in the classical traveling salesman problem. The problem of placing objects also uses real maps (Yandex). Two options have been worked out-with the limitation of substations in capacity and without limitation. This algorithm may be used to optimize the location of, for example, fuel and commodity supply bases. When placing objects in road network nodes, their coordinates are replaced by binary variables with minor algorithm changes. The results can be used for practical work in the field of transport logistics and placement of new objects, as well as teaching students how to solve economical problems using mathematical modeling and information technology.

Keywords: network modeling, routing, traveling salesman problem, object placement, electrical outlets, Excel.

References

  1. Dybskaya V. V., Zaitsev E. I., Sergeev V. I. Logistika. Polnyy kurs MVA: uchebnik [Logistics. Full MBA course: textbook]. Moscow: Eksmo, 2008, pp. 30–39. (In Russian).
  2. Ekonomiko-matematicheskoe modelirovanie / Pod redaktsiyey I.N. Drogobytskogo: uchebnik [Economic and mathematical modeling / Edited by I. N. Drogobytsky: textbook]. Moscow: Examen, 2006, 798 p. (In Russian)
  3. Kremer N. Sh. et al. Issledovanie operatsii v ekonomike: uchebnik [Study of operations in economics: textbook]. Moscow: Urait, 2014, 424 p. (In Russian).
  4. Rubchinskii A. A. Metodi i modeli prinyatiya upravlencheskih reshenii [Methods and models of management decisionmaking]. Moscow: Urait, 2015, рp. 111–113. (In Russian)
  5. Reshenie zadachi kommivoyazhora rekursivnim polnim pereborom [The solution to the traveling salesman problem recursive brute force]. Available at: www.habr.com/ru/post/151151/ (accessed: 10.09.2012)
  6. Mainika, E. Algoritmi optimizatsii na setyah i grafah: monografiya [Optimization algorithms on networks and graphs: monograph]. Moscow: Mir, 1981, рp. 241–264. (In Russian).
  7. Bellmore M., Nemhuser G. L., 1968. The Travelling Salesman Problem: A Survey. Operations Research, vol. 16, 3: 538–558.
  8. Garfinkel R., Namhauser G. L., 1972. Integer Programming. New York: John Wiley, Inc., pp: 354–360.
  9. Held M., Karp R., 1971. The Travelling-Salesman Problem and Minimum Spanning Trees, Part II. Math. Programming, vol. 1, 1: 6–25.
  10. Steckhan H. A., 1970. Theorem on Symmetric Travelling Salesman Problems. Operations Research, vol. 18, 6: 1163– 1167.
  11. Galyautdinov R. R. Zadacha kommivoyazhora – metod vetvei i granits [Traveling salesman problem – branch and boundary method]. (In Russian). Available at: www.galyautdinov.ru/post/zadacha-kommivoyazhera (accessed: 18.11.2013)
  12. Cormen, T., Leiserson, C., Rivest, R. Algoritmi. Postroenie i analiz [Algorithms. The construction and analysis]. Мoscow: МCNMO, 2002, pp. 845-846. (In Russian).
  13. Matai, R., Singh, S., Lal, M., 2010. Traveling salesman problem: An overview of applications, formulations, and solution approaches. In Traveling Salesman Problem, Theory and Applications, Ed. D. Davendra. InTech, рp: 356.
  14. Junger, M., Liebling, T., Naddef, D., Nemhauser, G., Pulleyblank, W., Reinelt, G., Rinaldi, G., Wolsey, L., 2009. 50 years of integer programming, 1958–2008: The early years and state-of-the-art surveys. Heidelberg: Springer, pp: 785.
  15. Cook, W., 2007. History of the TSP. The Traveling Salesman Problem. Date Views 20.03.2019 www.math.uwaterloo.ca/tsp/history/index.htm
  16. Laporte, G., 1992. The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2): 231–247.
  17. DAA – Travelling Salesman Problem. Date Views 23.11.2016. www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_travelling_salesman_problem.htm
  18. Jacobson, L. Applying a genetic algorithm to the traveling salesman problem, 2012. Date Views 20.03.2019 www.theprojectspot.com/tutorial-post/applying-a-genetic-algorithm-to-the-travelling-salesman-problem/5

For citation: Katargin N. V. Solving some network tasks in Excel. Corporate Governance and Innovative Economic Development of the North: Bulletin of the Research Center of Corporate Law, Management and Venture Capital of Syktyvkar State University, 2019, no. 1, pp. 150–159. DOI: 10.34130/2070-4992-2019-1-150-159 (In Russian).