Про задачу вивозу і доставки вантажу з часовими вікнами
Розглянуто узагальнення задачі маршрутизації з часовими вікнами – задачу вивозу і доставки вантажу з часовими вікнами. Проводиться порівняльний аналіз таких методів розв’язання поставленої задачі як груповий генетичний алгоритм та евристика адаптивного пошуку відкритої області....
Gespeichert in:
| Datum: | 2008 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Schriftenreihe: | Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/18560 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Про задачу вивозу і доставки вантажу з часовими вікнами / А.В. Атаманюк // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2008. — Вип. 1. — С. 4-9. — Бібліогр.: 4 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-18560 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-185602011-04-03T12:04:04Z Про задачу вивозу і доставки вантажу з часовими вікнами Атаманюк, А.В. Розглянуто узагальнення задачі маршрутизації з часовими вікнами – задачу вивозу і доставки вантажу з часовими вікнами. Проводиться порівняльний аналіз таких методів розв’язання поставленої задачі як груповий генетичний алгоритм та евристика адаптивного пошуку відкритої області. The author examined a generalization of the Vehicle Routing Problem with Time Windows – Pickup and Delivery Problem with Time Windows. The comparative analysis of methods to solve the problem is fulfilled. 2008 Article Про задачу вивозу і доставки вантажу з часовими вікнами / А.В. Атаманюк // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2008. — Вип. 1. — С. 4-9. — Бібліогр.: 4 назв. — укр. XXXX-0059 http://dspace.nbuv.gov.ua/handle/123456789/18560 519.23 uk Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
Розглянуто узагальнення задачі маршрутизації з часовими вікнами – задачу вивозу і доставки вантажу з часовими вікнами. Проводиться порівняльний аналіз таких методів розв’язання поставленої задачі як груповий генетичний алгоритм та евристика адаптивного пошуку відкритої області. |
| format |
Article |
| author |
Атаманюк, А.В. |
| spellingShingle |
Атаманюк, А.В. Про задачу вивозу і доставки вантажу з часовими вікнами Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
| author_facet |
Атаманюк, А.В. |
| author_sort |
Атаманюк, А.В. |
| title |
Про задачу вивозу і доставки вантажу з часовими вікнами |
| title_short |
Про задачу вивозу і доставки вантажу з часовими вікнами |
| title_full |
Про задачу вивозу і доставки вантажу з часовими вікнами |
| title_fullStr |
Про задачу вивозу і доставки вантажу з часовими вікнами |
| title_full_unstemmed |
Про задачу вивозу і доставки вантажу з часовими вікнами |
| title_sort |
про задачу вивозу і доставки вантажу з часовими вікнами |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2008 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/18560 |
| citation_txt |
Про задачу вивозу і доставки вантажу з часовими вікнами / А.В. Атаманюк // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2008. — Вип. 1. — С. 4-9. — Бібліогр.: 4 назв. — укр. |
| series |
Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
| work_keys_str_mv |
AT atamanûkav prozadačuvivozuídostavkivantažuzčasovimivíknami |
| first_indexed |
2025-07-02T19:32:52Z |
| last_indexed |
2025-07-02T19:32:52Z |
| _version_ |
1836564897125629952 |
| fulltext |
Математичне та комп’ютерне моделювання
4
УДК 519.23
А. В. Атаманюк
Хмельницький національний університет
ПРО ЗАДАЧУ ВИВОЗУ І ДОСТАВКИ ВАНТАЖУ
З ЧАСОВИМИ ВІКНАМИ
Розглянуто узагальнення задачі маршрутизації з часовими
вікнами – задачу вивозу і доставки вантажу з часовими вікна-
ми. Проводиться порівняльний аналіз таких методів розв’язан-
ня поставленої задачі як груповий генетичний алгоритм та ев-
ристика адаптивного пошуку відкритої області.
Ключові слова: задача вивозу і доставки вантажу з часо-
вими вікнами, груповий генетичний алгоритм, евристика ада-
птивного пошуку відкритої області.
Вступ. Задача вивозу і доставки вантажу з часовими вікнами є
узагальненням задачі маршрутизації з часовими вікнами і тому є NP –
складною задачею [1], яка розв’язується за допомогою евристичних
алгоритмів.
Постановка проблеми. В даній роботі проводиться порівняль-
ний аналіз методів, які можуть бути застосовані для розв’язання за-
дачі вивозу та доставки вантажу з часовими вікнами.
Виклад основного матеріалу. Математична модель, приведена
у джерелі [2], має наступний вигляд.
Випадок задачі вивозу і доставки вантажу містить n вимог та m
транспортних засобів. Задача визначена на графі, P = {1, …, n} –
множина вузлів вивозу, D = {n + 1, …, 2n} – множина вузлів достав-
ки. Вимога i зображається коло вузлів i та i + n. K – множина всіх
транспортних засобів, mK = . Один транспортний засіб не міг би
обслуговувати всі вимоги; оскільки наприклад може бути заявка, щоб
транспортний засіб мав морозильне відділення. Ki – множина транс-
портних засобів, що можуть обслуговувати вимогу i, та PPk ⊆ і
DDk ⊆ – підмножини вивозів і доставок відповідно, що можуть
обслуговуватися за допомогою транспортного засобу k, так для всіх i
та k: k ∈ Ki ⇔ i ∈ Pk ∧ i ∈ Dk. Вимоги називаються особливими
(спеціальними), якщо Ki ≠ K. Визначено, що DPN ∪= та
kkk DPN ∪= . Нехай knk += 2τ , Kk ∈ і kmnk ++=′ 2τ , Kk ∈ –
вузли, які представляють початковий і кінцевий пункт призначення
транспортного засобу k, відповідно. Граф G = (V, A) містить вузли
∪NV = },...,{},...,{ 11 mm ττττ ′′∪∪ і дуги VVA ×= . Для кожного
© А. В. Атаманюк, 2008
Серія: Фізико-математичні науки. Випуск 1
5
},...,{},...,{ 11 mm ττττ ′′∪∪ і дуги VVA ×= . Для кожного транспортного
засобу ми маємо підграф ),( kkk AVG = , де }{}{ kkkk NV ττ ′= ∪∪ і
kkk VVA ×= . Для кожного ребра (i, j) ∈ A ми призначаємо відстань
dij ≥ 0 і час подорожі tij ≥ 0. Припускається, що відстані та час невід’є-
мні; dij ≥ 0, tij ≥ 0 і час задовольняє нерівність трикутника; tij ≤ til + tlj
для всіх i, j, l ∈ V. Припускаємо, що 0, >++ iini st (це припущення
створює видалення підшляхів).
Кожен вузол i ∈ V має час обслуговування si та часове вікно
[ai, bi]. Час обслуговування представляє необхідний час для заванта-
ження та розвантаження і часове вікно визначає, коли повинно роз-
початися відвідування окремого місця; відвідування вузла i може від-
буватися тільки між часом ai та bi. Транспортному засобу дозволяєть-
ся прибуття до місця призначення до початку часового вікна, але він
повинен очікувати доки почнеться часове вікно перед здійсненням
відвідування. Для кожного вузла i ∈ N, li – це кількість товарів, що
повинні бути навантаженні на транспортний засіб у особливому вуз-
лі, li ≥ 0 для i ∈ P і li = – li – n для i ∈ D. Об’єм завантаженості транспо-
ртного засобу k ∈ K позначається Ck.
В математичній моделі використовуються чотири типи змінних
рішення:
– xijk, i, j ∈ V, k ∈ K – бінарна змінна, рівна одиниці, якщо ребро
між вузлом i та вузлом j використовується за допомогою транспорт-
ного засобу k, та нулю у іншому випадку;
– Sik, i ∈ V, k ∈ K – невід’ємне ціле число, що визначає коли
транспортний засіб k починає обслуговування у положенні i;
– Lik, i ∈ V, k ∈ K – невід’ємне ціле число, тобто верхня границя
відносно кількості товарів у транспортному засобі k після обслугову-
вання вузла i;
– Sik та Lik добре визначені тільки тоді, коли транспортний засіб k
дійсно відвідав вузол i;
– zi, i ∈ P – бінарна змінна, що визначає коли вимога i розміщу-
ється в місці збереження вимог; zi приймає значення одиниці, якщо
вимога розміщується в місці збереження вимог, та нуля у протилеж-
ному випадку.
Математична модель має вигляд (1):
( )
( ) ∑∑∑ ∑
∈∈
′
∈ ∈
+−+
Pi
i
Kk
,k
Kk Ai,j
ijkij zSxd
kk
γαβα ττmin , (1)
і для неї виконуються наступні умови:
1=+∑ ∑
∈ ∈
i
Kk Nj
ijk zx
i k
, Pi ∈∀ (2)
Математичне та комп’ютерне моделювання
6
0,, =− ∑∑
∈
+
∈ kk Vj
kinj
Vj
ijk xx , Kk ∈∀ , kPi ∈∀ (3)
{ }
1,, =∑
′∈ kk
k
Vj
kjx
τ
τ
∪
, Kk ∈∀ (4)
{ }
1,, =∑
∈
′
kk
k
Di
kix
τ
τ
∪
, Kk ∈∀ (5)
0=−∑∑
∈∈ kk Vi
jik
Vi
ijk xx , Kk ∈∀ , kNj ∈∀ (6)
jkijiikijk StsSx ≤++⇒= 1 , Kk ∈∀ , kAji ∈∀ ),( (7)
iiki bSa ≤≤ , Kk ∈∀ , kVi ∈∀ (8)
kinik SS ,+≤ , Kk ∈∀ , kPi ∈∀ (9)
jkjikijk LlLx ≤+⇒= 1 , Kk ∈∀ , kAji ∈∀ ),( (10)
kik CL ≤ , Kk ∈∀ , kVi ∈∀ (11)
0== ′ kk kk
LL ττ , Kk ∈∀ (12)
}1,0{∈ijkx , Kk ∈∀ , kAji ∈∀ ),( (13)
}1,0{∈iz , Pi ∈∀ (14)
0≥ikS , Kk ∈∀ , kVi ∈∀ (15)
0≥ikL , Kk ∈∀ , kVi ∈∀ . (16)
Цільова функція мінімізує зважену суму пройденої відстані, су-
му використаного часу при кожному транспортному засобі, і кіль-
кість незапланованих вимог.
З обмеження (2) випливає, що кожне місце вивозу відвідується
або, що відповідна вимога розміщується в місці збереження вимог. З
обмеження (3) випливає, що місце доставки відвідується, якщо відві-
дується місце вивозу, і що відвідування виконується тим же транспо-
ртним засобом. З обмежень (4) та (5) випливає, що транспортний за-
сіб залишає будь-який початковий пункт і транспортний засіб вхо-
дить у будь-який кінцевий пункт. З обмеження (6) випливає, що між
kτ та kτ ′ створюється впорядкований шлях для кожного k ∈ K.
З обмежень (7) та (8) випливає, що Sik – множина вірна вздовж
шляху, та що часові вікна задовольняються. Ці обмеження також ство-
рюють недопустимі підшляхи. З обмеження (9) випливає, що кожен
вивіз відбувається до попередньої доставки. З обмежень (10)-(12) ви-
пливає, що зважена змінна – це коректно множина вздовж шляху, та
що обмеження завантаженості транспортного засобу виконуються [2].
Задача вивозу і доставки вантажу з часовими вікнами може роз-
в’язуватись за допомогою евристики адаптивного пошуку відкритої
області та групового генетичного алгоритму.
Серія: Фізико-математичні науки. Випуск 1
7
Поняття генетичних алгоритмів вперше було введено Холлан-
дом у 1975 році [3].
Розглянемо загальну схему пошуку для групового генетичного
алгоритму [4]:
Ініціалізація популяція P;
Доки не (зустрінеться критерій завершення)
– Вибирається пара окремих представників x, y з P як батьків
відносно їхнього відповідної цінності (відповідного значення);
– Народжується дві дитини x′ , y′ , використовуючи оператор
розподілу до x та y з ймовірністю pcross;
– Народжується дві модифіковані дитини x ′′ , y ′′ , використовую-
чи оператор мутації (зміни) до x′ та y′ відповідно, з ймовірністю pmut;
– Вставка x ′′ та y ′′ у P, і по черзі переміщення двох гірших
окремих представників з P;
Повертає найкращого окремого представника з P як рішення.
Початкова популяція породжується вводячи евристики вставки [4].
Адаптація описаної схеми генетичного пошуку до задачі містить
наступні компоненти алгоритму [4]:
– генетичне кодування, тобто шлях рішень для задачі вивозу і
доставки вантажу з часовими вікнами зображається за допомогою
хромосомів (ланцюгів);
– генетичні оператори: відбору, розподілу та мутації;
– евристики вставки, тобто залежна евристична процедура, за
допомогою якої працює груповий генетичний алгоритм, щоб породи-
ти початкову популяцію та щоб виготовити реального нащадка.
У таблиці 1 [2, 4] наводяться результати для порівняння групо-
вого генетичного алгоритму та евристики адаптивного пошуку від-
критої області.
Таблиця 1
Порівняння групового генетичного алгоритму та алгоритму евристики ада-
птивного пошуку відкритої області для 100 споживачів
Груповий генетичний алгоритм Евристики адаптивного пошу-
ку відкритої області Прикла-
ди
К-сть
трансп.
засобів
Найкр.
заг. від-
стань
Сер. заг.
відстань
Сер.
час (с.)
Сер. рі-
шення
Найкраще
рішення
Сер.
час (с.)
1 2 3 4 5 6 7 8
LR101 19 1650.80 1650.80 67.00 1650.80 1650.80 40
LR102 17 1487.57 1488.74 89.53 1487.57 1487.57 47
LR103 13 1292.68 1292.67 82.87 1292.68 1292.68 45
LR104 9 1013.99 1037.16 136.83 1013.39 1013.39 26
LR105 14 1377.11 1377.11 70.97 1377.11 1377.11 40
LR106 12 1252.62 1252.63 81.33 1252.62 1252.62 41
LR107 10 1111.31 1112.26 95.67 1111.31 1111.31 44
LR108 9 968.97 969.02 102.50 968.97 968.97 25
Математичне та комп’ютерне моделювання
8
Продовження таблиці 1
1 2 3 4 5 6 7 8
LR109 11 1208.96 1233.99 103.80 1208.96 1208.96 41
LR110 10 1165.83 1176.20 142.13 1159.35 1159.35 35
LR111 10 1109.90 1113.60 105.53 1108.90 1108.90 44
LR112 9 1003.77 1040.34 168.70 1003.77 1003.77 27
LC101 10 828.94 828.94 55.03 828.94 828.94 43
LC102 10 828.94 828.94 68.67 828.94 828.94 44
LC103 9 827.86 827.86 85.33 1037.77 1035.35 49
LC104 9 818.60 818.67 139.90 860.15 860.01 63
LC105 10 828.94 828.94 58.33 828.94 828.94 41
LC106 10 828.94 828.94 63.60 828.94 828.94 42
LC107 10 828.94 828.94 65.97 828.94 828.94 43
LC108 10 826.44 826.44 81.00 826.44 826.44 46
LC109 9 827.82 827.82 118.10 1000.60 1000.60 35
LRC101 14 1703.21 1704.05 76.07 1708.80 1708.80 38
LRC102 12 1558.07 1559.65 95.53 1558.07 1558.07 41
LRC103 11 1258.74 1260.45 92.80 1258.74 1258.74 43
LRC104 10 1128.40 1129.32 108.23 1128.40 1128.40 52
LRC105 13 1637.62 1639.87 88.17 1637.62 1637.62 42
LRC106 11 1424.73 1441.82 95.63 1424.73 1424.73 42
LRC107 11 1230.14 1237.91 97.73 1230.14 1230.14 43
LRC108 10 1147.43 1159.82 111.67 1147.43 1147.43 25
LR201 4 1253.23 1260.41 103.43 1253.23 1253.23 69
LR202 3 1197.67 1255.78 234.50 1197.67 1197.67 60
LR203 3 952.29 962.82 381.50 949.40 949.40 98
LR204 2 849.05 879.01 486.50 849.05 849.05 181
LR205 3 1054.02 1078.84 166.37 1054.02 1054.02 58
LR206 3 931.63 941.67 259.03 931.63 931.63 86
LR207 2 903.60 927.58 418.77 903.06 903.06 187
LR208 2 736.00 760.95 531.07 734.85 734.85 285
LR209 3 932.43 955.96 236.90 930.59 930.59 73
LR210 3 964.22 972.34 268.13 964.22 964.22 77
LR211 2 888.15 897.03 478.53 911.52 911.52 126
LC201 3 591.56 591.56 59.27 591.56 591.56 36
LC202 3 591.56 591.56 115.50 591.56 591.56 59
LC203 3 591.17 519.17 191.67 591.17 591.17 81
LC204 3 590.60 620.38 346.13 590.60 590.60 141
LC205 3 588.88 588.88 94.07 588.88 588.88 48
LC206 3 588.49 588.49 124.20 588.49 588.49 60
LC207 3 588.29 588.35 137.03 588.29 588.29 62
LC208 3 588.32 588.75 141.93 588.32 588.32 69
LRC201 4 1407.21 1438.12 101.47 1406.94 1406.94 38
LRC202 3 1358.25 1400.11 161.70 1387.74 1374.79 82
LRC203 3 1093.89 114.40 268.17 1089.07 1089.07 69
LRC204 3 818.66 838.55 457.30 818.66 818.66 173
LRC205 4 1302.20 1305.37 147.20 1302.20 1302.20 75
LRC206 3 1159.03 1176.90 139.57 1337.75 1159.03 48
LRC207 3 1062.05 1070.56 218.97 1062.05 1062.05 66
LRC208 3 852.76 882.76 322.13 852.76 852.76 88
Висновок. Порівнюючи результати, можна прийти до висновку,
що алгоритм евристики адаптивного пошуку відкритої області дає
кращий результат за середній час виконання.
Серія: Фізико-математичні науки. Випуск 1
9
Список використаних джерел:
1. Гери М., Джонсон Д. Вычислительные машины и труднорешаемые зада-
чи. – М.: Мир, 1982. – 416 с.
2. Stefan Ropke, David Pisinger. An Adaptive Large Neighborhood Search Heuris-
tic for the Pickup and Delivery Problem with Time Windows, 2005. – P.1-30.
3. Holland JH. (1975) Adaptation in natural und artificial systems – An introduc-
tory analysis with applications to biology, control, und artificial intelligence //
The University of Michigan Press, Ann Arbor, MI.
4. Giselher Pankratz. A Grouping Genetic Algorithm for the Pickup and Delivery
Problem with Time Windows // OR Spectrum (2005) 27. – P.21-41.
The author examined a generalization of the Vehicle Routing Problem
with Time Windows – Pickup and Delivery Problem with Time Windows.
The comparative analysis of methods to solve the problem is fulfilled.
Key words: pickup and delivery problem with time windows, grouping
genetic algorithm, an adaptive large neighbourhood search heuristic.
Отримано: 05.06.2008
УДК 519.6
М. Я. Бартіш, О. В. Ковальчук, Л. В. Николайчук
Львівський національний університет імені Івана Франка
ТРИКРОКОВИЙ ІТЕРАЦІЙНИЙ МЕТОД РОЗВ’ЯЗУВАННЯ
СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ
Досліджується новий підхід до побудови методів розв’язу-
вання нелінійних систем. Даний метод базується на методі
спуску та деякій модифікації методу Ньютона. Досліджено
швидкість збіжності. Проведено чисельні експерименти на те-
стових задачах.
Ключові слова: задача про найменші квадрати, метод
Ньютона, градієнтний метод, система нелінійних рівнянь.
Вступ. Математичне моделювання складних фізичних процесів
дуже часто потребує розв’язування систем нелінійних рівнянь. Уні-
версальних методів для успішного розв’язування широкого класу по-
дібних задач нема, тому актуальною є проблема побудови нових ефе-
ктивних алгоритмів. Пропонується ітераційний метод для розв’язу-
вання систем нелінійних рівнянь, який не потребує аналітичного за-
дання матриці Якобі і більш повно на кожному кроці використову-
ється інформація про функцію. Проведено теоретичні та практичні
дослідження даного методу.
© М. Я. Бартіш, О. В. Ковальчук, Л. В. Николайчук, 2008
|