Логистическое планирование доставки товаров

СОДЕРЖАНИЕ

ВВЕДЕНИЕ3

1. АНАЛИЗ СУЩЕСТВУЮЩИХ ПРОБЛЕМ ТРАНСПОРТНОЙ ЛОГИСТИКИ5

1.1 Понятие транспорта и транспортной логистики 5

1.2 Транспортная экспедиция8

1.3 Основные принципы маршрутизации9

1.4 Задачи маршрутизации транспорта11

1.5 Разновидности ЗМТ13

1.6 Существующий инструментарий  для решения ЗМТ18

1.7 Результаты анализа и постановка  задачи20

2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАСПОРТА В УСЛОВИЯХ ГОРОДСКОЙ ДОРОЖНОЙ СЕТИ21

2.1 Классификация алгоритмов для  решения ЗМТ21

2.2 Генетический алгоритм23

2.2.1 Основной вид генетического  алгоритма23

2.2.2 Применение генетического алгоритма  для задач упорядочивания24

2.2.3 Применение алгоритма для  решения ЗМТ25

2.3 Задача построение планов  доставки для розничной клиентской  сети26

3. МЕТОД РЕШЕНИЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА В УСЛОВИЯХ ГОРОДСКОЙ ДОРОЖНОЙ СЕТИ31

3.1 Упрощение исходного графа  городской дорожній сети31

3.2 Архитектура генетического алгоритма32

3.3 Сравнительные результаты и  эффективность похода35

4. ВЫБОР ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ И ПОСТРОЕНИЕ БД36

4.1 Обоснование выбора используемого  инструментального средства......36

4.1.1 Java36

4.1.2 MySql37

4.1.3 GoogleMaps API37

4.2 Создание базы данных38

5  ТЕСТОВЫЙ ЗАПУСК ПРИЛОЖЕНИЯ40

5.1  Руководство  пользователя40

6   ЭКОНОМИЧЕСКАЯ ЧАСТЬ42

6.1 Описание изделия42

6.2  Расчет себестоимости и цены программного продукта42

6.3  Перечни работ для создания программного продукта42

ВЫВОДЫ ПО РАЗДЕЛУ45

7  ОХРАНА ТРУДА. 47

7.1 Выявление и анализ опасных и вредных производственных факторов, действующих в рабочей зоне проектируемого объекта47

7.2 Разработка мероприятий по предотвращению или ослаблению возможного воздействия опасных и вредных производственных факторов на работающих48

7.3 Расчет системы жизнеобеспечения48

ВЫВОДЫ ПО РАЗДЕЛУ51

ВЫВОДЫ52

ПЕРЕЧЕНЬ ССЫЛОК53

ПРИЛОЖЕНИЕ А55

ПРИЛОЖЕНИЕ Б65

ВВЕДЕНИЕ

Актуальность темы исследования.

Одним из способов экономии ресурсов при транспортировке грузов является применение систем поддержки  принятия решений в области транспортной логистики. Разработка программных  пакетов, решающих задачи этой отрасли, требует проведения серьёзных научных  исследований с целью получения  эффективных алгоритмов, пригодных  для применения в повседневной практике.

Одной из ключевых функций  систем поддержки принятия решений  в области транспортной логистики  является возможность расчёта и  построения эффективных с точки  зрения стоимости объезда маршрутов  различного назначения на транспортной сети.

Математическая формулировка этой задачи широко известна как задача маршрутизации транспорта (ЗМТ). Существует ряд разновидностей ЗМТ различными дополнительными условиями, позволяющими учитывать грузоподъёмность транспортных средств и другие ограничения  для более полного представления  деталей реальной действительности. ЗМТ является обобщением известной  задачи коммивояжёра (ЗК) на случай построения сразу нескольких замкнутых маршрутов, проходящих через некоторую общую  вершину, называемую депо. ЗМТ и ЗК принадлежат к классу задач дискретной оптимизации и являются NP-трудными. Не существует методов нахождения их точных решений и проверки оптимальности  приближённых за полиномиальное время. Известен точный алгоритм решения ЗМТ  на основе метода ветвей и границ, но в силу чрезмерно быстрого роста  времени вычислений его невозможно применять для задач с более  чем 25–30 вершинами.

