Алгоритмы оптимальной логистики по доставке грузов со складов до оптовых потребителей
Аннотация
Классическая проблема кратчайшего пути, которая заключается в поиске пути минимальной стоимости между двумя узлами в графе, эффективно решается за полиномиальное время. Однако во многих приложениях также есть дополнительные ограничения на бюджет или ресурсы на пути. Эта проблема известна как проблема ограниченного
кратчайшего пути и, к сожалению, относится к классу «трудных» проблем[4], для которых неизвестен алгоритм полиномиального времени[5].
В данной работе рассматривается задача об оптимальном выборе перевозчиков, с учётом тарифа стоимости перевозки, при перевозке груза в сети складов между заданной парой складов и ограничении по времени на выполнение. Даны дополнительные требования к алгоритму решения, который должен стать частью крупной высоконагруженной логистической системы, такие, как требование о минимальности используемых данных и скорости выполнения.
Предлагается метод решения проблемы ограниченного кратчайшего пути, основанный на алгоритме кластеризации DBSCAN[3], известных графовых алгоритмах[1],[2] и улучшенной версии алгоритма kSP[6] решения задачи кратчайшего пути с ограничением. Предложенный метод удовлетворяет дополнительным требованиям и реализован в
виде компьютерной программы.
кратчайшего пути и, к сожалению, относится к классу «трудных» проблем[4], для которых неизвестен алгоритм полиномиального времени[5].
В данной работе рассматривается задача об оптимальном выборе перевозчиков, с учётом тарифа стоимости перевозки, при перевозке груза в сети складов между заданной парой складов и ограничении по времени на выполнение. Даны дополнительные требования к алгоритму решения, который должен стать частью крупной высоконагруженной логистической системы, такие, как требование о минимальности используемых данных и скорости выполнения.
Предлагается метод решения проблемы ограниченного кратчайшего пути, основанный на алгоритме кластеризации DBSCAN[3], известных графовых алгоритмах[1],[2] и улучшенной версии алгоритма kSP[6] решения задачи кратчайшего пути с ограничением. Предложенный метод удовлетворяет дополнительным требованиям и реализован в
виде компьютерной программы.