цель:
разработать автоматизированный поиск оптимального (минимального по времени) маршрута груза
от места нахождения до места назначения
дано:
сеть отделений, для каждого отделения определен режим работы (график)
задано время на обработку груза (оформление, возможно распаковка/упаковка контейнера
или просто сортировка/накопление на следующий маршрут)
маршруты между отделениями, транспорт ходит по графику, задано время в пути
маршруты есть не между всеми отделениями
маршрут А-Б отличается от Б-А по графику
могут быть вовсе односторонние
груз - некая коробка
задача:
найти оптимальный маршрут для груза с учетом заданных ограничений - режим работы пункта,
время на обработку и параметры маршрута: время в пути, время прибыти/отправления
грузы не нужно группировать на маршруты и учитывать их "взаимное" влияние - вместимость автомобиля,
вместимость отделения
мат.модель:
отделение/пункт - вершина графа
маршрут - ребро графа
у вершин и ребер есть доп.атрибуты
работу со временем упростим след.образом: введем структуру {день.час}: где день и час просто числа, день -
номер по порядку с какой-то, взятой за начальную, даты, час - [0-23]
##сущности:
груз
пункт назначения
элемент графика/расписания
день.час
числовое значение
маршрут
пункт откуда
пункт куда
список элементов графика (день.час - время отправления, числовое значение = кол-во часов в пути)
поездка
пункт откуда
пункт куда
элемент графика (день.час - время отправления, числовое значение = кол-во часов в пути)
пункт
идентификатор (строка)
кол-во часов на обработку
список элементов графика (день.час - время октрытия, числовое значение = кол-во рабочих часов)
обработка в пункте
пункт
время прибытия
время готовности
время отправки
путь
список этапов - поездка/обработка
некоторые ограничения модели
создаем граф, описывающий отделения и маршруты
груз в какой то момент находится в конкретной вершине, нужно найти оптимальный маршрут до другой вершины
для поиска оптимального маршрута нужно перебрать все возможные маршруты от вершины А до Б с учетом графиков
маршрутов, графиков работы отделений, времени в пути и времени на обработку и найти среди них минимальный
по времени
время обработки груза учитывается и в начальном и в конечном пункте
маршрут(транспорт) может "прибыть" в закрытое отделение, при этом транспорт ждет открытия отделения,
для этого задано допустимое время ожидания (12часов)
отправляться маршрут в не рабочее время отделения не может. если есть реальная ситуация, когда транспорт
загружается в рабочее время, а отправляется после - маршрут нужно сконфигурировать так, что отправление
происходит до закрытия отделения, увеличив время нахождения (езды) на маршруте на этот промежуток
общий алгоритм обхода графа - рекурсия
в каждой вершине среди исходящих маршрутов точно нужно не брать "обратный" маршрут - по которому пришли
и исключить "зацикливание" а-б-ц-а. логически так вроде может быть - например, а-б-ц-а-д-е, но в таком случае
"дешевле" было остаться в а и ждать маршрута на д. пока просто исключаем зацикливание, т.е. нужно запоминать
все посещенные вершины, и в них не ходить
для выхода из рекурсии нужно определить условие
вычисляем некоторый первый маршрут, используем его продолжительность как максимальную - т.е. если текущий
рассматриваемый маршрут имеет большую продолжительность - выход из метода без сохранения результата
либо будет найден маршрут быстрее, либо останется первый найденный
конфигурации задается в текстовом виде (json)
##дальнейшее развитие:
добавляем атрибуты
груз
объем
габариты
вес
приоритет
маршрут
макс объем груза
макс габариты
макс вес груза
длина пути (км)
расход топлива (л)
пункт
максимальная вместимость отделения (суммарный макс.объем грузов)
(?) Т открытия сортировки - недостаточно аналитики
(?) Т закрытия сортировки - недостаточно аналитики
(?) скорость сортировки кол-во/ед.времени - недостаточно аналитики
добавляем функционал
хранение в бд
конфигурации
найденного для груза пути
формирование списка грузов для транспорта с учетом возможного объема
суммарный объем всех грузов дб меньше объема транспорта (80-90%?)
то же с весом
габариты (в-ш-г) каждого груза дб меньше допустимых для конкретного транспорта
приоритет груза
может повлиять на пересчет существующих путей грузов
разные алгоритмы вычисления оптимального пути
по минимуму км
по минимуму руб/км
группировка грузов
(?) сборка в партии (контейнеры) - недостаточно аналитики
добавление рест-интерфейса
(?) на входе конфигурация и список грузов, на выходе - список оптимальных путей для каждого груза
достаточно простой функционал - не имеет смысла реализовывать отдельно от остального api
веб-морда
создание, редактирование, удаление конфигураций - с визуализацией
регистрация местонахождения груза - для отслеживания перемещения
жизненный цикл груза - оформлен/.../доставлен
oauth для аутентификации и разграничения доступа
по организациям-перевозчикам
по разрешенным операциям
интеграция с яндекс.картами для поиска маршрутов между отделениями (заданы координатами) и изменения их
параметров (километраж, время в пути)