С середины 1990-х годов исследования сосредоточились в направлении  так называемых метаэвристик. Название метаэвристик указывает на то, что  они не являются законченными эвристиками, готовыми для применения, а только представляют собой некоторый метод  для построения законченной эвристики  для конкретной задачи. Большинство  из них основаны на наблюдениях за явлениями живой и неживой природы. Важной их особенностью является способность к преодолению точки локального минимума для продолжения поиска, поэтому потенциально они способны находить более качественные решения по сравнению с классическими эвристиками. Наибольший интерес вызывают следующие методы: поиск с исключениями моделируемый и детерминированный отжиг, алгоритм на основе муравьиных колоний и нейронные сети. В последние десять лет исследования уклонились в основном в сторону обработки сложных видов ограничений.

В настоящее время не существует формализированного способа получения  конкретных алгоритмов из метаэвристик, необходимого для автоматизации  их применения в программных пакетах. Использование эмпирических формул не гарантирует получения наилучшего значения параметров, подходящего для обработки некоторого конкретного набора входных данных. Длительные вычисления в ходе работы метаэвристик также усложняют ситуацию. Поиск алгоритмов, дающих достаточно качественные решения, но в то же время свободных от влияния управляющих параметров и при этом быстрых, способных за разумное время находить маршруты для 100 и более вершин, является актуальной задачей.

Цель и задачи исследования. Целью дипломной работы бакалавра является повышение эффективности поиска оптимальных маршрутов и решение задачи маршрутизации транспорта с ограничением по грузоподъемности.

Для достижения поставленной цели были решены следующие задачи:

1. провести анализ методов и подходов к решению задач маршрутизации транспорта;
2. разработать или модифицировать существующий алгоритм решения задачи маршрутизации транспорта с ограничение по грузоподъемности;
3. разработать программный продукт, способный находить и оптимизировать маршруты доставки для 100 и более клиентов;

Объектом исследования является городская дорожная сеть города Харьков.

Предметом исследования являются методы и подходы к решению задач маршрутизации транспорта.

Практическое значение полученных результатов.

Научно-технический эффект состоит в разработке алгоритма, приспособленного к условиям городской дорожной сети. Экономический эффект состоит в рациональном распределении транспорта, обеспечивающего доставку товаров.

Запланированы следующие  результаты:

1. проведение анализа методов и подходов к решению задач маршрутизации транспорта;
2. разработка алгоритма приспособленного к условия городской транспортной сети;
3. разработка программного продукта, способного прокладывать и оптимизировать маршруты доставки для 100 и более клиентов.

Структура и объем дипломной работы бакалавра. Дипломная работа бакалавра состоит из введения, 7 разделов, заключения и приложений. Полный объем выпускной работы бакалавра составляет 70 страницы, в том числе: 15 рисунков по тексту; 4 таблицы по тексту; 2 приложения на 19 страницах; список использованной литературы с 30 наименованиями на 2 страницах.

1. АНАЛИЗ СУЩЕСТВУЮЩИХ ПРОБЛЕМ ТРАНСПОРТНОЙ ЛОГИСТИКИ

1. Понятие транспорта и транспортной логистики

Транспорт – это отрасль  материального производства, осуществляющая перевозки людей и грузов. В  структуре общественного производства транспорт относится к сфере  производства материальных услуг. Транспорт  как составная часть более  крупной системы, т.е. логистической  цепи, привел к необходимости рассматривать  его в разных аспектах. С точки  зрения изучения эффективности работы отдельных видов транспорта, интерес представляют перевозки грузов между пунктами отправления и назначения на каждом из них. Однако с позиции организации перевозок целесообразно анализировать весь процесс перевозки в целом от двери грузоотправителя до двери грузополучателя. Если же учитывать интересы клиентуры, то здесь необходимо принимать в расчет не только перевозку на магистральных видах транспорта, но и обработку, хранение, упаковку и распаковку, подачу материалов к станкам в цехе и все связанные с этим процессы информации, сопровождающие материальный поток. Такой подход способствует оптимальному выбору транспортных услуг, ибо качество перевозок, как правило, в большей мере отражается на общих расходах, чем себестоимость перевозок.

С точки зрения специализации  и кооперирования производства, изучение транспорта нельзя ограничивать сферой отдельных материально-технических  связей. Он должен рассматриваться  во всей системе материально-технического снабжения – от первичного поставщика до конечного потребителя, включая  промежуточные этапы.

Современная логистика помогает рационально и эффективно управлять  движением материального потока в различных сферах грузоперевозок. Кроме того, она упрощает общий  процесс прохождения материального  потока всех возможных стадий – от источника первичного сырья до получения товара потребителем.

