Методът на Кларк и Wright

Въведение.

Описаният метод се използва в програмата "Прости маршрути за учредяване. Работа с карта. Изчисляването на оптимални варианти за доставка"

В статията "Оптимизация на планиране на доставката. Групиране алгоритъм к-средства (K-средства)" бе показано как да се получи оптималния маршрут за даден брой A / палети от определено място на изпращане, транспортния капацитет, не се взема под внимание.
В тази статия, ние показваме как да разберете броя на необходимата A / транспорт като се има предвид неговата товароносимост за генериране на оптималния маршрут.

Така че, задачата за намиране на най-печелившите трафик маршрут, който минава само веднъж през следващите параграфи, а след това се върнете към началната точка (основата). Оптималност критерий при формулирането на проблема са: минималният диапазон на превозното средство с максимално натоварване на тялото.

Формулираната проблем е известен като "търговски пътник проблем". Има много математически методи, за да се ориентират къде точно и приблизителното решение на проблема. Сред методите, които осигуряват точното решение, най-известните са:

Основният недостатък на тези методи е крайно време и сложността пространство, е важно да се вземат предвид за голям брой точки. Всички ефективен (намаляване на изчерпателни търсене) методите за решаване на "търговски пътник проблем" - евристични методи. От тях най-голямо използване намерено:

"Метод на генетични алгоритми"
"Метод Clarke-Райт"
"Ant алгоритъм колония"
"Най-близкият съсед"
"Метод за включване на най-близкия град"
"Евтините метод, включващи"

За решаването на проблема ни, най-подходящият метод е методът на Кларк и Райт. Той е един от най-приблизителни, итеративни методи и може да се използва за компютърни решения, предаващи задачи. грешка решение не надхвърля средно 5-10%. Предимствата на този метод са неговата простота, надеждност, гъвкавост и, който ви позволява да се разгледа редица допълнителни фактори, които влияят на крайния разтвор на проблема.

Вземем примера за това как да прилагат метода на Кларк и Райт.

Условието на задачата.

От началната точка, която се намира в карго терминал (съхранение), е необходимо да се доставят товари 12 получатели.

Таблица 1. Координати на търсенето и обема на получателя

Координати товари терминал (склад): x0 = 10, Y0 = 15. За камиони за доставка на максимална г ruzovmestimostyu се използва = 1500 бр.

Въпрос: Какъв е броят на превозните средства, необходими за дистрибуция на стоки. Какво транспортиране схема е оптимално?

Подготвителна работа.

Имайте предвид, тези точки в декартова координатна система. Местоположение разпределение център и 12 получатели, както и обемът на доставки за всеки реципиент са показани на Фигура 1.

Фигура 1. Разположение на база и доставка точки

Първоначалната схема на пътища предполага, че един маршрут (вж. Фиг. 2), разположени за доставка на стоки за всеки отделен получател. Например, водачът зарежда партида от 450 броя в кутия. и носи до точката 1, там се разтоварва, а след това се връща да се основава, да вземе втората партида от 400 броя. и носи до точката, 2 и т.н. По този начин, на оригиналния транспортиране веригата включва маршрути само радиално движение на автомобила, броят на радиален маршрут съвпада с броя на получателите. В този случай, транспортиращата верига 12 се състои от радиални линии.

Фигура 2. Първоначалната схема на доставка на товари

Методът се състои в това, че, като се започне от първоначалната схема транспортно, стъпка по стъпка, за да се премести в оптималната схема на предаване на кръгов маршрут. За тази цел, концепция, се въвежда като един километър печалби.

Фигура 3. Показани две схеми за доставка. Доставка Схема А (вляво) осигурява доставката на стоките в точки 1 и 2, заедно радиални пътеки. В този случай, общият пробег на превозни средства е равно на:

La = d01 + d10 + D02 + d20 = 2d01 + 2d02

Доставка Схема В включва доставка на стоките в точки 1 и 2 по маршрута пръстен. Тогава пробег на превозни средства, както следва:

Схема В по отношение на транспортния път дава обикновено по-добри резултати от схема А. Следователно в прехода от схема А за да се получи съгласно Схема Б километър спечелване:

S12 = La - Lv = d01 + D02 - D12

Като цяло, ние имаме км печеливша:

където Сий - км печалба, получена чрез комбиниране на точки I и J, km; d0i, d0j - разстоянието между основата и точките на едро и Й съответно km; dij - разстояние между точките и Й, км.

Получените стойности се записват в таблица 2, която показва разстоянието между точките dij (горната дясна част на матрицата) и печалби км Сий (долната лява част на матрицата).

