Оптимизация маршрутов автотранспортной доставки продукции компаний

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

Основными условиями задачи являются следующие:

1. Поставщик или дистрибьютор располагает одним или несколькими складами, с которых осуществляется доставка товаров клиентам.

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

3. Складские и транспортные мощности достаточны для выполнения заказов клиентов, то есть, гарантировано отсутствие дефицита.

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

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

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

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

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

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

1. Получение исходной информации.

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

Рисунок 9 - Алгоритм планирования маршрутов автотранспортной доставки мелкопартионных грузов

2. Определение кратчайших расстояний.

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

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

3. Закрепление потребителей за поставщиками (районирование).

При доставке грузов на развозочных (сборных, сборно-развозочных) маршрутах количество обслуживаемых клиентов может исчисляться сотнями или даже тысячами. Возникает необходимость в декомпозиции общей задачи планирования маршрутов автотранспортной доставки на ряд локальных задач, т.е. задач, в которых рассматривается не все множество складов, клиентов (точек доставки) и возможных маршрутов, а только их часть, которую называют - локальная система доставки. Локальная система доставки - это система, в которой клиенты (точки доставки) расположены недалеко друг от друга и их обеспечение осуществляется от одного поставщика (базы, склада, терминала). Районирование позволяет разбить всю обслуживаемую территорию на регионы, районы или сектора и закрепить эти регионы (районы, сектора) за поставщиками. Решаться эта задача может разными методами. В первом приближении из соображений «здравого смысла» разбивают всю обслуживаемую территорию на регионы, причем границы регионов совпадают, как правило, с границами административных районов. Затем каждый регион разбивают на сектора развозки, границы которых совпадают с границами микрорайонов или городских кварталов. Вместе с тем, широкое распространение в настоящее время получили методы кластерного анализа, например, метод k-средних или метод нечетких c-средних, которые также с успехом могут применяться для решения задачи районирования [17].

4. Определение схемы организации перевозок.

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

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

5. Проверка использования схемы «один к одному».

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

Таким образом, если вес заказа приблизительно равен грузоподъемности транспортного средства, либо необходимость соблюдения жестких ограничений по времени доставки заказа конкретного клиента требует применения схемы «один к одному», то планируется маятниковый маршрут. Если заказы клиентов имеют вес значительно меньший грузоподъемности транспортного средства, то используется схема «один ко многим» и планируются развозочные, сборные или сборно-развозочные маршруты.

6. Планирование маршрутов автотранспортной доставки при использовании схемы «один ко многим».

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

Определения критерия эффективности

Безусловно, основным критерием эффективности при решении задачи маршрутизации является минимум транспортных затрат. В качестве дополнительных критериев эффективности (оптимальности) в теории транспортной логистики наиболее часто рассматриваются следующие критерии: максимальна производительность ТС, т/ч; минимальная себестоимость доставки груза, руб./т; минимальное количество ТС, необходимых для освоения планового объема перевозок, ед.; минимальный суммарный пробег ТС, км; минимальная суммарная транспортная работа ТС, т•км; минимальное суммарное время работы ТС на маршрутах, ч; и ряд других.

Очевидно, что при использовании информационных систем для автоматизации планирования автотранспортной доставки выбирать приходится из тех вариантов критериев эффективности, которые предлагаются разработчиками (см. табл. 4). Например, Деловая карта позволяет выбрать один из четырех критериев эффективности, которые необходимо минимизировать: время, длина (пробег), транспортная работа, расход топлива. В связи с этим, возникает проблема выбора наилучшего или наиболее целесообразного в данной ситуации критерия оптимизации, которая является достаточно сложной, поскольку на выбор того или иного критерия влияет ряд факторов. Во-первых, ограничения по времени доставки заказов, которые связаны с требованиями к сохранности грузов, могут приводить к необходимости использования в качестве критерия оптимальности минимальное время. Во-вторых, применяемые транспортные тарифы. Если используются повременные тарифы, то очевидным критерием оптимальности сформированных маршрутов является минимальное время, если используются покилометровые тарифы - минимальный пробег, если используются сдельные тарифы - минимальная транспортная работа. Сложнее определиться с критерием оптимальности в том случае, когда применяются комбинированные или фиксированные тарифы. По нашему мнению, в этом случае целесообразно выполнить многовариантные расчеты с использованием нескольких критериев эффективности и на основании анализа полученных результатов выбрать тот критерий, который приводит к минимуму транспортных затрат.

