Задача маршрутизації міжбанківських фінансових зобов’язань
The problem of speeding up cross-currency transfers and mutual settlements between banks with the increasing amount of national electronic currencies, cryptocurrencies, and the overall volume of financial transactions can be considered as a routing problem. The solving time of this class of combinat...
Gespeichert in:
| Datum: | 2023 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Schlagworte: | |
| Online Zugang: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/289 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479660215926784 |
|---|---|
| author | Korolyov, Vyacheslav Ogurtsov, Maksym Khodzinskyi, Oleksandr |
| author_facet | Korolyov, Vyacheslav Ogurtsov, Maksym Khodzinskyi, Oleksandr |
| author_institution_txt_mv | [
{
"author": "Vyacheslav Korolyov",
"institution": "к. т. н., с.н.с. Інститут кібернетики ім. В.М. Глушкова НАН України, просп. Глушкова, 40, к. 801, 03680, Київ"
},
{
"author": "Maksym Ogurtsov",
"institution": "науковий співробітник ІК НАНУ"
},
{
"author": "Oleksandr Khodzinskyi",
"institution": "к. ф-м. н., с.н.с., ІК НАНУ"
}
] |
| author_sort | Korolyov, Vyacheslav |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:32:19Z |
| description | The problem of speeding up cross-currency transfers and mutual settlements between banks with the increasing amount of national electronic currencies, cryptocurrencies, and the overall volume of financial transactions can be considered as a routing problem. The solving time of this class of combinatorial  optimization  problems  can  be  significantly  reduced  by  using  hybrid  quantum-classical cloud services and heuristic algorithms, which provide approximate solutions for such problems. Numerical experiments were conducted on a hybrid service provided by the company D-Wave  using  the  quantum  annealing  algorithm  and  algorithms  from  the  networkx  library  to compare the speed of solving the traveling salesman problem for a fully connected graph with 105 vertices.  The  developed  routing  algorithms  provide  an  approximate  solution  to  TSP  or  VRP problems on D-Wave quantum computers in approximately 30 milliseconds. |
| first_indexed | 2026-06-09T01:09:48Z |
| format | Article |
| fulltext |
121
doi.org/10.15407/fmmit2023.36.121
Задача маршрутизації міжбанківських фінансових
зобов’язань
Вячеслав Корольов1, Максим Огурцов2, Олександр Ходзінський3
1 к. т. н., с.н.с. Інститут кібернетики ім. В.М. Глушкова НАН України, просп. Глушкова, 40, к. 801, 03680, Київ,
e-mail: korolev.academ@gmail.com
2 науковий співробітник ІК НАНУ, e-mail: maksymogurtsov@gmail.com
3 к. ф-м. н., с.н.с., ІК НАНУ, e-mail: okhodz@gmail.com
Проблему прискорення міжвалютних переказів та взаємних заліків між банками при
зростанні кількості національних електронних грошей, криптовалют та загального обсягу
фінансових трансакцій можна розглядати як спеціальну задачу маршрутизації. Час
розв’язування цього класу задач комбінаторної оптимізації можна суттєво скоротити
при застосуванні гібридних квантово-класичних хмарних сервісів та евристичних
алгоритмів, які знаходять наближені розв’язки. Для порівняння швидкості розв’язування
задачі комівояжера для повнозв’язного графу з 105 вершинами виконано чисельні
експерименти на гібридному сервісі фірми D-Wave алгоритмом квантового відпалу та
алгоритмами з бібліотеки networkx. Розроблені алгоритми маршрутизації забезпечують
наближене розв'язування задач комівояжера чи задач маршрутизації транспортних
засобів на квантових комп’ютерах D-Wave за прийнятний час.
Ключові слова: фінансові операції, маршрутизація, оптимізація
транзакцій, квантові обчислення, хмарний сервіс
Вступ. Комбінаторна оптимізація широко використовується нині у різних
сферах, зокрема, у логістиці, фармацевтиці, біоінформатиці, а також у фінансовій
сфері. Розвиток гібридних квантово-класичних обчислень дозволив прискорити
розв’язування багатьох відомих задач на графах, нині важливим аспектом є їх
застосування є сфера міжбанківських фінансових зобов’язань.
Метою даної роботи є змістовна постановка проблем оптимальної маршрутизації
для фінансових взаємних заліків як спеціальної задачі комбінаторної оптимізації
та дослідження можливостей розв'язування цієї задачі на квантових
комп’ютерах.
1. Змістовна постановка задачі маршрутизації для фінансових взаємних
заліків
Розглянемо ідею зменшення мережевих взаємних розрахунків між банками, що
оперують валютами та цінними паперами. Наприклад, банк №1 заборгував банку
№2 10 мільйонів доларів, а банк №2 винний банку №1 дев'ять мільйонів доларів.
Зрозуміло, що можна зробити взаємний залік і переказати по мережі один
УДК 519.8
mailto:korolev.academ@gmail.com
mailto:maksymogurtsov@gmail.com
mailto:okhodz@gmail.com
Вячеслав Корольов, Максим Огурцов, Олександр Ходзінський
Задача маршрутизації міжбанківських фінансових зобов’язань
122
мільйон доларів, тобто скоротити (оптимізувати) потоки електронних грошей.
Така задача не надто ускладнюється навіть, якщо використовуються, наприклад,
три валюти: долар США, британський фунт та євро.
Втім, коли відбувається перехід до транскордонної торгівлі, валют стає
набагато більше, і задача оптимізації потоків стає вже обчислювально складною.
Наведемо деяку статистику по системі MasterCard, щоб зрозуміти масштаб
мережі і складність задачі. MasterCard працює в 210 країнах в 150 валютах, зараз
випущено майже 3 мільярди пластикових карт. По цих картах циркулює більше
шести трильйонів доларів і користувачі карток та різні установи хочуть, щоб
перекази виконувались в реальному масштабі часу, наприклад, за п’ять секунд,
що визначає час на розв’язування задачі взаємних заліків між банками [1, 2].
Задача зменшення міжбанківських переказів може зводитись до задачі
маршрутизації, яка розглядається у комбінаторній оптимізації (КО). Тобто банки
можна розглядати як пункти доставки, які пропонують або потребують різні
види валюти; швидкість виконання банками трансакцій – це час доставки товарів
транспортними засобами; кількість одночасних переказів – кількість
транспортних засобів. Крім часу на вартість шляху впливає вартість послуг
переказів, які беруть банки та податки, що збирає держава, де зареєстрований
банк або фінансова установа. Для MasterCard основним обмеженням є час
виконання і підтвердження трансакції [2]. Класичний підхід до трансакцій через
долар не завжди вирішує питання, що і спричиняє потребу у застосуванні
алгоритмів оптимальної маршрутизації.
Таким чином, задачу поставки конкретному банку певного обсягу обраної
валюти з встановленими обмеженнями по часу можна подати у вигляді
спеціальної задачі маршрутизації з обмеженнями.
2. Постановка задачі балансування ліквідності у вигляді задачі КО
Розглянемо постановку задачі з точки зору одного банку. До кінця робочого дня
Банк має закрити розрахунки з іншими фінансовими установами (далі –
Партнери), яким Банк винен певну суму (від’ємні борги) – або які винні певну
суму Банку (додатні). При цьому як Банк, так і кожен Партнер має обмежену
кількість грошей на рахунку (рис. 3а). Між Банком та кожним Партнером (та в
будь-якої пари Партнерів) є фіксована комісія на пересилання грошей, результат
множення якої на об’єм переводу грошей можна вважати вартістю маршруту.
Очевидним варіантом розв’язання задачі є послідовний розрахунок з
кожним з Партнерів. Але при цьому може виникнути ситуація, коли в Банка (чи
Партнера) недостатньо грошей на рахунку для успішного розрахунку. До того ж
в цьому випадку матимемо максимальні комісії за пересилання грошей –
максимальну вартість маршруту. Тому пропонується цю задачу розбити на дві
підзадачі: перша включатиме виконання взаємозаліків між Партнерами, друга –
фінальний розрахунок з Банком. При цьому не кожна пара Партнерів
обов’язково мають прямі відносини – тож матимемо ряд заборонених маршрутів.
Додаткові обмеження будуть викликані часовими вікнами роботи Банку та
кожного з Партнерів, що можуть значно відрізнятись через різні часові пояси.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 121-125
123
25
-40
40
-7
-32
22
-47
52
-11
2
а б
25
-5
-10
5
-11
в г
Рис. 3. Балансування ліквідності банку у вигляді задачі КО
В поточній постановці перша підзадача може розв’язуватись, наприклад,
шляхом сортування боргів перед Банком та визначення найбільш близьких
додатних та від’ємних боргів для виконання взаємного заліку (рис. 3б),
враховуючи заборонені маршрути. При цьому певні Партнери, борг яких
повністю закривається на цьому кроці, можуть бути виключені з другої підзадачі
(рис 3в).
Далі слід розв’язати другу підзадачу, побудувавши послідовність
розрахунків (маршрут) з Партнерами, що залишились (рис 3г), мінімізуючи
загальну вартість маршруту та враховуючи часові вікна. Окрім комісії за
переклад, яка залежить від обсягу грошей, що переводяться, в Банку також
присутня й фіксована комісія за кожну операцію, тому розрахунок з кожним
Партнером слід виконувати за одну операцію (жодна точка не може бути
відвідана більше ніж один раз). Таким чином другу підзадачу було зведено до
задачі комівояжера з часовими вікнами та додатковими обмеженнями. Більш
складні постановки задачі, що включатимуть потреби кількох банків одночасно,
можуть відповідно бути перетворені та подані у вигляді, близькому до відомих
задач маршрутизації транспортних засобів (Vehicle Routing Problem – VRP) [2].
Розглянемо, як подібні задачі можуть розв'язуватися з використанням квантово-
класичних обчислень.
Вячеслав Корольов, Максим Огурцов, Олександр Ходзінський
Задача маршрутизації міжбанківських фінансових зобов’язань
124
3. Застосування гібридних хмарних сервісів до розв’язування тестової задачі
Для порівняння швидкості розв’язування задачі комівояжера для повнозв’язного
графу зі 105 вершинами виконано обчислювальні експерименти на гібридному
сервісі фірми D-Wave з використанням алгоритму квантового відпалу та
алгоритмами з бібліотеки networkx [4] (табл. 1).
Таблиця 1
Час розв’язування задачі комівояжера на традиційному комп’ютері та на гібридному квантово-
класичному хмарному сервісі для випадкового повнозв’язного графа зі 105 вершинами
№ Назва алгоритму Час виконання, сек
1 Квантовий відпал на гібр. кв.-клас. 34.7277×10-3
2 Жадібний алгоритм 0.002748
3 Алгоритм christofides 0.109148
4 Алгоритм traveling_salesman_problem 0.766987
5 Пороговий алгоритм зі початком від жадібного 0.188068
6 Алгоритм відпалу (на тому ж сервері без КК) 0.219865
Висновки. Виконано змістовну постановку задачі маршрутизації для фінансових
взаємних заліків як спеціальної задачі КО. Проаналізовано особливості та
складності, що виникають при взаємних заліках фінансових установ, включаючи
транскордонні та мультивалютні операції.
Задачу балансування ліквідності банку розбито на дві підзадачі. Перша
підзадача КО враховуватиме доступні можливості взаємозаліків між
банківськими установами-партнерами з урахуванням можливої відсутності
прямих взаємовідносин від ними. Другу підзадачу зведено до задачі КО – задачі
комівояжера з додатковими обмеженнями.
Сучасні квантові комп’ютери [1] можуть провадити обчислювання в
алгоритмах лише з обмеженою глибиною квантової схеми (кількістю зв’язків
між кубітами) за обмежену кількість кроків. Розроблені фірмою D-wave
алгоритми маршрутизації забезпечують наближене розв'язування задач
комівояжера чи задач маршрутизації транспортних засобів на квантових
комп’ютерах D-Wave приблизно за 30 мілісекунд. Алгоритми VRP/CVRP зі
складними обмеженнями можуть не знайти розв’язок або надати розв’язок з
втраченими пунктами відвідування, що є наслідком обмеженої глибини
квантової схеми та технологічної недосконалості квантового комп’ютера
адіабатичного типу.
Проведені (для повнозв’язного графу зі 105 вершинами) обчислювальні
експерименти показали, що розв’язування задачі комівояжера за допомогою
гібридного квантово-класичного хмарного сервісу D-wave може дозволити
отримати розв’язки задачі з меншим, ніж 5-6% відхиленням від оптимального
значення функції вартості.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 121-125
125
Література
[1] McMahon C, McGillivray D, Desai A, Rivadeneyra F, Lam JP, Lo T, Marsden D, Skavysh V.
Improving the Efficiency of Payments Systems Using Quantum Computing. — arXiv preprint
arXiv:2209.15392, 2022. (звернення 02.02.2023) https://arxiv.org/abs/2209.15392
[2] Доповідь з науково-прикладної конференції розробника квантових комп’ютерів D-Wave 19-
21 січня 2023. Quantum in Finance – MasterCard (звернення 02.02.2023)
https://www.youtube.com/watch?v=ihWLf_ywgmg
[3] Hulianytskyi L.F., Korolyov V.Yu., Khodzinskyi O.M. Solving the Problem of Vehicle Routing on
Modern Quantum-Classical Cloud Services. Selected Papers of the VIII International Scientific
Conference “Information Technology and Implementation" (IT&I-2021). Conference
Proceedings, Kyiv, Ukraine, December 01-03, 2021. p. 281-289. https://ceur-ws.org/Vol-
3132/Short_9.pdf
[4] Hagberg A, Conway D. Networkx: Network analysis with python. – 2020
https://networkx.github.io
The interbank financial obligations routing problem
Vyacheslav Korolyov, Maksym Ogurtsov, Oleksandr Khodzinskyi
The problem of speeding up cross-currency transfers and mutual settlements between banks with
the increasing amount of national electronic currencies, cryptocurrencies, and the overall volume
of financial transactions can be considered as a routing problem. The solving time of this class of
combinatorial optimization problems can be significantly reduced by using hybrid quantum-
classical cloud services and heuristic algorithms, which provide approximate solutions for such
problems. Numerical experiments were conducted on a hybrid service provided by the company
D-Wave using the quantum annealing algorithm and algorithms from the networkx library to
compare the speed of solving the traveling salesman problem for a fully connected graph with 105
vertices. The developed routing algorithms provide an approximate solution to TSP or VRP
problems on D-Wave quantum computers in approximately 30 milliseconds.
Отримано 31.03.23
https://arxiv.org/abs/2209.15392
https://www.youtube.com/watch?v=ihWLf_ywgmg
https://icyb180.org.ua/staff/hulianytskyi/
https://icyb180.org.ua/staff/korolyov/
https://icyb180.org.ua/staff/okhodz/
https://icyb180.org.ua/publications/solving-the-problem-of-vehicle-routing-on-modern-quantum-classical-cloud-services/
https://icyb180.org.ua/publications/solving-the-problem-of-vehicle-routing-on-modern-quantum-classical-cloud-services/
https://ceur-ws.org/Vol-3132/Short_9.pdf
https://ceur-ws.org/Vol-3132/Short_9.pdf
https://networkx.github.io/
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-289 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:09:48Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/f4/dd1e28d5abaae963e66c8f25555c87f4.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-2892025-02-21T17:32:19Z The interbank financial obligations routing problem Задача маршрутизації міжбанківських фінансових зобов’язань Korolyov, Vyacheslav Ogurtsov, Maksym Khodzinskyi, Oleksandr фінансові операції, маршрутизація, оптимізація транзакцій, квантові обчислення, хмарний сервіс The problem of speeding up cross-currency transfers and mutual settlements between banks with the increasing amount of national electronic currencies, cryptocurrencies, and the overall volume of financial transactions can be considered as a routing problem. The solving time of this class of combinatorial  optimization  problems  can  be  significantly  reduced  by  using  hybrid  quantum-classical cloud services and heuristic algorithms, which provide approximate solutions for such problems. Numerical experiments were conducted on a hybrid service provided by the company D-Wave  using  the  quantum  annealing  algorithm  and  algorithms  from  the  networkx  library  to compare the speed of solving the traveling salesman problem for a fully connected graph with 105 vertices.  The  developed  routing  algorithms  provide  an  approximate  solution  to  TSP  or  VRP problems on D-Wave quantum computers in approximately 30 milliseconds. Проблему  прискорення  міжвалютних  переказів  та  взаємних  заліків  між  банками  при зростанні кількості національних електронних грошей, криптовалют та загального обсягу фінансових  трансакцій  можна  розглядати  як  спеціальну  задачу  маршрутизації.  Час розв’язування  цього  класу  задач  комбінаторної  оптимізації  можна  суттєво  скоротити при  застосуванні  гібридних  квантово-класичних  хмарних  сервісів  та  евристичних алгоритмів,  які  знаходять  наближені  розв’язки.  Для  порівняння  швидкості  розв’язування задачі  комівояжера  для  повнозв’язного  графу  з  105  вершинами  виконано  чисельні експерименти  на  гібридному  сервісі  фірми  D-Wave  алгоритмом  квантового  відпалу  та алгоритмами  з  бібліотеки  networkx.  Розроблені  алгоритми  маршрутизації  забезпечують наближене  розв'язування  задач  комівояжера  чи  задач  маршрутизації  транспортних засобів на квантових комп’ютерах D-Wave за прийнятний час.  Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-13 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/289 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 121-125 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 121-125 2617-5258 1816-1545 10.15407/fmmit2023.36 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/289/241 Авторське право (c) 2023 Вячеслав Корольов, Максим Огурцов, Олександр Ходзінський (Автор) |
| spellingShingle | фінансові операції маршрутизація оптимізація транзакцій квантові обчислення хмарний сервіс Korolyov, Vyacheslav Ogurtsov, Maksym Khodzinskyi, Oleksandr Задача маршрутизації міжбанківських фінансових зобов’язань |
| title | Задача маршрутизації міжбанківських фінансових зобов’язань |
| title_alt | The interbank financial obligations routing problem |
| title_full | Задача маршрутизації міжбанківських фінансових зобов’язань |
| title_fullStr | Задача маршрутизації міжбанківських фінансових зобов’язань |
| title_full_unstemmed | Задача маршрутизації міжбанківських фінансових зобов’язань |
| title_short | Задача маршрутизації міжбанківських фінансових зобов’язань |
| title_sort | задача маршрутизації міжбанківських фінансових зобов’язань |
| topic | фінансові операції маршрутизація оптимізація транзакцій квантові обчислення хмарний сервіс |
| topic_facet | фінансові операції маршрутизація оптимізація транзакцій квантові обчислення хмарний сервіс |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/289 |
| work_keys_str_mv | AT korolyovvyacheslav theinterbankfinancialobligationsroutingproblem AT ogurtsovmaksym theinterbankfinancialobligationsroutingproblem AT khodzinskyioleksandr theinterbankfinancialobligationsroutingproblem AT korolyovvyacheslav zadačamaršrutizacíímížbankívsʹkihfínansovihzobovâzanʹ AT ogurtsovmaksym zadačamaršrutizacíímížbankívsʹkihfínansovihzobovâzanʹ AT khodzinskyioleksandr zadačamaršrutizacíímížbankívsʹkihfínansovihzobovâzanʹ AT korolyovvyacheslav interbankfinancialobligationsroutingproblem AT ogurtsovmaksym interbankfinancialobligationsroutingproblem AT khodzinskyioleksandr interbankfinancialobligationsroutingproblem |