Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
Volume 58 >>> № 6 NOVEMBER — DECEMBER 2022
-->

UDC 519.168; 519.854.3
V.A. Vasyanin1, O.M. Trofymchuk2, L.P. Ushakova3


1 Institute of Telecommunications and Global Information Space, National Academy of Sciences of Ukraine, Kyiv, Ukraine

 archukr@meta.ua

2 Institute of Telecommunications and Global Information Space, National Academy of Sciences of Ukraine, Kyiv, Ukraine

 itgis@nas.gov.ua

3 Institute of Telecommunications and Global Information Space, National Academy of Sciences of Ukraine, Kyiv, Ukraine

 archukr@meta.ua

THE PROBLEM OF GROUPAGE CARGO ROUTING IN A MULTICOMMODITY
TRANSPORT NETWORK WITH GIVEN TARIFFS AND DELIVERY TIME CONSTRAINTS

Abstract. The paper considers a network formulation of the problem of optimizing the routing of groupage cargo flows in a transport network with given tariffs for the transportation and processing of flows and restrictions on the throughput of arcs, nodes and the time of delivery of individual goods to the recipient. To calculate the delivery time, a method is proposed for generating a reference matrix for combining the flows of individual cargoes and efficient algorithms that allow one to determine the nodes of the union and the combined flows for all corresponding pairs in a multi-commodity network. It is proved that the problem with tariffs in a network setting can be transformed in polynomial time to an integer linear programming problem with a block structure and binding constraints. Peculiarities of solving the transformed problem with the use of well-known methods of integer programming and application software packages are presented.

Keywords: mathematical models of flow distribution and routing in multicommodity networks, optimization problems with discrete flows and parameters.


FULL TEXT

REFERENCES

  1. Vasyanin V.A. Methodology for designing multi-commodity communication networks with discrete flows: dis. ... doct. tech. sciences. 01.05.02. Kiev, 2017. 497 p. URL: https://itgip.org/wp-content .

  2. The freight story: A national perspective on enhancing freight transportation. Federal Highway Administration. 2005. Freight Management and Operations. URL: http://ops.fhwa.dot.gov/ freight .

  3. US international trade and freight transportation trends. United States Department of Transportation: Bureau of Transportation Statistics. 2003. URL: www.bts.gov .

  4. Barnhart C., Hane C.A., Vance P.H. Integer multicommodity flow problems. In: Network Optimization. Pardalos P.M., Hearn D.W., Hager W.W. (Eds.). Lecture Notes in Economics and Mathematical Systems. 1997. Vol. 450. P. 17–31. doi.org/10.1007/978-3-642-59179-2_2.

  5. Barnhart C., Hane C.A., Vance P.H. Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Operations Research. 2000. Vol. 48, N 2. P. 318–326. doi.org/10.1287/opre.48.2.318.12378 .

  6. Encyclopedia of optimization. Second Ed. Floudas C.A., Pardalos P.M. (Eds.). New York: Springer, 2009. 4626 p.

  7. Wang I-L. Multicommodity network flows: a survey, part I: applications and formulations. International Journal of Operations Research. 2018. Vol. 15, N 4. P. 145–153. doi.org/10.6886/IJOR.201812_15(4).0001.

  8. Wang I-L. Multicommodity network flows: a survey, part II: solution methods. International Journal of Operations Research. 2018. Vol. 15, N 4. P. 155–173. doi.org/10.6886/IJOR.201812_15(4).0002.

  9. Cohn A., Root S., Wang A., Mohr D. Integration of the load matching and routing problem with equipment balancing for small package carriers. Transportation Science. 2007. Vol. 41, Iss. 2. P. 238–252. doi.org/10.1287/trsc.1060.0174 .

  10. Hellsten E., Koza D.F., Contreras I., Cordeau J.F., Pisinger D. The transit time constrained fixed charge multi-commodity network design problem. Computers & Operations Research. 2021. Vol. 136. 105511. doi.org/10.1016/j.cor.2021.105511.

  11. Trivella A., Corman F., Koza D.F., Pisinger D. The multi-commodity network flow problem with soft transit time constraints: Application to liner shipping. Transportation Research Part E: Logistics and Transportation Review. 2021. Vol. 150. 102342. doi.org/10.1016/j.tre.2021.102342.

  12. Trofymchuk O.M., Vasyanin V.A. Simulation of packing, distribution and routing of small-size discrete flows in a multicommodity network. Journal of Automation and Information Sciences. 2015. Vol. 47, Iss. 7. P. 15–30. doi.org/10.1615/JAutomatInfScien.v47.i7.30 .

  13. Trofymchuk O.M., Vasyanin V.A., Kuzmenko V.N. Optimization algorithms for packing of small-lot correspondence in communication networks. Cybernetics and Systems Analysis. 2016. Vol. 52, N 2. P. 258–268. doi.org/10.1007/s10559-016-9822-5.

  14. Trofymchuk A.N., Vasyanin V.A. Computer simulation of the hierarchical structure of a communication network with discrete multi-product flows. USiM. 2016. N 2. P. 48–57. doi.org/10.15407/usim.2016.02.048.

  15. Trofymchuk A.N., Vasyanin V.A., Ushakova L.P. Study of the problem of optimizing the hierarchical structure of a sparse and dense communication network. Problemy upravleniya i informatiki. 2021. N 1. P. 5–21.

  16. Vasyanin V.A. Problem of distribution and routing of transport blocks with mixed attachments and its decomposition. Problemy upravleniya i informatiki. 2015. Vol. 47, Iss. 2. P. 56–69. doi.org/10.1615/JAutomatInfScien.v47.i2.60 .

  17. Vasyanin V.A. Computer modeling of distribution and routing of discrete multicommodity flows in a communication network. USiM. 2016. № 3. С. 43–53. doi.org/10.15407/usim.2016.03.043.

  18. Vasyanin V.A., Trofymchuk A.N., Ushakova L.P. Economic and mathematical models of the problem of distribution of flows in a multicommodity communication network. Mathematical modeling in economics. 2016. N 2. P. 5–21. URL: http://dspace.nbuv.gov.ua .

  19. Trofymchuk O.M., Vasyanin V.A., Kuzmenko V.N. Complexity of one packing optimization problem. Cybernetics and Systems Analysis. 2016. Vol. 52, N 1. P. 76–84. doi.org/10.1007/ s10559-016-9802-9.

  20. Vasyanin V.A. Reference matrix of flow merging in packing optimization problems on multicommodity networks. Systemni doslidzhennya ta informatsiyni tekhnolohiyi. 2014. N 3. P. 42–49. URL: http://dspace.nbuv.gov.ua .

  21. Gary M., Johnson D. Computers and hard-to-solve problems [Russian translation]. Moscow: Mir, 1982. 416 с.

  22. Even S., Itai A., Shamir A. On the complexity of timetable and multicommodity flow problems. SIAM J. Comput. 1976. Vol. 5, Iss. 4. P. 691–703. doi.org/10.1137/0205048.

  23. NVIDIA Developer. URL: https://developer.nvidia.com/cuda-zone .

  24. Best Practices Guide (PDF) — v11.6.2 (older) — Last updated March 24, 2022. URL: https://docs.nvidia.com/cuda .




Editorial Board Announcements Abstracts Authors Archive
about scope office editorial board instructions for authors subscriptions contacts
© 2022 Kibernetika.org. All rights reserved.