ВВЕДЕНИЕ 3
1. ЗАДАЧА О РАЗВОЗКЕ 6
1.1 Постановка задачи 6
1.2 Методы решения 7
1.2.2 Метод Литтла со штрафами 9
1.2.3 Модификация метода Литтла со штрафами 9
2. ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ 15
2.1. Генератор исходных данных для задачи о развозке 16
2.2. Численные эксперименты 16
2.2.1. Временные характеристики точного метода 16
2.2.2. Численное исследование точности алгоритма Кларка-Райта. 17
ЗАКЛЮЧЕНИЕ 28
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 29
Купить

Одной из важных задач большинства предприятий, которые осуществляют доставку товара потребителям, является сокращение издержек. Возможное решение данной проблемы заключается в сокращении пробега автотранспорта и, как следствие, уменьшении расхода ГСМ. Для осуществления этого предприятия, по сути, занимаются решением задачи о развозке.
Простейшей моделью задачи о развозке является следующая постановка:
1) имеется база, на которой есть достаточный объем однородной продукции;
2) имеется n пунктов потребления этой продукции, каждый пункт дает заявку на доставку продукции в объеме qt, t=1,...,n;
3) развозка продукции производится однотипными транспортными средствами объема Q;
4) заданы стоимости переездов как между пунктами потребления, так и между пунктами и базой (обозначим базу как пункт с номером 0) wtj, t=0,...,n, j=0,...,n.
Требуется найти набор маршрутов развозки, имеющий минимальную суммарную стоимость.
Как видно из приведенного описания задачи, при условии Yi=14i < Q задача превращается в хорошо известную задачу коммивояжера.
Для решения сформулированной выше задачи о развозке в 1964 году Кларком и Райтом [1] был предложен эвристический алгоритм, позволяющий быстро находить решение задач с большим количеством пунктов. Этот алгоритм до сих пор привлекает внимание исследователей [2]-[4]. Заметим, что в научной литературе отсутствуют описания точных алгоритмов решения этой задачи. В статье Борханова, Фазылова [5] сделана попытка построения алгоритма решения задачи о развозке на базе метода Литтла [6]. Однако, предложенный алгоритм не гарантирует получение точного решения.
Смоделируем ситуацию, которая возникает в организациях, специализирующихся на доставке товаров и грузов. Допустим, автомобилю компании необходимо развезти продукцию в определенные пункты и вернуться на базу. Задача формулируется следующим образом: определить в каком порядке автомобиль должен посещать клиентов, чтобы затраты на этот путь были минимальными (все пункты посещаются один раз).
Заметим, что интерес для практики представляют и более общие постановки задачи о развозке. Например,
1) перевозки обслуживаются разнотипными транспортными средствами,
2) имеется не одна, а несколько баз,
3) груз неоднородный, причем имеются условия частичной совместимости грузов, и т. п.
Время работа программы, реализующей эвристический алгоритм для нахождения маршрута для задачи о развозке, занимает малое количество времени, по сравнению с тем, какие размеры данных он может обработать. Однако результаты чаще всего получаются неоптимальными даже при небольших наборах данных.
В связи с необходимостью эффективного решений задачи о развозке, становится необходимым использование точных методов. Однако, время, затраченное на выполнение программы, реализующий точный алгоритм, принимает адекватные значения только при небольших данных.
В данной работе ставиться цель получения уточненного вариант метода из [5], обеспечивающего получение точного решения задачи о развозке. Второй целью работы является численная проверка эффективности алгоритма Кларка - Райта с помощью предложенного в работе точного алгоритма.
Для реализации поставленной в работе цели ставятся следующие задачи:
1) реализовать эвристический метод решения задачи о развозке
- метод Кларка-Райта,
2) реализовать метод решения задачи о развозке - уточненный
метод Литтла со штрафами,
3) разработать способ генерации входных данных для задачи о развозке,
4) провести численный эксперимент для определения для определения точностных характеристик эвристического метода,
5) предложить рекомендации по применению эвристического и точного методов.
Объектом исследования является решение задачи о развозке однородного груза с одной базы. Предметом исследования - алгоритм Кларка-Райта и алгоритм Литтла со штрафами.
Купить