Оптимизация процесса сервисного обслуживания кассовых аппаратов

      Алгоритм  использует три массива из n (число вершин сети) чисел каждый. Первый массив a содержит метки с двумя значениями: 0 (вершина ещё не рассмотрена) и 1 (вершина уже рассмотрена); второй массив b содержит расстояния – текущие кратчайшие расстояния от v_i до соответствующей вершины; третий массив c содержит номера вершин – k-й элемент c_k есть номер предпоследней вершины на текущем кратчайшем пути из v_i в v_k. Матрица расстояний D_ik задаёт длины дуг d_ik; если такой дуги нет, то d_ik присваивается большое число Б, равное “машинной бесконечности”.

     Теперь  опишем сам алгоритм.

1. Инициализация. В цикле от одного до n заполнить нулями массив а; заполнить числом i массив с: перенести i-ю строку матрицы D в массив b; a[i]:=1; c[i]:=0; где i – номер стартовой вершины.
2. Общий шаг. Найти минимум среди неотмеченных (т. е. тех k, для которых a[k]=0); пусть минимум достигается на индексе j, т. е. b_j£b_k; a[j]:=1;

если  b_k>b_j+d_jk, то b_k:=b_j+d_jk; c_k:=j. Условие означает, что путь v_i..v_k длиннее, чем путь  v_i..v_j,v_k . Если все a[k] отмечены, то длина пути v_i..v_k равна b[k]. Теперь надо перечислить вершины, входящие в кратчайший путь.

3. Выдача ответа. Путь v_i..v_k выдаётся в обратном порядке следующей процедурой:

     3.1. z:=c[k];

     3.2. Выдать z;

     3.3. z:=c[z]; Если z = 0, то конец, иначе перейти к 3.2.

      Для выполнения алгоритма нужно n  раз просмотреть массив b из n элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность. Проиллюстрируем работу алгоритма Дейкстры численным примером (для большей сложности, считаем, что некоторые города (вершины) i, j не соединены между собой, то есть D[i,j]=∞). Пусть, например, i=3. Требуется найти кратчайшие пути из вершины 3. Содержимое массивов a,b,c после выполнения первого пункта показано в таблице 1: 
 
 
 
 

      Таблица 1 – Содержимое массива после выполнения первого пункта.

      

     Очевидно, содержимое таблицы меняется по мере выполнения общего шага. Это видно из таблицы 2:

     Таблица 2 – Содержимое массива после  выполнения второго пункта.

       
 

      Таким образом, для решения ЗК нужно  n раз применить алгоритм Дейкстры следующим образом. Возьмём произвольную пару вершин j,k. Исключим непосредственное ребро C[j,k]. С помощью алгоритма Дейкстры найдём кратчайшее расстояние между городами j..k. Пусть это расстояние включает некоторый город m. Имеем часть тура j,m,k. Теперь для каждой пары соседних городов (в данном примере – для j,m и m,k) удалим соответственное ребро и найдём кратчайшее расстояние. При этом в кратчайшее расстояние не должен входить уже использованный город. Далее аналогично находим кратчайшее расстояние между парами вершин алгоритмом Дейкстры, до тех пор, пока все вершины не будут задействованы. Соединим последнюю вершину с первой и получим тур. Чаще всего это последнее ребро оказывается очень большим, и тур получается с погрешностью (рисунок 3), однако алгоритм Дейкстры можно отнести к приближённым алгоритмам.

     

     Рисунок 3 – Конечный тур при решении  задачи алгоритмом Дейкстры.

          2.1.4. Метод ветвей и границ

      К идее метода ветвей и границ приходили  многие исследователи, но Литтл с  соавторами на основе указанного метода разработали удачный алгоритм решения ЗК и тем самым способствовали популяризации подхода. С тех пор метод ветвей и границ был успешно применен ко многим задачам, для решения ЗК было придумано несколько других модификаций метода, но в большинстве учебников излагается пионерская работа Литтла.

      Общая идея тривиальна: нужно разделить  огромное число перебираемых вариантов  на классы и получить оценки (снизу  – в задаче минимизации, сверху –  в задаче максимизации) для этих классов, чтобы иметь возможность  отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной[2.2].

      2.2 Алгоритм Литтла

     В курсовой работе для решения задачи о коммивояжере применяется метод ветвей и границ, или алгоритм Литтла, относящийся к методам дискретной оптимизации. В сущности, это полный перебор решений, который оптимизируется за счет того, что при переборе вариантов по определенным признакам отсекаются неоптимальные множества перебора. Так как количество вершин от уровня к уровню возрастает в факториальной прогрессии, то отсечение вершин верхних уровней значительно сокращает общее число перебираемых вариантов.

     Общая схема метода такова:

1. Определяется нижняя граница длин на множестве Х₀ всех гамильтоновых контуров m(X₀).
2. Выделяется какая-либо одна дуга (i, j) и множество Х разбивается на два непересекающихся подмножества и таким образом, что образовано всеми гамильтоновыми контурами, содержащими дугу (i, j). А множество – все гамильтоновые контуры, не включающие дугу (i, j). Для каждого из подмножеств определяются нижние границы длин входящих в них гамильтоновых контуров: m( ) и m( ). Причем m( ) ≤ m( ) и m( ) ≤ m( ), так как является подмножеством и также является подмножеством .
3. Нижние границы m( ) и m( ) сравниваются и то из множеств и , которое имеет меньшую нижнюю границу, снова разбивается на два подмножества: и . Для данных множеств находятся нижние границы и так далее.
4. Процесс ветвления продолжается до тех пор, пока на каком-то k-ом шаге множество не будет содержать единственного гамильтонового контура, который называется первым рекордом. Затем рассматриваются оборванные ветви и их нижние границы сравниваются с длиной первого рекорда. Если они больше первого рекорда, то задача решена. В противном случае выполняется ветвление подмножества с наименьшей нижней границей до тех пор, пока не возникнет одна из ситуаций:

     - получится гамильтонов контур, длина  которого меньше длины первого  рекорда, такой контур называется  вторым рекордом;

     - полученный контур имеет длину больше первого рекорда, тогда ветвь является тупиковой.

     Ветвление продолжается до тех пор, пока не будут  просмотрены все подмножества, имеющие  нижние границы меньшие, чем длина  лучшего рекорда[1]. 
 
 
 
 
 
 
 
 

     3 ОПТИМИЗАЦИЯ МАРШРУТА  СЕРВИСНОГО ОБСЛУЖИВАНИЯ

     3.1 Математическая постановка задачи оптимизации

     Пусть N - число городов.

          Cij, i, j=1..N - матрица затрат, где Cij - затраты на переход из i-го города в j-й.

     Xij - матрица переходов с компонентами:

     Xij = 1, если коммивояжер совершает переход из i-го города в j-й,

     Xij = 0, если не совершает перехода, где i, j = 1..N и i≠j.

     Целевая функция Z=∑∑Cij*Xij→min.

     ∑Xij=1 – только один въезд в каждый j-й город;

     ∑Xij=1 – только один выезд из каждого j-го города.

     Xij={0,1}.

     Введем  дополнительное ограничение для исключения возможности подциклов: дополнительные целочисленные переменные

Ui≥0, Ui-Uj+N*Xij ≤ N-1, i,j=2…N[1].

     3.2 Нахождение оптимального пути

     За  один месяц (22 рабочих дня) инженер по регламенту должен проверить работоспособность около 250 касс в разных районах города. Занесем данные о кассах, их количестве и месте нахождения в таблицу 4.

     Таблица 4 – Расположение касс.

 

Продолжение таблицы 4.

 

     Продолжение таблицы 4.