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

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

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

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

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

2. 
   Поскольку действие задачи происходит в городе, то евклидово расстояние неприменимо. Рассматривается сетка дорог с большим количеством узлов – перекрестков, тупиков, через которые должны пройти маршруты движения спецтранспорта. Сетке дорог ставится в соответствие ориентированный граф, вершинами которого являются узлы дорожной сети, а ребрами – отрезки дорог между узлами. При этом стоит учитывать тот факт, что дороги могут быть односторонними либо двусторонними, либо вовсе временно закрытыми на ремонт. Поэтому отметим, что матрица расстояний будет в общем случае несимметрична. Также следует учитывать загруженность дорожной сети, связанную с временными затруднениями движения;
   
3. 
   В отличие от классической задачи коммивояжера мы имеем несколько субъектов обслуживания, несколько инкассаторских бригад. Потому решению задачи маршрутизации должен предшествовать этап кластеризации – разбиение исходного множества объектов на сектора обслуживания. При разбиении следует воспользоваться алгоритмами кластеризации, однако следует учитывать, что все маршруты должны начинаться в одной точке (база инкассаторов) и заканчиваться в ней же;
   
4. 
   Задача инкассатора решается для большого числа объектов обслуживания (несколько сотен), что накладывает жесткие требования на сложность применяемых алгоритмов (не сложнее O(n²)) и на мощность вычислительных средств;
   
5. 
   Отличия между задачами заключаются также и в формате выходных параметров – если в задаче коммивояжера требовалось просто определить порядок объезда объектов, то в задаче инкассатора требуется определить не только порядок, но и путь передвижения между двумя объектами, поскольку в условиях разветвленной дорожной сети способов добраться от одного объекта до другого можно найти достаточно много. При этом следует минимизировать число передвижений по одному и тому же участку дороги, т.е. избегать ситуаций, когда объект, находящийся на пути следования транспорта между двумя другими объектами, обслуживается в другое время, значит бригаде инкассаторов вновь придётся заезжать в этот объект по этому же участку, что нецелесообразно как с точки зрения здравого смысла, так и с точки зрения минимизации риска потери перевозимых денежных средств.