Таблица 4 - Критерии выбора перевозчиков [6]

Наименование критерия (показателя)	Ранг
Надежность времени доставки (транзита)	1
Тарифы (затраты) транспортировки	2
Общее время доставки	3
Готовность перевозчика к переговорам об изменении тарифа	4
Финансовая стабильность перевозчика	5
Наличие дополнительного оборудования (по грузопереработке)	6
Частота (периодичность) отправок	7
Наличие дополнительных услуг по комплектации и доставке груза	8
Потери и хищения груза (сохранность груза)	9
Экспедирование отправок	10
Квалификация персонала	11
Отслеживание отправок	12
Готовность перевозчика к переговорам об изменении сервиса	13
Гибкость схем маршрутизации перевозок	14
Сервис на линии	15
Процедура заявки (заказа) транспортировки	16
Качество организации продаж транспортных услуг	17
Наличие специального оборудования	18

Выбор метода решения.

В общем случае под выбором метода решения понимается выбор формального алгоритма нахождения рациональных развозочно-сборных маршрутов. Расчет маршрутов доставки грузов при мелкопартионных перевозках включает в себя два этапа: во-первых, решение задачи о распределении заказов по ТС (набор пунктов в маршрут) и, во-вторых, решение задачи коммивояжера (определение оптимальной последовательности объезда точек в маршрутах). Первая из указанных задач решается, как правило, с помощью приближенных методов, в частности, в Деловой карте реализованы четыре упомянутых выше алгоритма предварительной раскладки заказов по транспортным средствам: «Начинать с отдаленных точек», «Выбирать попутные заказы», «Определять дальние направления» и «Искать самые выгодные совмещения». Поскольку не ясно, чем один алгоритм отличается от другого, по нашему мнению, и в этом случае целесообразно выполнить многовариантные расчеты с использованием всех четырех алгоритмов и на основании анализа полученных результатов выбрать тот алгоритм, который приводит к минимуму транспортных затрат.

Расчет маршрутов доставки грузов

Расчет маршрутов доставки грузов, как указано выше, включает в себя: решение задачи о распределении заказов по ТС и решение задачи коммивояжера. Обе эти задачи автоматизированы в информационных системах Деловая карта, TopLogistic, ANTOR LogisticsMaster и др. Например, в Деловой карте расчет маршрутов доставки грузов включает следующие этапы:

1) подготовка данных (заполнение таблиц заказов, транспорта и пунктов);

2) установка параметров расчета маршрутов:

· определение критерия оптимизации (см. п. 6.1);

· определения метода предварительной раскладки заказов (см. п. 6.2);

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

· задание параметров и способа сохранения результатов расчета маршрутов;

3) выполнение расчета маршрутов и представление результатов.

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

Планирование маршрутов автотранспортной доставки при использовании схемы «один к одному».

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

Определения критерия эффективности (см. п. 6.1).

Выбор метода решения (см. п. 6.2).

Расчет маршрутов доставки грузов.

Расчет маршрутов доставки грузов в данном случае включает в себя:

· решение задачи выбора ТС (назначение ТС на обслуживание конкретного заказа);

· решение задачи выбора кратчайшего пути.

В случае расчета маршрутов доставки грузов с помощью Деловой карты последовательность решения задачи соответствует той, которая рассмотрена выше (см. п. 6.3).

Проверка соблюдения ограничений.

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

Корректировка маршрута.

В простейшем случае корректировка маршрута заключается в том, что нераспределенные заказы «вручную» добавляются к одному или нескольким существующим маршрутам. Например, если расчет маршрутов доставки осуществляется средствами Деловой карты, то пользователь должен выбрать в качестве способа предварительной раскладки заказов по транспортным средствам вариант «Восстановить по номерам точек». Затем, в таблице заказов необходимо для всех неопределенных заказов назначить транспортное средство (из тех, которые уже используются) и определить последовательность операций по погрузке и разгрузке каждого заказа. Если нельзя добавить нераспределенные заказы ни к одному из спланированных маршрутов по причине того, что не соблюдаются ограничения по грузоподъемности, времени доставки, максимальной длине и продолжительности маршрута и прочие, то необходимо для обслуживания этих заказов назначить не используемое транспортное средство из таблицы транспорта.

