Декомпозиция на задачата за маршрутизиране с времеви прозорци

Автор: Перцовски Александър Константинович Превод: Източник: Списание RSDN, www.rsdn.ru Материалът е предоставен от: Перцовски Александър Константинович

Математическа постановка на проблема

Проблем с групирането

След анализ на няколко бази от транспортни компании са формулирани следните критерии за оценка на географските райони на клъстера:

където ρ е линейното разстояние, а c е геометричният център на географската област на клъстера.

Този проблем за минимизиране се разглежда при ограниченията, формулирани въз основа на ограниченията на първоначалния проблем за маршрутизиране:

Също така, при изграждането на клъстер от географски области се спазва условието, че общото време на трансфери между точките, включени в GSR, по реда на добавянето им, не надвишава времето за работа на превозното средство.

Схема на метода на декомпозиция за набор от задачи за доставка на GSR

Метод на далечната точка

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

1. Определя се най-отдалечената от депото точкаp0,;
2. Създайте клъстерC0, добавете точкаp0към него;
3. Сред неразпределените точки изберетеpнай-близо до вече създадените клъстери;
4. Определяне на два клъстераC1, C2най-близо до точкатаp;
5. Проверете ограниченията за добавяне наpкъм клъстера последователно заC1,C2в реда на тяхната близост до точката и добавете точката към първия клъстер, за който ограниченията са изпълнени;
6. В случай, че ограниченията не са изпълнени за някой от клъстерите, създайте нов и добавете разглежданата точка към него;
7. Повторете стъпки 3-6, докато останат неразпределени точки.

Теорема 1.Методът на далечната точка има сложност O(n2), където n е броят на точките за доставка в разглеждания проблем.

Доказателството на теоремата е конструктивно и следва от оценките

Метод, базиран на алгоритъма на Свир

Този метод е много подобен на предишния. Разликата е в реда, в който се разглеждат точките. Ето неговата диаграма:

Подредете точките според полярния ъгъл, чийто връх съвпада с геометричния център на всички разглеждани географски точки, а страните са насочени към депото и разглежданата точка;

Като вземете предвид всички ограничения на теглото и размера и ограниченията на графика, започнете изграждането на готови полети във възходящ ред на полярния ъгъл;

В случай на неспазване на ограниченията, започнете изграждането на нов полет от посочената точка.

Теорема 2.Сложността на алгоритъма за конструиране на първоначалното разделение на географски области, базиран на алгоритъма Svir, е O(n*log(n)+n), където n е броят на точките за доставка в разглежданата постановка на проблема

Оценката също е конструирана по конструктивен начин, като се използва стъпка по стъпка оценка на всеки етап от алгоритъма.

Алгоритъм за подобряване на дяла на GSR

След получаване на първоначалната декомпозиция, с оглед на формулираната постановка на проблема, е необходимо да се извърши допълнителна обработка на полученото разделение за подобряване на стойността на целевия функционал. В същото време по време на анализа на потребителските данни беше направено заключението, че е необходимо да се разработи допълнителен алгоритъм за избор на точката, разглеждана в текущата стъпка. Това се дължи на борбата с така наречените "емисии", тоест GSR, съдържащ няколко точки. Появата им е възможнаналичието на ограничения за тегло и размер.

1. За всяка точка, която не е присвоена на съществуващ клъстер, определете разстоянията до конструираните клъстериd1,…, dm

2. Сортирайте получените разстояния във възходящ ред;

3. За всяка точка определете параметъра Δ =d2- d1,където параметритеdса подредени в параграф 2;

4. Разгледайте точката, за която Δ е максимално.

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

1. Вземете центровете на първоначалния дял;

2. Ако има неразпределени точки, изберете точка според описания по-горе алгоритъм;

3. Определяне на разстоянието от получената точка до GSR;

4. Проверете съответствието с ограниченията за тегло, обем и график за най-близката географска област на клъстера. Ако може да се добави точка, добавете я и отидете на стъпка 2;

5. Ако точката не може да бъде добавена към най-близкия GSR, опитайте по подобен начин да я добавите към втория най-далечен GSR. Ако е успешно, добавете и преминете към стъпка 2;

6. Ако точка 5 не е изпълнена, създайте нов GSR и добавете тази точка към него. Отидете на точка 2.

Апробация на алгоритъма за декомпозиция

Конструираният метод е тестван на няколко бази транспортни фирми. Таблицата по-долу показва резултатите от методите за конструиране на GSR, използвайки съответно метода, базиран на алгоритъма Swire и метода на далечната точка като алгоритъм за конструиране на първоначалното разлагане.

---