Математическая модель и алгоритм решения задачи маршрутизации транспортных средств с несколькими центрами с чередованием и единым местом сбора
DOI:
https://doi.org/10.17308/sait.2021.1/3368Ключевые слова:
задача маршрутизации, дискретная модель, метод ветвей и границ, оценка множестваАннотация
В статье рассматривается постановка задачи маршрутизации транспорта с несколькими центрами с чередованием и единым местом сбора. Для нее выделяются ключевые условия, которые отражают суть задачи и основные ограничения. С учетом этих условий представлена математическая модель задачи на основе специальным образом введенных булевых переменных, отвечающих за мини-маршрут. Также выделяются избыточные ограничения, которые могут следовать из постановки, но уже учтены в других ограничениях задачи. Для предложенной математической модели представлены теоремы об эквивалентных преобразованиях, которые необходимы для вычисления оценок множеств в ходе работы алгоритма. С использованием данных теорем строится точный алгоритм решения задачи на основе метода ветвей и границ. Представлено подробное описание шагов алгоритма. В завершении представлены результаты вычислительного эксперимента и их анализ. На основании полученных результатов можно сделать вывод об оптимальности найденных алгоритмом решений. Другой вывод заключается в необходимости доработки методики подсчета оценок множеств. Основными результатами исследования являются математическая модель и точный алгоритм решения задачи.
Библиографические ссылки
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
- Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
