Артемьев Эдуард Иосифович

ОПТИМИЗАЦИЯ СХЕМЫ ПЕРЕВОЗОК НА ТЕРРИТОРИЯХ С НЕОДНОРОДНОЙ ПРОПУСКНОЙ СПОСОБНОСТЬЮ

Чебоксары 2011

Содержание
Введение
Глава 1. Постановка задачи поиска оптимальных маршрутов
Глава 2. Формализация задачи
Глава 3. Условие равновесия притоков-оттоков
Глава 4. Оптимизация плана перевозок
Глава 5. Кодирование входных данных в файле изображения
Заключение
Приложение. Результаты работы программы

Введение

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

Эдуард Артемьев.
05.05.2011.
Глава 1
Постановка задачи
об оптимальных схемах доставки

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

Будем считать, что транспортировка продукта осуществляется на некоторой прямоугольной области. В одни точки области осуществляется приток продукта, из других точек осуществляется его отток (рис. 1.1).
Точками притока можно обозначить склады продукции или производящие предприятия, а точками оттока – торговые центры, в которых товар попадает в руки конечного потребителя.
Изначально известны координаты точек притока и оттока продукта. Также известны мощности поставщиков и потребителей, т.е. величины продукта, которые производятся (потребляются) за единицу времени.
Считаем, что сумма мощностей производителей равна сумме мощностей потребителей, т.е. речь идёт о транспортной задаче закрытого типа.
Также известны цены перевозки товара на различных участках рассматриваемой прямоугольной области. Под ценами на перевозку единицы товара на единицу расстояния можно понимать как финансовые затраты, так и затраты по времени.
Вообще, если речь идёт о денежных затратах, то характеристикой места будет являться удельная стоимость перевозки, а если речь идёт о затратах времени – пропускная способность местности.
Требуется составить оптимальный план перевозок на прямоугольной области, при котором общая стоимость перевозок будет минимальной.
Забегая вперёд, скажем, что решение задачи предполагает правильное заполнение матрицы перевозок, которая будет рассмотрена в следующей главе, и графическое построение схемы маршрутов перевозок на карте местности.
Глава 2
Формализация задачи

Для решения рассматриваемой задачи введём ряд обозначений и структур информации.

Во-первых, разобьём рассматриваемую прямоугольную область на пикселей. Таким образом мы упростим модель до перемещения продукта между четырёхсвязными прямоугольными областями. Т.е. такими областями, каждая из которых имеет только 4 соседних элемента: верхний, нижний, правый, левый.
Теперь пространство перемещений представляется прямоугольной матрицей, где продукт перемещается из одной ячейки в одну из черырёх соседних ячеек. Кстати, для хранения информации о характере таких перемещений, введём массив inp[x,y,i], где x,y – координаты пикселя, а i – номер направления притока (рис. 2.2).

Отметим, что каждая ячейка имеет 5 направлений притока: один приток извне и четыре притока от соседних ячеек.
Величина притока может принимать как положительные, так и отрицательные значения. Отрицательная величина притока может быть интерпретирована как отток продукта.
Так же введём массив price[x,y] для хранения информации об удельных ценах перевозок внутри пикселей. Общую стоимость перевозок по территории пикселя будем вычислять как

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

Глава 3
Условие равновесия притоков-оттоков

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

Т.е. равенство нулю суммы притоков ячейки является условием того, что в ней не возникнет переполнения или дефицита продукта. Иначе говоря, сумма притоков должна быть равна сумме оттоков.
Соблюдение условия равновесия каждой отдельной ячейки матрицы гарантирует равновесие матрицы транспортировок вцелом.
Аналогией закона равновесия является первый закон Кирхгофа (закон токов Кирхгофа), который гласит, что алгебраическая сумма токов в любом узле любой цепи равна нулю (значения вытекающих токов берутся с обратным знаком). Иными словами, сколько тока втекает в узел, столько из него и вытекает. Данный закон следует из закона сохранения заряда. Этот закон может применяться и для других физических явлений (к примеру, водяные трубы), где есть закон сохранения величины и поток этой величины.
Любое состояние матрицы, при котором соблюдается условие равновесия притоков, является одним из возможных решений транспортной задачи, но не обязательно оптимальным.
Руководствуясь только условием равновесия притоков можно найти стартовый план перевозок продукта, после чего останется только привести его к оптимальному виду путём преобразований. Кстати, так и работает программа «Поиск оптимальных маршрутов», созданная автором:
1) нахождение неоптимального стартового решения, удовлетворяющего условию равновесия;
2) постепенная оптимизация найденного решения.
Метод оптимизации плана перевозок по стоимости будет рассмотрен в следующей главе.

Глава 4
Оптимизация плана перевозок

Рассмотрим особенности оптимизации плана перевозок между четырьмя соседними ячейками матрицы транспортировок (рис. 4.1).

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

Листинг работы в системе Maple.
> restart;
# Суммы квадратов потоков перевозок в ячейках
S00:=inp000^2+inp001^2+(inp002+Delta)^2+(inp003-Delta)^2+inp004^2;
S10:=inp100^2+inp101^2+inp102^2+(inp103+Delta)^2+(inp104-Delta)^2;
S01:=inp010^2+(inp011+Delta)^2+(inp012-Delta)^2+inp013^2+inp014^2;
S11:=inp110^2+(inp111-Delta)^2+inp112^2+inp113^2+(inp114+Delta)^2;

# Стоимости перевозок в отдельных ячейках
SP00:=S00*P00;
SP10:=S10*P10;
SP01:=S01*P01;
SP11:=S11*P11;

# Общая стоимость перевозок.
# Это та величина, которую мы будем минимизировать.
SP:=SP00+SP10+SP01+SP11;

# Соответствие модулей потоков, связывающих ячейки.
inp003:=-inp011;
inp103:=-inp111;
inp002:=-inp104;
inp012:=-inp114;

# Условие экстремума.
diff(SP,Delta)=0;

# Решаем уравнение и находим Delta.
solve(%,Delta);

Итак, с помощью системы Maple нашли оптимальное значение величины Delta для получения минимальной стоимости перевозок на территории четырёх соседних ячеек:
(4.1)
При таком изменении дельта решение оптимизируется для четырёх соседних ячеек. Многократно повторяя такую оптимизацию для различных малых групп матрицы транспортировок, мы добьёмся постепенной оптимизации матрицы вцелом.
Отметим, что представленный метод был реализован в программе «Поиск оптимальных маршрутов» и показал себя надёжным, но медленным, требующим значительных затрат времени на проведение вычислений.
Глава 5
Кодирование входных данных в файле изображения

Программа «Поиск оптимальных маршрутов» в качестве входных данных берёт информацию из изображения-карты, подготовленной заранее в редакторе Paint.
Предполагается, что каждое такое изображение содержит карту какой-то местности, характеристики которой закодированы с помощью RGB-составляющих цвета.
В программе принят следующий способ кодирования:
R (red) − используется для указания мощностей поставщиков;
G (green) − используется для описания цены перевозки в данном месте;
B (blue) − используется для кодирования мощностей потребителей.
Такой подход значительно облегчает процесс формирования входных данных, ведь для создания карт можно использовать популярные графические редакторы. Такая методика является хорошей заменой «старому доброму» составлению громоздких текстовых файлов с числовыми данными.
Итак, для создания карт местности можно использовать те графические редакторы, которые позволяют точно регулировать цвета по модели RGB. Одним из таких редакторов является Microsoft Paint, позволяющий задавать цвета с помощью инструмента «Изменение палитры» (рис. 5.1).

В качестве характеристики пропускной способности места была использована удельная стоимость перевозки Price. В программе она вычисляется по формуле Price=. Таким образом величина Price принимает целые значения в диапазоне от 1 до 35903328718. Значение G=1 соответствует самой высокой пропускной способности (низкой стоимости), значение G=256 − самой низкой пропускной способности (высокой стоимости). Считается, что 256 различных значений Price вполне достаточно для описания различных дорожных и внедорожных условий перевозок. Таблица кодирования стоимости перевозки приведена на следующей странице.
Программа, представленные в данной работе, распознаёт изображения, сохранённые в растровом формате BMP (Bitmap Picture). При сохранении карт лучше выбирать режим «BMP 24-разряда (бита)».
Таблица кодирования стоимости перевозки Price с помощью градации зелёного цвета G.

Заключение

Результатом выполнения данной работы стало создание программы «Поиск оптимальных маршрутов».
Программа выполнена в среде программирования Lazarus, являющейся свободным программным обеспечением. Этот факт сразу же отметает возможные сомнения в легальности использования программных средств для её создания.
В данном труде разобран принцип работы программы. Рассмотрены примеры её использования.
Программа, работа которой описана в данной работе, может быть усовершенствована до более функциональной коммерческой версии, которая может быть использована менеджерами крупных компаний для организации оптимальной схемы перевозок грузов.
Среди очевидных плюсов программы следует отметить наглядный графический интерфейс, а также возможность сохранения этапов поиска оптимального решения в виде упорядоченного набора изображений.
Работа включает также примеры промежуточных расчётов с помощью математического пакета Maple.

Приложение Результаты работы программы