Диссертация (792540), страница 27

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 27)

В данном случае самизатраты на создание всех КТ не оптимизируются, а в качестве критериявыступают затраты на перевозку грузов от всех клиентов до своих КТ:187nЕ1   Di  Vi  s  min,(5.8)i 1гдеЕ1 - затраты грузоотправителей на подвоз продукции от предприятия доКТ;Di - расстояние перевозки от предприятия до КТ;Vi - объём производимой/добываемой контейнеропригодной продукции;s - расходная ставка на перевозку.2. Количество КТ не задано (k неизвестно), но известна средняястоимость одного КТ - с.

Критерием оптимизации выступает сумма общихзатрат на перевозку и на создание КТ:nE   Di  Vi  s  c  k    min ,(5.9)i 1гдеγ – нормативный коэффициент эффективности.Исследование, связанное с корректностью предлагаемой методологии,и решение поставленной задачи производилось по трем различным методам:1. Метод k-means [5]. В результате использования данного метода КТбудутрасполагатьсявгеометрическихцентрах,обеспечивающихоптимальные свойства с позиции наименьшего для всей сети перевозоксуммарного расстояния от точек-предприятий до КТ.

Такую кластеризациюназовем свободной, а метод, реализующий её, обозначим как алгоритм 1 [136].2. Метод k-means с проекцией на последнем шаге. Сначала произведемкластеризацию объектов с помощью метода k-means. В результате получимразбиение предприятий в виде кластеров с геометрическими центрами, а затемдля каждого центра найдем ближайшую железнодорожную станцию и будемсчитать, что здесь должен располагаться КТ. Реализацию метода с проекциейна последней итерации назовем – алгоритм 2 [136].3. Метод k-means с проекцией (k-means pro). Выбираем число k и напервом шаге выбрасываем k случайных точек, называемых центрами188кластеров.

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

Назовемреализацию такого метода - алгоритмом 3 [136].Для проведения экспериментальных и практических расчетов былнаписан и использован адаптированный под решаемые транспортные задачипрограммный продукт на языке JavaScript. Он реализуется в несколькихрежимах: с заданным или произвольным количеством кластеров. В первомслучае, реализация заключается в применении выбранного метода и заданиячисла кластеров k. Во втором – количество кластеров определяется согласновыбранному критерию (минимум суммарных затрат на перевозку и затрат насоздание k КТ или индексу Дэвиса-Болдина) с помощью перебора вариантовдля каждого k [136], [137].Стоит отметить, что такое разнообразие режимов работы позволяетэкспериментальным образом достигнуть наилучшего результата разбиения.Рассмотрим некоторые зависимости, закономерности и результаты,полученные на основе экспериментов при усреднении от 100 реализаций.Запустив на выполнение программу в режиме метод свободнойnкластеризации (Алгоритм 1), выберем в качестве критерия D   Di .

Дляi 1примера точные цифровые результаты показаны в таблице 5.1 [136], [151].189Таблица 5.1 - Пример выдаваемых программой результатовk=25; Общий объем грузовОбщее расстояниеОбъем перевозокСреднее расстояние до КПСреднее расстояние между КПNСтанции-КПКол-вопредприятий1Трофимовский2542Кротовка12558296 т19019,14 км18234000 т-км22,4 км98,1 кмНомера в списке предприятий788, 789, 790, 791, 792, 793, 794,795, 796, 797, 798, 799, 800, 801,802, 803, 804, 805, 806, 807, 808,809, 810, 811, 812, 813, 814, 815,816, 817, 818, 819, 820, 828, 829,830, 831, 832, 835, 837, 838, 839,840, 842, 843, 844, 845, 846, 847,848, 849, 850, 851, 852150, 151, 199, 200, 208, 576, 577,602, 611, 723, 724, 749Объем% отобщегообъемаСредрасст.до КП547139.82353736.316Результат выполнения программы представлен на рисунке 5.9.

