Разработка программного обеспечения для решения задачи маршрутизации транспорта, возникающей в реальной жизни
Решение задачи маршрутизации транспорта с ограничениями, возникающими в реальной жизни. Разработка математической модели задачи комбинаторной оптимизации и целочисленного программирования. Построение оптимальных маршрутов доставки товаров до потребителей.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 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Обзор алгоритмов методов решения задач линейного программирования. Разработка алгоритма табличного симплекс-метода. Составление плана производства, при котором будет достигнута максимальная прибыль при продажах. Построение математической модели задачи.
курсовая работа [266,4 K], добавлен 21.11.2013Расписание автобусов по сменам. Построение математической модели задачи. Основные теоретические сведения о симплекс-методе. Приведение задачи к каноническому виду. Выражение базисных переменных. Проверка оптимальности начального опорного решения задачи.
курсовая работа [590,4 K], добавлен 19.09.2013Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.
курсовая работа [232,4 K], добавлен 01.06.2009Решение задачи расчета структуры и объема товарооборота методом линейного программирования. Формулы ограничений, транспортная задача оптимизации доставки товаров. Решение задачи о назначениях на основе матрицы стоимостей в электронной таблице Excel.
контрольная работа [1023,6 K], добавлен 27.05.2013Построения математической модели с целью получения максимальной прибыли предприятия, графическое решение задачи. Решение задачи с помощью надстройки SOLVER. Анализ изменений запасов ресурсов. Определение пределов изменения коэффициентов целевой функции.
курсовая работа [2,4 M], добавлен 17.12.2014Описание языков программирования высокого уровня. Стандартные структуры данных, обзор принципов структурного программирования. Построение математической модели и выбор структуры данных для решения задачи. Тестирование и отладка программного кода.
курсовая работа [1,3 M], добавлен 05.12.2020Разработка структурной диаграммы программного модуля для целочисленного решения задачи линейного программирования с использованием симплекс-метода. Краткое описание всех уровней диаграммы с назначением всех ее блоков. Язык программирования Visual C#.
курсовая работа [874,7 K], добавлен 27.02.2013Сущность симплекс-метода. Общая характеристика задачи о смесях. Разработка основных алгоритмов решения задачи. Решение задачи в среде визуального программирования Delphi. Проектирование интерфейса пользователя. Разработка форм ввода-вывода информации.
курсовая работа [476,6 K], добавлен 22.05.2012Восстановление математической модели задачи нелинейного программирования. Решение уравнений прямых. Метод линеаризации: понятие, особенности применения при решении задач. Нахождение точки максимума заданной функции. Решение задачи графическим методом.
задача [472,9 K], добавлен 01.06.2013Описание предметной области решаемой задачи. Входные документы, необходимые для решения задачи, ее функции. Разработка информационного обеспечения задачи и реквизиты входной информации. Технология и алгоритмов решения задачи и их машинная реализация.
контрольная работа [15,1 K], добавлен 21.10.2010
