Discrete optimizations’ problems of deliveries of heterogeneous products
https://doi.org/10.26425/1816-4277-2023-5-70-76
Abstract
The article touches upon issues related to the tasks of the national project «Smart City». The paper analyzes the problem of supplying a conditional consumer with heterogeneous products in accordance with his demand for deliveries from several suppliers in a situation with fixed surcharges, in addition to the cost of purchasing each unit of production. For the situation under study, a model of a reduced transport type with a discontinuous piecewise linear objective function of minimized total costs and with a system of linear constraints is constructed. A method for finding the optimal solution one of the many such solutions, based on the ideas of the Hungarian algorithm is proposed, the justification of which is given on the basis of the corresponding lemma. A refinement of the method is presented in the presence of some restrictions related to suppliers. The polynomial complexity of the method, i.e. the problem is quickly solvable, and the significant limitation of the applicability of the method within the framework of the model are noted. Further possible research directions of a stochastic or fuzzy nature are indicated.
About the Author
V. V. EgorovRussian Federation
Vladislav V. Egorov Cand. Sci. (Phys. and Math.), Assoc. Prof. At the Department of Mathematical Methods in Economics and Management
References
1. Ministry of Digital Development, Communications and Mass Media of the Russian Federation. National project “Digital Economy of the Russian Federation”. https://digital.gov.ru/ru/activity/directions/858/ (accessed 08.03.2023). (In Russian).
2. Ministry of Digital Development, Communications and Mass Media of the Russian Federation. Direction of activity «Digital technologies» of the national project «Digital Economy of the Russian Federation». https://digital.gov.ru/ru/activity/directions/878/(accessed 08.03.2023). (In Russian).
3. Korte B., Vygen J. Combinatorial Optimization. Theory and Algorithms. Heidelberg: Springer Berlin; 2000. 2018. https://doi.org/10.1007/978-3-662-21708-5
4. Korbut A.A., Finkelshtein Yu.Yu., Discrete programming. Moscow: Nauka; 1969. (In Russian).
5. Balinski M.L. Fixed-cost transportation problems. Naval Research Logistics Quarterly. 1961;8(1):41–54 pp. https://doi.org/10.1002/nav.3800080104
6. Göthe-Lundgren M., Larsson T. A set covering reformulation of the pure fixed charge transportation problem. Discrete Appl. Math. 1994;48(3):245–259 pp. https://doi.org/10.1016/0166-218X(92)00177-N
7. Kowalski K., Lev B. On step fixed-charge transportation problem. Omega. 2008;36(5):913–917 pp. https://doi.org/10.1016/j.omega.2007.11.001
8. Raj K.A.A.D., Rajendran C. Fast heuristic algorithms to solve a single-stage Fixed-Charge Transportation Problem. International Journal of Operational Research. 2009;6(3):304–329 pp. https://doi.org/10.1504/IJOR.2009.026936
9. Agarwal Y., Aneja Y. Fixed-charge transportation problem: Facets of the projection polyhedron. Operational Research. 2012;60(3):638–654 pp. https://doi.org/10.1287/opre.1120.1041
10. Roberti R., Bartolini E., Mingozzi A. The Fixed Charge Transportation Problem: An Exact Algorithm Based on a New Integer Programming Formulation. Management Science. 2014;61(6):1275–1291 pp. https://doi.org/10.1287/mnsc.2014.1947
11. Cormen T.H., Leiserson Ch.E., Rivest R.L., Stein C. Introduction to Algorithms. The MIT Press; 2022. (In Russian).
12. Bertazzi L., Maggioni F. A stochastic multi-stage fixed charge transportation problem: Worst-case analysis of the rolling horizon approach. European Journal of Operational Research. 2017;267(2):555–569 pp. https://doi:10.1016/j.ejor.2017.12.004
13. Sudha G., Ganesan K. Interval-Fuzzy Fixed Charge Transportation Problems. International Journal of Fuzzy System Applications. 2022;11(3):1–14 pp. http://doi.org/10.4018/IJFSA.306281
14. Cavada M., Rogers C., Hunt D. Smart Cities: Contradicting Definitions and Unclear Measures. Proceedings of the 4th World Sustainability Forum, 1–30 November 2014. Basel: MDPI; 2014. 12 p. https://doi.org/10.3390/wsf-4-f004
15. Ministry of Construction, Housing and Communal Services of the Russian Federation. National project «Smart City». https://russiasmartcity.ru/about (accessed 12.03.2023). (In Russian).
16. Russian Federation. Department of the City of Moscow on competition Policy, Department of Information Technologies of the city of Moscow. Supplier portal. Operational purchases of goods, works and services.https://zakupki.mos.ru/ (accessed 14.03.2023).
Review
For citations:
Egorov V.V. Discrete optimizations’ problems of deliveries of heterogeneous products. Vestnik Universiteta. 2023;(5):70-76. (In Russ.) https://doi.org/10.26425/1816-4277-2023-5-70-76