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

     ВВЕДЕНИЕ

     В настоящее время – время высоких  технологий – людям не обойтись без помощи мобильных телефонов, компьютеров и интернета, без  помощи техники, которая выполняет  за них тяжелую умственную работу. К такой технике принадлежат  кассовые аппараты, которые имеет в своем обиходе каждый магазин. Ростовская фирма «Формула торговли» занимается приобретением, производством, сбытом и сервисным обслуживанием кассовых аппаратов. Конечно, при приобретении кассового аппарата покупателю дается гарантия на ремонт (при поломке аппарата), но также покупатель обязан заключить договор на сервисное обслуживание раз в один, два или три месяца. Сервисным обслуживанием занимаются специальные инженеры по регламенту, которые проверяют работоспособность касс и устраняют возникшие неполадки. Получается, что всего несколько человек должны за один месяц проверить работоспособность более 1000 кассовых аппаратов по всему городу.

     Задачей данной курсовой работы является минимизация затрат времени и средств при работе инженера и повышение эффективности работы всей фирмы. Таким образом, оптимизация процесса сервисного обслуживания кассовых аппаратов фирмы «Формула торговли» – и есть цель работы. 
 
 
 
 
 
 
 
 
 
 

     1 АНАЛИЗ ДЕЯТЕЛЬНОСТИ  ООО «ФОРМУЛА ТОРГОВЛИ»

     1.1 Описание деятельности  ООО «Формула торговли»

     ООО «Формула торговли» была создана  на рубеже тысячелетий. Ее основал Коренский  Сергей Александрович, профессор высшей математики. «Формула торговли» имеет множество филиалов, магазинов в г.Ростове-на-Дону и области. Так как по законам РФ каждый предприниматель или организация, которая совершает какие-либо способы торговли, обязана иметь кассу, она обязана заключить договор с любой сервисной службой, которая ежемесячно или хотя бы раз в три месяца должна проверять работоспособность этой кассы и ставить соответствующие пометки. Коренский предоставил людям наиболее обширный выбор кассовой и другой вспомогательной техники (счетчики денег, денежные ящики, сканеры, пластиковые карты).

     Контрольно-кассовая машина ККМ – устройство, предназначенное  для пробития чеков, на которых излагается информация о предпринимателе(его ИИН, название его фирмы), серийный номер кассового аппарата, название и цена товара и прочее. ККМ оснащена индикатором, собственной клавиатурой, питается либо от батарейки, либо от напряжения сети.

     - ШТРИХ – МИНИ – К;

     - ЭЛВЕС – МИКРО – К;

     - МЕРКУРИЙ 115К, 130К…;

     - ОРИОН 100К, 101К, 110К…;

     - ОКА и другие.

     Фискальный  регистратор  ФР – новое поколение  «касс». Это устройство соединено с компьютером через COM-порт и все действия выполняет только с его помощью, т.е. полностью пользуется интерфейсом компьютера. Однако он питается от сети через специальный блок питания.

     - ШТРИХ – ФР – К;

     - ЭЛВЕС – ФР – К;

     - ФЕЛИКС – 02К;

     - ШТРИХ – МИНИ – ФР – К  и другие.

     POS-терминал – это устройство, которое объединяет компьютер и ФР в одно целое. Он обладает собственным процессором, монитором, клавиатурой и огромными возможностями.

     Главный офис фирмы находится по адресу:  улица Карпатская, 41«Б». А на улице Доватора, 144 расположен главный филиал фирмы.

     Сервисный центр включает в себя:

     - директора сервисного центра;

     - начальника сервисного центра;

     - главного инженера;

     - старшего инженера по ремонту;

     - инженера по ремонту;

     - регламентного инженера по ремонту;

     - 4-х инженеров по регламенту;

     - 2-х инженеров по ремонту весов;

     - 2-х сервис-менеджеров;

     - инженера по приему и ремонту. 

     Инженер по регламенту производит сервисное  обслуживание закрепленных за ним касс в заранее определенном районе города, производит частичный ремонт и настройку  касс, а также ставит пометки в «Журнале учета вызовов технического специалиста». Фактически задачей инженера по регламенту является контролирование исправности касс, наличия пломб и голограмм, то есть защита клиента от штрафов налоговой службы.

     Сервис  центр Формулы торговли обслуживает более 1000 касс по г.Ростову-на-Дону и области. Обслуживание производят инженеры по регламенту. Все кассы разделены между ними примерно поровну. Таким образом, на одного инженера по регламенту приходится около 250 касс, в каждом магазине может находиться одна, несколько и более касс. Существует несколько форм договоров, в соответствии с которыми кассы обслуживаются один раз в месяц (базовый), в два месяца (упрощенный), в три месяца (эконом-договор).

     Для упрощения работы инженера по регламенту можно разделить область обслуживания по районам города, что позволит сэкономить время и расходы на бензин. Некоторые улицы попадают на границы разделения районов, в таких случаях инженер обслуживает сторону улицы, прилегающую к его району, что решает проблемы, связанные с ПДД (так как часто, чтобы переехать на другую сторону дороги, необходимо делать большой круг на машине).

     1.2 Постановка задачи  коммивояжера для  ООО «Формула торговли»

     В 1859 г.  У.  Гамильтон  придумал  игру  «Кругосветное  путешествие», состоящую в отыскании такого пути, проходящего через  все  вершины  (города, пункты назначения) графа,  чтобы  посетить  каждую вершину  однократно  и  возвратиться  в  исходную.  Пути,  обладающие  таким свойством, называются гамильтоновыми циклами.

     Задача  о гамильтоновых циклах в графе  получила  различные  обобщения. Одно из этих обобщений –  задача  коммивояжера,  имеющая  ряд  применений  в исследовании  операций,  в  частности  при  решении  некоторых  транспортных проблем. Задача коммивояжера является  одной из знаменитых задач теории комбинаторики. Она была поставлена в  1934  году,  и об неё, как об Великую теорему Ферма обламывали зубы лучшие  математики.  В своей  области  (оптимизации  дискретных  задач)  задача коммивояжера  служит своеобразным полигоном, на котором испытываются всё новые методы. Сейчас решение данной задачи необходимо во многих областях, связанных с замкнутыми и при этом жестко связанными по времени системами, такими как: конвейерное производство, многооперационные обрабатывающие комплексы, судовые и железнодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет авиационных линий. Поэтому данная проблема на современном этапе развития общества имеет не самое последнее по значимости место[2.2].

     Постановка  задачи следующая.

     Коммивояжер (бродячий торговец) должен посетить один и только один раз каждый из N городов и вернуться обратно в тот город, из которого он начал движение. Необходимо так выбрать его маршрут, чтобы суммарная длина его общего пути оказалась минимальной. Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого (в матрице вычеркивается диагональ). Целью решения является нахождение маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат[2.1].

     В данной курсовой работе рассматривается  только один город, Ростов-на-Дону, который  разделен по улицам. Поэтому каждой улице города сопоставим вершину  графа, а каждому возможному маршруту переезда из i-й улицы на j-ю – ребро графа и обозначим их (i,j). Тогда требования нахождения минимального пути, проходящего один и только один раз через каждый адрес, сводится к нахождению на графе контура минимальной длины, проходящего один и только один раз через каждую вершину. 
 
 
 
 
 
 
 

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

     2.1 Обзор методов

     2.1.1 Жадный алгоритм

      Жадный  алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. “Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.

     Посмотрим, как поведет себя при решении  ЗК жадный алгоритм. Здесь он превратится в стратегию “иди в ближайший (в который еще не входил) город”. Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рисунке 1, представляющую узкий ромб.

     Рисунок 1 – Сеть для жадного алгоритма.

     Пусть коммивояжер стартует из города 1. Алгоритм “иди в ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

     В пользу процедуры “иди в ближайший” можно сказать лишь то, что при старте из одного города она не уступит стратегии “иди в дальнейший”. Как видим, жадный алгоритм ошибается.

     2.1.2 Деревянный алгоритм.

     Алгоритм решения ЗК через построение кратчайшего остовного дерева для краткости будем называть деревянным. Рассмотрим цепь на рисунке 2.

     Рисунок 2 – Цепь.

     Если  справедливо неравенство треугольника, то d[1,3]£d[1,2]+d[2,3] и d[3,5]£d[3,4]+d[4,5] Сложив эти два неравенства, получим d[1,3]+d[3,5]£d[1,2]+d[2,3]+d[3,4]+d[4,5]. По неравенству треугольника получим:  d[1,5]£d[1,3]+d[3,5].

     Окончательно: d[1,5]£ d[1,2]+d[2,3]+d[3,4]+d[4,5].

     Итак, если справедливо неравенство треугольника, то для каждой цепи верно, что расстояние от начала до конца цепи меньше (или  равно) суммарной длины всех ребер цепи. Это обобщение расхожего убеждения, что прямая короче кривой. В этом суть свойства спрямления.

     Вернемся  к ЗК и опишем решающий ее деревянный алгоритм.

1. Построим на входной сети ЗК кратчайшее остовное дерево и удвоим все его ребра. Получим граф G – связный и с вершинами, имеющими только четные степени.
2. Построим эйлеров цикл G, начиная с вершины 1, цикл задается перечнем вершин.
3. Просмотрим перечень вершин, начиная с 1, и будем зачеркивать каждую вершину, которая повторяет уже встреченную в последовательности. Останется тур, который и является результатом алгоритма.

     Пример 1. Дана полная сеть, показанная на рисунке 2. Найти тур жадным и деревянным алгоритмами.

     Решение. Жадный алгоритм (иди в ближайший город из города 1) дает тур 1–(4)–3–(3)–5–(5)–4–(11)–6–(10)–2–(6)–1, где без скобок показаны номера вершин, а в скобках – длины ребер. Длина тура равна 39, тур показан на рисунке 2.

     Деревянный  алгоритм вначале строит остовное дерево, показанное на рисунке 3 штриховой линией, затем эйлеров цикл 1-2-1-3-4-3-5-6-5-3-1, затем тур 1-2-3-4-5-6-1 длиной 43, который показан сплошной линией на рисунке 3.

     Рисунок 3 – Конечный тур.

          2.1.3. Алгоритм Дейкстры

      Одним из вариантов решения ЗК является вариант нахождения кратчайшей цепи, содержащей все города. Затем полученная цепь дополняется начальным городом – получается искомый тур.

      Можно предложить много процедур решения  этой задачи, например, физическое моделирование. На плоской доске рисуется карта  местности, в города, лежащие на развилке дорог, вбиваются гвозди, на каждый гвоздь надевается кольцо, дороги укладываются верёвками, которые привязываются к соответствующим кольцам. Чтобы найти кратчайшее расстояние между i и k, нужно взять I в одну руку и k в другую и растянуть. Те верёвки, которые натянутся и не дадут разводить руки шире и образуют кратчайший путь между i и k. Однако математическая процедура, которая промоделирует физическую, выглядит очень сложно. Известны алгоритмы проще. Один из них – алгоритм Дейкстры, предложенный Дейкстрой ещё в 1959г. Этот алгоритм решает общую задачу: в ориентированной, неориентированной или смешанной (то есть такой, где часть дорог имеет одностороннее движение) сети найти кратчайший путь между двумя заданными вершинами.

      Алгоритм  использует три массива из 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.