Ситуация с нераспределенными заказами может быть более сложной и на первый взгляд неочевидной. Например, конкретный заказ не может быть обслужен ни одним из имеющихся транспортных средств (не соответствует грузоподъемности или типу ТС) или доставка конкретного заказа в указанную точку невозможна по причине отсутствия дороги, либо несоответствия дороги категории транспортного средства и по др. причинам. В этом случае необходимо корректировать не сам маршрут, а исходные данные и ограничения, используемые при расчете маршрутов доставки грузов, например, может потребоваться ТС большей грузоподъемности. В общем случае может измениться ситуация транспортного обслуживания, например, часть нераспределенных заказов на развозочно-сборных маршрутах может быть обслужена маятниковыми маршрутами. На рис. 10 эта ситуация отражена линией со стрелкой, которая связывает блок 9 с блоком 4 рассматриваемого алгоритма.

Вывод отчетов и документов.

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

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

В представленном условном примере ООО «НТК» имеет преимущество перед альтернативными транспортными компаниями по критериям «Надежность времени доставки» и «Готовность перевозчика к переговорам об изменении тарифа», но уступает им по критерию «Тариф за перевозку». Тем не менее, эта компания, получившая наивысший суммарный рейтинг - 24,35, имеет по совокупности пяти критериев преимущество над конкурентами.

Представленное в первом разделе отчета исследование позволяет сделать следующие выводы, обобщения и предложения.

1. Группа компаний «Лактика», являющаяся крупным производителем и поставщиком молочной продукции на российский рынок, реализует свою продукцию в регионе Санкт-Петербурга и Ленинградской области через свой филиал в Санкт-Петербурге со склада, расположенного по адресу: 5 Предпортовый проезд, д. 22.

2. ГК «Лактика» имеет в регионе Санкт-Петербурга и Ленинградской области обширную клиентскую сеть, представленную в Приложении 1 и включающую более 500 точек доставки. Всех клиентов ГК «Лактика» в зависимости от статуса клиента можно разделить на две группы: привилегированные клиенты, к которым относятся гипермаркеты торговых сетей, и обычные клиенты, к которым относятся все остальные заказчики продукции ГК «Лактика».

3. Анализ маршрутов доставки, выполненный как по несетевым клиентам, так и по гипермаркетам, показывает существенную неравномерность объемов поставок по дням недели, что приводит к неравномерной загрузке транспортных средств. Средняя загрузка ТС на маршрутах, обслуживающих несетевых клиентов, колеблется от 819,76 кг до 1028,5 кг, а на маршрутах, обслуживающих гипермаркеты, - от 491,71 кг до 1137,5 кг. Учитывая, что грузоподъемность ТС составляет 1500 кг, коэффициент использования грузоподъемности г на маршрутах, обслуживающих несетевых клиентов, колеблется от 0,55 до 0,75 , а на маршрутах, обслуживающих гипермаркеты, - от 0,33 до 0,76. Даже с учетом того, что перевозятся грузы 2-го класса, коэффициент использования грузоподъемности г должен приближаться к величине 0,8. Таким образом, загрузку ТС на маршрутах следует признать неудовлетворительной. Вследствие низкой загрузки на маршрутах работает избыточное количество автомобилей и, следовательно, ГК «Лактика» несет неоправданно высокие транспортные затраты.

4. Выявлено, что существующая в Санкт-Петербургском филиале ГК «Лактика» практика анализа эффективности маршрутов автотранспортной доставки носит довольно примитивный характер и нуждается в совершенствовании. По нашему мнению, для того, чтобы дифференцировать факторы, влияющие на эффективность маршрутов автотранспортной доставки и стимулировать ответственность логистов, осуществляющих планирование этих маршрутов, необходимо разработать систему ключевых показателей логистической деятельности. Предлагается взять за основу для разработки показателей логистической деятельности в Санкт-Петербургском филиале ГК «Лактика» используемую в Московском филиале компании ЭКЗ «Лебедянский» систему KPI для диспетчеров.

3.2 Разработка маршрутов автотранспортной доставки продукции группы компаний «Лактика» в Санкт-Петербурге и Ленинградской области с использованием программы «Деловая карта»

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

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