Ни для кого не секрет, что стоимость грузоперевозок во многом зависит от выбранного маршрута при перевозке груза. Бывают случаи, когда транспортные расходы, например стоимость топлива, равняется половине общей стоимость грузоперевозки. Сократить расходы на перевозку, не потратить лишнее время и доставить  максимально возможный объем  груза, поможет предварительный  выбор оптимального пути транспортной доставки.

Расчет маршрута перевозки  груза может занять не одни сутки, хотя некоторые перевозчики придерживаются мнения, что наилучший выбор пути определяется автоматически, когда  машина уже выезжает с грузом на маршрут. Данное мнение ошибочно, недаром  в транспортной логистике присутствует направление – «маршрутизация», непосредственно занимающаяся разработкой и расчетом маршрута движения транспорта при доставке груза.

Если же вы отправляете  грузы на небольшие расстояния, и  не чаще нескольких раз в месяц, само собой маршрут перевозки груза  можете разработать самостоятельно. Если вам потребуется доставлять различные грузы, ежедневно в  десятки мест, то в данном случае, помощь профессионалов из отдела маршрутизации  поможет вам не только скорее довести  груз, но и сделать его транспортировку  намного выгоднее. Именно от организации  и расчета маршрута грузоперевозки зависит её успех.

Транспортная логистика – это перемещение требуемого количества товара в нужную точку, оптимальным маршрутом за требуемое время и с наименьшими издержками. Затраты на создание любого товара складываются из себестоимости изготовления и издержек на выполнение всех работ от момента закупки материалов до момента покупки товара конечным потребителем. Большую часть стоимости составляют наценки каждого звена в цепи производитель – конечный покупатель. Движение материального потока от первичного источника сырья до конечного потребления также требует затрат, которые могут доходить до 50 % от общей суммы затрат на логистику [1].

Транспорт представляют как  систему, состоящую из двух подсистем: транспорт, предназначенный для  общего пользования, и транспорт  необщего пользования.

Транспорт общего пользования – отрасль народного хозяйства, которая обслуживает сферу обращения и население. Этот вид транспорта часто называют магистральным (магистраль – основная, главная линия в какой – либо системе, в данном случае – в системе путей сообщения). Понятие транспорта общего пользования охватывает городской, железнодорожный, водный (морской и речной), автомобильный и воздушный, а также трубопроводный транспорт.

Транспорт необщего пользования – внутрипроизводственный транспорт, а также транспортные средства всех видов, принадлежащие нетранспортным предприятиям; является, как правило, составной частью каких – либо производственных систем.

Транспорт участвует во множестве технологических процессов, выполняя задачи логистической системы, и существует как достаточно самостоятельная транспортная область логистики, требующая многоаспектной согласованности между участниками транспортного процесса. [2]

Таким образом, к задачам, решение которых усиливает согласованность  действий непосредственных участников транспортного процесса, относят:

• обеспечение технического соответствия участников транспортного процесса;
• согласование экономических интересов участников транспортного процесса;
• использование единых систем планирования.

Наличие единого оператора  сквозного перевозочного процесса, осуществляющего единую функцию  управления сквозным материальным потоком, создает возможность эффективно проектировать его движение и  добиваться заданных параметров на выходе.

При организации смешанной  перевозки логистическая система  предполагает [3]:

1. использование двух и более видов транспорта;
2. наличие единого оператора процесса перевозки;
3. единый транспортный документ;
4. единую тарифную ставку;
5. последовательно-центральную схему взаимодействия участников;
6. единую и высокую ответственность за груз;

Результат использования  транспортной логистической системы  – высокая вероятность выполнения «шести правил логистики»: нужный груз, в нужном месте, в нужное время, в необходимом количестве, необходимого качества, с минимальными затратами.

Обеспечение технической  и технологической сопряженности  в транспортной логистике требует  согласования экономических интересов  участников, а также использования единых систем планирования. Техническая сопряженность в транспортном комплексе означает согласованность параметров транспортных средств как внутри отдельных видов, так и в межвидовом разрезе. Эта согласованность позволяет применять модальные перевозки, работать с контейнерами и грузовыми пакетами. 
Технологическая сопряженность предполагает применение единой технологии транспортировки, прямые перегрузки, бесперегрузочное сообщение. 
Совместное планирование коммерческой деятельности участников логистической системы означает разработку и применение единых планов графиков.

К задачам, решаемым транспортной логистикой, специалисты относят [4]:

• создание транспортных систем, в том числе создание транспортных коридоров и транспортных цепей;
• обеспечение технологического единства транспортно-складского процесса;
• определение рационального маршрута доставки груза;
• выбор типа и вида транспортного средства и др.

 В настоящее время, задачи транспортной логистики ежедневно решаются транспортно-экспедиторскими организациями.  

