Задачи коммивояжера сабиров Василий Константинович зао “Прогноз”, 614068, г. Пермь, ул. С. Данщина, 5 sabirov@prognoz ru icon

Задачи коммивояжера сабиров Василий Константинович зао “Прогноз”, 614068, г. Пермь, ул. С. Данщина, 5 sabirov@prognoz ru


Смотрите также:
Задача коммивояжера...
Сравнение различных методов решения задачи коммивояжера на многопроцессорных системах...
Решение задачи коммивояжера методом...
1. 3 Постановка задачи коммивояжера как задачи на графе...
Книги о Перми в фондах цгб им. А. С. Пушкина...
Программа первого съезда терапевтов Приволжского федерального округа РФ «Современные проблемы...
«Докуметообеспечение на зао строительной Компании Дружба»...
Строительные нормы и правила...
С временными окнами и ее решение...
План Прогноз Прогноз Прогноз Таможенные платежи, перечисленные в федеральный бюджет, всего...
Список новых поступлений плоскопечатной литературы, поступившей в фонд крбс IV квартал 2008 г...
1. Постановка задачи коммивояжера...



Загрузка...
скачать

Статья публикуется в рамках Международной заочной научно-практической конференции студентов, аспирантов и молодых ученых «Современные проблемы управления риском», 20 октября 2010 г., Пермь


УДК 658.012.122

ЗАДАЧА ИНКАССАТОРА КАК МОДИФИКАЦИЯ

ЗАДАЧИ КОММИВОЯЖЕРА


Сабиров Василий Константинович

ЗАО “Прогноз”, 614068, г. Пермь, ул. С. Данщина, 5


sabirov@prognoz.ru


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

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


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

При этом по отношению к задаче коммивояжера задача инкассатора обладает рядом важных условий:

  1. Задача коммивояжера предполагает лишь учет расстояния, без рассмотрения перевозимого груза. Задача инкассатора должна учитывать объем перевозимых денежных средств, при этом следует различать операции доставки и инкассации (сбора) денежных средств в зависимости от требований объекта обслуживания. Таким образом, в задаче инкассатора веса приобретают не только ребра, но и вершины исходного графа. На основании этого можно сформулировать критерий минимизации риска перевозки денежных средств C = время * деньги. Решая задачу, требуется минимизировать величину C, т.е. как можно меньше возить по маршруту большие суммы денежных средств и ценностей.

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

  • минимум суммарных отклонений от установленных сроков доставки;

  • минимум межоперационных простоев спецтранспорта;

  • минимум времени нахождения на маршруте;

  • минимум пройденного спецтранспортом расстояния;

  • максимум вероятности успешной доставки наличности;

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

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

  3. Задача инкассатора решается для большого числа объектов обслуживания (несколько сотен), что накладывает жесткие требования на сложность применяемых алгоритмов (не сложнее O(n2)) и на мощность вычислительных средств;

  4. Отличия между задачами заключаются также и в формате выходных параметров – если в задаче коммивояжера требовалось просто определить порядок объезда объектов, то в задаче инкассатора требуется определить не только порядок, но и путь передвижения между двумя объектами, поскольку в условиях разветвленной дорожной сети способов добраться от одного объекта до другого можно найти достаточно много. При этом следует минимизировать число передвижений по одному и тому же участку дороги, т.е. избегать ситуаций, когда объект, находящийся на пути следования транспорта между двумя другими объектами, обслуживается в другое время, значит бригаде инкассаторов вновь придётся заезжать в этот объект по этому же участку, что нецелесообразно как с точки зрения здравого смысла, так и с точки зрения минимизации риска потери перевозимых денежных средств.

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

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

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

Рассмотрим отдельно алгоритм optimal bitonic tour (эвристика ближайшей точки).

Эвристический алгоритм поиска ближайшей точки ищет решения в полиномиальном классе, что минимизирует пересечения путей следования:



Рис. 1. Результат применения алгоритма optimal bitonic tour


Также при применении любого алгоритма можно воспользоваться корректирующим преобразованием двойного выбора, которое “пробегает” по получившейся траектории и корректирует её, если потребуется. Такое преобразование заметно увеличивает точность любого алгоритма. В частности, после преобразования двойного выбора, примененного к результату, полученному в результате выполнения алгоритма optimal bitonic tour, мы получаем точное решение задачи:



Рис. 2. Результат применения алгоритма optimal bitonic tour с преобразованием двойного выбора


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


^ Список литературы


1. Бабаев А.А. Формализация задачи инкассатора.

2. Болгова Е.В., Поляков В.Н. Реализация параллельного алгоритма для решения задачи о развозке грузов с применением кластеризации.

3. Смирнов М.И., Хайруллин М.З. Математические модели, используемые в системе оптимизации доставки товаров автотранспортом “Диспетчер”.

4. Суздальцев В.А., Турукина Е.А., Инновационные методы планирования экспресс-доставки грузов транспортной компанией.

5. Fozia Hanif Khan, Nasiruddin Khan, Syed Inayatullah, Shaikh Tajuddin Nizami, Solving TSP problem by using genetic algorithm.


^ Money collector problem as a TSP modification

Sabirov Vasily Konstantinovich

JSC “Prognoz”, 5, S. Danschina Street, Perm, 614068, Russia


In this article a currency of solving money collector problem as an alteration of TSP is based. A problem definition is requested for discussion and the key distinctions between the payment collection problem and TSP are described, such as preliminary clusterization, wide road network, risk of currency and wealth shipment. Methods of solving of both stages (clusterization and routing) are introduced, and optimal methods and transformations are exposed. Minimum-risk criterion which takes into account currency shipment is developed.


^ РЕКОМЕНДАЦИЯ СПЕЦИАЛИСТА

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

Рекомендую статью Сабирова В.К. “Задача инкассатора как модификация задачи коммивояжера” к участию в международной конференции “Современные проблемы управления риском” и к последующему опубликованию в журнале “Университетские исследования”.


Ивлиев Сергей Владимирович,

к.э.н.,

руководитель направления решений

для финансовых институтов

ЗАО “Прогноз”


28 сентября 2010 г.




оставить комментарий
Дата02.10.2011
Размер66,3 Kb.
ТипСтатья, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх