Задачи маршрутизации транспорта (Vehicle Routing Problems, VRP)¶

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

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

Задачу можно сформулировать следующим образом: используя ограниченное количество машин, доставить товары покупателям. Учитывая, ограничения:

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

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

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

Разновидности VRP¶

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

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

Оформление ветеринарных сертификатов в ГИС Меркурий из 1С Предприятие 7.7¶

• создание входящих ВСД из 1С
• создание исходящих(транспортных) ВСД из 1С
• смена владельца партии без перевозки
• создание производственных ВСД
• инвентаризация продукции на площадках ГИС Меркурий
• групповое создание ВСД, заполненных на основании документов Реализация товаров
• получение ответа о результате создания ВСД (принят или отклонен) с указанием причины отказа.

Операции со справочниками ХозСубъектов и Площадок в ГИС Меркурий

• получение списка площадок и хоз. субъектов
• создание новых ХозСубъектов и Площадок
• Создание связи Площадки и ХозСубъекта в ГИС Меркурий
• Получение GUID по ИНН ХозСубъекта
• Поиск Площадок по названию в пределах региона

Загрузка справочников:

• Партий,
• Продукции,
• Видов продукции,
• Единиц измерений,
• Формы упаковки,
• Стран и Регионов

ВСД = Ветеринарно-сопроводительная документация

описание

Разработчики:
Синявский Филипп

Благодарности:¶

Жуков Дмитрий
Александр Тувин
Горбанев Станислав
Анисимов Михаил mbIkola
Олег Крец
Алексей Диркс ADirks
Дмитрий Донченко
Sergey G. Pentyukhov serpent