2024, issue 2, p. 11-30
Received 06.03.2024; Revised 07.04.2024; Accepted 28.05.2024
Published 09.06.2024; First Online 14.06.2024
https://doi.org/10.34229/2707-451X.24.2.2
Mathematical Models of the Problem of Constructing Delivery Routes of Cargo in the Internal Zones of Trunk Nodes of a Hierarchical Transport Network
Volodymyr Vasyanin * 
, Liudmyla Ushakova
Institute of Telecommunications and Global Information Space of the NAS of Ukraine, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. The article discusses mathematical models of problems of constructing circular routes of vehicles in a multicommodity hierarchical network. As a rule, such networks consist of a decentralized backbone network and networks in the internal service areas of the backbone nodes (internal networks). In multicommodity networks, each node can exchange products (goods, cargo) with other nodes. In contrast to the distribution problems of a homogeneous interchangeable product, in multicommodity problems the flows of products are not interchangeable, the flow of each product must be delivered from a specific primary object to a specific customer. It is assumed that the multi-level structure of the transport network is defined and the geographical location of the main hubs and its internal service areas with a set of nodes for the delivery and collection of goods (customers) are known. Therefore, the problems of determining the main routes of vehicles and constructing circular routes of internal vehicles are considered independently of each other. The types of costs of real transport processes, which should be taken into account in the formation of the objective function of routing problems, are discussed and mathematical models of problems for constructing circular delivery routes with a heterogeneous fleet of vehicles are proposed. The possibility of solving the formulated problems with the help of well-known packages of mixed and integer linear programming is noted.
Purpose. The aim of the article is to formulate new mathematical models of the problem of constructing circular routes of vehicles in the internal networks of servicing the main nodes, which take into account the real costs of transport processes and the geographical features of internal networks.
The technique. The research methodology is based on the system analysis of many modern models, methods and algorithms for solving the problems of constructing circular routes for customer service in the internal zones of the main nodes of the hierarchical network.
Results. On the basis of the review and analysis of known mathematical models, several new variants of mathematical formulation of problems of designing routes of vehicles for the transportation of discrete cargo in the internal zones of the central nodes of the network have been developed. To solve the problems, precise, heuristic and metaheuristic methods and algorithms can be used, implemented in many commercial and non-commercial packages of mixed and integer programming programs, for example, IBM ILOG CPLEX, GAMS, AIMMS, Gurobi Optimizer, ABACUS, COIN-OR, GLPK, lp_solve. Many of them are available for free on the NEOS server (https://neos-server.org/neos/).
Scientific novelty and practical significance. The novelty of the work lies in the formulation of mathematical models of the problem of constructing circular routes of vehicles, which take into account the real costs of transport processes and geographical features of internal networks. The materials of the article form the methodological basis for the development of modern mathematical support for solving the problems of long-term, current and operational planning and management in the internal zones of the trunk nodes of the global hierarchical network.
Keywords: problems of combinatorial optimization, mathematical models of circular routes of vehicles.
Cite as: Vasyanin V., Ushakova L. Mathematical Models of the Problem of Constructing Delivery Routes of Cargo in the Internal Zones of Trunk Nodes of a Hierarchical Transport Network. Cybernetics and Computer Technologies. 2024. 2. P. 11–30. https://doi.org/10.34229/2707-451X.24.2.2
References
1. Lenstra J.K., Rinnooy Kan A.H.G. Complexity of vehicle routing and scheduling problems. Networks. 1981. No. 11. P. 221–227. https://doi.org/10.1002/net.3230110211
2. Laporte G. Fifty Years of Vehicle Routing. Canada Research Chair in Distribution Management, HEC Montr´eal, 2009. 23 p.
3. Dantzig G.B., Fulkerson D.R. Minimizing the number of tankers to meet a fixed schedule. Naval Research Logistics Quarterly. 1954. No. 1. P. 217–222. https://doi.org/10.1002/nav.3800010309
4. Kirby D. Is Your Fleet the Right Size? Operational Research Quarterly. 1959. No. 10. P. 252. https://doi.org/10.2307/3006624
5. Golden B.L., Assad A., Levy L., Gheysens F. The Fleet Size and Mix Vehicle Routing Problem. Computers & Operations Research. 1984. No. 11. P. 49–66. https://doi.org/10.1016/0305-0548(84)90007-8
6. Clarke G., Wright J.W. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research. 1964. Vol. 12. P. 568–581. https://doi.org/10.1287/opre.12.4.568
7. Salhi S., Rand G.K. Incorporating vehicle routing into the vehicle fleet composition problem. European Journal of Operational Research. 1993. No. 66. P. 313–330. https://doi.org/10.1016/0377-2217(93)90220-H
8. Osman I.H., Salhi S. Local Search Strategies for the Vehicle Fleet Mix Problem. Modern heuristic search methods. John Wiley & Sons, Chichester, UK, 1996. P. 131–153.
9. Lee Y.H., Kim J.I., Kang K.H., Kim K.H. A heuristic for vehicle fleet mix problem using tabu search and set partitioning. The Journal of the Operational Research Society. 2008. Vol. 59, No. 6. P. 833–841. https://doi.org/10.1057/palgrave.jors.2602421
10. Baldacci R., Battarra M., Vigo D. Routing a Heterogeneous Fleet of Vehicles. Technical Report DEIS OR. INGCE 2007/1, University Bologna, Italy, 2007. 25 p.
11. Baldacci R., Battarra M., Vigo D. Routing a heterogeneous fleet of vehicles. In Golden B.L., Raghavan S., Wasil E.A. (Eds.). The vehicle routing problem: Latest advances and new challenges, New York: Springer, 2008. P. 1–25.
12. Hoff A., Andersson H., Christiansen M., Hasle G., Løkketangen A. Industrial Aspects and Literature Survey: Fleet Composition and Routing. SINTEF REPORT NO. A7029, 2008. 49 p.
13. Hoff A., Andersson H., Christiansen M., Hasle G., Løkketangen A. Industrial aspects and literature survey: Fleet composition and routing. Computers & Operations Research. 2010. No. 37. P. 2041–2061. https://doi.org/10.1016/j.cor.2010.03.015
14. Baldacci R., Battarra M., Vigo D. Valid inequalities for the fleet size and mix vehicle routing problem with fixed costs. Networks. 2009. Vol. 54, Iss. 4. P. 178–189. https://doi.org/10.1002/net.20331
15. Baldacci R., Mingozzi A. A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming, Series A. 2009. Vol. 120, Iss. 2. P. 347–380. https://doi.org/10.1007/s10107-008-0218-9
16. Baldacci R., Bartolini E., Mingozzi A., Roberti R. An exact solution framework for a broad class of vehicle routing problems. Computational Management Science. 2010. Vol. 7, Iss. 3. P. 229–268. https://doi.org/10.1007/s10287-009-0118-3
17. Baldacci R., Toth P., Vigo D. Exact algorithms for routing problems under vehicle capacity constraints. Annals of Operations Research. 2010. Vol. 175, Iss. 1. P. 213–245. https://doi.org/10.1007/s10479-009-0650-0
18. Gheysens F., Golden B.L., Assad A. A Comparison of Techniques for Solving the Fleet Size and Mix Vehicle Routing Problem. OR Spectrum. 1984. No. 6. P. 207–216. https://doi.org/10.1007/BF01720070
19. Bräysy O., Dullaert W., Hasle G., Mester D., Gendreau M. An Effective Multi-restart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle Routing Problem with Time Windows. Transportation Science. 2008. Vol. 42, Iss. 3. P. 371–386. https://doi.org/10.1287/trsc.1070.0217
20. Miller C.E., Tucker A.W., Zemlin R.A. Integer programming formulations and traveling salesman problems. ACM. 1960. Vol. 7. P. 326–329. https://doi.org/10.1145/321043.321046
21. Baldacci R., Battarra M., Vigo D. Valid inequalities for the fleet size and mix vehicle routing problem with fixed costs. Networks. 2009. Vol. 54, Iss. 4. P. 178–189. https://doi.org/10.1002/net.20331
22. Baldacci R., Mingozzi A. A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming, Series A. 2009. Vol. 120, Iss. 2. P. 347–380. https://doi.org/10.1007/s10107-008-0218-9
23. Balinski M., Quandt R. On an integer program for a delivery problem. Operations Research. 1964. Vol. 12. P. 300–304. https://doi.org/10.1287/opre.12.2.300
24. Choi E., Tcha D. A column generation approach to the heterogeneous fleet vehicle routing problem. Computers & Operations Research. 2007. Vol. 34. P. 2080–2095. https://doi.org/10.1016/j.cor.2005.08.002
25. Golden B.L., Raghavan S., Wasil E.A. The Vehicle Routing Problem: Latest Advances and New Challenges. Springer Science & Business Media. 2008. 591 p. https://doi.org/10.1007/978-0-387-77778-8
26. Toth P., Vigo D. Vehicle Routing: Problems, Methods, and Applications. Second Edition, SIAM, 2014. 463 p. https://doi.org/10.1137/1.9781611973594
27. Vidal T., Crainic T.G., Gendreau M., Prins C. A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research. 2014. Vol. 234, Iss. 3. P. 658–673. https://doi.org/10.1016/j.ejor.2013.09.045
28. http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/index.html, http://www.gams.com/, http://aimms.com/, http:/www.gurobi.com/
29. http://www.informatik.uni-koeln.de/abacus/, http://www.coin-or.org/, http://www.gnu.org/software/glpk/glpk.html, http://groups.yahoo.com/group/lp_solve/info/
30. 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. https://doi.org/10.1615/JAutomatInfScien.v47.i7.30.
31. 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, Iss. 2. P. 258–268. https://doi.org/10.1007/s10559-016-9822-5
32. Vasyanin V.A., Trofymchuk O.M., Ushakova L.P. Constructing problems of vehicles ring routes in multicommodity hierarchical network. International Scientific Technical Journal "Problems of Control and Informatics". 2022. Vol. 67, Iss. 3. P. 37–55. (in Ukrainian) https://doi.org/10.34229/2786-6505-2022-3-3
33. Vasyanin V.A., Trofymchuk O.M., Ushakova L.P. Methodology of Mathematical Modeling for Perspective Development of Nodes and Transport Routes in a Multicommodity Hierarchical Network. I. Optimization Problems. Cybernetics and Systems Analysis. 2024. Vol. 60, No. 1. P. 103117. (in Ukrainian) https://doi.org/10.1007/s10559-024-00648-9
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)