2. Транспортная экспедиция

Транспортная экспедиция – это оказание услуг грузоотправителям и грузополучателям (клиентам), и организация доставки грузов  каким-либо видом транспорта. 

Первые экспедиторские организации  были созданы для завоза и вывоза грузов с железнодорожных станций. До 1979 года все грузоотправители и  грузополучатели сами  договаривались с автотранспортными предприятиями для доставки грузов на железнодорожную станцию или со станции. В 1979 году Совет Министров СССР  установил, что только предприятия грузового автотранспорта могут предоставлять транспортно-экспедиторские услуги. Позже был разработан  типовой договор на централизованную перевозку грузов автомобильным транспортом с железнодорожных станций, из морских и речных портов, аэропортов и обратно.  На протяжении многих лет транспортные компании пользовались этим договором.  Но услуги, оказываемые автомобильными предприятиями центровывоза, не были комплексными.

В идеале, транспортная экспедиция подразумевает организацию перевозки  грузов от двери склада грузоотправителя до двери склада грузополучателя, сокращенно «от двери – до двери». При  этом экспедиторское предприятие оказывает  полный комплекс услуг по доставке груза: доставку от склада грузоотправителя на грузовую железнодорожную станцию, погрузку в вагон, оплату железнодорожного тарифа, выгрузку из вагона на станции  назначения и доставку  груза автомобильным транспортом до склада грузополучателя. Руководство грузовыми перевозками и грузовыми станциями на железных дорогах  осуществляют грузовые службы. Первые экспедиторские компании были организованы  именно при грузовых службах, а затем они были преобразованы в государственные унитарные предприятия (ГУП).                       

Краткий перечень транспортно-экспедиционных услуг:

• составление маршрута перевозки груза по поручению клиента при смешанных перевозках (т.е.  при перевозках несколькими видами транспорта, эти перевозки также называются интермодальными). 
• заключение договоров с другими экспедиторами и участниками перевозочного процесса для фрахтования морских и речных судов, самолетов, вагонов и автомобилей;
• оформление транспортных накладных коносаментов и других документов, необходимых для доставки грузов по назначению;
• оплата транспортных тарифов и других платежей и сборов;
• взаимодействие со страховыми компаниями по страхованию грузов, участие в оформлении документов при несохранных перевозках ( т.е. при прибытия грузов с повреждениями, порчей или недостачей);
• выполнение обязанностей таможенного брокера  при перевозках экспортно-импортных  грузов;
• передача грузовладельцам информации о продвижении грузов, розыск грузов;
• организация переадресовки грузов в пути следования;
• получение разрешений и оформление документов на перевозку опасных, крупногабаритных и тяжеловесных грузов.

Это далеко не полный перечень услуг, которые могут быть обусловлены  договором транспортной экспедиции.

В рамках данной работы рассматриваются  методы и алгоритмы решения задач  маршрутизации транспорта, решаемых транспортно-экспедиционными организациями.

3.  Основные принципы маршрутизации

Маршруты в транспортной логистике делятся на 4 типа [5]:

1. Городское  –  в данном случае, транспортное средство перевозит груз только по городу, не выезжая за его пределы (Например, перевозка груза по Харькову);
2. Пригородные – движение транспортного средства, перевозящего груз в точку разгрузки, производится по маршруту в радиусе до 50 километров от точки его загрузки. (К примеру, доставка грузов по Харьковскому району);
3. Междугородние  – это маршрут перевозки груза, пролегающий от одного города к другому, на расстоянии более 50 километров, к данному пункту относятся грузоперевозки по Украине;
4. К международным  – относятся маршруты перевозки груза пересекающие границы соседних государств.

Сложность планирования маршрута при перевозке, напрямую зависит  от типа груза, так например, для перевозки крупногабаритных грузов используют нестандартные маршруты движения. Чаще всего, сложность расчета маршрута грузоперевозки зависит и от длины самого пути. Так же, во время движения транспортного средства в точку разгрузки груза, по ранее распланированному маршруту приходится решать внезапно появляющиеся проблемы. Допустим, при планировании городского маршрута, приходится учитывать количество светофоров возникающих на пути и вероятность возникновения пробок, а при международных перевозках грузов, во время расчета маршрута приходится учитывать наиболее удобные таможенные пункты и пути пересечения границы государств. В таких случаях, потраченное время на доставку груза экономится в расчетах не на сутки, а порой на недели.