Графикзависимости критерия D от k показан на рисунке 5.10. Полученные данные:количество кластеров – 25, D = 19019,14. Из графика видно, что с ростомколичества кластеров суммарное расстояние сначала резко уменьшается, азатем уменьшается медленно.Следующим шагом выберем в качестве критерия индекс ДэвисаБолдина, а метод оставим прежним – свободная кластеризация. Результатвыполнения программы представлен на рисунке 5.11.

График зависимостикритерия DB от величины количества кластеров k показан на рисунке 5.12.Оптимальный результат: количество кластеров – 10, DB = 0.63.В режиме метод k-means с проекцией, критерий – суммарноеnрасстояние от всех точек до своих центров D   Di . Результат выполненияi 1программы для k=25 представлен на рисунке 5.13. Полученные данные: D =27736,88 км. График зависимости критерия D от k показан на рисунке 5.14.190Рисунок 5.9 - Результат выполнения программы в режиме свободнойкластеризации с критерием суммарного расстояния200000180000160000140000D, км120000100000АЛГ 18000060000400002000001 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25kРисунок 5.10 – Зависимость суммарного расстояния перевозки от количествакластеров k в режиме свободной кластеризации191Рисунок 5.11 - Результат выполнения программы в режиме свободнойкластеризации с критерием Дэвиса-Болдина21,81,61,41,210,80,60,40,205678910111213141516171819202122232425kРисунок 5.12 - Зависимость индекса Дэвиса-Болдина от количества кластеровk в режиме свободной кластеризации192Рисунок 5.13 - Результат выполнения программы для k=25 в режимекластеризации с проекцией и критерием суммарного расстояния200000180000160000D, км140000120000100000АЛГ 38000060000400002000001 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25kРисунок 5.14 - График зависимости суммарного расстояния перевозки отколичества кластеров k в режиме кластеризации с проекциейИз графиков, представленных на рисунках 5.10 и 5.14, видно, что приnувеличении числа k суммарное расстояние D   Di сокращается.i 1193Далее для оптимизации числа кластеров k выберем индекс ДэвисаБолдина, а алгоритм оставим прежним – кластеризация с проекцией.

Результатвыполнения программы k=22 представлен на рисунке 5.15.Рисунок 5.15 - Результат выполнения программы в режиме кластеризации спроекцией и критерием Дэвиса-БолдинаГрафик зависимости критерия DB показан на рисунке 5.16.Полученные данные: оптимальное количество кластеров k = 22, DB = 0.71.1,81,61,41,210,80,60,40,205678910111213141516171819202122232425kРисунок 5.16 - Зависимость индекса Дэвиса-Болдина от количества кластеровk в режиме кластеризации с проекцией194Проведем кластеризацию при условии задания целевого критерия вслучае, когда известно число k (КТ), т.е. когда при проектировании заданыресурсы на создание всех КТ и известна средняя нормативная стоимостьодного КТ.

В этом случае сами затраты на создание всех КТ неоптимизируются, и в качестве критерия выступают затраты на перевозкугрузов от всех клиентов до своих КТ [136], [137].Проведем кластеризацию при заданных количествах k, которое будемменять от 1 до 25 по все трем алгоритмам, описанным выше. Результатывыполнения алгоритма 1, алгоритма 2 и алгоритма 3 в виде графиказависимостей представлены на рисунке 5.17 [136], [137].Как видно из рисунка 5.17, общие затраты на перевозку сокращаютсяпри увеличении k – числа КТ.

С этой точки зрения, чем больше КТ, тем меньшезатраты на перевозку продукции от производств до КТ.200180E1, млн. усл. ед.160140120100АЛГ 180АЛГ 260АЛГ 3402000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25kРисунок 5.17 – Зависимости затрат грузоотправителей на перевозку отколичества кластеров (планируемых к строительству КТ) при выполнениикластеризацииРассмотрим отличия в результатах, получаемых с использованиемметода кластеризации k-means и метода k-means pro. В разработанном методекластеризации k-means pro центры кластеров обязательно должны находитьсяна станциях.

Это ограничивает возможности получения лучших значений195критерия для процесса кластеризации, т.к. на каждой итерации проектируютсяполученные центры кластеров на железнодорожную станцию. При этомполучаем вариант кластеризации с худшим значением критерия Е1пр,вычисленного с использованием величины Dпр.Для метода кластеризации k-meansnikD   d ( xij , ei ) d ( x , e ) ijii 1 j 1,( xij1  ei1 ) 2  ( xij 2  ei 2 ) 2.(5.10)Для метода кластеризации k-means prokniDпр   d ( xij , сi* ),i 1 j 1d ( xij , ci* ) ( xij1  ci*1 ) 2  ( xij 2  ci*2 ) 2. (5.11)В работе вводится понятие «дефекта проекции» как разницы величиныкритерия качества «свободной» кластеризации и кластеризации «с проекцией»Δ = Е1пр – Е1.На рисунке 5.18 представлена зависимость Δ / Е1 от k, полученная наоснове многократных экспериментов для предприятий, расположенных натерритории Приволжского федерального округа.0,80,70,6Δ/E₁0,50,40,30,20,1012345678910 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25kРисунок 5.18 - Полученная зависимость Δ / Е1 от k для территории ПФО196При значительном увеличении числа КТ дефект проекции растет.Отсюда следует, что, когда разница Δ значительна (в проведенныхэкспериментах она достигала 30-40%), возможно, выгоднее создавать новыеобъекты терминально-логистической инфраструктуры, а не размещать КТ илиКНРЦ на уже существующих.Вышеприведенные зависимости дают возможность количественнооценить различные варианты при проектировании КТС.5.4 Математическая модель определения мест расположения контейнерныхтерминалов5.4.1 Математическая модель кластеризации при заранее заданной частимножества контейнерных терминаловНа практике при проектировании сети КТ может быть так, что часть КТуже функционирует.

При этом КТ уже обслуживают ряд предприятий, т.е. кним уже «привязаны» какие-то промышленные предприятия региона.Возникает проблема проектирования всей сети КТ при заданных k0 КТ.Очевидно, что методика построения сети меняется. Необходимо ввести новыйкритерий оптимизации и построить алгоритм, оптимизирующий введенныйкритерий при новых ограничениях.Самый простой способ решения этой задачи следующий. Сначалавычленить, из всей совокупности производств и станций, существующие КТ и«привязанные» к ним производства. Тогда задача сводится к кластеризацииоставшихся производств и определения новых КТ со своими кластерамипроизводств. Очевидно, эта задача не отличается от рассмотренной. Но, вобщем случае, более корректно считать заданными только местоположения197имеющихся КТ, а «привязанные» к ним производства включить в процедуруновой кластеризации.Основой для данного случая может служить рассмотренный метод kmeans pro, в котором изменяется способ построения «эталонов».

Вместополучения k центров, определяемых на основе полученных кластеров на m-ойитерации, k0 центров всегда записываем постоянными. В остальном действияалгоритма сохраняются. Очевидно, что при больших k0, приближающихся к k,т.е. когда почти все КТ заранее заданы, алгоритм может работать неэффективно и не находить локальный минимум. Другой способ – этоиспользование Алгоритма 2, который, в отличие от метода k-means pro,сначала находит геометрические центры (метод k-mеans), а затем ужепроектируетполученныерассматриваемойзадачецентрынажелезнодорожныенеобходимомодифицироватьстанции.Воперациюпроецирования. А именно: если расстояние до заданного КТ-станции отполученного центра меньше всех других расстояний до станций, то, очевидно,выбирается этот заданный КТ-станция. Если это другая станция l, тоанализируетсясуммарноерасстояниеотзаданногоКТ-станциидопроизводств данного кластера и сравнивается с вариантом, когда КТIвыбирается в станции l.

Если разница несущественна D  D   , то выбираемсуществующий КТ. Если разница существенная, то выделяем кластеры,расположенные рядом с существующим КТ, и для этого фрагмента решаемзадачу кластеризации с заданным одним КТ.5.4.2 Математическая модель кластеризации, когда число кластеровне заданоКак было показано в главе 4, кластеризация по методу k-meansпредполагает задание числа кластеров k как исходного параметра.

Характеристики

Список файлов диссертации