скачать Статья публикуется в рамках Международной заочной научно-практической конференции студентов, аспирантов и молодых ученых «Современные проблемы управления риском», 20 октября 2010 г., Пермь УДК 658.012.122 ЗАДАЧА ИНКАССАТОРА КАК МОДИФИКАЦИЯЗАДАЧИ КОММИВОЯЖЕРАСабиров Василий Константинович ЗАО “Прогноз”, 614068, г. Пермь, ул. С. Данщина, 5 sabirov@prognoz.ru В статье обосновывается актуальность решения задачи инкассатора как модификации задачи коммивояжёра. Предлагается постановка задачи, описываются основные отличия от задачи коммивояжера: учет риска перевозки денежных средств и ценностей, требование предварительной кластеризации, учет разветвленной дорожной сети. Предлагаются методы решения этапов задачи, выявляются оптимальные методы и преобразования. Формируется критерий оптимизации, учитывающий риск перевозки денежных средств. В связи с развитием сферы услуг сегодня значительно повышается интенсивность денежных потоков, увеличивается потребность в доставке и инкассации денежных средств и ценностей, в перевозке их из одной точки в другую. Для расширения сферы предоставляемых услуг ведущие банки развивают работу своих инкассаторских служб. Важной задачей для инкассаторской службы является не только оптимизация маршрута, но и минимизация риска утраты перевозимых денежных средств и ценностей. Поэтому актуальным сегодня видится решение задачи инкассатора, частного случая задачи коммивояжера, учитывающего как оптимизацию маршрутов, так и минимизацию риска. Постановка задачи инкассатора такова: имеется множество объектов, которые должны быть обслужены инкассатором (доставка либо инкассация денежных средств), имеется ограниченный набор инкассаторских бригад для обслуживания объектов. Требуется построить оптимальную маршрутную сеть для обслуживания всех объектов инкассации в срок при минимизации затрат на перевозки. При этом по отношению к задаче коммивояжера задача инкассатора обладает рядом важных условий:
Также можно выделить ряд критериев оптимизации для задачи инкассатора:
На выходе задача инкассатора должна обеспечивать составление оптимальных графиков использования имеющихся транспортных средств, построение оптимальных по транспортным расходам и времени доставки маршрутов и расписаний. Для решения задачи кластеризации используется метод «развала на кучи». Сначала в каждый кластер (по числу бригад) помещается по одному произвольному объекту инкассации (исходя из географического положения объектов), координаты которого принимаются за координаты центров кластеров. Затем для каждого нераспределенного пункта доставки определяется расстояние до центра каждого кластера. Пункт доставки помещается в тот кластер, расстояние до центра которого минимально. Далее корректируется центр кластера с учетом добавленного пункта. После определения центров кластеров, пункты перераспределяются между кластерами в зависимости от близости к центрам кластеров. К преимуществам данного метода относят высокую скорость кластеризации и простоту реализации алгоритма. В связи с указанными выше различиями основными методами решения задачи маршрутизации видятся метод имитации отжига, эвристика ближайшей точки, а также возможно применение генетических алгоритмов. Рассмотрим отдельно алгоритм 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. ^ 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 г.
|