Разработка программного обеспечения для решения задачи маршрутизации транспорта, возникающей в реальной жизни
Решение задачи маршрутизации транспорта с ограничениями, возникающими в реальной жизни. Разработка математической модели задачи комбинаторной оптимизации и целочисленного программирования. Построение оптимальных маршрутов доставки товаров до потребителей.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 28.11.2019 |
| Размер файла | 2,7 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.Allbest.Ru/
Размещено на http://www.Allbest.Ru/
Размещено на http://www.Allbest.Ru/
Федеральное государственное автономное образовательное учреждение высшего образования
Национальный исследовательский университет
Высшая школа экономики
Факультет информатики, математики и компьютерных наук
Образовательная программа «Интеллектуальный анализ данных»
Выпускная квалификационная работа (магистерская диссертация)
по направлению подготовки 01.04.02 Прикладная математика и информатика
Тема:
Разработка программного обеспечения для решения задачи маршрутизации транспорта, возникающей в реальной жизни
Работу выполнил Голубев А.П.
Студент группы 17 МАГ ИАД
Научный руководитель к.ф.-м.н.,
ст. преподаватель Е.К. Бацына
Нижний Новгород - 2019
Содержание
- Введение
- Постановка задачи и определения
- Вводимые определения
- Математическая модель
- Методы решения задачи маршрутизации транспорта
- Эвристический алгоритм вставок (Insertion heuristic)
- Метаэвристики и локальный поиск (Local Search)
- Табу поиск (Tabu Search)
- Обзор литературы
- Начальное решение
- Улучшение начального решения
- Пост-оптимизация
- Алгоритм решения задачи
- Начальное решение
- Улучшение начального решения
- Пост-оптимизация
- Полный алгоритм решения задачи
- Результаты
- Результаты: тестовые примеры для VRPTW
- Результаты: тестовые примеры для SDHVRPTWSD with 2D capacities
- Заключение
- Ссылки на литературу
- Приложения
- Глоссарий
- Детали реализации
- Пример входных данных
Введение
Задача маршрутизации транспорта - задача комбинаторной оптимизации и целочисленного программирования, относящаяся к классу NP-трудных задач. В базовой постановке, задача состоит в том, чтобы для определенного числа транспортных средств, находящихся в одном депо, построить оптимальные маршруты доставки товаров до всех потребителей.
Актуальность проблемы на текущий момент обусловлена потребностью индустрии в решении логистических задач по доставке товаров. Непосредственной частью таких задач является задача маршрутизации транспорта. Использование специализированного программного обеспечения на практике позволяет оптимизировать транспортировку товаров, значительно уменьшая затраты компаний [2]. Однако основной сложностью решения задач реального мира являются несколько факторов: большое число потребителей, значительные расстояния между потребителями и от потребителей до депо, множество сложных ограничений.
В данной работе рассматривается вариант задачи маршрутизации транспорта (англ. Vehicle Routing Problem) с ограничениями, возникающими в реальной жизни:
· Ограничение по грузоподъемности транспортных средств
· Временные окна (англ. Time Windows)
· Транспортные средства с разной грузоподъемностью и стоимостью использования (англ. Heterogeneous Fleet)
· Двухмерные спрос и грузоподъемность (каждая доставляемая единица продукции характеризуется объемом и весом)
· Разбиение заказа на несколько транспортных средств (англ. Split Deliveries)
· Ограничения потребителей на допустимые транспортные средства (англ. Site Dependency)
Рис. 1. Пример решения задачи маршрутизации транспорта [1]
Постановка задачи и определения
Задача маршрутизации транспорта состоит из нескольких основных сущностей: потребители, парк транспортных средств, маршруты и прочие. В данной работе, помимо базовых концепций вводятся специфичные определения, такие как, например, разбиение заказа. Вместе набор таких определений описывает задачу маршрутизации транспорта и, в какой-то степени, устанавливает область поиска решений. Затем, на базе определений, можно составить математическую модель всей задачи.
Далее в этом разделе будут определены основные сущности задачи и сформулирована математическая модель.
Вводимые определения
Потребители определены как набор заказчиков , находящихся в разных локациях соответственно. Традиционно, набор потребителей и депо (обозначающееся индексом 0) образуют набор всех рассматриваемых в проблеме локаций . Для каждой пары локаций ставится в соответствие стоимость проезда и время проезда . Каждый потребитель (кроме депо) имеет некоторый спрос , который необходимо удовлетворить.
Парк транспортных средств - набор машин , для которых заданы величины грузоподъемности (вместимости) . В простом случае, вместимость каждой машины равна некоторой константе (однородный парк транспортных средств). В случае неоднородности транспортных средств, помимо разных величин грузоподъемности, вводятся величины стоимости использования каждого транспортного средства: фиксированная цена использования и затраты на единицу пути .
Маршрутом является последовательный набор обслуживаемых локаций (потребителей), который начинается и заканчивается в депо .
Временные окна представляют собой временные интервалы, заданные для каждого потребителя . В зависимости от формулировки, могут быть 1. началом и концом начала разгрузки соответственно или 2. началом и концом обслуживания. В случае начала разгрузки 1., транспортное средство должно начать разгружаться не позднее, чем наступит время .
В случае обслуживания 2., транспортное средство должно закончить разгрузку не позднее, чем наступит время . Сама разгрузка (в любом из двух случаев) начинается не раньше, чем наступает время . В любом варианте формулировки, нет необходимости модифицировать математическую модель, т.к. несложно перейти от случая 1. к случаю 2 и наоборот.
Депо тоже имеет временной интервал - . Транспортному средству позволено выехать из депо только после наступления и запрещается приезжать позже наступления .
Двухмерные величины спроса и грузоподъемности определяют размерность перевозимого груза: каждая доставляемая единица груза имеет вес и объем. Такая формулировка позволяет отойти от габаритов каждого конкретного товара, позволяя использовать унифицированные единицы и упаковки независимо от специфики перевозки. С точки зрения объема и веса, более подходящим словом для описания грузоподъемности транспортного средства является вместимость. Этот термин в дальнейшем используется вместо грузоподъемности.
Разбиение заказа на несколько частей - возможность нескольким разным транспортным средствам доставлять части заказа одному и тому же потребителю. Это позволяет решать задачи, в которой заказы потребителей превышают полную вместимость транспортных средств. Также существуют случаи, когда использование разбиения заказов приносит дополнительный выигрыш за счет более высокой загрузки машин.
Разбиение транспортных средств на типы обычно подразумевает наличие машин с разными габаритами в транспортном парке. Такое дополнение позволяет решать задачи с разными потребителями: некоторые локации являются труднодоступными для крупного автотранспорта, например, мелкие магазины в черте города.
Математическая модель
Рассмотрим следующую математическую модель задачи маршрутизации транспорта со всеми перечисленными ограничениями (англ. Site-Dependent Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries (SDHVRPTWSD) with 2D capacities):
Для каждого ребра маршрута (исключая пустой маршрут ) и для каждого транспортного средства введем переменные следующим образом:
Введем переменную , определяющую долю заказа потребителя , доставляемую машиной .
Введем переменную определяющую время начала разгрузки машиной товаров для потребителя . Положим: .
Определим множество всех транспортных средств, которые могут обслуживать потребителя как множество . Тогда любое транспортное средство не из множества не может быть использовано в маршруте, где присутствует потребитель . Набор таких множеств известен и зафиксирован для каждой задачи.
Введем переменную , показывающую, используется ли транспортное средство в решении.
Математическая модель задачи выглядит следующим образом (формулировка основана на моделях [12], [13], [14]):
При условиях:
Целевая функция (0) состоит из двух частей. Первая часть показывает, что необходимо минимизировать затраты на перевозку, где - затраты на перевозку груза между потребителями при использовании машины . В данной работе, . Вторая часть показывает, что необходимо использовать самые выгодные с точки зрения фиксированной цены транспортные средства и минимизировать их общее число в задаче.
Равенства (1) и (2) показывают, что каждое использованное транспортное средство покидает депо, после достижения очередного потребителя, машина выезжает из этой локации, пока не достигнет депо в конце маршрута.
Уравнения (3) гарантируют, что спрос каждого потребителя будет полностью удовлетворен. Неравенства (4) и (5) показывают, что ни одной машине не назначается заказ, при котором нарушается её вместимость. Ограничения (6) определяют, что любой потребитель может быть обслужен лишь той машиной, которая приезжает к этому потребителю.
Неравенства (7) и ограничения (8) гарантируют корректное поведение и соблюдение временных интервалов обслуживания. Константа - достаточно большая, например, . А ограничения (9) обязуют каждое транспортное средство вернуться в депо до того, как завершится его временное окно.
Ограничения (14) гарантируют соблюдение допустимости доставки в случае с ограничений на транспортные средства.
Неравенства (15) показывают, что если машина доставляет товар до потребителя , эта машина используется в задаче и, следовательно, должна влиять на значение целевой функции.
Методы решения задачи маршрутизации транспорта
Рассмотрим два основных подхода к решению задачи маршрутизации транспорта: точный и эвристический. Точные методы позволяют получить оптимальное решение задачи, однако такие методы занимают слишком много времени на большом числе потребителей и сложных ограничениях и, соответственно, часто не являются целесообразными для решения реальных задач. В то же время, эвристические методы не гарантируют получение качественного решения, но на практике позволяют быстро получить хорошее решение для реальных задач индустрии.
Среди точных методов преобладают три основных, получающих решение целочисленной задачи линейного программирования: метод ветвей и границ, метод ветвей и отсечений, метод ветвей и цен (а также метод ветвей, отсечений и цен).
Эвристические методы делятся на множество различных подкатегорий: классические эвристические алгоритмы, генетические алгоритмы, метаэвристики и прочие. В случае эвристических методов чаще всего существуют три фазы построения решения: начало (инициализация), улучшение (оптимизация), пост-оптимизация. В зависимости от рассматриваемого алгоритма, задачи каждой из фаз меняются.
Например, в случае метаэвристического алгоритма:
· Фаза построения начального решения (англ. Initial solution phase) - фаза получения начального решения каким-то образом (эвристикой, точным методом, случайно и т.д.)
· Фаза улучшения (англ. Improvement phase) - фаза работы самой метаэвристики
· Фаза пост-оптимизации (англ. Post-optimization phase) - фаза улучшения «оптимального» с точки зрения метаэвристики решения с помощью какого-то дополнительного алгоритма (либо уже примененного раньше в предыдущих фазах, либо нового метода)
Далее в этой части будут рассмотрены некоторые эвристические и метаэвристические методы и подходы, использованные в данной работе при разработке программного обеспечения.
Эвристический алгоритм вставок (Insertion heuristic)
Рассмотрим эвристический последовательный алгоритм вставок, предложенный Мариусом Соломоном (англ. Marius Solomon) [3]. В целом, предложенный алгоритм - обобщение эвристики поиска ближайшего соседа с фокусом на наличие временных окон, так как алгоритм, в любой из вариаций, руководствуется двумя критериями: временем и расстоянием, что в теории приводит к небольшим ожиданиям разгрузки в сравнении с методами, основанными на критериях, учитывающих только расстояние.
Сначала алгоритм вставок инициализирует маршруты каким-либо методом. В случае данной работы, маршруты изначально предполагаются пустыми и содержат лишь 2 депо. После инициализации каждого маршрута, используются два критерия для вставки нового потребителя в текущий частично построенный маршрут между потребителями . Эти критерии применяются на каждой итерации пока полное решение не построено, то есть пока все потребители не обслужены.
Таким образом, для некоторого маршрута из потребителей, где , для каждого необслуженного потребителя вычисление его оптимального места в маршруте происходит по следующим формулам:
Лучший потребитель для вставки в маршрут определяется как тот, для которого:
Затем, лучший потребитель вставляется в маршрут между . Как только ни один новый допустимый потребитель не может быть добавлен, создается новый маршрут (если остались необслуженные потребители).
В данной работе, для определения критериев используется подход из [3]. Эвристика такого типа нацелена на выбор потребителя, затраты на вставку которого минимизируют общие расстояние и время маршрутов:
R_d (u),R_t (u)-полное расстояние и полное время текущего маршрута с u соответственно.
Метаэвристики и локальный поиск (Local Search)
На текущий момент, большой интерес в дискретной оптимизации представляют метаэвристики, в частности, они широко используются и для задачи маршрутизации транспорта. Метаэвристики - обобщенные процедуры получения решения задачи, которые обозревают пространство всех решений в поисках хороших решений, при этом часто используя базовые эвристические алгоритмы для построения маршрутов и улучшения существующих решений [1]. Правила поиска решений варьируются в зависимости от конкретной задачи и зачастую нуждаются в дополнительных алгоритмических улучшениях, тем не менее, оставляя основную концепцию без изменений.
Локальный поиск, в общем смысле, основан на идее перемещения от одного решения к другому в пределах окрестности поиска с помощью применения локальных изменений к текущему решению до тех пор, пока не найдено «оптимальное» с точки зрения алгоритма. Различные метаэвристические алгоритмы основаны на идее локального поиска: генетические алгоритмы [4], [5], табу поиск [6], управляемый локальный поиск (англ. guided local search) [7] и прочие.
Применительно к задаче маршрутизации транспорта, существует базовая модель работы локального поиска. Локальный поиск используется как эвристика для улучшения начального решения (фаза улучшения) и состоит из нескольких основных операторов (англ. move operators): relocate, exchange, cross, 2-opt, позволяющих получить из одного решение другое в некоторой малой окрестности. Схематичное использование локального поиска представлено на Рис. 2.
Рис. 2. Использование локального поиска. В точке входа на каждой итерации определяется критерий остановки, при котором текущее решение становится выходом локального поиска
В основе каждого оператора перемещения лежит определенная оптимизация. Для задачи маршрутизации транспорта эти оптимизации связаны с маршрутами в текущем решении:
· Relocate (перемещение) - оператор, который перемещает потребителя из одного маршрута в другой:
· Exchange (обмен) - оператор, который обменивается двумя потребителями в двух соответствующих маршрутах:
· Cross (пересечение) - концы двух маршрутов обмениваются:
{ik…in} из Ri перемещаются в Rj после j(l-1) {jl…jm} из Rj перемещаются в Ri после i(k-1),
· 2-opt (2-оптимизация) - переворачивание маршрута между двумя потребителями:
Рис. 3. Примеры работы основных операторов перемещения локального поиска [7]
Табу поиск (Tabu Search)
Табу поиск - эффективная метаэвристика, получившая широкое распространение в различных задачах комбинаторной оптимизации и часто применяющаяся в современных алгоритмах для получения лучших (state-of-the-art) результатов.
На каждом шаге алгоритма, происходит перемещение от текущего решения к лучшему в некоторой окрестности. Основной особенностью этого подхода является установление временных «табу» (запретов) на определенные переходы между решениями. По сути, под табу попадают недавно посещенные решения. Таким образом, устраняя уже построенные решения и их окрестности, механизм позволяет обозревать новые решения. Базовый механизм может быть усилен различными расширениями и вычислительными улучшениями, такими как интенсификация и диверсификация, динамическая длительность табу (англ. dynamic tabu tenure), табу для атрибутов решения вместо самого решения и прочими [1], [6], [8], [9], [10], [11].
Для непосредственного поиска лучшего решения используется локальный поиск с определенными ранее операциями.
Рис. 4. Пример алгоритма табу поиска
В данной работе рассматриваются две версии табу поиска, одна из которых, основываясь на [12], фокусируется на быстрой сходимости к наилучшему решению, запрещая рассматривать атрибуты плохих решений при локальном поиске. То есть всегда рассматриваются только хорошие решения (улучшающие целевую функцию).
Вторая версия, помимо использования идей первой версии, позволяет локальному поиску искать решение с табу до тех пор, пока нельзя будет его улучшить. В тот момент, когда локальный поиск нашел наилучшее решение в некоторой окрестности, списки табу сбрасываются, разрешается использовать ухудшающие операции перехода несколько итераций подряд, а возврат в старое хорошее решение запрещается через отдельные табу, давая некоторую гарантию того, что локальный поиск не сойдется к тому же локальному оптимуму, а найдет новый. Таким образом, вторая версия разрешает получать плохие решения в момент, когда локальный поиск остановился в точке локального оптимума. Под плохими решениями подразумеваются решения с целевой функцией хуже, чем у текущего решения.
Два этих подхода довольно сильно отличаются в преследуемых ими целях, первый - чисто интенсифицирующий, позволяет быстро сходиться к некоторому хорошему решению и на этом остановиться, второй - интенсифицирующий/диверсифицирующий, лучше обозревает всю область решений за счет перехода к более плохим, но отличающимся решениям при достижении локальных оптимумов. По сути, второй подход является некоторым расширением первого. Однако, в зависимости от задачи, тот или иной подход находит лучшее решение всей задачи, что продемонстрировано в секции с результатами.
Необходимо заметить, что две версии табу поиска отличаются и в определении табу. В первом случае (интенсифицирующий табу поиск):
· Под установлением табу подразумевается создание ограничения на поведение каждого оператора локального поиска (т.к. некоторые переходы между решениями будут заблокированы). Для эффективной проверки допустимости перехода, табу подвергается атрибут решения, а не все решение целиком, причем для каждого оператора локального поиска используется свой набор табу:
o Relocate: табу представляет собой пару значений (i, Ri), где i-потребитель, Ri - маршрут, из которого i был перемещен
o Exchange: табу представляет собой две пары значений
(i,Ri) и (j,Rj), где
o Cross: табу представляет собой две пары значений
o 2-opt: табу представляет собой пару значений
Таким образом, перед выполнением перехода между двумя решениями, в каждом операторе локального поиска проверяется нарушение табу: если нарушение присутствует, переход между решениями запрещен. Базовый алгоритм работы (интенсифицирующего) табу поиска с использованием локального поиска показан на Рис. 4.
В то же время, во втором случае (интенсифицирующий /диверсифицирующий табу поиск) дополнительно вводятся:
· Аналогично первому подходу, табу подвергается атрибут решения. Однако, в этом случае, используется один общий список табу, который пополняется в то время, когда разрешены переходы в плохие решения.
· Каждый оператор локального поиска использует одинаковый формат табу, который имеет вид пары значений , которая рассматривается в операторах локального поиска следующим образом:
o Relocate:
o Exchange:
o Cross:
o 2-opt:
Обзор литературы
В данном разделе будут рассмотрены основные статьи, на базе которых было разработано программное обеспечение для решения задачи маршрутизации транспорта, возникающей в реальной жизни.
Так как сама задача, как и её вариации, была сформулирована достаточно давно, существует большое множество статей и алгоритмов, посвященных решению задачи [1]. Однако, чаще всего, существующие статьи нацелены на решение одной из простых вариаций задачи, например, на решение задачи с наличием временных окон (VRPTW).
В связи с этим, данная работа основывается на нескольких отдельных статьях, алгоритмы из которых дополняются необходимыми шагами и переменными, для решения поставленной задачи маршрутизации транспорта со всеми ограничениями. Далее будут отдельно рассмотрены части алгоритма решения поставленной задачи, а затем представлен полный алгоритм.
Начальное решение
Эвристика для получения начального решения фокусируется в первую очередь на удовлетворении ограничения на различные типы транспортных средств (англ. site dependency). За основу алгоритма берется алгоритм получения начального решения из статьи [15]. Стоит заметить, что обозначения в математической модели [15] отличаются от обозначений в полной математической модели из данной работы.
Оригинальный алгоритм поиска начального решения позволяет решать задачу маршрутизации с разными типами транспортных средств (SDVRP). Для решения задачи с набором других ограничений (наличие веса и объема, разбиение заказа, временные окна и прочее) алгоритм модифицируется в данной работе.
Рис. 5. Исходная задача линейного программирования [15]
Идея алгоритма
Основная идея алгоритма: использование стратегии cluster-first, route-second [1], в котором сначала получают точное решение вспомогательной задачи линейного программирования (построение кластеров), а затем на его основе строят конечное решение эвристическими методами (построение маршрутов). Задача линейного программирования для начального решения отличается от представленной ранее математической модели.
В целом, получение начального решения состоит из 4 этапов:
1) Решение задачи линейного программирования из Рис. 5 (релаксация 0-1 задачи целочисленного программирования). На этом этапе происходит кластеризация потребителей по типам транспортных средств с использованием целевой функции, которая обеспечивает балансировку загрузку всех типов транспортных средств
2) Построение начальных маршрутов на базе решения задачи линейного программирования и поиск корневых точек маршрутов (потребителей с наибольшей вычисленной значимостью). По сути, корневая точка - крупный потребитель в некоторой окрестности (например, крупный магазин рядом с множеством мелких магазинов). Значимость каждого потребителя определяется как (из [15]):
3) Модификация задачи линейного программирования из пункта 1) с помощью изменения целевой функции: помимо балансировки нагрузки между типами транспортных средств, упор делается и на минимизацию расстояния от каждого потребителя до соответствующей ему корневой точки (центра кластера). Такая модификация гарантирует, что для некоторого близкорасположенного набора потребителей (например, магазины в одном районе), будет, при возможности, использован один тип транспортных средств, что позволяет получать более качественные начальные решения в задачах реальной жизни. Вводится следующее обозначение [15]:
Модификация целевой функции имеет вид [15]:
4) Построение конечных маршрутов, исходя из полученного решения задачи пункта 3)
Замечания
В отличие от предложенной релаксации решения задачи (Рис. 5) в статье [15]: , используется модификация, позволяющая решать задачу с разделением заказов между несколькими машинами (split deliveries) через введение новых переменных и следующих ограничений:
Из ограничений (5) и (6) следует, что при получении нецелочисленного значения только доля заказа доставляется до потребителя в случае его обслуживания одной из машин типа , а сама переменная показывает эту долю. Причем, ограничения (6) также гарантируют, что значение не может быть меньше значения , что позволяет запрещать слишком маленькие разбиения заказа (например, не имеет смысла рассматривать такие решения, где потребителю доставляется менее 25% всего заказа какой-то конкретной машиной). То есть , при большом числе разбиений, позволяет контролировать величину долей доставляемого заказа.
Ограничения (7) гарантируют, что максимальное число разбиений не превышает .
Вместо явного использования переменных добавляются следующие ограничения вида: . Заметим, что переменные являются заданными константами в каждой задаче.
Неравенства (3) из исходной задачи (Рис. 5) превращаются в набор неравенств (в силу наличия объема и веса продукции):
Вместо предложенного в статье [15] модифицированного алгоритма сбережений (англ. savings heuristic) из [16] для построения маршрутов, используется алгоритм вставок (англ. insertion heuristic) из статьи [3], описанный выше. Решение задачи с временными окнами также покрывается алгоритмом вставок для построения маршрутов, при решении задачи линейного программирования, временные окна не учитываются.
Значимость каждого потребителя вычисляется как (в силу наличия веса и объема):
Поиск решения задачи линейного программирования осуществляется с использованием программного обеспечения IBM CPLEX V12.7.1 [17] через программный интерфейс (API) на языке C++.
Улучшение начального решения
Эвристика для улучшения начального решения фокусируется на решении задачи маршрутизации транспорта с полным набором заданных ограничений. За основу берется алгоритм из статьи [12], улучшающий некоторое начальное решение.
Оригинальный алгоритм решает задачу маршрутизации при наличии временных окон и разбиения заказа (VRPTWSD). Этот алгоритм также модифицируется для того, чтобы обеспечить удовлетворение всех заявленных ограничений (неоднородный парк транспортных средств, типы транспортных средств и прочее).
Рис. 6. Алгоритм решения задачи VRPTWSD [12]
Идея алгоритма
Основная идея алгоритма улучшения состоит в использовании метаэвристики табу поиска [8] с локальным поиском для перемещения между решениями в пространстве поиска.
Общий алгоритм решения задачи представлен на Рис. 6. В качестве операторов локального поиска используются операторы: relocate, exchange, relocate split, 2-opt, модифицированные для решения задачи с разбиением заказа на несколько транспортных средств. При определенных условиях к результатам операции локального поиска применяются дополнительные методы route saving и intra relocate:
· Route saving устраняет маршруты меньше определенного размера (пороговое число задается константно для алгоритма)
· Intra relocate перемещает потребителя внутри одного маршрута в наилучшую с точки зрения целевой функции позицию
На Рис. 7 представлен пример перехода между решениями, в каждом из которых присутствует разбиение заказа между транспортными средствами. На Рис. 8 представлен оператор relocate split, введенный в алгоритме [12].
Рис. 7. Пример перехода от маршрута с двумя разбиениями к маршруту с одним разбиением [12]. Депо обозначены квадратом
математический модель маршрутизация транспорт
Рис. 8. Пример использования оператора relocate split [12]. Депо обозначены квадратом
Замечания
В статье [12] идет речь об использовании оператора 2-opt в локальном поиске. В данной работе, под оператором 2-opt подразумевается другая операция, описанная ранее. Поэтому, под оператором 2-opt статьи [12] стоит понимать оператор cross в данной работе.
Алгоритм построения начального решения из [12] не используется, вместо этого предлагается рассмотреть алгоритм, описанный ранее в этой части (статья [15]).
Помимо используемых 4 операторов локального поиска, в данной работе дополнительно используются 2 дополнительных оператора: 2-opt и relocate to new route. Оператор 2-opt устраняет пересечения дуг внутри одного маршрута, а relocate to new route создает новые маршруты путем перемещения каких-либо потребителей из других маршрутов при удовлетворении ограничений и улучшении целевой функции.
Аналогично механизму метода route saving, который полностью убирает маленькие маршруты, распределяя потребителей из этих маршрутов по другим более крупным, вводится метод merge splits, который устраняет разбиения заказов, тем самым уплотняя существующие маршруты и увеличивая долю доставляемого груза для конкретного потребителя. В частности, при максимальном числе разбиений заказа равном 2, такая операция позволяет в принципе устранить плохие разбиения и целиком обслужить потребителя в рамках одного маршрута.
Все методы улучшения начального решения умеют работать как с разбиением заказов, так и без разбиения, когда максимальное число разбиений равно 1, то есть можно обслужить потребителя только полностью, либо не обслужить вообще.
В операторе relocate split вместо перемещения такой же величины груза (вес и объем), перемещается доля величины груза, то есть после применения операции relocate split величина спроса потребителей в маршрутах может меняться. Такая постановка помогает разрешать ситуации, когда спрос каких-то потребителей превышает максимальную вместимость транспортных средств, и позволяет, таким образом, улучшать решения при наличии таких потребителей.
Временные окна на этой стадии жестко не ограничиваются в случае первой версии. Вместо этого используется подход, основанный на штрафах за нарушение временных окон. На каждой итерации улучшения начального решения помимо текущего решения и текущего лучшего решения хранится текущее лучшее допустимое решение. После нахождения улучшенного решения выбирается наилучшее и допустимое среди двух текущих лучших: обычного и всегда допустимого.
В отличие от фиксированного числа в [12] пороговое значение для размера маршрута в route saving выбирается динамически как 5% всех потребителей. То есть все маршруты размером не более 5% алгоритм route saving будет пытаться устранить, давая больше пространства для улучшения в случае большого числа потребителей.
Как было представлено ранее, была рассмотрена еще одна версия табу поиска, которая дополняет подход [12] с помощью использования «плохих» переходов (то есть переходов к более плохим решениям в окрестности).
Пост-оптимизация
В качестве фазы пост-оптимизации используется упрощенный алгоритм улучшения начального решения: на текущем лучшем и текущем лучшем допустимом решениях запускается процедура локального поиска без использования табу на несколько итераций.
На каждой итерации после применения локального поиска, к текущему решению применяется операция intra relocate. В некоторых случаях, когда табу поиск из предыдущего шага не доходит до оптимального решения, а выходит из-за достижения лимита по общему числу итераций, шаг пост-оптимизации позволяет найти текущий локальный оптимум, который может оказаться лучше, чем уже найденное лучшее решение.
Затем выбирается лучшее допустимое решение из двух: обычного решения и всегда допустимого, гарантируя выполнение допустимости, если она когда-либо ранее была выполнена.
Алгоритм решения задачи
Полный алгоритм решения состоит из нескольких отдельных алгоритмов: построения начального решения, поиска улучшенного решения, пост-оптимизации лучшего найденного решения.
Дополнительно к этому, алгоритм построения начального решения модифицируется, чтобы иметь возможность генерировать решения случайным образом. В данной работе генерируются несколько начальных решений, каждое из которых оптимизируется, и из всех лучших решений выбирается одно наилучшее, которое и является решением всей задачи.
Начальное решение
Алгоритм состоит из двух частей: решение задачи линейного программирования (англ. Linear Programming or LP) [15] и построение маршрутов с помощью эвристического алгоритма вставок [3].
Помимо этого, задача линейного программирования решается дважды с разной целевой функцией. Построение начального решения основывается на решении второй задачи линейного программирования. Одновременно генерируется несколько начальных решений.
Рис. 9. Алгоритм построения начального решения
Улучшение начального решения
Алгоритм использует механизм метаэвристики табу поиска и локальный поиск.
Ограничение на нарушение временных окон явно не накладывается, вместо этого используется штрафная целевая функция, значение которой увеличивается при росте числа нарушений.
Для дополнительной гарантии получения допустимого решения с точки зрения временных окон, штраф за нарушение временных окон периодически становится эквивалентен целевой функции (по значению), тем самым заставляя алгоритм локального поиска исправлять даже малые нарушения ограничений. Помимо допустимости, такая модификация показывает лучшие результаты при поиске оптимального решения. Все остальные ограничения явно удовлетворяются в операторах локального поиска.
Рис. 10. Алгоритм улучшения начального решения
Пост-оптимизация
Алгоритм независимо оптимизирует два полученных лучших решения: обычное и всегда допустимое. Затем, выбирается лучшее решение из двух. Стоит заметить, что обычное лучшее решение тоже может быть допустимым.
Рис. 11. Алгоритм шага пост-оптимизации
Полный алгоритм решения задачи
Согласно алгоритмам, приведенным раньше в этой части, полный алгоритм решения задачи маршрутизации транспорта с ограничениями, возникающими в реальной жизни, имеет вид:
Рис. 12. Поиск решения задачи маршрутизации транспорта
Результаты
В данной части будут представлены результаты решения задач маршрутизации транспорта. Для общей оценки работы алгоритма были использованы широко известные тестовые примеры [18] для задачи маршрутизации транспорта с временными окнами (VRPTW). Так как данные примеры не имеют ряда ограничений, многие из них выключены в разработанном программном обеспечении, чтобы обеспечить равные условия решения тестовых задач. Для оценки работы алгоритма в полном объеме были сгенерированы дополнительные тестовые задачи маршрутизации транспорта со всеми ограничениями.
Результаты: тестовые примеры для VRPTW
В этом разделе представлены результаты решения тестовых примеров из [18] для случая 100 потребителей. Следующие упрощения во входных данных были сделаны, чтобы обеспечить корректное и выравненное с другими алгоритмами решение задачи маршрутизации транспорта с временными окнами разработанным программным обеспечением:
· Целевая функция, определенная ранее как
,
изменена на
· Используется один тип транспортных средств, в котором все машины имеют одинаковую вместимость (homogeneous fleet)
· Объем и вес груза имеют одинаковые значения
· Разбиение груза на части не разрешается
Для сравнения результатов лучших известных эвристических решений и результатов алгоритма разработанного программного обеспечения используется таблица, состоящая из колонок:
1. Instance - название тестового примера
2. Best - значение целевой функции для лучшего известного решения, полученного эвристическим методом
3. Best N - значение числа маршрутов для лучшего известного решения, полученного эвристическим методом (соответствует целевой функции)
4. Reference - ссылка на работу, в которой получено лучшее известное решение
5. SDVRPTWSD - значение целевой функции, полученное алгоритмом, разработанным в текущей работе
6. N - значение числа маршрутов, полученное алгоритмом из данной работы
Результаты лучших решений взяты из источника [19] и представлены ниже. Следующие сокращение используются для описания эвристик, получивших лучшие известные результаты: BBB - [20], BVH - [21], CC - [22], CLM - [23], GCC - [24], GTA - [25], H - [26], HG - [27], IKMUY - [28], MBD - [29], LLH - [30], RGP - [31], RP - [32], RT - [10], SSSD - [34], S97 - [35], S98 - [36], TBGGP - [37], WL - [38]
Как видно из представленных ниже таблиц, разработанное программное обеспечение показывает хорошие результаты на кластеризованных тестовых задачах (те, что начинаются с буквы “C”).
Из таких результатов становится понятно (Табл. 1, 2, 3), что кластеризованные примеры хорошо решаются представленным алгоритмом: для 10 тестовых задач получены лучшие известные решения. Так как в большинстве случаев реальные данные представляют собой схожую картину (потребители группируются в некоторых определенных точках (например, городах), при этом между такими точками потребителей мало либо нет совсем), то можно говорить о том, что такой алгоритм табу поиска хорошо применим к реальным задачам.
Для более общей оптимизации всех задач, был использован второй вариант алгоритма табу поиска (интенсифицирующий/диверсифицирующий), где сначала осуществляется поиск наилучшего решения в некоторой окрестности, а затем осуществляется смена текущей окрестности посредством последовательности ухудшающих переходов. Результаты, представленные на Табл. 4, 5, 6, хотя и демонстрируют решения хуже для кластеризованных примеров, чем первая версия табу поиска, но показывают хорошие результаты на других задачах (начинающихся с “R” и “RC”). Более того, со второй версией табу поиска получилось достичь новых лучших эвристических решений для ряда таких тестовых задач.
Табл. 1. Результаты решения задачи VRPTW
Табл. 2. Результаты решения задачи VRPTW
Табл. 3. Результаты решения задачи VRPTW
Табл. 4. Результаты решения задачи VRPTW
Табл. 5. Результаты решения задачи VRPTW
Табл. 6. Результаты решения задачи VRPTW
Из представленных результатов можно заметить, что вторая версия алгоритма табу поиска получила новые лучшие решения для 10 тестовых задач (“R” и “RC”), при этом получив лучшие известные эвристические результаты для 2 кластеризованных тестовых задач. Причем среднее отклонение от лучших решений в этом варианте алгоритма составляет около 10%, что является отличным результатом, учитывая тот факт, что некоторые из задач были решены лучше.
Стоит заметить, что результаты на кластеризованных примерах во втором случае хуже и похожая ситуация может возникнуть и в задачах реального мира. В связи с этим предлагается при необходимости использовать оба алгоритма независимо, а затем выбирать наилучшее решение из двух финальных.
Результаты: тестовые примеры для SDHVRPTWSD with 2D capacities
В этой части рассматриваются результаты работы алгоритма на примерах задачи маршрутизации транспорта, возникающей в реальной жизни. Тестовые примеры были специально сгенерированы с наличием ранее заданных ограничений. В качестве основы для генератора использовались ранее представленные тестовые примеры [18].
По аналогии с оригинальными примерами, каждый сгенерированный тестовый пример назван в формате m<название оригинального тестового примера>. То есть, если был использован тестовый пример c101, сгенерированный на базе него новый пример будет иметь название mc101.
При генерации применялись следующие модификации:
· Введены типы транспортных средств и типы потребителей по следующим правилам:
o Все машины делятся на 3 типа: легкие грузовики, (стандартные) грузовики и полуприцепы. Вместимости таких машин соответственно задаются как:
o Потребители делятся на 4 типа: маленькие, средние, большие и очень большие. Маленькие потребители могут быть обслужены только легкими грузовиками машинами, средние - легкими грузовиками и стандартными грузовиками, большие - легкими, стандартными грузовиками и полуприцепами. Очень большие потребители не обслуживаются легкими грузовиками, так как такое обслуживание полагается не целесообразным. Тип потребителя определяется исходя из размера его заказа как:
средний размер заказа
· Для каждого типа машин заданы величины фиксированной цены использования и затрат на единицу пути:
- среднее расстояние между двумя потребителями
· Число транспортных средств каждого типа задано как:
· Рассматриваются два варианта задачи: с наличием разбиений заказов (Табл. 9, 10) и без (Табл. 7, 8)
Результаты работы программного обеспечения на сгенерированных примерах представлены далее в виде таблиц. Каждая колонка имеет следующее значение:
1. Instance - название тестового примера
2. Objective - значение целевой функции, полученное разработанным алгоритмом
3. Cost (или cost function) - значение целевой функции без учета стоимости использования транспортных средств. Это значение эквивалентно значению целевой функции в оригинальных тестовых примерах из [18]
4. Feasible - допустимо или нет получившееся решение
5. N - число использованных машин (число маршрутов)
6. Small - число использованных легких грузовиков
7. Medium - число использованных стандартных грузовиков
8. Big - число использованных полуприцепов
Табл. 7. Результаты решения задачи SDHVRPTW
Табл. 8. Результаты решения задачи SDHVRPTW (вторая версия алгоритма табу поиска)
Табл. 9. Результаты решения задачи SDHVRPTWSD
Табл. 10. Результаты решения задачи SDHVRPTWSD (вторая версия алгоритма табу поиска)
Заметим, что результаты решения задачи с разрешением разбиений заказа получились хуже, чем в случае, когда разбиение заказа запрещено.
Кроме того, одно из решений больше не является допустимым (Табл. 9, mc101). Однако в реальной жизни возникают примеры, в которых нельзя допустимо решить задачу без разбиений, например, когда некоторые заказы превышают вместимость какого-либо транспортного средства, либо имеются очень сжатые временные окна, при которых невозможно полностью обслужить некоторых потребителей, если отправлять новое транспортное средство прямо из депо.
Заключение
В данной работе была рассмотрена задача маршрутизации транспорта, возникающая в реальной жизни. Отличительными особенностями такого класса задач является большое число потребителей и сложных ограничений, которые часто тяжело удовлетворить.
Была сформулирована прикладная задача маршрутизации и представлена математическая модель, предложен алгоритм решения поставленной задачи маршрутизации в общем виде и разработано программное обеспечение, решающее задачи описанного типа.
Результаты работы программного обеспечения показаны на известных в научном сообществе тестовых примерах Мариуса Соломона и численно продемонстрирована эффективность разработанного алгоритма на ряде таких примеров. Дополнительно, были сгенерированы новые тестовые задачи, включающие в себя все перечисленные ранее ограничения. Эти задачи также были решены и их результаты приведены в соответствующей части.
-
Ссылки на литературу
1. P. Toth and D. Vigo. The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications, 2002
2. G. Hasle, K.A. Lie, E. Quak. Geometric Modelling, Numerical Simulation and Optimization: Applied Mathematics at SINTEF, 2007
3. M.M. Solomon. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 1987
4. L. Davis. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, 1991
5. J.L. Blanton and R.L. Wainwright. Multiple vehicle routing with time and capacity constraints using genetic algorithms. Fifth International Conference on Genetic Algorithms, 1993
6. F. Glover and M. Laguna. Tabu search. Handbook of combinatorial optimization, 1998
7. P. Kilby, P. Prosser and P. Shaw. Guided local search for the vehicle routing problem with time windows. Meta-heuristics: Advances and Trends, 1999
8. F. Glover and M. Laguna. Tabu search. Modern Heuristic Techniques of Combinatorial Problems, 1993
9. A. Hertz, E.D. Taillard and D. De Werra. Tabu search. Local Search in Combinatorial Optimization, 1997
10. Y. Rochat and E.D. Taillard. Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics, 1995
11. P. Toth and D. Vigo. The granular tabu search and its application to the vehicle routing problem. INFORMS Journal of Computing, 2003
12. S.C. Ho and D. Haugland. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Computers&Operations Research, 2004
13. P.W. Frizzel and J.W. Griffin. The split delivery vehicle scheduling problem with time windows and grid network distances. Computers&Operations Research, 1995
14. J. Larsen. Vehicle routing problem with time windows - finding optimal solutions efficiently. 1999
15. I-Ming Chao, B. Golden, E. Wasil. A computational study of a new heuristic for the site-dependent vehicle routing problem. INFOR: Information Systems and Operational Research, 1999
16. B. Golden, T. Magnanti and H. Nguyen. Implementing Vehicle Routing Algorithms. Networks, 1977
17. IBM ILOG CPLEX Optimization Studio V12.7.1
18. Benchmarking test instances developed by M. Solomon
19. Best known results for M. Solomon test instances.
20. J. Berger, M. Barkaoui and O. Brдysy. A Parallel Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows. Defense Research Establishment Valcartier, Working paper, 2001
21. R. Bent and P. Van Hentenryck. A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows. Technical Report CS-01-06, Department of Computer Science, Brown University, 2001
22. Z.J. Czech and P. Czarnas. A Parallel Simulated Annealing for the Vehicle Routing Problem with Time Windows. 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, 2002
23. J.-F. Cordeau, G. Laporte, and A. Mercier. A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows. Centre for Research on Transportation, Working paper, 2000
24. Agnieszka Debudaj-Grabysz, Zbigniew J. Czech and Piotr Czarnas. Silesia University of Technology and University of Wroclaw, Poland, 2004
25. L.M. Gambardella, E. Taillard, and G. Agazzi. MACS-VRPTW: A Multiple Ant Colony System fo Vehicle Routing Problems with Time Windows. New Ideas in Optimization, 1999
26. J. Homberger. Verteilt-parallele Metaheuristiken zur Tourenplanung. Gaber, Wiesbaden, 2000
27. J. Homberger and H. Gehring. Two Evolutionary Metaheuristics for the Vehicle Routing Problem with Time Windows. INFOR, 1999
28. T. Ibaraki, M. Kubo, T. Masuda, T. Uno and M. Yagiura. Effective Local Search Algorithms for the Vehicle Routing Problem with General Time Windows. Department of Applied Mathematics and Physics, Kyoto University, Japan, Working paper, 2001
29. D. Mester, O. Brдysy and W. Dullaert. A Multi-parametric Evolution Strategies Algorithm for Vehicle Routing Problems. Institute of Evolution, University of Haifa, Israel, Working paper, 2005
30. H. Li, A. Lim, and J. Huang, Local Search with Annealing-like Restarts to Solve the VRPTW. Department of Computer Science, National University of Singapore, Working paper, 2001
31. L.M. Rousseau, M. Gendreau and G. Pesant. Using Constraint-Based Operators to Solve the Vehicle Routing Problem with Time Windows. Journal of Heuristics, 2002
32. S. Ropke&D. Pisinger. A general heuristic for vehicle routing problems. Department of Computer Science, University of Copenhagen, technical report
33. G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt and G. Dueck. Record Breaking Optimization Results Using the Ruin and Recreate Principle. Journal of Computational Physics, 2000
34. P. Shaw. A New Local Search Algorithm Providing High Quality Solutions to Vehicle Routing Problems. University of Strathclyde, Glasgow, Scotland, Working paper, 1997
35. P. Shaw. Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. Principles and Practice of Constraint Programming - CP98, Lecture Notes in Computer Science, Springer-Verlag, 1998
36. E. Taillard, P. Badeau, M. Gendreau, F. Geurtin, and J.Y. Potvin. A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows. Transportation Science, 1997
37. M. Woch, P. Lebkowski. Sequential Simulated Annealing for the Vehicle Routing Problem with Time Windows. Decision Making in Manufacturing and Services, 2009
38. CMake build toolchain
39. Intel Threading Building Blocks.
40. Microsoft Excel
41. GitHub platform
42. Open-source Vehicle Routing Problem project source code
Приложения
Глоссарий
Программное обеспечение - множество программ, используемых для управления компьютером и решающих какую-то поставленную задачу посредством компьютерных вычислений.
Алгоритм - набор инструкций, описывающий действия, необходимые для решения некоторой задачи.
Комбинаторная оптимизация - область теории оптимизации. Суть комбинаторной оптимизации заключается в поиске оптимального объекта в конечном множестве имеющихся объектов.
Линейное программирование - дисциплина, посвященная теории и методам решения задач на множествах, которые задаются системами линейных уравнений и неравенств.
Оптимальное решение - наиболее предпочитаемое решение среди некоторого множества, обычно, максимально удовлетворяющее поставленные в задаче требования.
Жадный алгоритм - алгоритм, который на каждом этапе принимает локально оптимальные решения, при этом, не гарантируя глобальную оптимальность конечного решения.
Эвристический алгоритм - алгоритм решения с использованием практических методов, которые не гарантируют точности или оптимальности, но при этом являются достаточными для нахождения решения. Обычно используется для решения задач, в которых невозможно найти точное/оптимальное решения по тем или иным причинам.
Генетический алгоритм - эвристический алгоритм, использующий в качестве идеи механизмы функционирования схожие с естественным отбором в биологических системах.
Допустимое действие - действие, которое возможно совершить в рамках заданной модели и которое удовлетворяет определенным ограничениям этой модели.
Допустимое решение - решение, которое удовлетворяет все поставленным ограничениям заданной модели, в частности, полученное путем совершения только допустимых действий.
Операционная система - набор взаимосвязанных программ, которые управляют ресурсами компьютера и обеспечивают взаимодействие между этими ресурсами и пользователем.
Язык программирования - формально определенный синтетический язык, предназначенный для написания компьютерных программ.
Утилита - вспомогательная компьютерная программа.
Скрипт - сценарий, описывающий последовательность действий на некотором языке программирования, которые выполняются системой, например, операционной.
Детали реализации
Программное обеспечение для решения задачи маршрутизации состоит из нескольких частей:
· Пользовательское приложение для запуска разработанного алгоритма на тестовых примерах с интерфейсом командной строки
...Подобные документы
Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [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