Таблица 2. Матрица километър разстояния и печалби

Сега нека се върнем към нашия пример. Таблица. 1 се вземат данните:

0 продукт (тази база): x0 = 10, Y0 = 15
Позиция 1: Х1 = 17, Y 1 = 15
Позиция 2: Х2 = 6 = 15, y2
Позиция 3: x3 = 13, Y3 = 3
и т.н.

Изчисляваме D01 разстояние между точките 0 и 1 на формулата:

По същия начин, ние получаваме от разстоянието:

за точки 0 и 2. D02 = 4
за точки 0 и 3. d03 = 12,37
параграфи 1 и 2. d12 = 11
претенции 1 и 3. D13 = 12.65
за позиции 2 и 3. D23 = 13.89
и т.н.

Тогава за точките I и J се получи км спечелване Сий = d0i + d0j - dij.

претенции 1 и 2. S12 = D01 + D02 - D12 = + 7 4-11 = 0
претенции 1 и 3. S13 = d01 + d03 - D13 = + 7 12.37 - 12.65 = 6.72
за позиции 2 и 3. S13 = D02 + d03 - D23 = + 4 12.37 - 13.89 = 2.48
и т.н.

Получената стойност се записва в таблица 3 .., където разстоянието между точките, представени с dij (горната дясна част на матрицата) и печалби км Сий (долната лява част на матрицата)

Таблица 3. Оценка разстояния m atritsa километър и печалби

Сега, когато се извършват всички необходими подготвителни работи, преминете направо към решаването на проблема.

Стъпка по стъпка описание BGV.

В матрица км печели намерите клетка (I *, к *), с максимална печалба км Smax:

В този случай, при спазване на следните три условия:

точки I * и к * не са част от един и същ маршрут;
точки I * и к * са началната и / или крайната цел на тези маршрути, в които те принадлежат;
Box (I *, к *) не е заключен (т.е. наблюдава при предишните стъпки на алгоритъма).

Ако не можете да намерите място, което отговаря на три условия, изброени, а след това преминете към стъпка 2. Ако не можете, след това преминете към стъпка 6.

Маршрутът, която включва точката I *, означен като Път 1. Съответно, по маршрута, която включва елемент й *, означен като Начин 2.

Представяме следната нотация:

N = - множество получатели;

- подгрупа от елементите, които изграждат Route 1;

- подмножество на точките, включени в маршрута 2.

Очевидно е, че (съгласно етап 1, условието 1).

Изчислете общия обем на пратки по маршрути 1 и 2:

където Qk - обем търсене на к точки, единици (виж Таблица 4).

Тествано на следните условия:

където в - товарни транспортни единици.

Ако състоянието е удовлетворена, а след това преминете към стъпка 4. Ако не - към стъпка 5.

Сливането на пътища 1 и 2 в един кръгов маршрут X. Предполагаме, че точката I * е крайната дестинация на маршрут 1 и ал к * на - отправната точка на маршрута 2. Когато верижното маршрути 1 и 2 отговарят на следните условия:

последователността на точките за местоположение по маршрут 1 от начало до точка I *, не се променя;
точка I * е свързан с т к *;
последователността на подреждане на точки по маршрут от точка 2 J * до края не се променя.

Повторете стъпки 1-4 до следващия път, повторението не е намерен Smax, който отговаря на три условия на етап 1.

Очакваме общият пробег на превозното средство.

ОПИСАНИЕ СЕРИЙНА НАЧИН РЕШЕНИЯ KLARKA_RAYTA.

Целият курс на решения на проблемите, представени в таблица 4.

Таблица 4. движи и междинни резултати на проблема

Колона 1 - брой на повторение.

Колона 4 - на стойност Smax км победа максимум.

Преброява 5, 6 и 7 - резултатите от проверката на условия 1, 2 и 3 в Етап 1. "+" - положителен, "-" - отрицателна.

Брои 8 и 9 - обем на трафика по маршрута 1, която включва точката I * (q1) и Начин 2, която включва елемент J * (Q2).

Граф 10 - провери състоянието, където в - товарен автомобил. "+" - положителни тестови условия, "-" - отрицателна.

Брой 11 - сериен номер на маршрута на пръстен (само по време на решението получи общо четири кръгов маршрут, виж фигура 4 ..).

Клетка 12 - пръстенна структура път формира в тази итерация.

Фигура 4. графично представяне на оптимални схеми за доставка

Помислете как нарастващата търсенето на оптималното решение. Нека започнем с факта, че първоначалният план транспортиране се състои от 12 радиални пътища, когато превозвайки товари във всяка от дестинациите, се извършва от отделен маршрут (виж. Фиг. 2). Общият пробег на превозни средства (виж триъгълна матрица на разстояния в таблица 3 ..):