Чаще всего, наиболее важным для грузоотправителя является слежение и контроль перевозки груза. Независимо от перевозимого груза, в требования грузоотправителя входит его круглосуточный мониторинг. Несмотря на то, что GPS навигация набрала свою популярность, в Украине еще есть места, где спутниковая связь остается недоступной, именно профессиональное планирование маршрута передвижения транспортного средства поможет вам избежать подобных мест, и позволит быть всегда в курсе  – где на данный момент находится ваш груз.

При благополучном завершении перевозки груза, данный маршрут  чаше всего используется вновь для  регулярных грузоперевозок.

Регулярные маршруты грузоперевозок делятся на три типа: 
Маятниковые маршруты перевозки груза  – когда транспортировки груза производится между определенными пунктами, туда и обратно. [6] Варианты маятникового движения представлены на рисунке 1.1.

Рисунок 1.1  – Варианты маятникового движения

Развозные маршруты перевозки  груза – грузоперевозка проходит по тому же принципу что и маятниковые, но с разгрузкой в нескольких местах по пути следования транспортного средства.

Кольцевые маршруты перевозки  груза – данные маршруты имеют вид замкнутого круга, с разгрузками и загрузками на всем протяжении пути (рисунок 1.2).

Рисунок 1.2 – Кольцевые маршруты перевозки груза

Все представленные маршруты имеют свои особенности, например маятниковые, в данном случае нужно учитывать  обратный путь, который будет груженный, либо пустой, от этого, в конечном счете, зависит прибыльность грузоперевозок. В таких случаях желательно, провести корректировку маршрута, для снижения себестоимости перевозки, либо наоборот, загрузиться у другого поставщика и в конечном счете увеличить конечную прибыль. Именно в данных нюансах разбирается служба логистики, оптимальный вариант маршрута при перевозке груза способствует его успешной доставки, а так же извлечению максимальной выгоды из грузоперевозок.

4. Задачи маршрутизации транспорта

Задачи маршрутизации  транспорта (ЗМТ) – задачи комбинаторной оптимизации, в которых для парка транспортных средств, расположенных в одном или нескольких депо, должен быть определен набор маршрутов до нескольких отдаленных точек – потребителей [7]. Интерес к ЗМТ вызван ее практической значимостью при значительной сложности. Наглядный пример ЗМТ показан на рисунке 1.3.

Рисунок 1.3 – Пример ЗМТ

ЗМТ – хорошо известная задача целочисленного программирования, относящаяся к классу NP-трудных задач, что означает, что вычислительная сложность задачи зависит от размера входных данных экспоненциально.

Для таких задач обычно достаточно искать приближенные решения, которые находятся достаточно быстро и достаточно точны для требуемых  целей. Обычно это достигается разными  эвристическими методами. 

Задачи ЗМТ лежат на пересечении двух хорошо изученных задач. 

Задача коммивояжера (Traveling Salesman Problem, TSP): если грузоподъемность с  каждого транспортного средства принимается бесконечной (точнее, достаточной), то задача ЗМТ сводится к множественной задаче коммивояжера (Multiple Traveling Salesman Problem, MTSP) путем добавления к исходному графу k-1 (где k – количество маршрутов) копий нулевой вершины и ее ребер (между этими копиями ребра отсутствуют). 

Задача об упаковке рюкзака (Bin Packing Problem, BPP): решение данной задачи, по сути, эквивалентно решению задачи ЗМТ при условии, что все расстояния принимаются равными нулю (таким образом, эффективность всех подходящих решений будет одинакова).

Задачи маршрутизации  являются ключевыми в областях транспортных перевозок, перемещения и логистики. Во многих областях рынка доставка товара добавляет к его стоимости  сумму, сравнимую со стоимостью самого товара. Тем не менее, использование  компьютерных методов оптимизации  доставки товара часто выражается в экономии порядка 5–20% от общей его стоимости.

Классический вариант задачи маршрутизации:

Маршрутизация транспорта относится  к комбинаторным задачам, которые  можно представить в виде графа G(V, E):

V = {v0, v1, ..., vn} – множество вершин (v0 – депо, v1..n – потребители); 
E – множество ребер {(vi, vj) | i ≠ j};

C – матрица неотрицательных расстояний (стоимости пути) cij между потребителями;

m – количество машин;

Ri – маршрут i-й машины (i=1..m);

C(Ri) – стоимость маршрута Ri;

qi – объем груза, поставляемый i-му потребителю.

