[Из песочницы] Задача инкассатора
Перечислим задачи, составляющие «задачу инкассатора»:
- выбор формы сделки по приобретению УС.
- кластеризация Сети. Решение этой задачи даст заданное нами некоторое количество множеств УС для внутридневного (внутрисменного) обслуживания если существуют ограничения по количеству автомобилей и персоналу обслуживающих Сеть.
- размещение УС и центров обслуживания (далее — ЦО) Сети. Решение этой задачи даёт «дорожную карту» развития Сети во времени и пространстве.
- прогнозирование скорости расходования купюр (в разрезе номиналов) в УС кластера перед загрузкой кассет банкнотами в целях израсходования остатка денежных средств к дате и времени момента обслуживания (с учётом тенденций перехода населения на безналичную оплату покупок, сезонности, зарплатных проектов поблизости, прогноза погоды и тому подобных существенных факторов) с заданной вероятностью.
- вычисление кратчайшего пути (задача коммивояжёра).
Подготовка графа
Особенности городов с лабиринтной уличной застройкой в том, что между двумя точками подчас быстрее дойти пешком, чем доехать транспортом. Это характерно для исторических центров современных городов, которые ещё являются и центрами притяжения множества торговых предприятий и потоков людей, а значит и УС.
Таким образом, если два и более УС кластера находятся в непосредственной близости друг от друга, то вершины, в которых они находятся, на графе отождествляются.
Часть дуг де-факто имеет общие участки. Например, мосты, эстакады и тому подобное. При подготовке графа придётся «вводить» дополнительные «пустые» вершины (например вершины на концах моста к которым сходятся дуги от вершин этого берега). То есть провести операцию добавления вершин.
Добавляем вершины на концах этого ребра (моста, ж/д переезда, эстакады и т.п.) и все вершины графа по обе стороны соединяем с добавленными вершинами.
0-м шагом будет Матрица сильной связности орграфа получается логическим поэлементным умножением матрицы достижимости R (G) на транспонированную себя.
Эта операция позволяет нам получить подграфы равные сильно связанным компонентам на которых впоследствии будем выделять подграфы-кластеры.
И в довершении необходимо получить конденсат. Из вершин входящих в конденсат будет проведена операция слияния вершин.
Специализированные интернет-сервисы (например, Яндекс.Пробки) предоставляют один или несколько альтернативных путей между двумя точками-адресами.
При этом, часть дуг между вершинами фактически проходят по улицам через адреса других вершин кластера. При подготовке графа возможно следует исключать альтернативные пути между такими вершинами.
Орграф кластера не всегда, таким образом является транзитивным так как может не существовать замыкающей дуги между некоторыми вершинами.
Несмотря на то, что все вершины графа принадлежат плоскости, нагруженный орграф на основе городского трафика, как правило, не являться евклидовым.
С лёгкостью можно наблюдать как на примере организации дорожного движения, так и в отдельные периоды времени суток из-за существенных ассиметричных изменений трафика. В последнем случае существенно нарушается правило треугольника весов дуг, выраженных во времени достижения от одной вершины до другой.
Кластеризация узлов сети
Очевидно, что если множества УС расположены так, что мы можем выделить нужное нам количество кластеров исходя из физических ограничений обслуживания Сети, то мы могли бы минимизировать затраты на обслуживание.
Кроме того, кластеризация открывает возможности производить загрузку кассет каждого УС конкретного кластера с прогнозом израсходования денежного остатка в одну заданную дату, которая и будет датой обслуживания, или даже с точностью до временного промежутка в несколько часов внутри рабочей смены в течении которой происходит обслуживание.
При расчёте маршрута вес дуги должен учитывать вероятность израсходования купюр до момента обслуживания конкретного УС и время затрачиваемое на замену кассет.
При посменной организации процесса обслуживания Сети кластер должен обладать свойством в соответствии с которым сумма весов дуг гамильтонова цикла графа-кластера должна быть не более времени периода обслуживания (далее — Смена), то есть меньше либо равна рабочей Смене команды одного обслуживающего автомобиля.
Алгоритм включает предварительное определение количества кластеров исходя из возможностей обеспечения процесса обслуживания Сети спецтехникой и персоналом.
Кластеры будут обладать свойствами важными для будущего развития Сети, например такими, как «сжатие» и «растяжение».
Первое («сжатие») будет иметь место если изначально первичные кластеры были достаточно удалены друг от друга, но по мере роста Сети либо будут возникать новые кластеры между более «старыми», либо «старые» кластеры разрастутся, приближаясь своими границами друг к другу.
Свойство «растяжения» будет иметь место когда кластеры растут в направлениях противоположных и центроиды кластеров «уходят» друг от друга на более дальние расстояния.
Кластеры, образованные на основе подграфов взвешенного орграфа не будут иметь четких географических границ, поскольку из-за динамического трафика взвешенный орграф не является евклидовым при современной технологии обслуживания Сети.
Ситуация может измениться вместе с технологией доставки кассет до УС. Доставка кассет с помощью коптеров может «пересадить» обслуживающий персонал, например, на мотоциклы способные изменить веса орграфа, сделав орграф практически евклидовым.
Географически близкие между собой точки не обязательно принадлежат одному кластеру, поскольку между ними может не быть прямого пути с приемлемым трафиком. Однако, возможно при том, что возможно пешком пройти от одного УС до другого и это займет приемлемое время.
В этом случае, возможно следует при подготовке орграфа кластера к расчету на решение «задачи комивояжёра» не только «перенести» УС к соседнему кластеру, но и провести операцию «отождествления» этих вершин.
Если в банке вследствие каких-либо процессов (например маркетинговый план) существует список точек на карте населённого пункта, которые необходимо в перспективе обеспечить УС, то так же исходя из Стратегии и Финансового плана следует завести бизнес-процесс продуктом которого будет план-график развития Сети, особенно если нет возможности приобретать большие партии УС единовременно и приходится докупать поштучно или мелкооптовые партии.
Выбор алгоритма кластеризации определяется свойствами пространства и времени суток в котором разворачивается действие.
Населённые пункты исторически застраивались исходя из самых различных принципов, ландшафта, наличия природных и искусственных несносимых и непереносимых объектов, а потому имеют уникальную сеть автодорог и объектов-точек для наиболее экономически обоснованного размещения УС.
Как следствие, форма кластера на карте не будет иметь чётких границ. Напротив, кластеры будут «отращивать волосы» при дополнительном росте сети за счёт единичных дополнений УС. При этом эти «волосы» соседних кластеров могут «переплетаться».
В то же время взвешенный орграф такими визуальными свойствами уже обладать не будет в силу принципа назначать веса на основании трафика, а не физических расстояний дорог.
Веса орграфа могут настолько динамичными, что есть риск при одном и том же заданном количестве кластеров некоторые «пограничные» УС могут попадать, то в один, то в другой соседствующий кластер. Этого допускать нельзя, поскольку это создает проблемы при планировании загрузки УС, так как даты и Смены обслуживания соседних кластеров могут существенно не совпадать. Следовательно в ряде таких случаев придётся такие блуждающие точки назначать кластерам принудительно.
Сеть будет представлена в виде взвешенного орграфа на основе трафика полученного от интернет сервисов типа Яндекс.пробки, что избавит нас от географических проблем и мы можем подобрать алгоритм из семейства эвристических графовых алгоритмов.
Каждый кластер просто обязан быть связной компонентой, чтобы находить наиболее оптимальное решение задач коммивояжёра. Но если кластер как граф будет обладать свойством сильной связности, то такое решение будет заведомо более оптимальным.
Размещение УС и ЦО Сети
Решение задачи размещения должно достигать не только цели максимизации объёмов расчётно-кассового обслуживания клиентов банка и комиссионного дохода, но и задачу минимизации расходов на обслуживание сети в дальнейшем и, как следствие, задачу максимизации прибыли от использования Сети.
Отметим, что решаемых задач может быть на самом деле две. Так задача размещения новых УС по отношению к существующему ЦО является задачей обратной к задаче размещения ЦО относительно уже существующей Сети. Найденные координаты центроидов кластеров покажут нам и наиболее оптимальное гипотетическое расположение ЦО кластеров.
Как правило, у большинства банков в одном регионе только один ЦО Сети и, в какой-то момент, когда количество УС в Сети уже достаточно велико, что трафик становится существенным фактором роста затрат времени, возникает необходимость создания дополнительных ЦО для отдельных кластеров (или их групп), центроиды которых с ростом Сети неизбежно удаляются от единственного существующего ЦО.
Моментом, когда следует открывать дополнительный ЦО должно считать момент, когда сумма текущих расходов на достижение удаленных кластеров (Ртек), стоимость фондирования повышенных остатков денежных средств для более длительного периода между датами обслуживания (Рфонд) превысит сумму текущих затрат дополнительного ЦО с учётом амортизации основных средств и фонда оплаты труда и стоимости фондирования единовременного отвлечения ресурсов на приобретение этих основных средств.
С необходимостью организации дополнительного ЦО банк может столкнуться раньше, когда будет достигнут физический «потолок» дальнейшего масштабирования деятельности существующего ЦО на растущей Сети.
В банке с развивающейся Сетью должен существовать регламент по размещению УС, в котором зафиксирован элемент бизнес-процесса прохождения предварительной экспертизы при наличии одновременно альтернативных вариантов решений размещения. Если альтернатив нет и директивно даны точки для размещения УС, то экспертиза ничем не поможет и решение оптимизации расходов будет находиться далее уже в «задаче коммивояжёра».
Задача прогнозирования расхода купюр
Прогнозирование строится на следующих исходных данных:
- Оперативных данных из системы о текущей скорости расходования купюр.
- Исторических данных и вероятности реализации прогноза на очередной отрезок времени между датами обслуживания устройства самообслуживания.
В каждую кассету (настроенную на определенное достоинство купюры и при смене кассет в сейфовом отделении банкомата важно не перепутать гнезда кассет с различными купюрами) происходит закладка, чтобы в итоге дать сумму в размере не более застрахованной для конкретного банкомата. Технические возможности УСов предполагает загрузку 4-х кассет. Стандартная конфигурация купюрного состава (100, 1000, 5000) даёт максимальный объём порядка 4 млн рублей.
Предполагаем, что время между датами обслуживания УС кластера не может быть больше срока исчерпания остатка хотя бы в одном устройстве из данного кластера. Даже точнее, опустошение кассет УС заряженных наиболее «ходовыми» купюрами крупных номиналов (1000 и 5000).
Таким образом, полагаем, что загрузка отдельных УС с учётом графика обслуживания кластера, может не достигать максимально возможных размеров загрузки, что теоретически даёт дополнительную возможность снизить затраты ещё и на страхование денежных средств в конкретном банкомате. Однако это верно не для всех банкоматов, поскольку прогноз обязан учитывать наличие и особенности зарплатных проектов с корпоративными клиентами банка, а именно график выдачи авансов и расчётов по зарплате работникам клиентов. В такие даты, близлежащие к клиенту УС подвергаются ускоренному опустошению.
Следовательно, страховка (договор заключается на период) для таких банкоматов должна учитывать пиковые нагрузки расходования остатка. Поэтому, в таких случаях это будет максимально возможная загрузка и сэкономить на страховке получится не по всем УС.
Задача интерпретации данных о трафике для весов дуг и вершин графа. Подготовка графа для расчёта маршрута
Современный городской трафик характеризуется существенной для наших целей изменчивостью и трудной предсказуемостью из-за ДТП, дорожных работ, осадков и тому подобное.
Уже во время следования маршрута загрузка трафика может внезапно резко и неравномерно возрасти и, чтобы не ставить под угрозу работу сети, необходимо использовать оперативный инструмент для пересчета и получения самого «дешевого» маршрута для оставшегося количества пока ещё не обслуженных узлов кластера.
Чтобы улучшить вычислительные способности службы необходимо не только выделить кластеры УС («пограничные» УС могут менять «прописку»), но и локализовать их обслуживание по времени суток (периоды по 8 часов в 3 смены при круглосуточной организации работы автопарка и обслуживающего бизнес-процесс персонала).
Например, обслуживание кластера, расположенного в части города наиболее страдающей от «пробок», следует планировать на ночную смену. Кроме того, в этом случае скорее всего не придётся пересчитывать маршрут кратчайшего пути, так как веса графа не будут меняться во время всего следования маршрута. Однако, с другой стороны, резко увеличивается криминальный риск (риск нападения на инкассаторов), который потребует увеличения расходов на охрану экипажа.
Как говорилось выше возможно техническое решение доставки наличных до УС коптерами. Однако это не решает проблему если по-прежнему нужны люди для физической замены кассет. Это повлияет на затраты на автомобиль, поскольку кассир и охранник смогут пользоваться не специальным бронированным авто, а обычным, только для своей доставки до точки размещения УС.
Чтобы не решать задачу прогнозирования изменения весов во времени мы предлагаем алгоритм на основе подхода пересчета оставшегося маршрута из текущих данных о городском трафике, остатках в УС и, следовательно, изменённых весах дуг.
Наш подход предполагает пошаговый расчёт маршрута во время его следования службой диспетчирования. В этом случае инкассаторы не будут знать следующую точку в маршруте, пока она не объявлена диспетчером.
То есть к моменту окончания обслуживания очередной вершины должен быть рассчитан новый маршрут с учётом изменённых данных по весам дуг без включения в расчёт уже обслуженных вершин.
То есть на каждом шаге рассчитывается маршрут на (N — m) вершин. Для этого на каждом шаге производится операция ликвидации дуги по которой проходит инкассаторская машина на момент очередного расчёта (рис. 1 и 2).
Особенности решения «задачи коммивояжёра»
Эта задача находит себе применение во многих отраслях деятельности и финансовое посредничество не является исключением из этого правила. Не будем здесь повторять общеизвестные условия и ограничения этой задачи. Сосредоточимся на особенностях решения в рамках «задачи инкассатора.»
Очевидно, что должен быть реализован замкнутый вариант решения задачи коммивояжёра, поскольку после объезда всех запланированных в маршруте УС извлечённые кассеты должны быть завезены в ответственный обслуживающий центр.
Накладываемые ограничения на решение:
Требования службы физической безопасности по неповторяемости предыдущего маршрута. То есть, если во время расчёта маршрута получится решение аналогичное предыдущему, то оно отбрасывается и для реализации принимается другое, ближайшее к полученному результату.
Выбор решения определяется не столько точностью результата, сколько скоростью выполнения алгоритма в «полевых» условиях на аппаратных средствах, доступных банку по цене и качеству.
