Доцент кафедры прикладной информатики
в экономике и управлении,
Оренбургский государственный университет
Моделирование многокритериальной оптимизации путей обслуживания платежных терминалов
Основным видом деятельности г. Оренбурга является предоставление услуг населению по мгновенной оплате. Абонент получает удобную возможность оплаты счетов от разных поставщиков услуг в одном терминале в любой точке города в любое время суток с максимальной скоростью и гарантированным качеством. Владелец терминала получает доход в размере 3-5 % от суммы проведенных платежей и вознаграждение от операторов, в пользу которых принимает платежи.
Для нами была разработана информационная система учета платежных терминалов, основной целью проектирования которой явилось создание более эффективного процесса обработки информации по терминалам, выдачи отчетов по затребованным данным, а так же экономия времени, затрачиваемого специалистом технической поддержки на выполнение своих функций. Спроектированная информационная система обеспечивает ввод первичных документов, обработку и формирование выходных документов, определение оптимальных путей объезда платежных терминалов для устранения неполадок.
В практической деятельности отдела технической поддержки существует задача обслуживания неисправных платежных терминалов. Как только поступает информация о неисправности платежных терминалов, механик выезжает на точки установки терминалов с целью устранения неисправности, если это возможно на месте. Так как от простоя неисправного терминала фирма теряет долю прибыли, необходимо минимизировать эти потери, путем устранения неполадок в кратчайшие сроки. А так же, из-за неупорядоченного объезда неисправных терминалов затрачивается большое количество времени и увеличиваются затраты. Поэтому в информационной системе решается задача определения оптимального пути объезда неисправных терминалов на основании количества неисправных терминалов, расстояния между терминалами, расстояния между терминалами и перекрестками, информации о качестве дорог, пропускной способности дорог, других характеристиках.
Ежемесячно приходит большое количество информации о неисправных терминалах и в системе организован удобный доступ к информации о неисправных терминалах, формирование заявки на объезд терминалов на основе реализации алгоритма ветвей и границ решения задачи коммивояжера и алгоритма свертки множества критериев. Решение задачи оптимального обслуживания неисправных терминалов позволяет отслеживать информацию о неисправных терминалах, быстрее устранять поломки и существенно снижать издержки по обслуживанию.
Задача коммивояжера (ЗК) заключается в отыскании оптимального маршрута (тура), проходящего через указанные вершины графа по одному разу. В условиях задачи указываются критерий оптимальности маршрута (кратчайший, самый дешевый, совокупность критериев) и соответствующие матрицы расстояний. Чтобы формализовать решение задачи, вводятся следующие обозначения.
Пусть вершины графа перенумерованы числами jÎТ = {1,2,3..n}. Тур коммивояжера может быть описан циклической перестановкой t = (xj1,xj2,..,xjn,xj1), причем все j1..jn – разные номера; повторяющийся в начале и в конце j1, показывает, что перестановка зациклена. Расстояния между парами вершин сij , i,j=1,…,n, образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал:
| (1) |
,где i,j=1,…,n, n-число вершин графа.
Относительно математической формулировки ЗК можно сделать два замечания. Во-первых, в постановке сij, i, j=1,…,n, означали расстояния, поэтому они должны быть неотрицательными, т. е. для всех jÎТ:
сij³0; сjj=∞, i,j=1,…,n, | (2) |
где последнее равенство означает запрет на петли в туре), симметричными, т. е. для всех i, j:
сij= сji, i,j=1,…,n, | (3) |
и удовлетворять неравенству треугольника, т. е. для всех:
сij+ сjk³сik, i, j=1,…,n. | (4) |
Методы решения задачи коммивояжера: полный лексический перебор, «жадный» и «деревянный» алгоритмы, метод Робертса-Флореса, метод ветвей и границ, генетический алгоритм, другие методы и алгоритмы.
Для решения задачи коммивояжера при наличии многих критериев автором предложена интеграция методов: метода ветвей и границ и метода аддитивной свертки критериев. Метод ветвей и границ - общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации.
Граф имеет вершинами точки установки терминалов и перекрестки, а дуги графа – отрезки дорог между ними. Рассматривалась совокупность критериев: минимум расстояния, максимум качества и минимум загруженности дорог в час объезда. Матрица расстояний С=[сij] содержит обобщенные веса, полученные в результате аддитивной свертки оценок по заданным критериям. Аддитивная свертка оценок по критериям производится по формуле:
сij = 
λk*αijк, (5)
где λk – приоритет критерия k, k=1,…,m, m-число заданных локальных критериев;
αijк –нормализованная оценка ребра графа (xixj) по критерию k, k=1,…,m, i,j=1,…,n.
Для решения поставленной задачи строится граф, вершинами которого являются точки установки платежных терминалов и перекрестки улиц, а дугами – отрезки улиц между точками и перекрестками.
Рассмотрим работу системы на примере. Механику отдела технической поддержки дана заявка на объезд неработающих платежных терминалов. Точками нахождения этих терминалов являются: магазин «Формула» (х1), остановка «Музыкальная школа» (х5), остановка «МНТК» (х6), остановка «МЖК»(х7), расположенных в поселке «Степной» г. Оренбурга.
На рисунке 1 представлен граф дорог и установленных терминалов.
Рисунок 1 – Графовая модель. Веса ребер-нормализованные обобщенные оценки весов ребер графа
В рассмотренном примере получен оптимальный путь объезда неисправных терминалов x0-x1-x7-x5-x6-x0. При этом найден оптимальный путь по совокупности критериев: кратчайший по расстоянию, наилучший по качеству дорог и наименьший по загруженности в час объезда терминалов механиком. Учитывая цены на горюче-смазочные материалы и потери при простаивании механика в пробках, полученный оптимальный путь сокращает издержки на обслуживание терминалов для . А так как в заявке на объезд неисправных терминалов могут содержаться точки установки в разных частях города, то сокращение затрат будет еще более значительно для организации. На рисунке 2 представлен полученный оптимальный путь при заданных критериях.
Рисунок 2 – Оптимальный путь объезда платежных терминалов
Список литературы
1. Алексеев, В. Е. Графы и алгоритмы. Структуры данных. Модели вычислений : учебник / , . - М. : Интернет-Ун-т Информ. Технологий: Бином. Лаборатория знаний, 20с.
2. Бережная, Е. В. Математические методы моделирования экономических систем: Учебное пособие/ , . - М.: Финансы и статистика, 2001.-368 с.
3. Харари, Ф. Теория графов. Пер. с англ./ Ф. Харари - Едиториал УРСС, 200с.
АНКЕТА
участника международной научно-практической
интернет-конференции профессорско-преподавательского состава, аспирантов и студентов высших учебных заведений «Инновационные технологии: приоритетные направления развития» 12-14 апреля 2011 г.
Фамилия | Беляева |
Имя | Мария |
Отчество | Алексеевна |
Место работы (учебы) | Оренбургский государственный университет |
Должность | Доцент кафедры прикладной информатики в экономике и управлении |
Учебное звание, ученая степень | Доцент |
Название доклада | Моделирование многокритериальной оптимизации путей обслуживания платежных терминалов |
Номер секции | 3 |
Телефон | |
*****@***ru |