L0 = 2 * D01 + 2 * D02 +. + 2 * D012 = 2 * 7,0 + 4,0 * 2 + 2 * 2 * 12,4 + 5,1 +. + 2 * 7,3 = 195 Км.

Сега започва стъпка по стъпка преход към новата оптимално решение, че чрез комбиниране на радиални линии в пръстен ще намали общия пробег на превозното средство (графично това ново решение е представено на фиг. 4).

Ние комбинират два радиални Начин 0-8-0 (обем доставка на 200 бр.) И 0-3-0 (обем доставка на 400 бр.) В общата кръгова маршрута (под № 1) 0-8-3-0 (обем доставка 600 бр.). В този случай, общият пробег на превозни средства е намалял с 23.0 км.

За периферен път № 1 - (. 600 броя) 0-8-3-0 граничат радиална траектория 0-5-0 (150 бр.). В този случай, параграф 5 прикрепите към стъпка 8. в резултат на нова структура на трасето на околовръстния 0-5-8 -3-0 (750 бр.). Общият пробег на превозни средства, е намалял с 21,4 км.
Обърнете внимание на важността на прилепнали точки последователност в кръгова маршрут, а именно 0-5-8 -3-0, не 0-5-3-8-0 или 0-8-3-5-0.
Ако аз * = 8 и к * = 5, а след това след сливането, те трябва да бъдат по маршрута една след друга.

Комбинации от параграфи 3 и 5 ще осигурят печалба от 17.2 км. Но тази асоциация не е възможно, тъй като и двете позиции вече са включени в кръгов маршрут №1 - 0-5-8-3-0, и можете да комбинирате елементи са от различни маршрути. По този начин, нарушение установи условия 1 и преминете към следващата итерация.

За периферен път № 1 - (. 750 броя) 0-5-8-3-0 граничат радиалните направления 0-12-0 (150 бр.). В този случай, параграф 12 се прикрепя към стъпка 3, за да се получи новата структура на трасето на околовръстния 0-5-8-3-12 -0 (1300 бр.). Общият пробег на превозни средства е намалял с 14.6 км.

Предмети 12 и 8 не се обединят, тъй като те вече са включени в маршрута на пръстен 1 (счупен условие 1).

Смесват две радиални посоки (. 450 броя) 0-1-0 и 0-11-0 (475 броя). В общата кръгова траектория (под № 2) 0-11-1-0 (925 бр.). В този случай, общият пробег на превозни средства е намалял с 13.4 км.

Артикули, 3 и 6 не могат да бъдат комбинирани поради нарушаване на условията 2. Параграф 3 е част от кръгов път 1 и маршрута е необходимо, "междинен" позиция, това означава, че се отнася до параграфи 8 и 12: 0-5-8-3- 12-0. Радиална маршрут 0-6-0 може да бъде прикрепен към пръстена, от едната страна на неговите "крайни" точки - 5 или 12, но с "междинен продукт", параграфи 3 и 8, не може да се свърже.

Повторете същата логиката на аргумента, както в предишните 7 повторения. Трябва да отбележим само, че в повторения на 9, 11, 12, 16 и 18 на сдружението е не само поради нарушаването на условията

Повторения на 21-60

Вече не правят смисъл, тъй като тяхното изпълнение не вече води до промяна в плана за транспортиране.

Общо км награда за 20 повторения на:

S = 23,0 + 21,4 + 14,6 + 13,4 + 8,8 + 8,3 + 7,9 + 7,8 = 105,3 км

и общият пробег на автомобилите, съответно:

L1 = L0 - S = 195 = -105.3 89.7 km

Графично оптимално пренасяне схема, показана на фиг. 4. Както може да се види, оптималната транспортиране верига включва четири кръгов маршрут (12 вместо оригиналните радиални пътища). Общият пробег на превозни средства може да се определя със следната формула:

, където Li - дължината на аз-ти маршрута, km; R - броят на маршрути.

Да разгледаме например кръгов маршрут 0-5-8-3-12-0. Дължината на маршрут определя по формулата (виж Таблица 4 ..):

L1 = d0,12 + d12,3 + d3,8 + d8,5 + d5,0 = 7,3 + 5,1 + 4,1 + 5,4 + 12,0 = 33,9 km.

По подобен начин, останалите дължината на маршрута напред.

РЕЗУЛТАТИ решение.

Резултатите от решаването на проблема са обобщени в таблицата по-долу: