close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Кибернетика. Информационные системы и технологии
УДК 519.658:004.421
ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО КОЛИЧЕСТВА И РАСПОЛОЖЕНИЯ ЛОГИСТИЧЕСКИХ
ЦЕНТРОВ: МАТЕМАТИЧЕСКАЯ МОДЕЛЬ И ЧИСЛЕННЫЙ МЕТОД
Д.С.Бухаров1
Иркутский государственный технический университет,
664074, г. Иркутск, ул. Лермонтова, 83.
Построена математическая модель актуальной оптимизационной задачи транспортной логистики об оптимальном размещении нескольких логистических центров на полигоне обслуживания. Исследована задача об определении оптимального количества логистических центров. Разработан метод решения вышеуказанных задач,
включающий вычислительные алгоритмы последовательного улучшения с использованием мультистарта и последовательного улучшения с выделением активных зон. Выполнена программная реализация, проведен вычислительный эксперимент, включающий решение серий модельных задач.
Ил. 10. Табл. 1. Библиогр. 12 назв.
Ключевые слова: математическая модель; численный метод; программное обеспечение; транспортная логистика.
DETERMINATION OF OPTIMAL NUMBER AND LOCATION OF LOGISTICS CENTERS: MATHEMATICAL MODEL
AND NUMERICAL METHOD
D.S. Bukharov
Irkutsk State Technical University,
83 Lermontov St., Irkutsk, 664074.
The author builds a mathematical model of the actual optimization problem of transport logistics on the optimal location of
a number of logistics centers at the site of service. The problem of determining the optimal number of logistics centers is
also studied. The method to solve the above problems is developed. It includes computational algorithms of successive
improvement with the use of multistart and successive improvement with the identification of active zones. Software implementation is performed. The computational experiment, which includes the solution of series of model problems, is
conducted.
10 figures. 1 table. 12 sources.
Key words: mathematical model; numerical method; software; transport logistics.
Введение. Для развития транспортно-логистической системы и получения существенного экономического эффекта необходимо решить несколько
основных проблем, таких как оптимальное размещение нескольких логистических центров и определение
оптимального количества складов на полигоне обслуживания. Задача об определении оптимального количества складов традиционно решается графическим
методом [1, с. 397], который показывает изменение
издержек при изменении количества складов. Увеличение числа складов влечет за собой увеличение расходов на их содержание, но при этом снижаются
транспортные расходы (затраты на доставку и потери
от удаленности потребителя от склада). Данный метод эффективен при развитой дорожной сети. В противном случае, а также при существенных изменениях
ландшафта, оказывающих влияние на длину маршрута, транспортные расходы могут изменяться неравномерно [2]. Таким образом, для уточнения возможных
расходов целесообразно рассматривать данную задачу совместно с задачей об оптимальном размещении
нескольких логистических центров. Эту задачу, в зависимости от требований к размещению складов,
можно рассматривать как в дискретной, так и в непрерывной постановках.
Для решения задачи в дискретной постановке за-
частую используется метод k-средних [3,4], основанный на определении расстояния до логистических
центров и переопределении центра тяжести, или метод FOREL [5], основанный на переопределении центра тяжести для потребителей, попавших в окружность заранее заданного радиуса, и исключении их из
дальнейшего рассмотрения. Данные методы гарантируют достижение не глобального минимума, а только
одного из локальных, результат зависит от выбора
исходных координат логистических центров. К основным их недостаткам можно отнести требование к хорошо развитой дорожной сети и концентрации потребителей в определенных точках, что невозможно для
крупных городов. Для метода FOREL требуется также
заранее определить радиус охвата.
В данной работе представлены математические
модели для задач об оптимальном размещении нескольких логистических центров и об определении
оптимального количества логистических центров в
виде задач вариационного исчисления специального
вида, предложены методы их решения.
В основе предлагаемых методов лежит подход,
успешно применявшийся при исследовании задач об
оптимальном маршруте, оптимальном размещении
логистического центра, идентификации и сегментации
логистических зон [6,7], основанный на принципах
___________________________
1
Бухаров Дмитрий Сергеевич, аспирант, e-mail: bukharovds@gmail.com
Bukharov Dmitry, Postgraduate, e-mail: bukharovds@gmail.com
8
ВЕСТНИК ИрГТУ №4 (63) 2012
Кибернетика. Информационные системы и технологии
Гюйгенса (построение фронтов вторичных волн) и
Ферма (перемещение луча света по кратчайшему пути). Впервые аналогия между распространением света
в неоднородной среде и минимизацией интегрального
функционала была предложена И. Бернулли [8].
1. Задача об определении оптимального расположения нескольких логистических центров
(складов). Пусть в некоторой ограниченной области
D  R 2 c кусочно-гладкой границей заданы точки
Bi ( xi , y i ) , i  1, n , в которых располагаются потребители и кусочно-непрерывная функция v( M )  0 ,
характеризующая в точке M ( x, y) мгновенную скорость движения грузов. Также имеются 1  m  n
складов, расположение которых заранее неизвестно
Ak ( xk , yk ) , k  1, m . Тогда для любой точки
M ( x, y)  D минимальное время доставки из M в
Bi вычисляется по формуле
d i
(1)
Ti ( M )  min 
.
i ( M )
v ( x, y )
i ( M )
Требуется
найти
оптимальные
расположения
( x , y ) , k  1, m , и разбиение множества
потребителей на m подмножеств, определив номера
I k  ik1 ,..., iks  потребителей, обслуживаемых
складов
складом
*
k
*
k
Ak ( xk , yk ) , k  1, m , таким образом, чтобы
суммарное время доставки до всех
было минимально возможным, т.е.
потребителей
m
 T ( x , y )  min .
k 1 iI k
i
k
k
(2)
Параметрами минимизации являются координаты
складов xk , yk и состав подмножеств потребителей
Ik .
Поставленная логистическая задача является задачей отыскания глобального минимума для непрерывной функции многих переменных, вид которой, в
свою очередь, определяется при решении серий задач минимизации интегрального функционала (1).
Автору не удалось найти в литературе аналитических или численных методов, которые позволяли бы
решать подобные задачи в общем случае. В ходе проведенного исследования был опробован ряд подходов
к построению вычислительных методов. Ниже приводятся два из них, которые оказались эффективными
при решении модельных задач, в том числе с известными аналитическими решениями.
2. Метод последовательного улучшения с использованием мультистарта (МПУМ). Идея метода
заключается в итеративном улучшении получаемого
решения при помощи последовательной сегментации
области на зоны, обслуживаемые одним центром, и
нахождении оптимального расположения этого центра
в соответствующей зоне. Генерация начальных поло-
жений повторяется несколько раз, в результате находятся локальные минимумы, среди которых выбирается лучший вариант. Данный процесс описывается
следующим алгоритмом:
Шаг №1. Определяются начальные координаты
складов Ak ( k  1,, m ) методом случайной генерации положений.
Шаг №2. Из точек
Ak выпускаются световые волны и производится сегментация области D на m
зон. Для каждого потребителя Bi ( i  1,, n ) устанавливается принадлежность к зоне Dk . Затем внутри k -ой области определяется оптимальное расположение склада Ak . Процесс переопределения координат (шаг №2) повторяется до тех пор, пока изменяются координаты складов Ak .
Шаг №3. Определяется суммарное время доставки груза со всех складов до «своих» потребителей.
Запоминается конечное положение Ak и процесс повторяется с шага №1.
Без использования многократного генерирования
(мультистарта – шаг №1) возможны следующие ситуации:
 Найдено расположение логистических центров, соответствующее локальному минимуму задачи
(1) – (2), причем каждый склад обслуживает хотя бы
одного потребителя.
 Задано такое начальное размещение складов,
при котором после сегментации области D в зоне
возможного обслуживания хотя бы одного склада не
обнаруживается ни одного потребителя («неправильное» размещение).
Использование мультистарта позволяет находить
различные локальные экстремумы и отсекать «неправильные» размещения.
3. Метод последовательного улучшения с выделением активной зоны (МПУАЗ). Идея данного
метода заключается в выделении на полигоне обслуживания двух зон: «активной» и «неактивной». Сначала для всех потребителей находится центр тяжести.
Далее выделяется «неактивная» зона, которая представляет собой область обслуживания данным центром тяжести, т.е. охватывает часть полигона. «Радиус охвата» составляет как минимум половину расстояния до самого удаленного потребителя. Данный радиус варьируется в зависимости от числа складов,
которые необходимо разместить, и от числа потребителей, попавших в «активную» зону. После определения размеров зон перебираются некоторые комбинации начальных положений складов. Выделение зон
необходимо для размещения складов в наибольшей
удаленности от центра тяжести всех потребителей.
Для наглядности рассмотрим метод МПУАЗ на
плоскости, соответственно «неактивная» зона будет
иметь форму окружности:
Шаг №1. Определяется центр тяжести для всех
потребителей. На рис. 1 центр тяжести обозначен точ-
ВЕСТНИК ИрГТУ №4 (63) 2012
9
Кибернетика. Информационные системы и технологии
кой O . Выбирается наиболее удаленный от O потребитель, обозначим его точкой D . Строится окружность радиуса R  OD , которая охватывает всех
потребителей. Назовем полученную область «активной» зоной – на рис. 1 закрашена белым цветом.
Шаг №2. Строится окружность радиуса r  R / 2 .
Если в «активной» зоне число потребителей
меньше числа складов m , то радиус
так, что
na
r уменьшается
na  m . Полученную область назовем «неак-
тивной» зоной – на рис. 1 закрашена серым цветом.
Шаг №3. Производится размещение (m  1) -го
фиксированного склада в потребителях в «активной
зоне» (перебираются все возможные комбинации по
(m  1) -му складу среди na потребителей без повторений), m -й склад располагается в каждой из следующих точек:
 во всех остальных потребителях, исключая
фиксированные склады, и в точке O ;
 в точках, являющихся центрами тяжести для
каждого потребителя «активной» зоны, и точке O ,
исключая совпадения с потребителями; данные точки
на рис. 2 обозначены серым цветом;
 в точках, являющихся центрами тяжести для
всех возможных парных комбинаций потребителей в
«активной» зоне, исключая совпадения с потребителями, точкой O и ранее определенными точками;
данные точки на рис. 3 обозначены серым цветом.
Для каждой комбинации производится сегментация области D на m зон и определяется оптимальное расположение складов в каждой зоне
множество точек, являющихся центрами тяжести для
всех возможных парных комбинаций потребителей в
«активной» зоне. Тогда мощность объединения множеств N c , N act , N
и O будет равна
B  m( N  Nc  Nact  O) . Количество комбинаций по (m  1) -му складу среди
na потребителей без
повторений
Cnma 1 
щее
составляет
na !
. Таким образом, об(na  m  1)!(m  1)!
число
перебираемых
комбинаций
равно
na ! B
.
(na  m  1)!(m  1)!
Рис. 2. Центры тяжести для парных комбинаций
потребитель – точка О
Dk . Запо-
минается лучшее решение. Шаг №3 повторяется для
всех комбинаций фиксированных (m  1) складов
среди
na потребителей.
Рис. 3. Центры тяжести для парных комбинаций
потребителей
4. Задача об определении оптимального количества логистических центров (складов). Пусть в
некоторой ограниченной области
гладкой границей заданы точки
D  R 2 c кусочно-
Bi ( xi , y i ) , i  1, n , в
которых располагаются потребители, и кусочнонепрерывная функция v( M )  0 , характеризующая в
Рис. 1. Выделение «активной» и «неактивной» зон
Определим общее число перебираемых комбинаций. Пусть N – множество «свободных» потребителей, количество которых (n  m  1) ;
N c – множе-
ство точек, являющихся центрами тяжести для каждого потребителя «активной» зоны и точки O ; N act –
10
точке M ( x, y) мгновенную скорость движения грузов. Также имеются 1  m  n складов, расположение и количество которых заранее неизвестно
Ak ( xk , yk ) , k  1, m . Тогда для любой точки
M ( x, y)  D минимальное время доставки из M в
Bi вычисляется по формуле (1).
ВЕСТНИК ИрГТУ №4 (63) 2012
Кибернетика. Информационные системы и технологии
Будем предполагать, что расходы на доставку и
потери от несвоевременной доставки пропорциональны времени доставки. Тогда можно считать, что единица времени равна условной денежной единице.
Расходы на содержание и эксплуатацию складов обозначим через
Tst ,k , k  1, m .
Требуется определить такое количество складов
m и их размещение, при котором были бы минимальны общие затраты на доставку (2) и общие расходы на
m
содержание и эксплуатацию складов
T
k 1
m
st , k
, т.е.
m
 Ti ( xk , yk )   Tst ,k  min .
k 1 iI k
(3)
k 1
Здесь, как уже отмечалось, параметрами минимизации являются количество складов m , их координаты
xk , yk и состав подмножеств потребителей I k , определяемый при решении задачи (2).
Для решения данной задачи используется ниже
описанный метод.
5. Метод определения оптимального количества складов. Идея метода заключается в последовательном увеличении числа складов, начиная с двух,
с отысканием для них оптимального расположения.
Число складов увеличивается до тех пор, пока не будет определен минимум затрат (3). Данная идея реализована в виде следующего алгоритма:
Шаг №1. Определяется оптимальное расположение одного логистического центра и подсчитывается
время (3). Полученное время и расположение склада
запоминаются.
Шаг №2. Увеличивается число рассматриваемых
складов на 1 (максимум равен числу потребителей n )
и производится поиск оптимального расположения
методом МПУАЗ.
Шаг №3. Производится сравнение временных затрат. Если при текущем количестве центров затраты
меньше, то запоминается время и расположение
складов и выполняется шаг №2. В противном случае
решение найдено.
Очевидно, что не более чем за n  1 итерацию
получим решение. Одна итерация включает в себя
выполнение шагов №2 и №3.
6. Программная система «Волна». Рассмотренные в пунктах 2,3,5 методы реализованы в программной системе «Волна». На рис. 4 представлена вкладка
«2D изображение», на которой отображено решение
задачи об определении оптимального числа логистических центров и их размещении.
Оптическая среда, в которой распространяется
световая волна, пока предполагается однородной, т.е.
задача рассматривается на плоскости. Кратчайшее
расстояние между соседними узлами преодолевается
за 1 единицу времени, по диагоналям – за 2 единицу времени. Затраты на открытие одного склада
принимаются равными 10 единицам времени. Потребители обозначены черно-белыми точками, склады –
белыми.
При данных условиях оптимальное число складов
равно 3. Общие затраты составляют приблизительно
49,314 единицы времени, что совпадает с аналитическим решением.
Рис. 4. Интерфейс вкладки «2D изображение»
ВЕСТНИК ИрГТУ №4 (63) 2012
11
Кибернетика. Информационные системы и технологии
7. Вычислительный эксперимент. Рассмотренные методы МПУМ и МПУАЗ протестированы на ряде
модельных задач. На рис. 5 – 8 представлены некоторые из них. Белые области на рис. 8 – непроходимые
барьеры. Потребители обозначены черно-белыми
точками, склады – белыми. По результатам проведен-
ного вычислительного эксперимента можно сделать
вывод о том, что рассматриваемые в данной работе
методы эффективно решают задачи с расположением
потребителей близким к равномерному. Найденные
методами МПУМ и МПУАЗ решения совпадают с полученными аналитически.
Рис. 5. Модельная задача: а – расположение потребителей; б – расположение двух складов; в – расположение
трех складов; г – расположение четырех складов
Рис. 6. Модельная задача: а – расположение потребителей; б – расположение двух складов; в – расположение
трех складов; г – расположение четырех складов
Рис. 7. Модельная задача: а – расположение потребителей; б – расположение двух складов; в – расположение
трех складов; г – расположение четырех складов
Рис. 8. Модельная задача с барьерами: а – расположение двух складов; б – расположение трех складов;
в – расположение четырех складов
12
ВЕСТНИК ИрГТУ №4 (63) 2012
Кибернетика. Информационные системы и технологии
На рис. 9 и 10 представлены модельные задачи, в
которых методом МПУМ при размещении шести и более складов не удалось построить решение, что объясняется специфическим расположением потребителей на местности. Потребители обозначены чернобелыми точками, склады – белыми. Данная ситуация
характерна для областей с неравномерным распределением населения (например, Иркутская область), при
котором населенные пункты расположены группами и
находятся на достаточно большом расстоянии друг от
друга. Данный класс задач позволяет решить метод
МПУАЗ.
Рис. 9. Модельная задача с групповым расположением
потребителей
Рис. 10. Модельная задача с непроходимыми
барьерами
Номер
рисунка
5,б
5,в
6,б
6,в
7,б
7,в
Метод
МПУАЗ
МПУМ
МПУАЗ
МПУМ
МПУАЗ
МПУМ
МПУАЗ
МПУМ
МПУАЗ
МПУМ
МПУАЗ
МПУМ
Количество
складов
2
3
2
3
2
3
В таблице представлено сравнение методов
МПУМ и МПУАЗ для модельных задач, в которых оптическая среда, характеризующая ландшафт местности, предполагается однородной, т.е. задачи рассматриваются на плоскости. Кратчайшее расстояние между соседними узлами преодолевается за 1 единицу
времени, по диагоналям – за 2 единицу времени.
Лучшее время, найденное методами, совпадает с построенным автором аналитическим решением. Число
вылетов характеризует количество «неправильных»
размещений. В общее число минимумов включены все
найденные при помощи соответствующего алгоритма
локальные и глобальные минимумы. Метод МПУМ
находит меньшее число минимумов, так как при случайной генерации начального распределения координат не удается попасть в область притяжения для некоторых экстремумов, ввиду того что она может быть
достаточно мала. Метод МПУАЗ позволяет находить
большее количество экстремумов за счет специально
сконструированной генерации начальных положений,
при которой «подвижный» ( m -й) склад располагается
в точках, являющихся центром тяжести между парой
(или группой) потребителей. Число итераций в методе
МПУАЗ соответствует числу комбинаций, перебираемых при решении задачи.
Проведенный вычислительный эксперимент показал, что метод МПУМ эффективен при решении задач,
в которых потребители размещены достаточно равномерно. Метод МПУАЗ позволяет решить все рассмотренные и представленные в данной работе задачи, однако для этого потребуется использовать больше вычислительных ресурсов.
Для рассмотренных в работе модельных задач
глобальные минимумы можно получить геометрически. Они также были найдены методами МПУМ и
МПУАЗ. Однако в общем случае данные методы не
гарантируют нахождение всех локальных экстремумов, поэтому при решении более сложных задач выбирается наилучший из полученных локальных минимумов.
Вообще говоря, автору неизвестны алгоритмы,
позволяющие гарантированно находить глобальный
экстремум без жестких ограничений на класс задач,
Число минимумов
общее
глобальных
8
4
8
4
16
6
15
6
13
2
10
2
21
2
20
2
13
4
13
4
55
20
31
16
Число вылетов
ВЕСТНИК ИрГТУ №4 (63) 2012
0
0
2
426
2
0
31
265
4
0
76
0
Число итераций
56
10000
78
10000
120
10000
285
10000
240
10000
812
10000
Лучшее
время
16,971
11,314
30,627
22,627
33,941
28,284
13
Кибернетика. Информационные системы и технологии
как, например в [9]. Так, в [10, 11] представлено применение муравьиных алгоритмов для поиска глобального экстремума. Но они не гарантируют нахождение
всех локальных экстремумов, поэтому для поиска
наилучшего решения также требуется многократная
генерация стартовых положений муравьев и повторение процедуры поиска, т.е. фактически использование
мультистарта.
Заключение. В работе представлены математические модели задач об оптимальном размещении
нескольких логистических центров и об определении
оптимального количества логистических центров. Разработаны методы решения поставленных задач:
 Метод последовательного улучшения с использованием мультистарта (МПУМ), основанный на
многократной генерации начальных положений логистических центров и отыскании в каждой ситуации
локальных экстремумов с целью нахождения глобального минимума.
 Метод последовательного улучшения с выделением активной зоны (МПУАЗ), идея которого заключается в разделении всей логистической области на
«активную» и «неактивную» зоны и рассмотрении
возможных начальных положений логистических центров относительно потребителей, попадающих в «активную зону».
ной системы «Волна», которая также позволяет решать ранее рассмотренные задачи об оптимальном
маршруте (включая задачу об оптимальной прокладке
высокоскоростной железнодорожной магистрали), об
оптимальном размещении одного логистического центра, об идентификации и сегментации логистических
зон. Кроме того, реализован метод определения оптимального количества складов, основанный на сравнении суммарных затрат (3) для различного числа
логистических центров и выборе оптимального варианта.
Проведен вычислительный эксперимент, включающий решение ряда модельных задач. Для решения
данных задач использовано несколько методов, среди
которых лучшие результаты показали методы МПУМ и
МПУАЗ, однако они имеют некоторые недостатки. Метод МПУМ не позволяет эффективно решать один из
классов модельных задач. Метод МПУАЗ позволяет
решить все модельные задачи, однако требует значительных вычислительных затрат при достаточно
большом количестве потребителей. Данную проблему, возможно, удастся решить распараллеливанием
процедуры поиска координат складов как на уровне
задач, так и на уровне данных [12].
Работа выполнена при финансовой поддержке
Российского фонда фундаментальных исследований,
проект № 11-07-00245.
Данные методы реализованы в рамках программБиблиографический список
1. Лукинский В.С. Модели и методы теории логистики:
матические технологии в науке и управлении: труды XVI
учеб. пособие. 2-е изд. / под ред. В.С.Лукинского. СПб.: ПиБайкальской Всерос. конф. Иркутск: ИСЭМ СО РАН, 2011.
тер, 2008. 448 с.
Т. 2. С. 99–106.
2. Журавская М.А., Тарасян В.С. Идентификация и сег8. Курант Р., Гильберт Д. Методы математической физики.
ментация логистических зон утилизации старых автомобиПер. с англ. М.: Мир, 1965. 408 с.
9. Стрекаловский А.С. Элементы невыпуклой оптимизалей на основе теории нечетких множеств // Транспорт Урала. 2010. №3 (26). С. 29–33.
ции. Новосибирск: Наука, 2003. 356 с.
3. Мандель И.Д. Кластерный анализ. М.: Финансы и стати10. Hu XM., Zhang J., Li Y. Orthogonal Methods Based Ant
стика, 1988. 176 с.
Colony Search for Solving Continuous Optimization Problems //
4. Anil K.J. Algorithms for clustering data / Anil K. Jain – New
Journal of computer science and technology. SCIENCE PRESS.
Jersy: Prentice Hall, 1988. 320 p.
Jan. 2008, 23(1). Р. 2–18.
5. Загоруйко Н.Г. Прикладные методы анализа данных и
11. Карпенко А.П., Чернобривченко К.А. Эффективность
знаний. Новосибирск: Изд-во Института Математики, 1999.
оптимизации методом непрерывно взаимодействующей
270 с.
колонии муравьев (CIAC) // Наука и образование (электрон6. Казаков А.Л., Лемперт А.А., Бухаров Д.С. Об одном чисный
журнал).
2011.
№
2.
URL:
ленном методе решения некоторых задач оптимизации,
http://technomag.edu.ru/doc/165551.html (дата обращения:
возникающих в транспортной логистике // Вестник ИрГТУ.
19.11.2011).
2011. №6(53). С. 6–12.
12. Немнюгин С., Стесик О. Параллельное программирова7. Казаков А.Л., Бухаров Д.С., Лемперт А.А. Решение неконие для многопроцессорных вычислительных систем. СПб.:
торых прикладных задач оптимизации с использованием
БХВ-Петербург, 2002. 396 с.
методов геометрической оптики // Информационные и мате-
14
ВЕСТНИК ИрГТУ №4 (63) 2012
1/--страниц
Пожаловаться на содержимое документа