Таблица заказов включает следующие поля:

«Номер заказа» - строка, идентифицирующая заказ.

«Приоритет» - числовое значение, при расчете доставки заказов сначала по транспортным средствам распределяются заказы с наибольшим приоритетом. Не заданный приоритет равносилен = 0.

«Откуда» - место загрузки заказа (его описание, например, «склад 1» - по нему определяется адрес и координаты. В случае формирования заказов из клиентской базы - название или другие атрибута клиента. Поле в расчетах не участвует, служит для упрощения подготовки данных.

«Адрес загрузки» - место загрузки, если ввод данных не определяется полем «откуда», то может быть использовано для задания координат по адресу. Поле в расчетах не участвует, служит для упрощения подготовки данных.

«Тип машины» - строка, перечисляющая типы машин, пригодные для перевозки данного груза (см. описание таблицы «Транспорт»).

«Вес груза», «Объем груза», «Стоимость» - характеристики заказа, влияющие на количество одновременно перевозимых заказов (см. описание таблицы «Транспорт»).

«Куда», «Адрес разгрузки» - то же, но для места разгрузки.

«Координаты откуда (X, Y)» - географические координаты места загрузки заказа.

«Координаты куда (X, Y)» - географические координаты места разгрузки заказа. транспортный перевозка груз маршрут

«Загрузить после» - дата и/или время, после которого машина должна прибыть к месту загрузки заказа. Если оно не установлено, ограничения снизу на время загрузки нет.

«Загрузить до» - дата и/или время, до которого машина должна прибыть к месту загрузки заказа. Если оно не установлено, ограничения сверху на время загрузки нет. Если не установлено также «Загрузить после», считается, что загрузка заказа может происходить в любое время.

«Разгрузить после», «Разгрузить до» - аналогично предыдущему пункту, но для разгрузки.

«Сопроводительный документ» - информационное поле, в расчетах не используется.

«Продолжительность погрузки», «Продолжительность разгрузки» - в минутах время, необходимое для погрузки и разгрузки данного заказа. Если они не указаны, то эти величины берутся из общих параметров. Задавая время для каждого заказа можно получить более точные временные характеристики маршрута (например, для разгрузки груза в небольшом магазине требуется 20 минут, а для разгрузки в гипермаркете - 40 минут). Вообще, при расчете времени на погрузку и разгрузку необходимо учитывать «Межотраслевые нормы времени на погрузку, разгрузку вагонов, автотранспортных средств и складские работы», утвержденные постановлением Министерством труда и социального развития Российской Федерации от 17.10.2000 №76 [17].

Следующие поля используются для сохранения результата расчета в таблице заказов:

«Время загрузки» - время прибытия в точку загрузки заказа.

«Время разгрузки» - время прибытия в точку разгрузки заказа.

«Номер машины» - номер машины, на которой будет перевозиться заказ.

«Номер точки загрузки» - индекс точки загрузки в общем маршруте для машины.

«Номер точки разгрузки» - индекс точки разгрузки в общем маршруте для машины.

Формат полей «...до» и «...после» по умолчанию устанавливается как короткий формат времени. Если его установить как «дата-время», и то же самое проделать с таблицей транспортных средств («Начало работы» и «Конец работы»), то при расчете маршрутов будет учитываться еще и дата заказа.

На рис. 11 представлен фрагмент сформированной таблицы заказов.

Координаты можно вводить как с помощью выбора пункта или задания адреса, так и непосредственно с карты, с помощью кнопок «Взять точку загрузки с карты» и «Взять точку разгрузки с карты» (самые правые на панели инструментов над таблицей заказов).

Таблица транспорта включает следующие поля:

«Номер», «Описание» - поля, задающие номер и описание транспортного средства, используются как его идентификаторы.

«Грузоподъемность», «Максимальный объем» - определяют количество заказов, которые может перевозить транспортное средство одновременно, т.е. сумма соответствующих характеристик одновременно перевозимых заказов не может превышать эти значения. Если одна или обе характеристики не заданы, то проверка на ее превышение не проводится.

«Максимальная длина маршрута», «Максимальная продолжительность» - ограничения на длину и время маршрута для этого транспортного средства. Если эти величины не указаны, то они берутся из общих параметров

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

Рисунок 11 - Вид таблицы заказов Деловой карты (фрагмент)

«Максимальная стоимость заказов» - величина, также определяющая суммарную характеристику, а не характеристику одновременно перевозимых грузов. За счет этого это поле можно, например, использовать в качестве максимального суммарного веса грузов, перевозимых за один маршрут, вместо использования поля грузоподъемности. В данном случае желательно во избежание путаницы изменить описание поле в Мастере проектов.

«Тип машины» - слово, определяющее тип машины, например, «Открытая», «Лотковая», «Рефрижератор», и т.д. или просто «А», «Б», «В». Соответственно, в заказах указывается тип машины, на котором можно перевозить груз. Если заказ может перевозиться на нескольких типах машин, то их можно перечислить через запятую и/или пробел: «А, Б» - такой заказ попадет только в машины с типом «А» или «Б». Поскольку запятая и пробел используются здесь как разделители, тип машины нужно указывать одним словом. Тип машины не чувствителен к регистру букв. Если в заказе не указан тип машины, считается, что груз может перевозиться на машине любого типа.

«Вес машины» - характеристика, необходимая для минимизации маршрутов по параметру «Длина * Вес» (см. «Параметры»).

«Расход топлива на 100 км» - характеристика, необходимая для минимизации маршрутов по параметру «Расход топлива».

«Коэффициент скорости» - определяет, насколько быстрее движется машина, чем расчетное время при прокладке маршрутов. Необходимо для более точного времени попадания на ту или иную точку маршрута и позволяет выделять более быстрые и более медленные машины. Если не задано, то коэффициент считается равным 1. Коэффициент 2 указывает на то, что машина движется в два раза быстрее, 0.5 - в два раза медленнее.

«Начало работы», «Конец работы» - временные ограничения. Если не задано, то соответствующее ограничение снимается. Так же, как и в случае таблицы заказов, может быть временем или датой-временем (во втором случае придется вводить дату каждый раз при расчете маршрутов на день)

«Использовать» - указывает, использовать машину при расчете доставки или нет (например, если машина на ремонте или без водителя, то при расчете доставки грузов надо поставить в этом поле «Нет» - и она не будет учитываться).

«Исходное положение (Описание)» - служит для удобства ввода начального положения, по описанию автоматически определяются начальные координаты.

«Исходное положение (X, Y)» - начальная точка, в которой находится транспортное средство перед выездом по маршруту (гараж, склад, место жительства водителя и т.д.).

Путь из этой точки в точку загрузки первого заказа учитывается при расчете.

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

«Начало маршрута», «Конец маршрута» - начало и конец маршрута в реальном или в относительном времени, в зависимости от того, задано ли реальное время для точек маршрута или для временных рамок работы транспортного средства.

«Длина маршрута, км», «Продолжительность маршрута, час», «Кол-во заказов» - длина, продолжительность маршрута и количество заказов, обработанных на этом маршруте.

«Расход топлива, л» - расход топлива, вычисленный на основании длины маршрута и среднем расходе топлива на 100 км.

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

«Ширина проезжей части» - величина ширины проезжей части в метрах, ограничивающая использование данной машины. Если поле не заполнено, то берется значение из настроечных параметров.

«Высота проезжей части» - высота высоты проезжей части в метрах, ограничивающая использование данной машины. Если поле не заполнено, то берется значение из настроечных параметров.

«Категория грузового транспорта» - описание категории, обозначающее вес машины в терминах дорожных знаков, т.е. 1 т, 1.5 т, 3.5 т. и т.д. Категория грузового транспорта используется для прокладки маршрутов только по тем улицам и дорогам, для которых разрешено движение данной категории, если не определена необходимость использования страницы маршрутной карты, определяющей пропуска и лицензии или индивидуальный порядок использования машины. Необходимость использования страницы маршрутной карты определяется по содержанию следующего поля.

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

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

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

Рисунок 12 - Вид таблицы транспорта Деловой карты (фрагмент)

Таблица пунктов включает следующие поля:

«Название» - текстовое поле для ввода наименования точки (склад, гараж и т.п.)

«Адрес» - текстовое поле для ввода адреса точки. Если вводится адрес, то привязка точки к карте производится автоматически.

«Долгота», «Широта» - числовые поля в которых при заполнении таблицы формируются координаты точки. Если при заполнении таблицы вводится адрес точки, то соответствующие координаты формируются и заносятся автоматически. Кроме этого могут быть введены явные значения координат или занесены координаты точки, указанной на карте.

«Флаг удаления» - логическое поле, которое при истинном состоянии - «Да», определяет факт того, что запись помечена на удаление, т.е. находится в корзине. При отсутствии поля исключается возможность использования корзины.

На рис. 13 представлен вид таблицы пунктов Деловой карты открытого проекта, содержащую только одну запись.

Рисунок 13 - Вид таблицы пунктов Деловой карты

Окна таблиц заполнения заказов, транспорта и пунктов имеют одинаковые инструменты, обеспечивающие заполнение и редактирование таблиц, управление их видом и документирование. Вид данных таблиц и инструменты их редактирования подробно рассматриваются в руководстве пользователя Деловой карты [6].

Заполнение таблиц осуществляется вручную с использование инструментов «Добавить запись», «Редактировать запись» и «Сохранить запись».

В Деловой карте предусмотрено автоматическое заполнение таблицы заказов с помощью групповых операций и скриптов.

Для задания пунктов заказов «Откуда» и «Куда» предусмотрены групповые операции. Выбрать групповые операции можно соответственно кнопками «Откуда» или «Куда». При щелчке по соответствующей кнопке включается меню для выбора одной из возможных групповых операций. Имя групповой операции в списке над чертой. В меню присутствуют также имена пунктов, введенных в таблице пунктов (список под чертой).

Операция: <Заполнить из выборки клиентов>, обеспечивает формирование записей таблицы Заказов по всем записям таблицы клиентов, отобранным на панели работы с клиентами (вся таблица или выборка по запросам).

Если операция выбрана клавишей «Откуда», то заполняются поля:

Поле таблицы заказов «Откуда» - содержанием поля «Имя клиента» таблицы клиентов;

Поле таблицы заказов «Адрес загрузки», заполняется содержанием полей, составляющих адрес клиента (город, улица, дом, корпус или литера, квартира).

Поля таблицы заказов «Координаты откуда (X)», «Координаты откуда (Y)» - содержанием полей «Координаты X,Y» таблицы клиентов.

Если операция выбрана клавишей «Куда», то заполняются поля:

· поле таблицы заказов «Куда» - содержанием поля «Имя клиента» таблицы клиентов;

· поле таблицы заказов «Адрес разгрузки» - заполняется содержанием полей, составляющих адрес клиента (город, улица, дом, корпус или литера, квартира);

· поля таблицы заказов «Координаты куда (X)», «Координаты куда (Y)» - содержанием полей «Координаты X, Y» таблицы клиентов.

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

Операция <Установить как в текущей записи> обеспечивает заполнение во всех записях таблицы заказов полей «Откуда», «Адрес Загрузки», «Координаты откуда (X)», «Координаты откуда (Y)» или полей «Куда», «Адрес разгрузки», «Координаты куда (X)», «Координаты куда (Y)» (в зависимости от того какой клавишей выбрана операция <Откуда> или <Куда>) информацией из аналогичных полей записи таблицы заказов на которой установлен фокус.

При выборе в меню групповых операций наименования пункта, все записи таблицы заказов в полях «Откуда», «Адрес Загрузки», «Координаты откуда (X)», «Координаты откуда (Y)» или в полях «Куда», «Адрес разгрузки», «Координаты куда (X)», «Координаты куда (Y)» (в зависимости от того какой клавишей выбрана операция <Откуда> или <Куда>) заполняются информацией выбранного пункта. Т.е. когда загрузка всех заказов осуществляется на одном складе, удобно ввести склад в таблицу пунктов, а затем выбрать групповую операцию <Откуда> - <Склад>. В поле «Откуда» всех записей таблицы заказов будет занесено наименование пункта «Склад», в поле «Адрес загрузки» всех записей будет внесен адрес пункта «Склад» из таблицы пунктов, а во все поля «Координата X,Y загрузки» будут внесены координаты пункта «Склад» из таблицы пунктов.

Предусмотрено заполнение таблицы заказов по программам, заданным скриптами. Выполнение программ осуществляется интерпретатором Деловой карты, аналогично программам формирования форм печати и расчета информации по маршрутам. При выборе инструмента «Скрипты» открывается меню со списком имен существующих скриптов (под чертой), которые хранятся в таблице скриптов данного проекта. Выбор скрипта обеспечивает его выполнение и заполнение таблицы заказов. Если таблица заказов уже имеет записи, предлагается предварительно очистить таблицу или дополнить записями, сформированными по выбранному скрипту.

На рис. 14 представлен вид окна «Скрипты для таблицы заказов» включаемое при выборе пункта меню «Редактировать скрипты».

Рисунок 14 - Вид окна «Скрипты для таблицы заказов»

Справа расположены инструменты для выбора и вставки в текст скрипта полей таблицы функций и констант.

Панель выбора обеспечивает выбор текущего скрипта для редактирования. Выбор осуществляется по имени. Выбранный скрипт заносится в редактируемое поле в левой части окна. Например, скрипт с именем setAddress, представленный на рис. 13, предназначен для формирования записи в поле «Адрес разгрузки» таблицы заказов. Сюда заносится полный адрес клиента, которому необходимо доставить заказ. Эти данные переносятся в таблицу заказов из таблицы клиентов Деловой карты.

Установка параметров расчета маршрутов.

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

Панель выбора «Минимизировать» обеспечивает выбор способа минимизации:

Время - маршруты рассчитываются таким образом, чтобы суммарное время всех маршрутов было минимальным.

Длину - суммарная длина всех маршрутов минимальна.

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

Расход топлива - по возможности самые длинные маршруты будут назначаться машинам с наименьшим расходом топлива. При этой установке необходимо заполнения поля «Расход топлива на 100 км» для всех машин.

Панель выбора «Предварительная раскладка» обеспечивает выбор одного из четырех способов предварительного расчета маршрутов. Это алгоритмы, которым в соответствии с их свойствами, присвоены следующие названия - «Начинать с отдаленных точек», «Выбирать попутные заказы», «Определять дальние направления», «Искать самые выгодные совмещения» и «Восстановить по номерам точек». Так как не существует метода точного расчета даже для одной машины, в программе реализовано четыре разных алгоритма предварительной раскладки заказов по машинам и оптимизации порядка их следования, каждый из который может оказаться наиболее эффективным при расчете конкретного класса задач (на это влияет соотношение количества машин и количества заказов, пространственное размещение точек разгрузки относительно точек погрузки). После предварительной раскладки заказов по машинам во всех случаях осуществляется дополнительная оптимизация путем попыток переноса заказов с одной машины на другую.

Установка «Единица измерения веса» в килограммах или тоннах учитывается при предварительной раскладке «Вес*длину».

Далее предусмотрено задание величин следующих параметров:

«Коэффициент скорости» - коэффициент, на который, в общем случае, делится расчетное время передвижения из одной точки маршрута в другую. При расчете движения конкретной машины учитывается так же коэффициент скорости этой машины (т.е. время для конкретной машины = расчетное время / (общий коэффициент * коэффициент для этой машины)). Общий коэффициент позволяет одновременно изменять время сразу для всех машин, в зависимости от времени суток или дня недели, в то время как коэффициент для конкретной машины показывает, насколько она быстрее движется относительно других.

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

«Макс. продолжительность» - маршрут для каждой машины будет занимать не больше времени, чем указано в этом поле. Если пусто - ограничение снимается. На продолжительность маршрута для каждой машины еще влияют «Начало работы», «Конец работы» и «Максимальная продолжительность», если они указаны в таблице транспортных средств для этой машины.

Установки времен «Начало работы» и «Конец работы» является общей и если введена, то используется для тех машин, для которых эти параметры не введены.

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

«Длительность погрузки», «Длительность разгрузки» - для расчета времени маршрута, указывает, какое время машина будет простаивать, пока загружается или разгружается один заказ. Это время включается в общую продолжительность маршрута. Эти времена суммируются, даже если несколько заказов загружаются или разгружаются в одном месте. Время на загрузку/разгрузку не учитывается при проверке времени прибытия и окончания работы машины, т.е. если машина заканчивает работу в 18:00, время разгрузки 10 минут, то последнее время прибытия машины к месту разгрузки - 18:00, а не 17:50. То же касается и продолжительности маршрута. Продолжительность погрузки/разгрузки можно также указать индивидуально для каждого заказа в таблице заказов.

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

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

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

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

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

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

«Многорейсовые маршруты» - установка позволяющая повторные использования освобождающихся машин для доставки не распределенных заказов.

«Интервал между рейсами» используется при многорейсовых маршрутах.

Панель «Сохранение маршрута в таблице транспорта» - предлагает выбор из четырех способов сохранения описания маршрута в таблице транспорта. Если поле, соответствующее описанию маршрута, в таблице отсутствует, то выбор невозможен. (см. раздел Сохранение информации о маршруте в таблице транспортных средств).

Панель «Сохранение маршрутов в файле» предлагает выбор из четырех способов сохранения описания маршрута в файле. Обеспечивается сохранение в текстовом или Dbase файле в соответствие с установками на редактируемой панели «Имя файла для сохранения». Устанавливать папку и имя файла можно через файловое окно, открываемое при щелчке по инструменту «Выбрать файл и тип файла». Тип сохраняемого файла - текстовый или Dbase, определяется установкой расширения в имени файла, соответственно txt или dbf.

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

На рис. 15 представлен вид закладки «Параметры» Деловой карты.

Рисунок 15 - Вид закладки «Параметры» Деловой карты

В случаях, когда все доставляемые заказы требуют задания предельного одинакового времени транспортировки, можно сделать установку в поле «Макс. время транспортировки, мин».

В таблице заказов предусмотрено необязательное поле «Макс. время транспортировки», которое должно быть определено в мастере проектов, и в которое можно ввести время в минутах, для каждого из заказов, для которых это необходимо.

При расчетах доставки заказов, для каждого из заказов время от погрузки до разгрузки не будет превышать время, установленное в общих параметров (если установлено), а для заказов с определенным полем «Макс. время транспортировки» - время введенное в поле.

Выполнение расчета маршрутов и представление результатов.

Производится на закладке «Маршруты» кнопкой «Рассчитать маршруты». В процессе расчета включается индикатор прогресса. Если критерии расчета маршрута не заданы, т.е. в таблице заказов не определены ни весовые, ни объемные характеристики, ни критерии времени доставки, ни приоритеты, а в таблице транспорта не заданы режимы использования транспорта (время начала и конца работы), то расчет маршрутов может занять длительное время. Чем больше критериев задано, т.е. чем более полно сформулированы условия, тем быстрее осуществляется расчет маршрутов.

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

Вид закладки «Маршруты» Деловой карты с результатами расчета представлен на рис. 16.

Предусмотрено три режима представления результатов, переключаемых закладками «Точки маршрута», «Заказы» и «Маршрут». Представление результатов в каждом из вариантов обеспечивается по отношению к машине, на которую установлен фокус (в примере, представленном на рис. 16, - это машина к 451 АС Форд Транзит). Маршрут транспортного средства также отображается на карте.

В верхнем окне закладки «Маршруты» представлен список машин, дополненный информацией о длине маршрутов, продолжительности маршрутов и количестве обслуженных каждой машиной заказов. Справа от данного окна представлены результаты одновременно по всем машинам, для которых рассчитаны маршрута, а также информация о количестве нераспределенных заказов, т.е. заказов, которые в силу накладываемых ограничений остались не распределенными ни на одну из машин или остались нераспределенными в силу нехватки машин.

Рисунок 16 - Вид закладки «Маршруты» с результатами расчета маршрутов

На закладке «Точки маршрута» (см. рис. 15) представлена информация о номера заказов, обслуживаемых на данном маршруте, весе и объеме заказов, времени погрузки и выгрузки, общем объеме и общем весе заказов в транспортном средстве, а также об ошибках в процессе расчета (превышение длины маршрута, времени маршрута или грузоподъемности транспортного средства).

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

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



3.3 Расчет маршрутов по обслуживанию клиентов

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

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

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

Подготовка данных для расчета маршрутов по обслуживанию несетевых клиентов заключается в решении следующих задач:

1) выбор клиентов из базы: построение и сохранение SQL-запроса;

2) формирование таблиц транспорта и пунктов;

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

Выбор клиентов из базы осуществляется путем построение и сохранение SQL-запроса.

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