Разработка программного обеспечения для решения задачи маршрутизации транспорта, возникающей в реальной жизни
Решение задачи маршрутизации транспорта с ограничениями, возникающими в реальной жизни. Разработка математической модели задачи комбинаторной оптимизации и целочисленного программирования. Построение оптимальных маршрутов доставки товаров до потребителей.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 28.11.2019 |
| Размер файла | 2,7 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
· Ключевая библиотека, содержащая реализацию самого алгоритма и вспомогательный инструментарий. Сама библиотека использует библиотеки программного продукта IBM CPLEX V12.7.1 [17].
· Вспомогательные инструменты для автоматизированного сбора результатов, конвертации тестовых примеров во входной формат приложения и т.д.
Приложение для запуска и библиотека написаны на языке программирования C++ (стандарт языка C++14). Утилиты и вспомогательные скрипты написаны на языке Python (версии 3). Для того чтобы собрать и запустить программное обеспечение, необходимо удовлетворить минимальные требования, имея следующие компоненты:
· Операционная система на базе ядра Linux (например, Ubuntu). В случае ОС Windows, поддержка IBM CPLEX [17] не реализована, однако, имеется возможность использовать альтернативную эвристику для построения начального решения, которая не имеет внешних зависимостей
· Компилятор языка C++, поддерживающий стандарт языка C++14
· Система сборки программного обеспечения CMake [38] (минимальной версии 2.8)
· Для использования утилит и скриптов необходим интерпретатор языка Python 3
Дополнительно, существует возможность оптимизировать работу программного обеспечения с помощью библиотеки Intel TBB [39] на операционных системах с ядром Linux.
Исходный код программного обеспечения [42] является открытым, находится в публичном доступе и размещен на веб-сервисе GitHub [41], где в настоящее время размещаются наиболее крупные IT проекты с открытым исходным кодом.
Пример входных данных
Входные данные для приложения, которое запускает алгоритм решения задачи, имеют унифицированный вид в табличном стиле для удобного редактирования в инструментах типа Microsoft Excel [40].
Так как используется уникальный стиль, для конвертации данных из других форматов используются специальные вспомогательные скрипты. В частности, такой скрипт существует для конвертации тестовых примеров [18], результаты, решения которых представлены в соответствующем разделе.
Входные данные имеют следующий вид:
· Таблица потребителей описывает атрибуты каждого потребителя
o Id - идентификационный номер. 0 считается номером депо
o Volume - объем заказа
o Weight - вес заказа
o Hard TW begin - начало временного окна
o Hard TW end - конец временного окна
o Service time - время обслуживания
o Suitable vehicles - транспортные средства, которые могут обслуживать потребителя
· Таблица транспортных средств описывает парк доступных транспортных средств
o Id - идентификационный номер транспортного средства
o Volume - максимальный допустимый объем перевозимого груза
o Weight - максимальный допустимый вес перевозимого груза
o Fixed cost - цена использования
o Variable cost - затраты на единицу маршрута
· Таблица транспортных затрат на перемещение между потребителями описывает стоимость проезда от одного потребителя к другому
· Таблица временных затрат на перемещение между потребителями описывает время, затрачиваемое на перемещение от одного потребителя к другому
· Значение максимального числа разбиений заказа показывает, на сколько частей можно максимально делить заказ потребителя
Рис. 13. Пример входных данных для приложения
Размещено на allbest.ru
Подобные документы
Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [607,2 K], добавлен 13.03.2015Краткий обзор решения транспортных задач. Экономическая интерпретация поставленной задачи. Разработка и описание алгоритма решения задачи. Построение математической модели. Решение задачи вручную и с помощью ЭВМ. Анализ модели на чувствительность.
курсовая работа [844,3 K], добавлен 16.06.2011Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Функционирование систем массового обслуживания с разными типами заявок. Построение математической модели. Постановка задачи оптимизации среднего времени ожидания. Решение задачи оптимизации и разработка программного кода для оптимизации системы.
курсовая работа [538,5 K], добавлен 11.08.2017Функционирование систем массового обслуживания с разными типами заявок. Построение математической модели, постановка задачи оптимизации среднего времени ожидания. Решение задачи оптимизации системы. Разработка программного кода для оптимизации системы.
дипломная работа [581,7 K], добавлен 27.10.2017Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Решение задачи на составление компромиссного списка. Построение математической модели. Цена перемещения элементов. Вывод программы. Закреплении элемента а1 на первом месте, а а4 на пятом. Матрица оценок для задачи. Оптимальное решение в виде списка.
курсовая работа [37,5 K], добавлен 30.01.2016Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.
курсовая работа [100,0 K], добавлен 31.10.2014