Автор: Пользователь скрыл имя, 23 Февраля 2013 в 16:00, курсовая работа
В даній курсовій роботі на прикладі розглянуто cинтез системи підтримки прийняття рішень (СППР) для оптимізації парку транспортних засобів та оптимізації маршрутів вантажних перевезень в умовах невизначеності. Для досліджень та аналізу в курсовій роботі було використано різні алгоритми формування маршрутів та різні критерії для прийняття рішень, для оптимізації парку транспортних засобів. Всі розрахунки проводились в декілька етапів :
Формування saving таблиці
Формування маршрутів на основі Saving алгоритму;
r = r + 1;
else
break
end
i = i + 1;
end
R(j, r) = 0;
l = l + L0(1, R(j, r - 1) - N0);
dr = Dmax - qr;
Data(j, 1) = l;
Data(j, 2) = qr;
Data(j, 3) = dr;
j = j + 1;
end
LTotal = sum(Data(:, 1));
E = GetE(R, Data(:, 3), Dmax);
end
function [ R, Data, LTotal, E ] = GetRouteModified( S, X, Y, X0, Y0, F, L, L0, Dmax, N0)
j = 1; % Индекс для R
SLeft = S;
[sRowsCount, nothing] = size(SLeft);
gCount = 0;
while sRowsCount > 0
l = 0; % Текущее пройденое растояние
qr = 0; % Текущее количество згруженого товара
dr = 0; % Текущая остача
R(j, 1) = 0;
[G, nothing, nothing] = GetGamiltonCicle( SLeft, X, Y, X0, Y0, N0 );
[nothing, gColsCount] = size(G);
gLeft = gColsCount;
r = 2; % Индекс для RI
for gi = 1:gColsCount
g = G(gi) - N0;
% Тут можно было бы вставить r = g + 1 и все бы работало, но r
% используется после цикла как кличество элементов R(j, :)
f = F(g);
if qr + f <= Dmax
R(j, r) = G(gi);
qr = qr + f;
if (r == 2)
l = l + L0(1, g);
else
l = l + L(R(j, r - 1) - N0, R(j, r) - N0);
end
r = r + 1;
gLeft = gLeft - 1;
else
break
end
end
R(j, r) = 0;
l = l + L0(1, R(j, r - 1) - N0);
dr = Dmax - qr;
Data(j, 1) = l;
Data(j, 2) = qr;
Data(j, 3) = dr;
% Нужно удалить из матрицы STemp все елементы, в которых первый или
% второй столбец равен какому-либо из елементов текущего пути
% R(j, :)
for si = sRowsCount:-1:1
for ri = 2:r
if SLeft(si, 1) == R(j, ri) || SLeft(si, 2) == R(j, ri)
SLeft(si, :) = [];
sRowsCount = sRowsCount - 1;
break
end
end
end
j = j + 1;
if sRowsCount == 0 && gLeft == 1
g = G(gColsCount) - N0;
f = F(g);
R(j, 1) = 0;
R(j, 2) = G(gi);
R(j, 3) = 0;
qr = f;
l = L0(1, R(j, 2) - N0) * 2;
dr = Dmax - qr;
Data(j, 1) = l;
Data(j, 2) = qr;
Data(j, 3) = dr;
end
end
LTotal = sum(Data(:, 1));
E = GetE(R, Data(:, 3), Dmax);
end
function [XR, YR] = PlotRoute( R, X, Y, X0, Y0, N0, NR )
[m, n] = size(R);
XR = zeros(m, n);
YR = zeros(m, n);
for i = 1:m
for j = 1:n
if R(i, j) == 0
XR(i, j) = X0;
YR(i, j) = Y0;
else
XR(i, j) = X(R(i, j) - N0);
YR(i, j) = Y(R(i, j) - N0);
end
end
end
%Xr = XR';
%Yr = YR';
% Делаем радугу!
%
http://www.mathworks.com/help/
%
http://www.mathworks.com/help/
for i = 1:m
H(i, :) = plot(XR(i, :), YR(i, :));
str = num2str(i);
M(i, :) = cellstr(strcat('Маршрут R', str));
hold all
end
plot(X, Y, 'Marker', 'Square', 'MarkerSize', 5, 'MarkerFaceColor', 'Cyan', 'MarkerEdgeColor', 'Blue', 'LineStyle', 'None');
hold all
plot(X0, Y0, 'Marker', 'Square', 'MarkerSize', 8, 'MarkerFaceColor', 'Red', 'MarkerEdgeColor', 'Black');
legend(H,
M, 'Location','NorthEastOutside')
text(X0, Y0, '-0', 'FontSize', 11, 'FontName', 'Consolas', 'Color', [1.0, 0.2, 0.2], 'FontWeight', 'Bold');
for i = 1:35
text(X(i), Y(i), strcat('-', num2str(i + N0)), 'FontSize', 9, 'FontName', 'Consolas', 'Color', [0.2, 0.2, 0.2], 'FontWeight', 'Bold');
end
for i = 1:m
text(XR(i, 2) - 0.7, YR(i, 2) + 1.7, strcat('R', num2str(i)), 'FontSize', 11, 'FontName', 'Consolas', 'Color', [0.5, 0.5, 0.5], 'FontWeight', 'Bold');
end
%grid on
axis([0, 80, 0, 80]);
xlabel('X');
ylabel('Y');
title(strcat('Програма замовлень №', num2str(NR)));
set(gca, 'FontSize', 10, 'FontName', 'Consolas');
end
function [ SW, SWX, SWY ] = GetSweepingMatrix( X, Y, X0, Y0, N0 )
[nothing, XCount] = size(X);
XTemp = X - X0;
YTemp = Y - Y0;
[SW(:, 2), nothing] = cart2pol(XTemp, YTemp);
for i = 1:XCount
SW(i, 1) = i + N0;
end
SW = sortrows(SW, -2);
SWX = zeros(1, XCount + 1);
SWY = zeros(1, XCount + 1);
for i = 1:XCount
j = SW(i, 1) - N0;
SWX(1, i) = X(1, j);
SWY(1, i) = Y(1, j);
end
SWX(1, XCount + 1) = SWX(1, 1);
SWY(1, XCount + 1) = SWY(1, 1);
end
function [ RSW, DataSW, LTotalSW, ESW, FirstNode ] = GetOptimalRoute( SW, F, L, L0, Dmax, N0 )
[ SWCount, nothing ] = size(SW);
SWNodes = SW(:, 1);
LMin = 0;
for i = 1:SWCount
[RSWTemp, DataSWTemp, LTotalSWTemp, ESWTemp] = GetRouteMatrix(SWNodes, F, L, L0, Dmax, N0);
if LTotalSWTemp < LMin || LMin == 0
LMin = LTotalSWTemp;
iMin = i;
end
SWFirst = SWNodes(1, :);
SWNodes(1, :) = [];
SWNodes(SWCount, :) = SWFirst;
end
low = SWCount - iMin + 1;
SWNodes = [];
SWNodes(1:low) = SW(iMin:SWCount, 1);
SWNodes(low + 1:SWCount) = SW(1:iMin - 1, 1);
FirstNode = SWNodes(1, 1);
[RSW, DataSW, LTotalSW, ESW] = GetRouteMatrix(SWNodes, F, L, L0, Dmax, N0);
end
function [ ROut, LengthROut, TotalLengthROut ] = OptimizeRoutes( RIn, L, L0, N0 )
[ rRowCount, rColumnCount ] = size(RIn);
LengthROut = zeros(rRowCount, 1);
TotalLengthROut = 0;
ROut = zeros(rRowCount, rColumnCount);
for i = 1:rRowCount
[ Ri, LengthRi ] = AveragedCoefMethod( RIn(i, :), L, L0, N0 );
ROut(i, :) = Ri(1, :);
LengthROut(i, 1) = LengthRi;
TotalLengthROut = TotalLengthROut + LengthRi;
end;
end
function [ EI, EIJ ] = GetEIJ( F, RC, LL, DMax, C )
nj = length(F);
e1 = floor(F(1, 1) / DMax);
eRMax = floor(F(1, nj) / DMax) + 2;
ni = eRMax - e1 + 1;
EI = zeros(1, ni);
EIJ = zeros(ni, nj);
% RsCount = zeros(1,nj);
% for j = 1:nj
% [RsCount(1, j), nothing]
% end;
ei = e1 - 1;
for i = 1:ni
ei = ei + 1;
EI(1, i) = ei;
for j = 1:nj
f = 0;
if ei < RC(1, j)
f = C(1, 4) * (RC(1, j) - ei);
elseif ei > RC(1, j)
f = C(1, 5) * (ei - RC(1, j));
end;
EIJ(i, j) = C(1, 1) * F(1, j) - C(1, 2) * LL(1, j) - C(1, 3) * RC(1, j) - f;
end;
end
end
В ході виконання даної роботи було розроблено власну СППР, яка дозволяє вирішувати задачу комівояжера.
Роботу даної СППР було продемонстровано на прикладі доставок цементу на склади. Тобто, в ролі комівояжера виступає водій, що розвозить замовлення, якому необхідно виїхати зі складу об’їхати 30 замовників, при цьому побувавши в кожного лише один раз і повернутися на склад.
Для цього дана система розраховує відстані між вузлами та відстані від базового вузла (складу) до кожного з вузла, який виступає в ролі замовника. А лише потім приступає до прокладання маршрутів між вузлами, застосовуючи при цьому такі алгоритми: saving-алгоритм, модифікований saving-алгоритм, sweeping та модифікований- sweeping з різними початковими точками.
Кожний алгоритм застосовується до кожної із 3-х можливих програм загальних вантажних перевезень (F1 – F3). Після чого, порівнявши довжини маршрутів, для кожної програми обираються оптимальні маршрути, які б дали найкоротшу загальну довжину, які потім ще й оптимізовуються за допомогою генетичного алгоритму.
І на фінішному етапі, за допомогою критерії прийняття рішень, визначили оптимальну кількість транспортних одиниць транспортного парку.
Усі розрахунки були виконані у програмному середовищі MatLab 7.10. Програмний код наведений у додатку А.
Дана СППР дає можливість значно збільшувати доходи компанії, за рахунок зменшення витрат палива та часу на доставку товару та за рахунок простою транспорту без дії.
Результатом виконання даної роботи є автоматизована СППР, яка вирішує проблему оптимізації транспортних маршрутів та визначення оптимальної чисельності транспортного парку.
Дана СППР можна застосовувати до інших задач, які можна звести до задачі комівояжера.
МДГУ ім. Петра Могили, 2003.
МДГУ ім. Петра Могили, 2006.
12. Лазарев Ю. Начала
13. Хант Б., и др. (B. Hunt et al.) MATLAB Р2007 с нуля [Лучшие книги, 2008] (djvu,352 p.,4198K,300dpi,ru).
14. Трунов О.М., Волокова С.О Приклади розв’язку практичних задач зкурсу "Дослідження операцій". – Миколаїв: МДГУ, 2008. – 116 с.