Содержание к диссертации
Введение
Глава 1. Модели и методы решения задачи развозки 10
1.1. Проблемные ситуации, приводящие к необходимости решения задачи развозки в производственных условиях 10
1.2. Системный анализ, как метод решения слабоструктурированных проблем 18
1.3. Подходы к решению дискретных многокритериальных задач 27
1 .4. Методы решения классических прототипов задачи развозки 36
1.4.1. Транспортная задача 36
1.4.2. Задача коммивояжера 40
1.4.3. Задача поиска оптимального пути в графе 42
1.4.4. Задача о наименьшем покрытии 42
1.4.5. Понятие вычислительной сложности 46
1.5. Существующие варианты формальной постановки задачи развозки и подходы к их решению 49
1.6. Выводы, цели и задачи исследований 59
Глава 2. Системный анализ проблемы 62
2.1. Вводные положения 62
2.2. Анализ проблемы 64
2.2.1. Модель проблемной ситуации 64
2.2.2. Анализ целей 68
2.2.3. Формирование критериев 70
2.2.4. Определение ограничений и формирование допущений 72
2.3. Формальная постановка задачи 78
2.4. Системная модель планирования развозки и подходы к решению 79
2.5. Размерные (количественные) допущения 83
2.6. Выводы по главе 84
Глава 3. Решение многокритериальной задачи поиска эффективных путей на графе 86
3.1. Формализация транспортной сети 86
3.2. Выбор метода решения многокритериальной задачи поиска эффективных путей на графе общего вида 91
3.3. Анализ векторного алгоритма Флойда-Уоршалла 99
3.3.1. Корректность алгоритма 100
3.3.2. Оценка вычислительной сложности 104
3.4. Пример применения алгоритма Флойда-Уоршалла 105
3.5. Окончательный выбор оптимальных путей 107
3.6. Выводы по главе 109
Глава 4. Модели процесса развозки и алгоритмы составления плана перевозок 110
4.1. Алгоритм формирования маршрута обхода ТТ ПО
4.2. Перебор вариантов комплектации ТС 113
4.3. Перебор вариантов порядка следования ТС по маршруту 118
4.4. Функции развозки 120
4.5. Перебор вариантов загрузки каждого ТС при данном упорядочении 124
4.6. Поиск способа использования одного ТС в нескольких рейсах 128
4.7. Система допущений в модели задачи развозки и формирование базовой модели развозки 135
4.7.1. Допущения с вариациями 135
4.7.2. Безвариантные допущения 138
4.8. Сводный алгоритм решения базовой задачи развозки 140
4.9. Выводы по главе 146
Глава 5. Описание программного комплекса и решение практической задачи развозки 147
5.1. Структура специального программного обеспечения 147
5.2. Вычислительный эксперимент решения практической задачи развозки 150
5.3. Выводы по главе 160
Заключение 162
Список литературы 164
Приложения 175
- Системный анализ, как метод решения слабоструктурированных проблем
- Определение ограничений и формирование допущений
- Выбор метода решения многокритериальной задачи поиска эффективных путей на графе общего вида
- Перебор вариантов порядка следования ТС по маршруту
Введение к работе
Актуальность проблемы. Современная экономическая ситуация в России характеризуется все возрастающей конкуренцией на рынке товаров и услуг. Одним из следствий этого является повышение уровня требований клиентов. В таких условиях развитие любой компании, ориентированной на обслуживание большого числа потребителей, должно быть очень динамичным. Целью этого развития является предоставление услуг такого качества и в таком объеме, которые будут соответствовать ожиданиям клиентов. Известно, что затраты на производство некоторых товаров составляют лишь около 10% их стоимости, в то время как доля расходов на доставку может достигать 50%, а в ряде случаев и больше.
Сегодня потребители все чаще обращают внимание на дополнительные критерии, такие как сроки доставки, возможность получения заказанного товара в четко оговоренное время, а также качественное информационное сопровождение процесса выполнения заказа.
Научной основой задачи оптимального планирования грузоперевозок является классическая транспортная задача. Разнообразие целей и критериев при ее постановке в применении к различным практическим областям привело к появлению большого класса «развозочных» задач, решением которых в разное время занимались такие ученые как Дж. Литл, Р. Беллман, С. Уоршалл, Р. Флойд, И. X. Сигал, Э. Дейкст-ра, В. А. Житков, А.В. Ефремов. Однако, существующие подходы к решению задачи развозки исходят из ее упрощенной постановки, не в полной мере соответствующей реальным условиям.
Таким образом, повышение эффективности оперативного планирования в сфере транспортного обслуживания с привлечением современных информационных технологий с целью предоставления клиентам услуг такого качества и в таком объеме, которые будут соответствовать их ожиданиям, является одной из фундаментальных проблем науки и производства. Исследованиям в рамках данной фундаментальной проблемы и посвящена настоящая работа.
Диссертационная работа выполнена в рамках госбюджет-ной НИР по теме «Математическое и компьютерное моделирование в задачах проектирования и оптимизации функционирования информационных и технологических систем» (№ госрегистрации 01.2006.05298), а также гранта РФФИ 06 - 07 - 89189-а по теме «Разработка информационных технологий выбора на необозримом для ЛПР
множестве альтернатив».
Цель работы. Разработка и исследование модели оптимального планирования перевозок грузов от одного поставщика нескольким получателям, позволяющей определить оптимальные маршруты развозки, перечень грузов, перевозимых каждым транспортным средством и расписание движения единиц автотранспорта.
Поставленная цель достигается посредством решения следующих задач.
Системный анализ проблемы планирования развозки с целью выработки обоснованной формальной постановки общей задачи, соответствующей реальным производственным условиям.
Систематизация вариантов производственных условий, приводящих к различным упрощающим допущениям модели процесса развозки.
Синтез базового варианта модели процесса развозки.
Разработка алгоритмов решения задачи планирования грузоперевозок на основе базового варианта модели.
5. Создание программного обеспечения, реализующего разрабо
танные алгоритмы.
6. Проведение вычислительных экспериментов и практическая реа
лизация результатов исследования в производственных условиях.
Объект исследований. Транспортные перевозки, осуществляемые по схеме «один ко многим» с преобладанием маршрутизации по схеме коммивояжера.
Методы исследования. Выполненные исследования базируются на использовании аппарата теории графов, многокритериальной дискретной оптимизации, теории NP-полных задач, имитационного моделирования. Общей методологической основой является системный подход.
Научная новизна работы состоит в следующем.
Разработан способ декомпозиции общей задачи развозки, основанный на построении системы частных задач, каждая из которых содержит определенные упрощающие допущения, соответствующие различным вариантам производственных условий.
Разработан и исследован базовый вариант модели процесса развозки, содержащий элементы неопределённости в оценке эффективности создаваемой системы маршрутов развозки и учитывающий необходимость оперативного решения многокритериальной задачи раз-
возки без привлечения экспертов.
3. Разработан и исследован многокритериальный вариант алгоритма Флойда-Уоршалла, позволяющий найти между всеми парами вершин графа общего вида множество путей, недоминируемых по отношению Парето.
Теоретическая и практическая значимость. Теоретические результаты работы используются в научной и учебной деятельности Воронежской государственной технологической академии, Воронежской государственной лесотехнической академии и могут быть использованы в Тамбовском государственном техническом университете и Воронежском государственном архитектурно-строительном университете.
Практические результаты работы реализованы при автоматизации транспортного цеха предприятия ООО «Агросвет», что подтверждено актом о внедрении, а также могут быть использованы при разработке информационных систем планирования перевозок в различных хозяйственных отраслях.
Наиболее существенные результаты, полученные автором и выносимые на защиту. На защиту выносятся математические методы исследования моделей планирования развозки грузов, алгоритмы, комплекс проблемно-ориентированных программ.
Формальная постановка задачи развозки, выработанная по результатам системного анализа проблемы и соответствующая реальным производственным условиям.
Система вариантов производственных условий, на основании которой получен набор упрощающих допущений, определяющих различные частные задачи общей задачи развозки.
Базовый вариант модели процесса развозки, состоящий из выбранных частных задач, образованных полученной системой допущений, и позволяющий решить поставленную задачу в условиях много-критериальности и наличия временных ограничений.
Многокритериальный вариант алгоритма Флойда-Уоршалла, позволяющий найти между всеми парами вершин графа общего вида множество путей, недоминируемых по отношению Парето.
5. Алгоритмы решения задач определения оптимальной загрузки и расписания движения транспортных средств.
6. Программный комплекс для решения задачи развозки. Апробация работы. Основные результаты диссертационной
работы докладывались и обсуждались
на II международной научной конференции «Современные проблемы прикладной математики и математического моделирования» (Воронеж, с 11 поіб декабря 2007 г.);
на Международной научной конференции «Математические методы в технике и технологиях» (Саратовский государственный технический университет, 27-31 мая 2008 г., ММТТ-21);
на III Международной научной конференции «Современные проблемы прикладной математики и математического моделирования» (Воронеж, с 2 по 7 февраля 2009 г.);
на Всероссийской научной конференции студентов, аспирантов и молодых ученых (Воронеж, с 12 по 13 ноября 2009 г.).
Публикации. Основное содержание работы изложено в 7 публикациях, приведённых в конце текста автореферата, из них 3 [1,2,3] - в изданиях, рекомендуемых ВАК РФ. В публикациях, изданных в соавторстве [1-6], личный вклад соискателя состоит в следующем: [1], [4], [5] - разработка модели; [2] - разработка алгоритма; [3], [6] - разработка прямого хода алгоритма и пакета программ.
Программное средство, реализующее разработанные алгоритмы, зарегистрирвано в Государственном информационном фонде ФГНУ «Центр информационных технологий и систем органов исполнительной власти» под номером №50200901019 от 20.10.2009г.
Объем и структура работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы из 120 наименований и приложения. Основной текст изложен на 174 страницах. Работа содержит 11 таблиц и 13 рисунков.
Системный анализ, как метод решения слабоструктурированных проблем
Системный анализ — это совокупность методологических средств и процедур, используемых для подготовки, обоснования и осуществления решений по сложным проблемам самого различного характера. Процедуры и методы системного анализа направлены на выдвижение альтернативных вариантов решения проблем, выявление масштабов неопределенности по каждому из вариантов и сопоставление их по тем или иным критериям эффективности [66].
Системный анализ является междисциплинарной методологией исследований при решении различного рода задач на уровне современных научно-технических требований, в том числе при выполнении комплекса работ по патентным исследованиям, определению технического уровня и научно-техническому прогнозированию, экспертизе объектов техники на патентную чистоту, а также по методологическим основам и организации технического творчества [86].
Системный анализ как средство исследования сложных проблем был впервые разработан в США в 1948 г. для оптимизации задач военного управления [95]. В дальнейшем тематика исследований систем значительно расширилась. В 50-х годах системный анализ был применен при исследовании хозяйственных проблем американских городов, а с середины 60-х — в федеральных ведомствах США, в деловой, социальной и других сферах. Затем системный анализ начали использовать и в других странах: Англии, Франции, Японии и пр. [2, 66].
Ведущие зарубежные ученые в области системного анализа: Р. Ама-ра, Д. Герц, Э. Квейд, М. Д. Месарович, Ч. Д. Хич, Р. Акоф, Л. фон Берта-ланфи, К. Чен, Д. Медоуз и др. [47].
В СССР системный анализ получил распространение в 50-х годах. Сферой его применения стали радиоэлектроника, автоматика, средства вычислительной техники, информационные системы, автоматизированные системы управления, системы связи и др. Начиная с 60-х годов в стране издается ежегодник "Системные исследования", где рассматриваются основные методологические проблемы системного анализа. Большой вклад в развитие проблем системного анализа и практики его применения внесли отечественные ученые А. Г. Аганбегян, Л. В. Канторович, Д. М. Гвишиани, С. В. Емельянов, Н. Н. Моисеев, Г. С. Поспелов, Л. Н. Сумароков, Г. В. Шорин, В. М. Глушков, Е. П. Голубков, Ю. И. Черняк, В. Н. Садовский, В. В. Дружинин, А. А. Ляпунов, И. В. Блауберг, А. И. Уемов и многие другие [66].
В настоящее время системный анализ широко используется при принятии решений в теоретических и прикладных исследованиях и разработках, в различных областях человеческой деятельности: в науке, технике, экономике, биологии, медицине, истории, политике, военном деле и др.
Важнейшие принципы системного анализа заключаются в следующем: 1) процесс принятия решений должен начинаться с выявления и чет кого формулирования конечных целей, а также критериев, по которым может оцениваться их достижение; 2) необходимо рассматривать всю проблему как целое, т.е. как единую систему, и выявлять все последствия и взаимосвязи каждого частного реше ния; 3) необходимы выявление и анализ возможных альтернативных путей достижения цели; 4) цели отдельных подсистем не должны вступать в конфликт с це лями всей системы.
Практическая ценность и эффективность системного анализа обусловливаются возможностью достаточно строго рассматривать слабо структурированные, имеющие большую долю неопределенности ситуации.
В научно-технической литературе определилось два направления в толковании сущности системного анализа, его отличительных особенностей и границ применения [2].
1. Делается упор на математический аппарат, и под системным анализом подразумевается исследование, задача которого состоит в том, чтобы количественно определить наилучшую стратегию управления, исходя из математического критерия оптимальности. Основа такого исследования - в описании сложной системы с помощью формальных средств (диаграмм, сетей, математических уравнений).
2. Делается упор на логику системного анализа и подчеркивается неразрывная связь его с процессом принятия решений - выбором определенного образа или курса действия из нескольких возможных альтернативных вариантов.
Логический системный анализ рассматривается как методология уяснения и упорядочения (структуризации) проблемы, которую предстоит решить с применением или без применения математики и ЭВМ. При этом в понятие структуризации вкладывается, с одной стороны, выяснение реальных целей самой системы, альтернативных путей достижения этих целей и взаимосвязей между компонентами в процессе реализации каждого альтернативного варианта, с другой - углубленное понимание внешних условий, в которых возникла проблема, а отсюда - последствий и границ осуществления того или иного решения.
Определение ограничений и формирование допущений
Проблема решения многих оптимизационных задач в значительной мере усложняется, когда имеется несколько критериев оптимальности. Исследованию и анализу современных подходов и методов решения задач многокритериального выбора вариантов и проблемы в целом посвящено достаточно большое число публикаций, содержательный анализ которых можно найти в [1, 6, 7, 28, 46, 51, 52, 60, 67, 68, 71, 81, 101, 108, 116, 117, 119, 120]. Среди них основными, наиболее используемыми, являются: аксиоматический подход, предполагающий справедливость ряда аксиом о системе предпочтений лица, принимающего решения (ЛПР); эвристический подход, основывающийся на некоторых соображениях о системе предпочтений лица, принимающего решения, а не на четко сформулированных допущениях.
Разные методы принятия решений в рамках данных подходов отличаются видом получаемой от ЛПР информации и способом перехода от сравнения вариантов по отдельным критериям к выбору по векторному критерию.
Аксиоматический подход лежит в основе прескриптивной теории полезности, в которой рассматриваются различные наборы аксиом, характеризующих систему предпочтений ЛПР и позволяющих доказать существование скалярной функции полезности (аддитивной, мультилинейной и др.), определенной на множестве векторных оценок и обладающей измерительными свойствами [40, 61,91]. Широкое распространение в рамках данного подхода получили также методы рационального выбора, использующие для описания предпочтений язык функций выбора [56]. Иллюстрацией аксиоматического подхода могут служить работы [39, 89, 90]. В [89] приводится обзор исследований различных аспектов проблемы нахождения значений функции полез- ности, удовлетворяющих аксиомам фон Неймана и Моргенштерна.
В эвристическом подходе можно выделить прямые методы и методы, в которых постулируется форма функциональной зависимости, а параметры вычисляются с использованием экспертной информации.
В прямых методах принцип оптимальности формируется в явном виде, позволяя непосредственно выражать цель векторной оптимизации в виде функции частных критериев. Известны несколько принципов оптимальности [19, 49, 69]: принцип гарантированного уровня или максимина, принцип квазиравенства частных критериев, принцип абсолютной уступки, принцип относительной уступки, лексикографический метод, принцип выделения главного критерия, принцип последовательной уступки и др.
При использовании прямых методов к ЛПР предъявляются слишком жесткие требования. Человек далеко не всегда в состоянии сформулировать явно принцип оптимальности, соответствующий его предпочтениям.
В [49] приводятся методы, в которых форма зависимости частных критериев постулируется, а ее параметры либо непосредственно назначаются ЛПР, либо определяются путем обработки экспертной информации. Наиболее употребительными являются метод взвешенных сумм и мультипликативный метод [23, 24, 29, 31].
В этих методах выбор той или иной формы, как правило, ничем не оправдывается, кроме как простотой получения решения. Но даже эта простота относительна. В [98], например, отмечается, что метод последовательного сравнения для определения весовых коэффициентов при его экспериментальном использовании оказался настолько трудоемким для усвоения его экспертами и занял так много времени, что в дальнейшем от него пришлось отказаться.
Для решения задач многокритериального выбора эффективных вариантов многие перечисленные методы следует признать малоперспективными по следующим причинам.
1. При использовании лексикографических методов отношение жесткого приоритета между некоторыми показателями может привести к неоправданным решениям. Например, отношение приоритета между стоимостью оборудования и его надежностью приведет либо к недопустимой стоимости, либо к неоправданно малой надежности.
2. Лексикографический метод и методы уступок требуют достаточно точного решения однокритериальных оптимизационных задач, что не всегда возможно из-за сложной топологической структуры множества допустимых решений и сложного поведения критериев.
3. Многие прямые методы оптимизации, как показывают экспериментальные и теоретические исследования, имеют весьма медленную сходимость [52, 92, 93, 95].
4. При использовании метода взвешенных сумм основной проблемой является получение информации, позволяющей определить веса критериев в свертках.
Таким образом, к основным недостаткам, не позволяющим в полной мере применять эти методы к задачам многокритериального выбора решений, следует отнести: необходимость решения очень большого числа одно-критериальных задач оптимизации, которое сравнимо с числом эффективных вариантов, сильно растущим с ростом количества критериев [40, 58] и отсутствие эффективных быстродействующих методов однокритериальной оптимизации.
Выбор метода решения многокритериальной задачи поиска эффективных путей на графе общего вида
Как было отмечено в главе 1, общая постановка задачи развозки предполагает изначально неизвестными эффективные маршруты, связывающие точки развоза груза. Определить эти маршруты можно с помощью алгоритма поиска набора эффективных путей на графе общего вида при векторном критерии качества.
Как известно, при решении скалярной задачи поиска оптимальной последовательности обхода вершин, например, задачи коммивояжера, на входе соответствующего алгоритма должна быть матрица со значениями кратчайших расстояний между всеми парами вершин графа. Подобная матрица получается путем выполнения одного из алгоритмов поиска оптимальных путей между парами вершин в графе. Существует много модификаций и методов решения этой задачи, зависящих от свойств графа (ориентированный или неориентированный, есть ли в нем контуры и т.д.), так и от свойств весов (неотрицательные или произвольные и т.д.). Одной из популярных является задача поиска кратчайших путей между всеми парами вершин. Для ее решения найден весьма эффективный алгоритм, созданный Уоршаллом и Флой-дом [53, 103], причем он применим к графам общего вида, содержащим, например, циклы.
При наличии нескольких критериев эффективности задача существенно усложняется. Как было сказано в главе 1, наиболее эффективным способом решения задачи многокритериальной оптимизации является двухэтапная схема. На первом этапе с помощью какой-нибудь из априорных мажоритарных схем отсеиваются заведомо «плохие» варианты и строится множество неулучшаемых оценок, т.е. недоминируемых в смысле соответствующего бинарного отношения. На втором этапе применяются неформальные процедуры, использующие информацию, полученную от экспертов.
Одним из наиболее популярных, прежде всего в силу своей простоты, способов решения задачи первого этапа является применение алгоритма линейной свертки критериев (АЛСК), т.е. метод оптимизации свертки вида: где q\ — критерий оптимальности, Я/ — вес г-го критерия. Доказано [70], что посредством перебора возможных значений Я/ и оптимизации полученного обобщенного критерия можно получить набор Парето-оптимальных решений.
Однако, исследования [45] показали, что для многих задач дискретной оптимизации подобный подход не позволяет найти все эффективные решения. Этот факт обусловлен, прежде всего, нарушением в большинстве задач условия теоремы Карлина [37] о выпуклости области допустимых оценок.
Известен векторный алгоритм Форда-Беллмана [11, 16], позволяющий найти в графе общего вида все неулучшаемые пути от фиксированной вершины s до всех остальных вершин. Условия его применения достаточно просты. 1. В графе пара вершин может соединяться не более чем одной дугой. 2. Векторный вес любого контура доминируется нулевым вектором (иными словами, в графе нет контуров с отрицательными весами). Этот алгоритм удобно представить на неформальной версии языка PASCAL:
Здесь A[i,j] — векторный вес ребра, соединяющего г-ю иу-ю вершины графа; Щ.и Л - набор Парето-оптимальных весов путей, соединяющих /-ю и у-ю вершины графа; CPAR(») - функция выбора Паретовских альтернатив на данном предъявлении; ITpedw[v] — список вершин графа, предшествующих вершине V.
Вычислительная сложность алгоритма - 0(n L ), где п - число вершин графа, L = max D[i, j] - верхняя оценка мощности множества Эффекту тивных путей, ведущих к фиксированной вершине. Его л-кратное применение для всех 5 = 1,...п позволяет найти эффективные пути между всеми парами вершин. Вычислительная сложность алгоритма в этом случае — 4 2 0(n -L ). При условии, что нас интересует пути не между всеми парами, а только пути вида (s-»v), где self, VGF, UczV — множество выделенных вер 3 2 шин (ТТ), вычислительную сложность можно оценить как 0{h-n -L ), где
Очевидно, что этот алгоритм подходит для решения задачи выбора оптимальных маршрутов при условии приемлемости вычислительной сложности. Однако, известно, что в скалярной задаче поиска оптимальных путей между всеми парами, или парами из некоторого выделенного множества вершин графа скалярный вариант алгоритма Флойда-Уоршалла более экономичен, чем такой же алгоритм Форда-Беллмана.
Перебор вариантов порядка следования ТС по маршруту
Дано: множество, содержащее т различных типов элементов: А = {а\, а\, ..., а\, Z2,... #2 ат- ---- ат}- (ТС в заданной комплектации) и количест ва щ 0 элементов каждого типа, ]Г щ = N. »=1 Требуется найти все упорядоченные //-выборки из элементов множества . Напомним необходимые сведения из комбинаторики. -«-множество — множество из п различных элементов: - {п) - множество — множество, содержащее п различных типов эле ментов: - г - выборка множества — совокупность из г элементов данного мно жества (если выборка из и-множества, то повторяющихся элементов нет, ес ли из (и)-множества, то есть повторения). Перестановки с повторениями - упорядоченные и-выборки из (т)-множества {п т). Если некоторые элементы такой выборки совпадают, то могут существовать неразличимые (совпадающие) перестановки. Обозначим rij — количество повторений /-го элемента, у = \,...,т, п. Число таких перестановок: Известна формула, определяющая количество перестановок: Например, в слове "мама" имеется 6 различных перестановок букв. В данном слове есть объекты 2-х типов - "м" и "а". Всего множество содержит 4! 4 элемента. Следовательно, число перестановок равно Р(2,2) = = 6. Дей ствительно, имеем следующие комбинации: "аамм", "мама", "амам", "ммаа", "амма", "маам".
Согласно размерным допущениям п. 2.5, число различных вариантов перестановок невелико - в пределах нескольких десятков. В рассмотренном выше примере число перестановок при различных вариантах использования ТС варьирует от 1 до 6. Например, в варианте № 4 (1, 4, 4) существует 3 перестановки - (1,4, 4); (4, 1, 4); (4, 4, 1). При генерации таких перестановок удобно воспользоваться схемой рекурсивного поиска с возвратом. Обозначим п — количество штук различных ТС в анализируемом варианте комплектации, пО - общее количество штук ТС с учетом их возможного повторения; dop - массив разрешения использованияу -го ТС; первоначально dop\J] равен количеству единицу-го ТС, содержащегося в стеке, соответствующего варианту комплектации ТС; Р - упорядоченный список номеров ТС. Предлагается следующий алгоритм, который назовем Алгоритм упо Варианты комплектации подбираются из условия, что суммарная грузоподъёмность машин должна быть не меньше общей массы заказанных грузов. Если эти две величины равны, то каждую машину надо загружать полностью и её работа заканчивается, когда кузов опустеет. Если же общая грузоподъёмность строго больше суммарной массы грузов, то некоторые машины придётся загружать не полностью. Таким образом, имеется некоторая свобода в определении степени загруженности ТС. Этот факт можно использовать для минимизации максимального времени развозки, чтобы была больше гарантия уложиться в срок.
Способ решения задачи определяется следующим фактором. Фактор 4. Характер перевозимого груза. Выделим следующие варианты. Вариант 1. Насыпной груз - возможно поделить массу заказов в любой пропорции. Данное допущение выполняется весьма редко. Вариант 2. Однородный, мелкогабаритный и его можно делить на мелкие порции. В формальной постановке это допущение можно свести к требованию, что грузоподъёмность ТС и потребности клиентов - целые неотрицательные числа. Числа могут быть отвлечёнными, т.е. отражать кратность грузов каждого заказа. Этот вариант принимается как базовый в нашей задаче. Кратность груза в тестовых задачах выбирается из усредненной массы среднестатистической упаковки товаров общего потребления. Вариант 3. Неоднородный — набор блоков разной массы. Задача с такими условиями представляет большой интерес и не меньшую сложность. В рамках текущей работы мы не будем ее рассматривать. Предположим, что порядок объезда ТТ фиксирован. Известны заказанные грузы и время T[i,j] на переезд от і-й к z+1-й ТТ в этом упорядочении, а также время 2Т0, г] поездки от базы до г-й ТТ. Также известно время 6(/, т), которое потребуется, чтобы в /-й ТТ разгрузить т кг груза. Зная эти величины, можно для любой массы х груза подсчитать номера ТТ, в которые этот груз распределится, а также общее время, которое потребуется чтобы полностью этот груз развезти.