С каждой вершиной Vi ассоциировано  некоторое количество товаров, которые  должны быть доставлены соответствующему потребителю. Задача маршрутизации  состоит в определении такого множества маршрутов m с минимальной  общей стоимостью, чтобы каждая вершина  множества V была посещена только одним  автомобилем только один раз. Кроме  того, все маршруты должны начинаться и заканчиваться в депо (v0).

Решением задачи является:

• Разбиение множества V на подмножества (маршруты); задание порядка обхода на каждом подмножестве (перестановка вершин маршрута).
• Решение является приемлемым, если все маршруты удовлетворяют дополнительным ограничениям задачи.

Целевой функцией является стоимость  решения задачи:

FЗМТ = ∑C(Ri), i = 1..m, где C(Ri) – сумма длин ребер маршрута Ri.

В классическом варианте требуется  найти приемлемое решение с минимальной стоимостью.

5.  Разновидности ЗМТ

Обычно, в реальных задачах  оптимизации возникает множество  дополнительных ограничений и вариаций, наиболее важные из которых перечислены  ниже.

• Capacitated VRP (CVRP): каждое транспортное средство имеет ограниченную и грузоподъемность.
• VRP with Time Windows (VRPTW): каждый заказчик должен быть обслужен в определенное «временное окно».
• Multiple Depot VRP (MDVRP): используются несколько депо для обслуживания клиентов.
• VRP with Pick-Ups and Delivering (VRPPD): клиенты могут возвращать некоторые товары в депо.
• VRP with Backhauls (VRPB): аналогично предыдущей, но возврат начинается только после доставки всех товаров из депо.
• Split Delivery VRP (SDVRP): каждый клиент может обслуживаться одновременно несколькими машинами.
• Periodic VRP (PVRP): доставка может осуществляться в течение нескольких дней.
• Stochastic VRP (SVRP): некоторые компоненты задачи (количество и запросы клиентов, длина пути) могут иметь случайное поведение.
• VRP with Satellite Facilities (VRPSF): существует возможность дозагрузки автомобиля на маршруте. 

1. Маршрутизация с ограничением по грузоподъемности (Capacitated VRP, CVRP).

В задачах  этого типа вводится дополнительное ограничение: объем грузов на каждом маршруте Ri не должен превышать заданной величины Q (одинаковый для всех машин).

Цель: Минимизировать парк машин, необходимых для выполнения задания, а также общее время выполнения задачи.

2. Маршрутизация с ограничением по времени (VRP with Time Windows, VRPTW).

Данная задача подобна ЗМТ с основным дополнительным условием: для выполнения запроса каждого клиента vi существует известный промежуток времени, определенный как интервал [ei,li] – намеченный горизонт.

Рисунок 1.4 – Маршрутизация с ограничением по времени

На рисунке (Рисунок 1.4) представлен типичный вариант решения задачи с ограничением по времени. Для выполнения заказа каждого клиента существует допустимый интервал времени (показан белым цветом), реальный момент выполнения заказа в соответствии с полученным решением отмечен чертой.

Цель: минимизировать количество машин, общие времена пути и ожидания, необходимые для обработки запросов клиентов в назначенные интервалы  времени.

Ограничения: по сравнению  с ЗМТ, в задачах данного типа добавляются следующие условия:

1. решение неприемлемо, если клиент обслуживается после верхней временной границы;
2. машина, прибывшая ранее нижней временной границы, ожидает ее наступления;
3. как вариант, опоздание не влияет на пригодность решения, но добавляет некоторое штрафное значение к целевой функции.

Получив решение VRPTW, кроме всего остального, имеется возможность точнее подобрать время выезда транспорта из депо и тем самым избежать бесполезных простоев.

3. Маршрутизация с несколькими депо (Multiple Depot VRP, MDVRP).

В наличии  может быть несколько депо, которыми обслуживаются потребители. В случае, если потребители сгруппированы  вокруг каждого депо, задача может  быть разбита на несколько независимых. Однако, если потребители и депо расположены в беспорядке, нужно  искать решение для задачи маршрутизации  с множественным депо (MDVRP).

Данная задача требует  распределения потребителей по разным депо. В каждом депо располагается  парк транспорта. Каждая машина выезжает из своего депо, обслуживает потребителей, прикрепленных к данному депо, и затем возвращается обратно.

Цель: минимизировать парк транспорта и общее время пути.

Ограничения: Каждый маршрут  должен удовлетворять стандартным  ограничениям ЗМТ, а также начинаться и заканчиваться в одном и том же депо.