Задачі побудови кільцевих маршрутів транспортних засобів у багатопродуктовій ієрархічній мережі
The paper formulates mathematical models for the problems of constructingring routes of vehicles in a multicommodity hierarchical network. As a rule,such networks consist of a decentralized backbone network and networks inthe internal service areas of the backbone nodes (internal networks). In amult...
Gespeichert in:
| Datum: | 2023 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
2023
|
| Schlagworte: | |
| Online Zugang: | https://jais.net.ua/index.php/files/article/view/58 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems of Control and Informatics |
Institution
Problems of Control and Informatics| id |
oai:ojs2.jais.net.ua:article-58 |
|---|---|
| record_format |
ojs |
| institution |
Problems of Control and Informatics |
| baseUrl_str |
|
| datestamp_date |
2024-03-13T12:59:27Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
багатопродуктові ієрархічні мережі задачі комбінаторної оптимізації математичні моделі кільцевих маршрутів транспортних засобів |
| spellingShingle |
багатопродуктові ієрархічні мережі задачі комбінаторної оптимізації математичні моделі кільцевих маршрутів транспортних засобів Vasyanin, Volodymyr Trofymchuk, Oleksandr Ushakova, Lyudmila Задачі побудови кільцевих маршрутів транспортних засобів у багатопродуктовій ієрархічній мережі |
| topic_facet |
багатопродуктові ієрархічні мережі задачі комбінаторної оптимізації математичні моделі кільцевих маршрутів транспортних засобів multicommodity hierarchical networks combinatorial optimization problems mathematical models of vehicle ring routes многопродуктовые иерархические сети задачи комбинаторной оптимизации математические модели кольцевых маршрутов транспортных средств |
| format |
Article |
| author |
Vasyanin, Volodymyr Trofymchuk, Oleksandr Ushakova, Lyudmila |
| author_facet |
Vasyanin, Volodymyr Trofymchuk, Oleksandr Ushakova, Lyudmila |
| author_sort |
Vasyanin, Volodymyr |
| title |
Задачі побудови кільцевих маршрутів транспортних засобів у багатопродуктовій ієрархічній мережі |
| title_short |
Задачі побудови кільцевих маршрутів транспортних засобів у багатопродуктовій ієрархічній мережі |
| title_full |
Задачі побудови кільцевих маршрутів транспортних засобів у багатопродуктовій ієрархічній мережі |
| title_fullStr |
Задачі побудови кільцевих маршрутів транспортних засобів у багатопродуктовій ієрархічній мережі |
| title_full_unstemmed |
Задачі побудови кільцевих маршрутів транспортних засобів у багатопродуктовій ієрархічній мережі |
| title_sort |
задачі побудови кільцевих маршрутів транспортних засобів у багатопродуктовій ієрархічній мережі |
| title_alt |
Constructing problems of vehicles ring routes in multicommodity hierarchical network Задачи построения кольцевых маршрутов транспортных средств в многопродуктовой иерархической сети |
| description |
The paper formulates mathematical models for the problems of constructingring routes of vehicles in a multicommodity hierarchical network. As a rule,such networks consist of a decentralized backbone network and networks inthe internal service areas of the backbone nodes (internal networks). In amulticommodity network, each node can exchange products (goods, cargo)with all other nodes. In foreign literature, the design problems of such networks are called Multi-Echelon Location-Routing Problem (ME LRP). InMulti-Echelon LRPs, there are multiple intermediaries between the backbone nodes (central primary nodes) and nodes in the inner zones of thebackbone nodes (end customers, clients), and the distributed product fromthe backbone nodes passes through two or more secondary of intermediaries(called satellites) before reaching the end consumer. In classical LRP twoproblems are combined for a joint solution — the problem of determiningthe location of secondary objects (satellites or depots) and main backboneroutes of vehicles and the problem of constructing ring routes of internal vehicles to serve customers with a known demand for a homogeneous interchangeable product. Unlike distribution problems for a homogeneous interchangeable product, in multicommodity LRP (MC LRP), product flows arenot interchangeable — the flow of each product must be delivered from aspecific primary object to a specific client. In this paper, it is assumed thatthe multi-level structure of the transport network has already been determined and the geographic location of the backbone nodes and their internalservice areas with the set of pickup and delivery cargo nodes (clients) areknown. Therefore, the problems of determining the main backbone routes ofvehicles and constructing ring routes of internal vehicles are considered independently of each other. The types of costs of real transport processes arediscussed, which should be taken into account when forming the objectivefunction of routing problems, and mathematical models are proposed for theproblems of constructing combined (Vehicle Routing Problem with Simultaneous Pickup and Delivery) and split (The Split Delivery Vehicle RoutingProblem) ring routes with a heterogeneous fleet of vehicles. The possibilityof solving the formulated problems with the help of well-known packages ofmixed and integer linear programming is noted. |
| publisher |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine |
| publishDate |
2023 |
| url |
https://jais.net.ua/index.php/files/article/view/58 |
| work_keys_str_mv |
AT vasyaninvolodymyr constructingproblemsofvehiclesringroutesinmulticommodityhierarchicalnetwork AT trofymchukoleksandr constructingproblemsofvehiclesringroutesinmulticommodityhierarchicalnetwork AT ushakovalyudmila constructingproblemsofvehiclesringroutesinmulticommodityhierarchicalnetwork AT vasyaninvolodymyr zadačipostroeniâkolʹcevyhmaršrutovtransportnyhsredstvvmnogoproduktovojierarhičeskojseti AT trofymchukoleksandr zadačipostroeniâkolʹcevyhmaršrutovtransportnyhsredstvvmnogoproduktovojierarhičeskojseti AT ushakovalyudmila zadačipostroeniâkolʹcevyhmaršrutovtransportnyhsredstvvmnogoproduktovojierarhičeskojseti AT vasyaninvolodymyr zadačípobudovikílʹcevihmaršrutívtransportnihzasobívubagatoproduktovíjíêrarhíčníjmereží AT trofymchukoleksandr zadačípobudovikílʹcevihmaršrutívtransportnihzasobívubagatoproduktovíjíêrarhíčníjmereží AT ushakovalyudmila zadačípobudovikílʹcevihmaršrutívtransportnihzasobívubagatoproduktovíjíêrarhíčníjmereží |
| first_indexed |
2025-10-30T02:48:34Z |
| last_indexed |
2025-10-30T02:48:34Z |
| _version_ |
1847373347359293440 |
| spelling |
oai:ojs2.jais.net.ua:article-582024-03-13T12:59:27Z Constructing problems of vehicles ring routes in multicommodity hierarchical network Задачи построения кольцевых маршрутов транспортных средств в многопродуктовой иерархической сети Задачі побудови кільцевих маршрутів транспортних засобів у багатопродуктовій ієрархічній мережі Vasyanin, Volodymyr Trofymchuk, Oleksandr Ushakova, Lyudmila багатопродуктові ієрархічні мережі задачі комбінаторної оптимізації математичні моделі кільцевих маршрутів транспортних засобів multicommodity hierarchical networks combinatorial optimization problems mathematical models of vehicle ring routes многопродуктовые иерархические сети задачи комбинаторной оптимизации математические модели кольцевых маршрутов транспортных средств The paper formulates mathematical models for the problems of constructingring routes of vehicles in a multicommodity hierarchical network. As a rule,such networks consist of a decentralized backbone network and networks inthe internal service areas of the backbone nodes (internal networks). In amulticommodity network, each node can exchange products (goods, cargo)with all other nodes. In foreign literature, the design problems of such networks are called Multi-Echelon Location-Routing Problem (ME LRP). InMulti-Echelon LRPs, there are multiple intermediaries between the backbone nodes (central primary nodes) and nodes in the inner zones of thebackbone nodes (end customers, clients), and the distributed product fromthe backbone nodes passes through two or more secondary of intermediaries(called satellites) before reaching the end consumer. In classical LRP twoproblems are combined for a joint solution — the problem of determiningthe location of secondary objects (satellites or depots) and main backboneroutes of vehicles and the problem of constructing ring routes of internal vehicles to serve customers with a known demand for a homogeneous interchangeable product. Unlike distribution problems for a homogeneous interchangeable product, in multicommodity LRP (MC LRP), product flows arenot interchangeable — the flow of each product must be delivered from aspecific primary object to a specific client. In this paper, it is assumed thatthe multi-level structure of the transport network has already been determined and the geographic location of the backbone nodes and their internalservice areas with the set of pickup and delivery cargo nodes (clients) areknown. Therefore, the problems of determining the main backbone routes ofvehicles and constructing ring routes of internal vehicles are considered independently of each other. The types of costs of real transport processes arediscussed, which should be taken into account when forming the objectivefunction of routing problems, and mathematical models are proposed for theproblems of constructing combined (Vehicle Routing Problem with Simultaneous Pickup and Delivery) and split (The Split Delivery Vehicle RoutingProblem) ring routes with a heterogeneous fleet of vehicles. The possibilityof solving the formulated problems with the help of well-known packages ofmixed and integer linear programming is noted. Формулируются математические модели задач построения кольцевых маршрутов транспортных средств в многопродуктовой иерархической сети. Как правило, такие сети состоят из децентрализованной магистральной сети и сетей во внутренних зонах обслуживания магистральных узлов (внутренних сетей). В многопродуктовой сети каждый узел может обмениваться продуктами (товарами, грузами) с другими узлами. В зарубежной литературе задачи проектирования таких сетей называют задачами многоступенчатого (многоуровневого, многоуровневого) размещения и маршрутизации (Multi-Echelon Location-Routing Problem - ME LRP). В многоступенчатых LRP имеется несколько посредников между магистральными узлами (центральными первичными объектами) и узлами во внутренних зонах магистральных узлов (конечными потребителями, клиентами), а продукт, распределяемый из магистральных узлов, проходит через два или более второстепенных посредников в сети (сателлитов) к конечному потребителю. В классической LRP объединены для совместного решения две задачи – задача определения расположения вторичных объектов (сателлитов или депо) и магистральных маршрутов транспортных средств и задача построения кольцевых маршрутов внутренних транспортных средств для обслуживания клиентов с известным спросом на однородный взаимозаменяемый продукт. В отличие от задач распределения однородного взаимозаменяемого продукта, в многопродуктовых задачах LRP (Multi-Commodity Location-Routing Problem — MC LRP) потоки продуктов не взаимозаменяемы, поток каждого продукта должен быть доставлен с определенного первичного объекта к конкретному клиенту. Предполагается, что многоуровневая структура транспортной сети определена и известно географическое расположение магистральных узлов и его внутренние зоны обслуживания с множеством узлов доставки и сбора грузов (клиентов). Поэтому задачи определения магистральных маршрутов транспортных средств и построения кольцевых маршрутов внутренних транспортных средств рассматриваются независимо друг от друга. Обсуждаются виды затрат реальных транспортных процессов, которые должны учитываться при формировании целевой функции задач маршрутизации и предложены математические модели задач построения комбинированных и разделенных кольцевых маршрутов с неоднородным парком транспортных средств. Указывается возможность решения сформулированных задач с помощью известных пакетов смешанного и целочисленного линейного программирования. Формулюються математичні моделі задач побудови кільцевих маршрутів транспортних засобів у багатопродуктовій ієрархічній мережі.Як правило, такі мережі складаються з децентралізованої магістральноїмережі та мереж у внутрішніх зонах обслуговування магістральнихвузлів (внутрішніх мереж). У багатопродуктовій мережі кожен вузолможе обмінюватися продуктами (товарами, вантажами) з іншими вузлами. У зарубіжній літературі задачі проектування таких мереж називаютьзадачами багатоступінчастого (багатоешелонного, багаторівневого) розміщення та маршрутизації (Multi-Echelon Location-Routing Problem —ME LRP). У багатоступінчастих LRP є кілька посередників між магістральними вузлами (центральними первинними об’єктами) і вузламиу внутрішніх зонах магістральних вузлів (кінцевими споживачами, клієнтами), а продукт, що розподіляється з магістральних вузлів, проходить через два або більше другорядних посередників у мережі (сателітів) до кінцевого споживача. У класичній LRP об’єднані для спільногорозв’язання дві задачі — задача визначення розташування вториннихоб’єктів (сателітів або депо) та магістральних маршрутів транспортнихзасобів та задача побудови кільцевих маршрутів внутрішніх транспортних засобів для обслуговування клієнтів з відомим попитом на однорідний взаємозамінний продукт. На відміну від задач розподілу однорідного взаємозамінного продукту, у багатопродуктових задачах LRP(Multi-Commodity Location-Routing Problem — MC LRP) потоки продуктівне взаємозамінні, потік кожного продукту має бути доставлений з певного первинного об’єкта до конкретного клієнта. Передбачається,що багаторівнева структура транспортної мережі визначена і відомігеографічне розташування магістральних вузлів та його внутрішні зониобслуговування з множиною вузлів доставки і збору вантажів (клієнтів). Тому задачі визначення магістральних маршрутів транспортнихзасобів та побудови кільцевих маршрутів внутрішніх транспортних засобів розглядаються незалежно одна від одної. Обговорюються видивитрат реальних транспортних процесів, які мають враховуватися приформуванні цільової функції задач маршрутизації та запропоновані математичні моделі задач побудови комбінованих та розділених кільцевихмаршрутів із неоднорідним парком транспортних засобів. Зазначаєтьсяможливість розв’язання сформульованих задач за допомогою відомих пакетів змішаного та цілочисельного лінійного програмування. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2023-07-07 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/58 10.34229/2786-6505-2022-3-3 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 67 № 3 (2022): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 37-55 International Scientific Technical Journal "Problems of Control and Informatics; Том 67 № 3 (2022): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 37-55 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 67 No. 3 (2022): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 37-55 2786-6505 2786-6491 10.34229/2786-6505-2022-3 uk https://jais.net.ua/index.php/files/article/view/58/129 Copyright (c) 2022 Volodymyr Vasyanin, Oleksandr Trofymchuk, Lyudmila Ushakova https://creativecommons.org/licenses/by-nc-nd/4.0/ |