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

На правах рукописи

РАЗИНА МАРИЯ АЛЕКСАНДРОВНА

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ СТАНЦИЙ СКОРОЙ ПОМОЩИ ДЛЯ ОБСЛУЖИВАНИЯ НАСЕЛЕНИЯ ЗАДАННОЙ ОБЛАСТИ

Специальность 05.13.18- Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Казань 2005

Работа выполнена в Казанском государственном техническом университете им. А Н.Туполева.

Научный руководитель: доктор технических наук, профессор Галиев Шамиль Ибрагимович

Официальные доктор физико-математических наук, профессор

оппоненты: Коннов Игорь Васильевич

доктор физико-математических наук, профессор Маликов Александр Иванович

Ведущая организация Институт проблем информатики Академии наук РТ

Защита состоится ЛО _ 2005 года в ^ часов на

заседании диссертационного совета Д 212.079.01 в Казанском государственном техническом университете им. А.Н. Туполева по адресу: 420111, г. Казань, ул. Карла Маркса, 10.

С диссертацией можно ознакомиться в библиотеке Казанского государственного технического университета им. А.Н.Туполева.

Автореферат разослан 2005 г.

Ученый секретарь диссертационного совета доктор физ.-мат. наук, профессор

П. Г. Данилаев

Общая характеристика работы

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

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

Первая работа по задаче расположения была исследована в 1909 году Альфредом Вебером, который исследовал расположение склада для обслуживания потребителей с известными координатами и потребностями в материале, хранящемся на складе Далее Купер рассмотрел обобщение этой задачи

На сегодняшний день существует множество работ, посвященных задаче расположения станций обслуживания Имеются различные модели их исследования такие как модели n-центров (minimax модели) модели п-медиан (mimsum модели) вероятностные модели, модели теории массового обслуживания и другие

В обзоре Брандо М Ли Чина С С указано более 50 различных моделей, используемых для решения задач выбора расположения станций обслуживания Принципиальные результаты о моделях и методах их решения представлены в работах Дрезнера 3 , Лов Р Ф , Морриса Дж Г , Михалевича В С , Трубина В А Шора Н 3 Имеется большое число статей, посвященных данной задаче, которые можно найти в библиографиях работ указанных авторов Имеются специальные выпуски журналов, такие, как «Location Science» и другие, целиком посвященные этим задачам

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

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

Каждая из рассматриваемых в работе постановок задач порождает задачи нелинейной оптимизации, в частности, минимаксные и минимаксиминные Задачи такого типа исследованы многими авторами Демьянов В Ф, Васильев Л В, Васильев Ф П , Федоров В В , Кларк Ф , Михалевич В С , Гупал А М , Норкин В И , Поляк Р А , Заботин Я И , Коннов И В и другими

Для решения задачи оптимизации расположения станций обслуживания важно уметь находить глобальный экстремум целевых функций Существуют различные методы нахождения глобального экстремума, см , например, работы Жилинскаса А Г , Жиглявского А А , Хорста Р , Пардалоса Р , Туи Г и др Среди различных методов глобальной оптимизации одними из важных являются методы, использующие липшицевость функции В работе выявляется липшицевость

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

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

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

1) исследовать свойства моделей л-центров и п-медиан;

2) разработать алгоритм подбора параметров метрики, позволяющей адекватно описывать расстояния между любыми двумя точками заданной области;

3) определить свойства бисекторов и областей Вороного для пар точек в различных /р-метриках;

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

5) исследовать возможность нахождения решения с использованием многокритериальности.

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

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

Научная новизна. В диссертационной работе получены следующие новые научные результаты:

1) доказана липшицевость целевых критериальных функций и найдены постоянные Липшица для них;

2) предложена методика определения параметров метрики, адекватно описывающей расстояния для заданной области;

3) выявлены вид и свойства бисекторов и областей Вороного для пар точек в различных

4) предложены алгоритмы нахождения глобальных экстремумов целевых функций;

5) предложен алгоритм нахождения субоптимальных областей решений задачи;

6) предложен метод решения задач с учетом многокритериальности.

Достоверность результатов работы Достоверность полученных результатов

подтверждается сформулированными и доказанными теоремами, а также численными экспериментами с использованием программного комплекса

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

Апробаций работы. Основные результаты работы докладывались и обсуждались на следующих международных всероссийских конференциях и

семинарах ИХ Международная конференция по вычислительной механике и современным прикладным программным системам (Владимир 2003 г) 4-й Российский научный форум «Догоспитальный этап медицинской помощи традиции и стереотипы» (Москва 2003 г 1 Всероссийская молодежная научно-техническая конференция с международным участием «Интеллектуальные системы управления и обработки информации» (Уфа 2003 г) III Всероссийская научно-техническая конференция «Математические методы и информационные технологии в экономике социологии и образовании» (Пенза 2003 г) XXVI Congresso Nacional de Matematica Aphcada e Computacional (Sao Jose do Rio Preto (Brasil), 2003), II Международная научно-практическая конференция с Новые медицинские технологии в охране здоровья здоровых, в диагностике, лечении и реабилитации больных» (Пенза, 2004 г), VIII Международная научно-практическая конференция «Системный анализ в проектировании и управлении* (Санкт-Петербург, 2004 г), XIV Международная научно-техническая конференция «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза 2004 г) Результаты работы также использованы в НИР за 2003 год (отчет ПМ7-СМ-1, КГТУ 2003, № Госрегистрации 012 00316705 Инз № 02 20 0307056) и в учебном проиессе кафедры Прикладной математики и информатики КГТУ им А Н Туполева

Публикации По теме диссертации опубликовано 12 научных работ включая 1 отчет о НИР, 3 статьи и 8 тезисов докладов

Структура и объем диссертации Диссертационная работа состоит из введения четырех глав и библиографического списка Работа содержит 109 страниц машинописного текста 19 рисунков и 17 таблиц Список литературы включает 88 наименований

Содержание работы

Во введении содержится обоснование актуальности проблемы основные научные положения и результаты

В первой главе введены критерии оптимизации и сформулированы модели п-центров и n-медиан с различными условиями, выявлены свойства этих моделей

Пусть G - заданная область обслуживания, являющаяся ограниченной замкнутой многоугольной областью на плоскости Р с некоторой метрикой Введем декартову систему координат Обозначим через (х„ у,) координаты точки плоскости соответствующей /-той станции скорой помощи с„ 1 < i < п Пусть f = (с,, Cj, , с„) = (*< Уи *г У2, , х„, Уп) - совокупный вектор координат всех станций скорой помощи с„ 1< / < п Предположим что известно расположение г больниц как совокупность точек Ь,, \Щ<т Также пусть на плоскости Р введено расстояние d(a,b) между произвольными точками а и b Рассмотрим следующие задачи

1 Требуется выбрать расположение п станций с>, с2, , с„ (п>1) скорой помощи таким образом, чтобы минимизировать максимальное по всем возможным точкам вызова расстояние от точки s вызова до ближайшей станции с, скорой помощи mm d(s cj Сформулированная задача называется моделью п-центров и

представляется в следующем виде

minFf(f), F,(í)=max min d{s,c,),

£ ssG 1<1<п U)

здесь и далее s = s(x,y) - произвольная точка из области G Для дальнейшего изложения введем функцию

2 Требуется выбрать расположения станций скорой помощи таким образом, чтобы минимизировать максимальную по всем возможным точкам вызова

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

min FifO, F2(fy = max mm [d(s,c;) + d(sA)] (2)

seG Icjin ¡<k<m

Легко убедиться, что F2(Ç) можно представить в виде

F2(Ç) = max [ min d(s,Cj) + mm dfs.b/J] =■ m,i\ ç£>?(s,0. гДе scG lijin l<k<m stG

<p2{s,Ç) = mm d{s,Cj) + mm d{s,bk) ¡cj<n l^kim

В сформулированной задаче для каждой станции может задаваться свое множество больниц куда доставляют пациентов машины скорой помощи станции с,, 1<1<п Пусть В = фь Ь2, , Ьщ} >л В, ç В, 1<i< л, В, и В2 ^ иВ„ = В Тогда можно положить, что

F2(£) = max mm [ dfs.cj + d(s, bk)] seG lijin bkeBj

В частном случае, когда n = m и ß, = {b}, получим функцию F-JÇ) s виде

F2(Ç)= max mm [d(s,c,) + d(s, b)j (3)

SeG l<l<n

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

min F3(£), F3(Ç) = f p(s) min d{s,c.) ds, (4)

i q nisn

где p(s) - частота вызовов с различных точек s области G Для дальнейшего изложения введем следующую функцию = nun d{s с,)

1<1<п

4 Требуется расположить п [п>1) станций таким образом, чтобы в модели п-медиан учесть доставку пациента в ближайшую от него больницу Эта задача записывается в следующем виде

min F,(i), F«(f) = \ p(s) [(2-ûf) d(s,cq) + a ( d(s,br) + d(br,cq))} ds (5)

* G

Здесь индексы гид находятся из условий d(s,br) = nun d(s,bk) и d(s,cq) = nun d(s,c,)

l<k<m lij<n

соответственно Коэффициент a (0<aä1) отражает долю случаев, когда

осуществляется доставка пациента в больницу Для дальнейшего изложения введем

функцию <p4(s,Q = (2-а) d{s,cq) + а ( d(s,br) + d(br,c„))

Возможны различные варианты обслуживания и, следовательно, в

подинегральном выражении могут участвовать различные слагаемые Модель п-

медиан в общем случае записывают в виде

minFsfê), F5(î)= f p(s) f[ mm d(s,c,)]ds. (6>

4 g i^m

где f(t) - некоторая функция от f Таким образом задача (4) - частный случай задачи (6), а задачу (5) можно рассматривать как частный случай (6), если принять, что в (6) для f введены еще и другие аргументы

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

вектора х = (Х|, хг, хм) вводится следующим образом /р(х) =|| х ||р =

I N V Р

2>р| в

1/=/ !

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

Для решения поставленных задач с использованием /р-норм в работе доказаны следующие утверждения

Лемма 1 Для любого р, 1<р<да, функции (р^,^ и являются

липшицевыми по каждому из аргументов в и £ при фиксированном втором из аргументов Постоянная Липшица функции /р^З по б при фиксированном £ и по { при фиксированном 5 равна 2<2р|/2р при 1<р<2 и 1 при 2<р<^ Постоянная Липшица функции по £ при фиксированном в также равна 2'2р),2р при 1<р<2 и 1 при

2<р<» Постоянная Липшица функции г/>г(5,ф по в при фиксированном £ равна 2 2<2»>/2р При 1<р<2 и 2 при 2<р<х Постоянная Липшица функций ^(э.ф и ^(в.ф по каждой из координат вектора £ при фиксированных остальных и фиксированном э равна 1

Теорема 1 Функции и являются липшицевыми по £ следовательно, и по каждой из координат вектора £ при фиксированных остальных Постоянные Липшица функций РДф и по £ одинаковы и равны 2(2ру2р при 1<р<2 и 1 при 2<р<а> Постоянные Липшица для и Р^(^) по каждой из координат вектора £ при фиксированных остальных одинаковы и равны 1 при любом р , 1 <р<да

Теорема 2. Функция является липшицевой по £ следовательно, и по каждой из координат вектора £ при фиксированных остальных Постоянная Липшица функции по £ не превосходит величины 212 рУ2р | р(5)с& при ^\<р<2 и

в

1:1- \ р(5)с1з при 2<р<оо Постоянная Липшица функции Р3(() по каждой из координат в

вектора £ при фиксированных остальных не превосходит величины Ц при любом р, 1<р<ю

Можно убедиться, что функция не является липшицевой по £ Свойства р5<£) зависят от свойств функции (и, если /'будет липшицевой, тогда легко показать, что тоже липшицева Оценки постоянной Липшица лучше получать для конкретного вида {

Каждую из задач (1)-(5) можно представить как минимизацию соответствующей функции 1 <1 < 5, при условии { е Р" Построим минимальный прямоугольник О, содержащий множество 6, и пусть стороны 0 параллельны осям декартовой системы координат Можно показать, что условие Р" можно заменить на условие что эквивалентно условию с, е О, 1 < I й п Таким образом,

рассмотренные задачи (1)-(4) являются задачами минимизации липшицевых функций на параллелепипеде Установленное свойство позволяет использовать методы поиска глобального экстремума липшицевых функций для решения задач (1)-(4)

Задача (1) при р=2 и р= 1 и сводится к задаче покрытия области в л кругами (квадратами при р=1) наименьшего возможного радиуса (Указанные квадраты являются «кругами» в прямоугольной метрике) В случае произвольной /р-метрики (1<р<сг) получим что задача (1) сводится к покрытию в п «кругами» наименьшего возможного диаметра Задача (2) в случае когда определена по (3), сводится к задаче покрытия в п эллипсами (в /„-метрике) наименьшего возможного размера В

одном из фокусов эллипса будет находиться станция скорой помощи а в другом -больница в которую доставляется пациент Для решения задач (1) и (2) можно использовать алгоритм разработанный Галиевым Ш И , основанный на последовательном уменьшении размера покрывающих фигур В случае р=1 указанные задачи сводятся к задаче линейного программирования

Задача (4) при 1 5 р S х может быть решена градиентным методом в точках где градиент существует Отметим что область G - конечная Аналогично работе Дрезнера 3 приближенное решение задачи (4) при р=1 И р-ю можно найти заменив р-1 на р'= р +/ где t - малая величина а вместо р=ос выбрав достаточно большое значение так чтобы линии уровней мало отличались для любых

S Cr G Отметим что поведение линий уровней исследовано в работе Лов Р Фи Морриса Дж Г

Задача (5) в данной работе решается методом деформируемого многогранника с использованием различных исходных точек поиска, то есть методом который в глобальной оптимизации известен как мультистарт

Указанные выше подходы к решению задач (1)-(5) не гарантируют нахождения глобального экстремума Глобальный экстремум для задач (1)-(4) можно найти используя липшицевость функций можно

реализовать вложенные методы ломаных т е решить следующую задачу nun 111111 F(0 (х, у г) eD, 1S/S3, */ У/

или

nun nun nun min F,{f), (*,, у,) e D /=1,2 */ У; ** Ул

В работе аналогичным образом решена задача и для /1=3 Хотя в этом случае резко увеличивается время счета для поставленной задачи этот фактор не является критичным так как задача не предназначена для решения в режиме реального времени Когда число л больше трех, предлагается использовать метод глобальной оптимизации липшицевых функций предложенный в работе Р Хорста и П Пардалоса Обозначим решения полученные в результате глобальной оптимизации, через fy 1</<4

Может оказаться что найденные решения 1<у<4 могут быть не приемлемы например в указанных точках нельзя расположить станции скорой помощи в силу каких-либо причин Поэтому в качестве решения желательно получить не отдельную точку, а множество точек для которых значение целевой функции отличается от возможного глобального экстремума £ на допустимую величину / Решение 1<(<4 называется субоптимальным (f-субоптимагьным), если выполняется условие

Для нахождения субоптимальных областей решений предложен следующий алгоритм

Алгоритм U1

1) из каждой точки с, 1<1<п проведем к произвольных лучей L так чтобы

выпуклая оболочка произвольных точек, отличных от С, и лежащих на в качестве внутренней точки

2) на каждом луче найдем первый нуль (ближайший к точке уравнений

injx dp(s z) - F* = /', ze U - при целевой функции Fi(f),

nu\ [сЦз.г) + mm dp(sA)]- F' = /'. ze L,, - при целевой функции Ffä

| p(s) dp(s,z) ds - j p(s) rfp(s, c,') ds = г/л, ze L,/ - при целевой функции F3(Ç)

3) в случае если е„ окажется вне V, то для отрезка [с,', е„] найдем наибольший отрезок [с/, е, ] содержащийся в V, Переобозначим полученное е„ вновь как

4) построим многоугольник М, = е,1 е,2 е^ Построенные многоугольники М, составляют искомую субоптимальную область решений

Поскольку функция dp(s,z) является липшицевой то ma\ dp(s,z) также является

липшицевой Используя липшицевость функций, можно гарантированно найти требуемый первый нуль функции с помощью алгоритма предложенного Дуллиевым А М и Заботиным В И

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

(7)

Для нахождения решения задач (7) можно использовать принцип Парето

На основе установленной выпуклости функций

тах dp(s,z)t шах [с/р(5,г) + dp(s,bl)], | р(в) с^.г) (й, ге\/,

доказывается что множество оценок в пространстве критериев является выпуклым Указанное свойство позволяет строить множество эффективных (по Парето) решений Так, при л=1 множество эффективных решений для двух критериев и Рз(£), находится из решения задачи пип (Л + П-4 Ыг)),

г

при Яе(0 1) Для случая трех критериев множество эффективных решений находится из решения задачи

пип (Л, Р,(г) + Я2 ад + ()-Л,-Аг) ед), 2

при различных выбранных значениях Я,, Л? е(0,1) таких, что Л, + Я2 < 1

Во второй главе разработан метод и алгоритм нахождения функции, позволяющей вычислить расстояние между двумя произвольными точками области с учетом транспортных коммуникаций Также излагается разработанный метод автоматизации процесса снятия расстояний с карты, реализованный в соответствующем программном комплексе При введении критериев оптимизации в задачах (1)-(6) используется расстояние между обслуживающей станцией и потребителем которые в общем случае не соединены прямой дорогой Следовательно, евклидова метрика для вычисления расстояния не всегда приемлема Различные расстояния можно определить с помощью различных норм В данной работе используется взвешенная /р-норма

ч 1/р

Ip M

, Г> 0.

определяющая взвешенную (функцию расстояния) которая для

2-мерного пространства будет иметь вид

где (ха,Уа) и (хь,уь) - координаты произвольных точек а и b соответственно, a,beG При р=1 или р-2 получим соответственно прямоугольную или евклидову метрику Поскольку реальные транспортные коммуникации не образуют прямоугольную сетку, то задавая 1<р<2, можно получить функцию d^a.b), более адекватно описывающую реальные расстояния Как указано в работах Дрезнера, может бы гь

сведена к с параметром то есть параметр р ограничен интервалом

Параметры функции вычисляются исходя из следующего

критерия

т~/ т | ¡I /,. и jo ^ Ф(г,р)= 2 I B'jl -» nun,

где m - количество расчетных точек ограниченной области - реальное

расстояние (по дорогам) меаду точками а, и а; Если транспортные коммуникации в среднем имеют наклон а к осям координат, то необходимо осуществить преобразование декартозой системы, заключающееся в повороте осей на угол a Тогда функция расстояния dp(a,b) будет содержать дополнительный параметр а Процедура нахождения параметров функции расстояния состоит во вращении осей координат и одновременном расчете параметров г и р при кавдом повороте

Предлагаемая в работе методика определения функции расстояния состоит из следующих двух этапов

1) Нахождение числа расчетных точек т

Задается значение г и для к случайных наборов г точек определяются значения параметров (а/", гЛ р/"), (агт, ггт, Рг^), , («Л г/Л р/") Затем с выбранной доверительной вероятностью /?, находится интервал Г накрывающий найденные значения параметра р рГ, pi", , Ри его математическое ожидание рсрт Используя Ре,"1, находятся значения остальных параметров функции расстояний В результате получается «средняя» метрика, соответствующая найденным параметрам {асрт, гС(Л Рсрт), а также длина ^ доверительного интервала

2) Определяется степень адекватности полученной метрики реальным расстояниям области G

Для каждого из к случайных наборов г точек оценивается, насколько существенно отличается метрика («,т, ¡Л рГ), 1 </</с. рассчитанная по /-му набору точек, от «средней» метрики тсрт, prt,m) Для этого формируются и проверяются к гипотез о существенности различий /-ой метрики со «средней» метрикой

Н, а (Различие отклонений реальных расстояний от расстояний, рассчитанных по метрикам (сцт, тГ, р!") и (асЛ i"cpm, pcpm), несущественно), 1<i<k

Для проверки гипотез Hh Ник, в данной работе используется критерий согласия Смирнова при заданной доверительной вероятности /?г Обозначим через С количество принятых гипотез Вычислим долю г метрик, несущественно отличающихся от «средней» г = ^ Если длина у полученного на первом этапе

доверительного интервала удовлетворяет заданной точности и доля не меньше заданной величины л„р„т, то можно считать, что с выбранной доверительной вероятностью р2 «средняя» метрика с параметрами (а, г, р) = (асрт, гфт, рСрт) может

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

В работе предлагается следующий метод автоматизации процесса снятия расстояний с карты между произвольными точками области G Прежде всего, необходимо представить систему дорог области в виде взвешенного графа Г Вершинами графа Г будут являться перекрестки дорог, весами дуг - длины дорог между перекрестками После задания графа Г необходимо случайным образом сгенерировать координаты точек вызовов В общем случае эти точки не совпадут с имеющимися вершинами графа Рассмотрим любые две из сгенерированных точек, например, а< и а2 Чтобы вычислить длину минимального пути между точками а, и а2, необходимо

1) определить направление, в котором располагается точка а2 относительно точки а, В прямоугольной метрике найти ближайшую вершину V к точке а» по найденному направлению графа Г,

2) аналогично найти ближайшую вершину и/для точки эг.

3) найти длину Я кратчайшего пути мевду вершинами V и V/ в графе Г и вычислить величину 11 + (^(а^) + (^(аг.м)

В большинстве случаев невозможно проехать напрямую от точки V (перекрестка дорог) до произвольной точки а1 В то же время часто можно проехать этот путь по ломаной, смежные части которой в большинстве случаев перпендикулярны друг другу Поэтому в данной работе для расчета расстояний от а» до V и от а2 до IV принята прямоугольная метрика

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

Третья глава посвящена исследованию свойств бисекторов, областей Вороного для отдельных точек и пар точек в различных /р-метриках В задачах (2) и (5) необходимо учитывать доставку пациента в больницу, в этом случае возникает задача определения бисекторов пар точек В работе рассмотрены бисекторы и области Вороного для множества пар точек при различных /р-метриках, а также установлены некоторые свойства эллипса в /р-метрике

Областями (многоугольниками) Вороного совокупности точек {с,, 1 <1 ¿п) являются множества

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

Для исследования видов бисекторов многоугольников используется понятие «квазирасстояния» Квазирасстояния в частном случае совпадают с расстояниями, вводимыми через I, Пусть дана точка с (сеР), целое число т {т>2), ненулевые числа Ьи Ь2, , Ьт и различные п р й,, й2, ы , ё?т с общей точкой пересечения в точке с, у, - угол мевду Я, и прямой проходящей через точки в и с, а метрика в пространстве является евклидовой Квазирасстоянием 0(э,с) между точками s и с называется величина равная

0(5,с) = £ Ь, Ь^.Я) Ь,</2(з,с) эт л = сЫ5,с)]Т Ь, апр, (8)

здесь dj(s,f?i) - евклидово расстояние от точки до прямой Пусть дано положительное число А, а числа bu bj, ..., bm удовлетворяют условию (8) Множество точек s втаких, что

называется D-многоугольником размера А с диагоналями Rj, Rp.....Rm.

Бисектором B(c,,Cj) двух точек С,, Су называется множество точек s плоскости Р, таких, что.

B(c,,cJ -{seP: D(s,c,) = D(s,c,)}

В работе доказаны следующие вспомогательные утверждения

Лемма 2 Для любой SeP, D(S,c) положительна тогда и только тогда, когда

для каждого i, 1 </<m, имеем: m

V, = £ b„ sinЫ > О,

где - угол между прямыми

Теорема 3 Каждый центросимметричный многоугольник К" с центром в точке с, т диагональными линиями R» и вершинами v«, VheR, 1< к < m, может быть представлен следующим образом

K = {seP : D(s,c) £ max d2(Vi,,c)), l<k<m

где D(S,C) определено по (8) с некоторыми ненулевыми коэффициентами Ь„ 1<7 <Ш.

На основе доказанных утверждений исследованы свойства областей Вороною для отдельных точек Пусть frG - граница множества G. Области Вороного обладают следующими свойствами

2) max min D(s,c,) = max max Dfs.cJ;

3) если равные выпуклые D-многоугольники Kj, 1 <j < Л, образуют покрытие множества G, то VjçKj, 1</<П;

4) если G - многоугольник, то границей каждой области У,, 1 <;' <п, является ломаная линия Точки излома ломаной frVj называются вершинами области Vf

5) если G - многоугольник, то замкнутый выпуклый D-многоугольник покрывает область Ц тогда и только тогда, когда К, покрывает все вершины vf области

Для исследования бисекторов и областей Вороного для пар точек в различных в работе доказаны ряд утверждений

Бисектором двух пар точек называется геометрическое место

точек s плоскости Р, сумма расстояний от которых до точек fn и ^г равна сумме расстояний от s до и до /гг. т.е. ;

В„ = {seP: d0 (s, f„) + d„ (s, f12) = d„ (s, Гц) + dp (s, f22)}.

Пусть задано множество пар точек {(ft1, 1 <i<n) Областью Вороного V, пары

точек ff,i, f,2) называется геометрическое место точек s плоскости Р, сумма

расстояний от которых до (п и ДО А,г не превосходит любой суммы расстояний до f,i И

до/¡г. 1 т е :

V, = {seP: dp (s, i,,j + d„ (s, f,-J < min [ dp (s. f„) + d„ (s, fl2) ]}. /s)sn

Рассмотрим общий случай, когда точки fu, fu, hi и не лежат на одной прямой, параллельной оси ох либо оси оу (рис. 1а) Построим минимальный

прямоугольник Яц, содержащий все точки Ац, /г» И ^22, стороны которого

параллельны осям ох и оу Также построим минимальные прямоугольники Я), содержащий точки (ц и ^г, и Яг, содержащий точки И Ггг, стороны этих прямоугольников также пусть будут параллельны осям ох и оу Обозначим через Р, периметр прямоугольника Я,, /=1,2 Если прямоугольник Я вырождается в отрезок, то периметр R полагаем равным удвоенной длине отрезка

В работе исследуется вид бисектора при различных положениях двух пар точек в /р, 0<р<у~, определяются условия существования и вид двумерных областей бисектора, определяется их количество, условия совпадения бисектора со всей плоскостью, а также связь между бисекторами двух точек и двух пар точек

В результате исследований сформулированы и доказаны следующие утверждения для р=1

Лемма 3 Если вершина v прямоугольника Яц является точкой бисектора В), то V принадлежит двумерной неограниченной части (О) ИЛИ Ог на рис 1а) бисектора Ви образованной продолжениями смежных сторон прямоугольника Яц, проходящих через точку V

Теорема 4 Если периметры прямоугольников Я^ И Я; равны И Я - Я] П Яг* 0 (см рис 1а), то Я является частью бисектора В(, а (Я-! и Яг) \ (Я\ I"! "г) — не является Если какая-нибудь из границ Я, например дЬ, принадлежит границе Яц (см рис 16), то внешние перпендикуляры к границе Яц, проведенные в точках д и /1 соответственно, ограничивают бесконечную двумерную область бисектора

На рис 1а)бисектор 8» состоит из отрезков аЬ, сс1 и двумерных областей Я, 0| и О? На рис 16) бисектор состоит из ломаных аЬс, def и двумерной заштрихованной части Из теоремы 4 следует, что, если прямоугольники Я< и Яг совпадают, при этом лежат в диаметрально противоположных вершинах, а в двух

а) б)

Рисунок 1

Теорема 5. Вершина V прямоугольника Я,г является точкой бисектора В, тогда и только тогда, когда выполняется равенство

2 б, (V, Я,) + ' Р, = (1, (V, Яг) + 1 Рг,

здесь с/, (V, Я,) - расстояние от точки V до прямоугольника Я,, а Р, - периметр прямоугольника Я,, 1=1,2

Теорема 6. Если центры прямоугольников R1 и R¡ совпадают, а * то бисектор 81 содержит четыре бесконечные двумерные области, ограниченные продолжениями смежных сторон прямоугольника Я^г Если центры прямоугольников К) и Яг совпадают, а Л) * и Я» с Я; либо с (см рис 2а), то бисектор В» состоит из четырех двумерных областей указанного вида

а) 6)

Рисунок 2

На рис 2а) бисектор Bt состоит из двумерных областей D¡, D¡, D3 И D<

Теорема 7 Внутри Rj2, НО вне R-RiO, R2, если существует бисектор В1, то он является ломаной линией (например, см рис 26)

Пусть с, - центр найденного прямоугольника R,, 1=1,2 Построим минимальный прямоугольник R' содержащий точки Ct и Сг, такой, что стороны R' параллельны осям ох и оу

Теорема 8. Пусть центры прямоугольников Ri и R¡ расположены так, что R -квадрат (см рис 26), тогда бисектор fij содержит точно две двумерные бесконечные области, ограниченные продолжениями смежных сторон прямоугольника Rn и начинающиеся в диаметрально противоположных вершинах Rj2

На рис 26) кроме двух бесконечных областей, бисектор В, содержит ломаные abcde и fghij

Теорема 9 Пусть Bi - бисектор точек Ci И Сг, являющихся центрами прямоугольников Ri И R¡ соответственно, Cj * Сг И 81 - бисектор пар точек (fu, fu) и (fu, Ы- Тогда

1) Bi" содержит две двумерные бесконечные области, ограниченные сопряженными сторонами прямоугольника тогда и только тогда, когда содержит точно две двумерные бесконечные области, ограниченные сопряженными сторонами прямоугольника Rui

2) если fl, содержит два неограниченных параллельных луча Li И £.2, не содержащихся в двумерных частях и направленных в разные стороны, тогда содержит два неограниченных параллельных луча L¡ И L2 таких, что Li И ¿.2 направлены в разные стороны, параллельны между собой и параллельны

Таким образом, в частных случаях знание бисектора B¡ точек Cj и Ci (центров соответственно) позволяет делать вывод и виде бисектора пар точек

В работе исследован вид бисектора при различных положениях двух пар точек в метрике бисектор состоит не из ломаных

линий, как в случае а из кривых, повторяющих в некоторой степени поведение

ломаных при /) Для некоторых возможных положений пар точек (fu, f<2) И (fu, fe)

бисекторы Вр 1<р<ос представлены на рис 3 где также изображены и бисекторы в, для тех же пар точек

а] Рисунок 3 б)

На рис За) для р-1 2 бисектор Вр отображен сплошной линией ßf 2 состоит из двух кривых abc и def, разграничивающих области Вороного V, (внутри кривых) и V2 (вне их) При увеличении р, 1<р<ж бисектор Вр остается примерно таким же При р-1 бисектор состоит из четырех двумерных (заштрихованных) областей Dj, D¡ D¡ и D4

На рис 36) бисектор 8< состоит из ломаных abc, def vi двумерной части R = R, п R¡ Бисектор Вр для 1<p<œ будет кривой На рис 36) приведена сплошная линия бисектора ВР для р=1 2, которая повторяет в некоторой степени поведение ломаной abcdeg

В работе исследован вид бисектора при различных положениях двух пар точек в /р, 0<р<1 Если 0<р<1, то бисектор состоит из кривых, совпадающих с кривыми бисектора при 1 <р<®, и кривых, близких по виду к границам двумерных бесконечных частей бисектора при р=1 Например, на рис За) бисектор Boa представлен в виде шести разрывных (штриховых) кривых Для случая расположения пар точек, как показано на рис 36), бисектор Вр для р=0 8 изображен штриховой линией, причем при х<0 бисектор Во в состоит из трех линий

Для метрики U построение и виды бисекторов пар точек аналогичны случаю для метрики /j с разницей в том, что при построении бисекторов используются не прямые, параллельные осям координат как при р=1, а биссектрисы первого и второго координатных углов

В работе исследованы бисекторы «специальных» пар точек Пусть заданы точки с( и с2, множество точек B={bt, b¿, , b,} и его подмножества В, и В2 «Специальной» парой точек для фиксированной seP является пара, первыми элементами которых являются с( или с2, а вторые элементы выбираются из множества В одним из следующих способов

1) b¡(S)£B таково, что

dp(s,b,(S)) = min dp(s,bk), 1<к<п

2) b,;, s) eB таково, что dp(s,blt,si) = min dpfs.bk)

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

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

Доказаны следующие теоремы.

Теорема 10. При выборе вторых элементов пар точек по способу 1) бисектор Bp, 1 <р<®, пар точек не зависит от вторых элементов пар и совпадает с бисектором двух точек с, и сг.

Теорема 11 Пусть ß,o В2=В*0 и Вр, 1 <р<ъэ, - бисектор пар точек с первыми элементами с, или с2, а вторые элементы этих пар выбираются по способу 2) Положим В'р - часть Вр такая, что для любой se В'9 ближайшими точками из В„ 1 </ <2, являются точки из В'. Тогда ß'p содержится в бисекторе двух точек cf и с2, то есть не зависит от вторых элементов пар.

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

1. Объединение областей Вороного для всех станций с,, 1 <1<п, представляет собой всю рассматриваемую область обслуживания.

2. Если р*1 и рл», /и пары (fl1f f,2) и (f,b fl2) таковы, что среди f,,, fl2, f,i, fl2 имеется по крайней мере три различных точки, то множество Vn V, имеет нулевую площадь.

3. При р=1 и р=х> границами областей V, являются отрезки прямых, параллельных осям координат, либо образующие угол 45° с осью абсцисс.

Знание бисекторов для р<1 позволяет дополнять бисекторы для р>1 и описывать границы двумерных частей бисекторов для р=1.

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

Обобщенная методика решения задачи размещения станций скорой помощи в работе представлена в виде блок-схемы, представленной на рис. 4. На основании найденных решений задач (1)-(5), областей субоптимальных решений, а также построенного множества Парето-эффективных решений задач (1)-(5), ЛПР может сделать окончательный выбор решения.

На основе приведенной обобщенной методики разработан программный комплекс для решения задачи. Для разработки использовались среда DELPHI 5 и СУБД DBASE. Структура программного комплекса включает в себя три основных модуля, реализующих: 1) автоматическое вычисление по карте кратчайших расстояний; 2) расчет параметров метрики; 3) решение задачи оптимизации.

Рисунок 4

С помощью программного комплекса получены некоторые численные решения задачи На рис. 5а) приведены примеры решений, полученных отдельно для задач (1) и (4), области субоптимальных решений, а также множество решений, оптимальных по Парето Решение, полученное при р=1 для задачи (1) (критерия Р,(£)) отмечено точкой С, а для задачи (4) (критерия Р3(£)) - отрезком [вда, ¿<и] Области субоптимальных решений по критерию обозначены многоугольниками, а по критерию - областями в) и 52. В табл 1 приведены значения отклонений критериев от оптимальных значений

Таблица 1

При расположении с» Отклонение критерия Fi от минимального значения не более чем на, % Отклонение критерия Fj от минимального значения не более чем на, %

на отрезке [Roo, Roí] 3.4

Внутри области RuR^RuRu 10.3

Внутри области Яг)Я2гЯ23Я?г.( 17.2

Внутри области RnRsiRuRu 27 5

Внутри области Sj 3.2

Внутри области S¡ 8.1

Рисунок 5

Анализ результатов показывает, при р=1 наиболее предпочтительно расположение в точке или внутри пересечения области и области

Ни- При использовании /0-метрики (с параметрами а=85°, 1=1.03, р=1.416) по критерию '"((О оптимальное расположение станции - в точке Ей а по критерию — в точке Е?. При этом множество решений, оптимальных по Парето, представляет собой кривую, соединяющую точки Е1 И Ег и изображенную на рис. 5а) штриховой линией.

На рисунке 5б) приведены решения для задачи (2) (по критерию для

района Азино, в двух вариантах: 1) доставка пациента в дежурную больницу; 2) доставка пациента в ближайшую больницу. Для варианта 1 при расположении больницы в точке Ьг'(Ь)г, Ь)3) оптимальное расположение станции скорой помощи

находится в точке сДсД стэ) Для 2-го варианта когда необходимо доставить пациента в ближайшую из больниц Ь/, Ь^2, Ь) , станцию скорой помощи оптимально разместить в точке С)

При использовании критерия решение будет зависеть от величины

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

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

Основные результаты работы

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

2 Исследованы математические модели оптимизации т-центров и т-медиан доказана липшицевость критериальных функций и найдены постоянные Липшица для них

3 Предложена методика определения параметров метрики базирующаяся на проверке ряда гипотез и позволяющая оценивать реальные расстояния области с заданной степенью точности

4 Выявлены вид и свойства бисекторов и областей Вороного для пар точек в различных /р-метриках

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

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

7 Предложен метод решения задачи размещения станций скорой помощи с учетом многокритериальности

8 Разработан программный комплекс, реализующий методики и алгоритмы решения поставленной задачи для произвольной ограниченной многоугольной области й

9 Получены оптимальные расположения станций скорой помощи для некоторых районов г Казани, получены значения параметров метрик для отдельных частей г Казани и всего г Казани, а также для ряда городов Республики Татарстан Набережные Челны, Альметьевск, Нижнекамск

Основное содержание диссертации изложено в следующих публикациях

1 Галиев Ш И , Разина М А Упаковки и покрытия ограниченной области центросимметричными многоугольниками // Вестник КГТУ им Туполева - 2003 -№2 - С 34-40

2 Емалетдинова Л Ю , Галиев Ш И , Разина М А Рафиков М М , Контри РФФ, Гаргану Ф Использование непрерывных моделей для оптимизации расположения станций скорой помощи // Вычислительная механика и современные прикладные программные системы Тезисы докладов ИХ Международной конференции 30 июня - 5 июля 2003 г -Владимир, 2003 - С 266-267

3 Емалетдинова Л Ю , Галиев Ш И , Разина М А , Рафиков М М , Контри РФФ, Гаргану Ф Оптимизация расположения станций скорой помощи для

обслуживания населения заданной области // Догоспитальный этап медицинской помощи традиции и стереотипы Материалы 4-го Российского научного форума 20 -23 октября 2003 г - Москва 2003 - С 48-49

4 Разина М А Алгоритмы и программы для оптимизации расположения станций скорой помощи // Математические методы и информационные технологии з экономике, социологии и образовании Тезисы докладов II! Всероссийской научно-технической конференции 19-20 декабря 2003 г - Пенза, 2003 - С 288-290

5 Галиев Ш И , Емалетдинова Л Ю , Разина М А Оптимизация расположений подстанций скорой помощи Отчет о НИР / Казан гос технич ун-т - ПМ7-СМ-1, № Госрегистрации 01 2 00316705 Инв № 02 20 0307056 -Казань 2003 -26 с

6 Contn R F F , Gargano F , Emaletdinova L lu , Gahev Sh I , Raz'na M A , Rafikov M Aplicacao de Modelos Continuos para Otimizacao de Localizacoes das Estacoes de Pronto Socorro // Anais do XXVI Congresso Nacional de Matematica Aplicada e Computacional 8-11 de septembro 2003 - Sao Jose do Rio Preto (Brasil), 2003 - P 114

7 Разина М А Емалетдинова Н Ю Решение задачи оптимизации размещения станций скорой помощи для некоторых районов г Казани // Интеллектуальные системы управления и обработки информации Тезисы докладов Всероссийской молодежной научно-технической конференции с международным участием 3-4 декабря 2003 г - Уфа, 2003 - С 113

8 Галиев Ш И Емалетдинова Л Ю , Разина М А Задачи размещения станций скорой помощи и методы их решения // Новые медицинские технологии в охране здоровья здоровых, в диагностике лечении и реабилитации больных Материалы II Международной научно практической конференции 25-26 марта 2004 г - Пенза 2004 -С 121-124

9 Галиев Ш И , Емалетдинова Л Ю , Разина М А Нахождение глобального экстремума и субоптимальных решений для задач размещения станций скорой помощи // Вестник КГТУ им Туполева - 2004 - №3 - С 40-45

10 Емалетдинова Л Ю Разина М А Подбор метрики для оценки расстояний в городе // Математические методы и информационные технологии в экономике социологии и образовании Тезисы докладов XIV Международной научно-технической конференции 20-21 декабря 2004 г - Пенза, 2004 - С 355-358

11 Галиев Ш И Разина М А Области Вороного в Lp-метрике для совокупности заданных пар точек//Вестник КГТУ им Туполева -2004 - №4 -С 19-26

12 Галиев ШИ Емалетдинова ЛЮ, Разина МА Применение методов глобальной оптимизации липшицевых функций для решения задач размещения станций скорой помощи // Системный анализ в проектировании и управлении Тезисы докладов VIII Международной научно-практической конференции 22-24 июня 2004г - Санкт-Петербург, 2004 -С 177-179

Автор выражает глубокую благодарность доктору технических наук профессору Емалетдиновой Лилии Юнеровне за многочисленные научные консультации и организационную помощь при решении задач данной работы

Формат 60x84 1/16 Бумага офсетная Печать офсетная Печ.л1,25 Усл.печ.л 1,16 Усл кр-отт 1,16 Уч-изд.л 1,0

Тираж 100 Заказ Е70._

Типография Издательства Казанского государственного технического университета 4200111, Казань, К Маркса, 10

05-ü -OS. Ii

915

Введение.

Глава 1 Математические модели задачи размещения и их свойства.

1.1 Постановка задачи размещения.

1.2 Модель n-центров, свойства модели.

1.3 Модель n-медиан, свойства модели.

1.4 Метод решения задачи размещения с использованием одного из критериев.

1.5 Нахождение субоптимальных решений.

1.6 Многокритериальный подход к решению задачи оптимизации расположений.

Выводы.

Глава 2 Метод подбора метрики для оценки расстояний.

2.1 Теоретические аспекты определения функции расстояний.

2.2 Метод определения числа необходимых точек.

2.3 О снятии с карты расстояний между точками.

I*. ■

2.4 Алгоритм расчета метрики.

Выводы.

Глава 3 Бисекторы и области Вороного.

3.1 Бисекторы и области Вороного.

3.1.1 Центросимметричные многоугольники.

3.1.2 Бисекторы.

3.1.3 Области Вороного и их свойства.

3.2 Бисекторы и области Вороного двух пар точек.

3.2.1 Эллипсы в 1Р-метрике.

3.2.2 Бисекторы и области Вороного двух пар точек.

3.2.3 Бисекторы двух пар точек в Ц.

3.2.4 Бисекторы пар точек в 1Р, 1<р<оо.

3.2.5 Бисекторы для 1Р, 0<р<1.

3.2.6 Бисекторы пар точек в 4,.

3.2.7 Бисекторы специальных пар точек.

3.2.8 Свойства областей Вороного.

Выводы.

Глава 4 Алгоритмическое и программное обеспечение решения задачи.

4.1 Обобщенный алгоритм решения задачи.

4.2 Программное обеспечение решения задачи.

4.3 Пример решения задач.

4.3.1 Пример расчета метрик.

4.3.2 Решение задачи для района Азино г.Казани.

4.3.3 Решение задачи для Ново-Савиновского вместе с Московским и частью Кировского районов г. Казани.

Выводы.

Основные результаты, полученные в диссертации.

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

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

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

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

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

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

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

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

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

Первая работа по задаче расположения была исследована в 1909 году Альфредом Вебером [87], который исследовал расположение склада для обслуживания потребителей с известными координатами и потребностями в материале, хранящемся на складе. Далее Купер рассмотрел обобщение этой задачи [55].

В настоящее время существует множество работ, посвященных задаче расположения станций обслуживания. Имеются различные модели их исследования, такие как: модели л-центров (minimax модели); модели л-медиан (minisum модели); вероятностные модели; модели теории массового обслуживания; и другие.

Каждая из рассматриваемых в работе постановок задач порождает задачи нелинейной оптимизации, в частности, минимаксные и минимаксиминные. Задачи такого типа исследованы многими авторами: Демьянов В.Ф., Васильев Л.В. [14], Васильев Ф.П. [1], Федоров В.В. [43], Кларк Ф. [28], Михалевич B.C., Гупал A.M., Норкин В.И. [34, 35], Поляк Р.А. [78], Заботин Я.И. [24, 25], Коннов И.В. [30-32] и другими.

В обзоре Брандо M.J1. и Чина С.С. [50] указано более 50 различных моделей, используемых для решения задач выбора расположения станций обслуживания.

Принципиальные результаты о моделях и методах их решения представлены в работах Дрезнера 3. [57], Лов Р.Ф., Морриса Дж.Г. [72], Михалевича B.C., Трубина В.А., Шора Н.З. [35], в статьях [64, 58, 47, 54, 56, 60, 79, 62, 68, 69], см. также указанный выше обзор [50] и библиографии в [57, 35, 72]. Имеются специальные выпуски журналов, такие, как «Location Science» [64] и другие, целиком посвященные этим задачам.

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

Для непрерывных моделей, как правило, нельзя использовать методы, разработанные для дискретного случая. Здесь разработаны свои методы, например, методы недифференцируемой оптимизации [1, 36, 17, 42].

Для решения задачи оптимизации расположения станций обслуживания важно уметь находить глобальный экстремум целевых функций. Существуют различные методы нахождения глобального экстремума, см., например, работы Жиглявского А.А., Жилинскаса А.Г. [22, 23], Хорста Р., Пардалоса Р., Туи Г. [65, 66] и др. Среди различных методов глобальной оптимизации одними из важных являются методы, использующие липшицевость функции.

При введении критериев оптимизации в той или иной мере используется расстояние между обслуживающей станцией и потребителем. Вводимые расстояния зависят от многих факторов. Например, в городе из точки А до точки В не всегда можно проехать по соединяющей их прямой. Следовательно, евклидово расстояние не всегда приемлемо. Различные расстояния можно определить с помощью различных норм. Как известно, норма ||х|| элемента х из действительного N-мерного пространства RN удовлетворяет следующим трем условиям: х|| > 0 для VxgRn, ||х|| = 0 тогда и только тогда, когда х = 0; с • х|| = |с| • ||х|| для VxeRN и се(-оо,со); х + у|| = ||х|| + ||у|| для V^yeft*'- неравенство треугольника.

Пусть V- единичный «шар» в Ft1:

V={xeRN: ||х||<1},

По свойствам этого «шара» выделяют круговые и блок нормы. Норма 11-11 считается круговой тогда и только тогда, когда: лz1 + (^-л)z2\\<^, (1) для V Zj, z2 е frV, zf * z2 и VA g (0,1), здесь frV-граница множества V.

Блок нормы вводятся как нормы, единичный «шар» V для которых является выпуклым многогранником в RN (в R2 выпуклым многоугольником). Для блок норм в (1) нужно заменить неравенство «<» на «<».

В работе [86] показано, что блок нормы в R2 можно определить как:

I|Z||= z I(y/,Z)|, (2) j=i где { у/, j = 1,2,.,/77} - множество векторов, z = (х,у), у/- транспонированный вектор у;, (у/, z) - скалярное произведение.

В данной работе запись (2) заменяется на эквивалентную форму: т z||= z b;d2(z,Rj), (3) j=1 где bj - положительные числа, Rj - различные прямые, проходящие через начало координат, a d2(z, Rj) - евклидово расстояние от точки z до прямой Rj.

Известно [83], что блок нормы плотны в множестве всех норм в R". Использование блок норм во многих случаях позволяет свести задачу оптимизации расположения станций обслуживания к задаче линейного программирования. Исходя из указанного, блок нормы играют большую роль при решении задачи расположения. Поэтому в данной работе рассматриваются блок нормы, исследуются порождаемые ими бисекторы и области Вороного при заданных блок нормах.

Если в (3) допустить, что коэффициенты Ь; могут быть и отрицательными, то получим, что множество V, определяемое функцией || z ||, уже не будет выпуклым. Для подобного случая получены необходимые и достаточные условия того, что эта функция будет гипер-прямоугольной нормой, для которой выполняются первые два свойства нормы, но не выполняется неравенство треугольника. Введенные с помощью таких норм «расстояния» позволяют рассматривать задачи, в которых обходной путь лучше кратчайшего пути. Такие случаи возникают, если учитывается загруженность дорог, количество пробок на кратчайших путях.

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

Как известно, /р-норма вектора х с N координатами х„ 1<i<N, вводится следующим образом: N

W =

H\xi р i=l р> 1. Отметим, что вместо 1р(х) часто используется запись || х ||р.

При р= 1 эта норма называется прямоугольной (или манхэттенской), для р=2 получаем евклидову норму, а при р=оо получаем чебышевскую норму:

Цх) = max (|х,|, \х2\.|xw|).

Расстояния (метрики), вводимые по этим нормам, считаются соответственно прямоугольными (манхэттенскими), евклидовыми и чебышевскими. В общем случае метрика, соответствующая /р-норме, считается /р-метрикой.

В литературе по оптимизации расположений метрика, вводимая по 1Р-норме, обозначается как /р-метрика, см., например, работы [59, 74, 83, 86], и как Lp-метрика - см., например, работы [70, 71, 81]. Учитывая, что обозначение «Lp-пространство» в функциональном анализе используется в ином смысле (как множество абсолютно интегрируемых функций), в данной работе будем использовать обозначение «/р-метрика».

При исследовании задач расположения станций обслуживания в городах часто используется прямоугольная метрика. Для более точного решения этих задач Ward и Wendell [86] ввели в R2 норму, представимую в виде: cci\\ х + a24l || X |U а{> 0, а2>0, а^ а2> 0, то есть представимую как некоторую линейную комбинацию прямоугольной и чебышевской нормы. В дальнейшем было выяснено, что эта норма является частным случаем блок нормы. Таким образом была еще раз подтверждена важность блок норм.

Важную роль в исследовании задач расположений играют взвешенные /р-нормы, введенные Лов Р.Ф. и Моррисом Дж.Г. в работах [73, 74]. Указанные нормы получаются умножением /р-норм на весовой коэффициент г, г>0.

Нормы можно также классифицировать на дифференцируемые и недифференцируемые. Установлено (см., например, [57]), что /р-нормы при

1 <р<со являются дифференцируемыми почти всюду. Блок нормы не являются дифференцируемыми.

В [76] Лов Р.Ф. и Уолкер Дж.Х. показали, что взвешенные /р-нормы более предпочтительны, чем блок нормы, так как дают более точные результаты. Таким образом, блок нормы позволяют иногда проще решать задачу, а взвешенные /р-нормы дают лучшее решение. Исходя их этого в данной работе используются как блок нормы, так и взвешенные /р-нормы.

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

Положим, задана совокупность точек {сь с2, сп} в FP и введено некоторое расстояние d(a,b) между точками а и Ь. Многогранником (многоугольником в R2) Вороного называется множество:

Vj = {xeRn: d(x,Cj) < min d(x,Cj)}, 1 <j<n.

1 <i<n

Эти множества для евклидового расстояния ввел Г.Ф. Вороной при изучении свойств полиэдров, а также при построении квадратичных форм. Иногда эти множества называют многоугольниками (ячейками) Дирихле, многоугольниками Тиссена, ячейками Вигнера-Зейтца, а также многоугольниками близости. Совокупность многогранников (многоугольников) Вороного называется диаграммой Вороного. Для евклидовой метрики многогранник (многоугольник) Вороного образуется пересечением полуплоскостей и может быть ограниченным многогранником (многоугольником для R2) или бесконечной областью, ограниченной гиперплоскостями. При использовании прямоугольной метрики области V, также представляют собой ограниченные многогранники или бесконечные области, ограниченные гиперплоскостями. Если метрика отлична от прямоугольной и евклидовой, то V„ как правило, ограничены не плоскостями (прямыми в R2), а достаточно сложными поверхностями. Поэтому можно говорить об областях Вороного.

Построение областей Вороного является нетривиальной задачей. Имеется много работ по построению диаграмм Вороного. Так, например, в работе [80] разработан алгоритм построения этих диаграмм для точек на плоскости (при евклидовой метрике) со сложностью 0(п \одп).

Диаграммы Вороного в R2 для метрик 1-, и 1„ исследованы в работах [70,

71]. В работе [71] рассмотрены некоторые проблемы построения диаграмм Вороного для метрик 1Р, р> 1.

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

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

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

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

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

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

В первой главе введены критерии оптимизации и рассмотрены модели ^-центров и я-медиан. Выведены следующие свойства моделей:

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

2) найдены постоянные Липшица целевых функций моделей л-центров и л-медиан как по всему вектору переменных, так и по каждой их координат при фиксированных остальных.

Предложены следующие методы.

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

2. Построения областей субоптимальных решений.

3. Нахождения решений задач с учетом многокритериальности.

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

1). Нахождение числа расчетных точек т.

2). Определение степени адекватности полученной метрики реальным расстояниям области G.

Также в главе изложен разработанный метод автоматизации процесса снятия расстояний с карты.

Третья глава посвящена исследованию бисекторов и областей Вороного. Введены и указаны некоторые свойства эллипса в /р-метрике.

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

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

2. Выявлено, что в 1Р, 1 <р<оо бисектор состоит не из ломаных линий, как в случае 1Ь а из кривых, повторяющих в некоторой степени поведение ломаных при Ц.

3. Если 0<р<1, то бисектор состоит из кривых, совпадающих с кривыми бисектора при 1 <р<оо, и кривых, близких по виду к границам двумерных бесконечных частей бисектора при р=1.

4. В too построение и виды бисекторов пар точек аналогичны случаю для

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

Доказаны некоторые свойства областей Вороного для пар точек.

1. Объединение областей Вороного представляет собой всю рассматриваемую область обслуживания.

2. При ртЛ и р^оо множество Vf\ V, имеет нулевую площадь, если />/ и пары точек таковы, что среди всех четырех точек имеется по крайней мере три различных точки.

3. При р=1 и р-оо границами областей V/ являются отрезки прямых, параллельных осям координат, либо образующие угол 45° с осью абсцисс.

Знание бисекторов для р< 1 позволяет в некоторой степени дополнять бисекторы для р>1 и описать границы двумерных частей бисекторов для р=1.

В четвертой главе приведено методическое и алгоритмическое обеспечение решения задачи оптимизации расположения станций скорой помощи. Описан программный комплекс «Решение задачи расположения», программная реализация его модулей. Кроме того, в этой главе приведены оптимальные расположения станций скорой помощи для некоторых районов г.Казани, получены значения параметров метрик для отдельных частей г.Казани и всего г.Казани, а также для ряда городов Республики Татарстан: Набережные Челны, Альметьевск, Нижнекамск.

Основные результаты работы опубликованы в [6-9, 11, 12, 19-21, 40, 41,

Основные результаты, полученные в диссертации

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

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

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

4. Выявлены вид и свойства бисекторов и областей Вороного для пар точек в различных ^-метриках.

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

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

7. Предложен метод решения задачи размещения станций скорой помощи с учетом многокритериальности (для случая одной станции).

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

9. Получены оптимальные расположения станций скорой помощи для некоторых районов г.Казани, получены значения параметров метрик для отдельных частей г.Казани и всего г.Казани, а также для ряда городов Республики Татарстан: Набережные Челны, Альметьевск, Нижнекамск.

1. Васильев Ф.П. Численные методы решения экстремальных задач. М: Наука, 1980.-520 с.

2. Вентцель Е.С. Теория вероятностей . М.: Наука, 1964. - 576 с.

3. Галиев Ш.И. Максимин, задачи покрытий и упаковок. Казань: Изд-во Казан, гос. технич. ун-та, 1997. - 260 с.

4. Галиев Ш. И. Направления убывания для минимаксных задач // Журнал вычислительной математики и математической физики. 1993. - т.ЗЗ, №1. - С.19-28.

5. Галиев Ш. И. Направления убывания для минимаксиминных задач // Журнал вычислительной математики и математической физики. 1994. -т.34, №3. - С.323-343.

6. Галиев Ш.И., Емалетдинова Л.Ю., Разина М.А. Нахождение глобального экстремума и субоптимальных решений для задач размещения станций скорой помощи // Вестник КГТУ им. Туполева. 2004. - №3. - С.40-45.

7. Галиев Ш.И., Емалетдинова Л.Ю., Разина М.А. Оптимизация расположений подстанций скорой помощи: Отчет о НИР / Казан, гос. технич. ун-т. ПМ7-СМ-1; № Госрегистрации 01.2.00316705; Инв.№ 02.20.0307056. - Казань, 2003. - 26 с.

8. Галиев Ш.И., Заботин В.И. О непрерывном обзоре поверхности Земли // Исследование Земли из Космоса. 1983. - №1. - С.117-120.

9. Галиев 111.И., Разина М.А. Области Вороного в Lp-метрике для совокупности заданных пар точек // Вестник КГТУ им. Туполева. 2004. -№4.-С. 19-26.

10. Галиев 111.И., Разина М.А. Упаковки и покрытия ограниченной области центросимметричными многоугольниками // Вестник КГТУ им. Туполева. -2003. №2. - С.34-40.

11. Галиев Ш.И., Сатаров А.З. Задачи размещения станций скорой помощи с использованием непрерывных моделей // Вестник КГТУ им. А.Н.Туполева. 1996. - №4. - С.39-44.

12. Демьянов В.Ф., Васильев J1.В. Недифференцируемая оптимизация. М.: Наука, 1981.-384 с.

13. Дубов Ю.А., Травкин С.И., Якимец В.Н. Многокритериальные модели формулировки и выбора вариантов систем. М.: Наука, 1986. - 296 с.

14. Дуллиев A.M., Заботин В.И. Итерационный алгоритм проектирования точки на невыпуклое многообразие в линейном нормированном пространстве // Журнал вычислительной математики и математической физики. 2004. - т.44, №5. - С.827-830.

15. Евтушенко Ю.Г. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) // Журнал вычислительной математики и математической физики. 1971. — т. 11, №6. - С.1390-1403.

16. Емалетдинова Л.Ю., Валитова Н.Л., Разина М.А. Проектирование информационного и программного обеспечения автоматизированных информационных систем: Учебное пособие. Казань: Изд-во Казан, гос. технич. ун-та, 2004 г. - 105 с.

17. Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремума.- М.: Наука. Гл. ред. физ.-мат. лит., 1991.- 248с.

18. Жилинскас А.Г. Глобальная оптимизация. Аксиоматика статистических моделей, алгоритмы, применения / Ин-т математики и кибернетики АН ЛитССР. Вильнюс: Мокслас, 1986. - 168с.

19. Заботин Я.И., Крейнин М.И. К сходимости методов отыскания минимакса // Известия ВУЗов. Математика. 1977. - №10. - С.56-64.

20. Заботин Я.И., Фукин Н.А. Алгоритм в методе штрафов с аппроксимацией допустимого множества // Известия ВУЗов. Математика. 2004. - №1. -С.36-47.

21. Кант В.И. Математические методы и моделирование в здравоохранении.- М.: Медицина, 1987. 224 с.

22. Кини Р.Л., Райфа X. Принятие решений при многих критериях: предпочтения и замещения. М.: Радио и связь, 1981. - 560 с.

23. Кларк Ф. Оптимизация и негладкий анализ. М.: Наука, 1988. - 280 с.

24. Кожевников Ю.В. Теория вероятности и математическая статистика: учебное пособие для вызов. М.: Машиностроение, 2002. - 416 с.

25. Коннов И.В. Комбинированный релаксационный метод для поиска векторного равновесия // Известия вузов. Математика. 1995. - №12. -С.54-62.

26. Коннов И.В. Методы недифференцируемой оптимизации. Казань, изд-во КГУ, 1993.- 100с.

27. Коннов И.В. Сходимость релаксационных методов решения задач недифференцируемой оптимизации с ограничениями // Исследования по прикладной математике. Казань, 1990. - Вып. 17. - С.50-57.

28. Михайлов А.Ю. Модель оценки пропускной способности улично-дорожной сети // Вестник ИрГТУ. 2003. - т.14, №2. - С.80-83.

29. Михалевич B.C., Гупал A.M., Норкин В.И. Методы невыпуклой оптимизации. М.: Наука, 1987. - 279 с.

30. Михалевич B.C., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования. М. Наука, 1986. - 260 с.

31. Пиявский С.А. Один алгоритм отыскания абсолютного экстремума функции // Журнал вычислительной математики и математической физики. 1972. - т. 12, №4. - С.888-896.

32. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. - 256 с.

33. Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. М.:1. Мир, 1989.-478 с.

34. Положение об организации деятельности станций скорой и неотложной медицинской помощи: Приказ Министерства Здравоохранения РТ №694 от 7 августа 1993 г.- Казань.

35. Разина М.А. Алгоритмы и программы для оптимизации расположения станций скорой помощи // Математические методы и информационные технологии в экономике, социологии и образовании: Тезисы докладов III

36. Всероссийской научно-технической конференции 19-20 декабря 2003 г.1. Пенза, 2003. С.288-290.

37. Соболь И.М. О поиске экстремальных значений функции от нескольких переменных, удовлетворяющей общему условию Липшица // Журнал вычислительной математики и математической физики. 1988. - т.28, №4. — С.483-491.

38. Федоров В.В. Численные методы максимина. М.: Наука, 1979. - 280 с.

39. Штойер Р. Многокритериальная оптимизация: теория, вычисления и приложения. М.: «Радио и связь», 1992. - 504 с.

40. Aurenhammer F. Voronoi diagram a survey of a fundamental geometric data structure // ACM Computing Surveys. - 1991. - Vol.33, №.3. - P.345-405.

41. Barrodale I., Young A. Algorithms for best Ц and L» linear approximations on a discrete set // Numerical Mathematics. 1966. - Vol.8. - P.296-306.

42. Batta R., Mannur N.R. Covering-location models for emergency situations that require multiple response units // Management Science. 1990. - Vol.36, №1. — P.16-23.

43. Berens W. The suitability of the weighted lp-norm in estimating actual road distances // European Journal of Operational Research. 1988. - №34. -P.39-43.

44. Bhattacharya U., Rao J.R. and Tiwari R.N. Fuzzy multicriteria facility location problem // Fuzzy sets and systems. 1992. - Vol.51. - P.277-287.

45. Brandeau M.L., Chin S.S. An overview of representative problems in location research // Management Science. 1989. - Vol.35, №6. - P.645-674.

46. Brimberg J, Love R.F. Estimating travel distances by the weighted lp-norm // Naval Research Logistics. 1991. - №38. - P.241-259.

47. Brimberg J, Love R.F., Walker J.H. The effect of axis rotation on distance estimation // European Journal of Operational Research. 1995. - №80. -P.357-364.

48. Cooper L.L. Heuristic Methods for Location-Allocation Problems II SIAM Review. 1964. - №6. - P.331 -343.

49. Cooper L.L. Location-Allocation Problems // Operation Research. 1963. -Vol.11.-P.331-343.

50. Cooper L.L. The Transportation-Location Problem // Operation Research. -1972. -Vol.20. -P.94-108.

51. Drezner Z. (editor) Facility location: A survey of applications and methods. -N.Y.: Springer-Verlag, 1995. 572 p.

52. Drezner Z. The p-centre problem Heuristic and optimal algorithms II Journal of operational Research Society. - 1984. - Vol.35, №8. - P.741-748.

53. Drezner Z., Wesolowsky G.O. Optimum location probabilities in the lp distance Weber problem // Transportation Science. 1981. - Vol. 15, No. 2. - P.85-97.

54. Drezner Z., Wesolowsky G.O. The location of an obnoxious facility with rectangular distances // Journal of Regional Science. 1983. - №23. - P.241-248.

55. Duda R.O., Hart P.E. Pattern Classification and Scene Analysis. N.Y.: John Wiley & Sons, 1973.

56. Elzinga D.J., Hearn D.W. Geometrical solutions for some minimax location problems // Transportation Science. 1971. - Vol.6. - P.379-394.

57. Elzinga D.J., Hearn D.W. The minimum covering sphere problem // Management science. 1972. - Vol. 19, №1. - P.96-104.

58. Hamacher H.W., Nickel S. Classification of location models // Location Science. 1998. - №6. - P.229-242.

59. Hansen P., Jaumard B. Lipschitz Optimization // Horst R., Pardalos P. Handbook of Global Optimization. Dordrecht: Kluwer, 1994.

60. Horst R., Tuy H. Global Optimization. Deterministic approach. Berlin: Springer-Verlag. -1996.

61. Klein R., Wood D. Voronoi diagrams based on general metrics in the plane // Theoretical Aspects of Computer Science: Proceedings of 5-th Symposium LNCS 294 (Cori R., Wirsing M., editors.). Berlin: Springer-Verlag, 1988. -P.281-291.

62. Ко М.Т., Lee R.C.T., Chang J.S. Rectilinear m-center problem // Naval Research Logistics. 1990. - №37. - P.419-427.

63. Larson R.C., Odoni A.R. Urban Operation Research. Englewood Cliffs: Printire Hall, 1981.

64. Lee D.T. Two-dimensional Voronoi Diagrams in the Lp metric // Journal of the Associations for Computing Machinery. - 1980. - Vol.27, №4. - P.604-618.

65. Lee D.T., Wong C.K. Voronoi diagrams in L^Lp) metrics with 2-dimentional storage application // SIAM Journal of Computing. 1980. - Vol.9, №1. -P.200-211.

66. Love R. F., Morris J. G. Facilities location models and methods. N.Y.: Elsevier Science Publishing Co., 1988.

67. Love R.F., Morris J.G. Mathematical models of road travel distances // Management science. -1979. Vol.25, №2. - P. 130-139.

68. Love R.F., Morris J.G. Modelling inter-city road distances by mathematical functions // Operational Research Quarterly. 1972. - Vol.23. - P.61-71.

69. Love R.F., Morris J.G. On estimating road distances by mathematical functions // European Journal of Operational Research. 1988. - №36. - P.251-253.

70. Love R. F., Walker J.H. An empirical comparison of block and round norms for modeling actual distances // Location science. 1994. - Vol.2. - P.21-43.

71. Mladineo R.H. An algorithm for finding the global maximum of a multimodal, multivariate function // Mathematical programming. 1986. - №34. - P.188-200.

72. Polyak R. A. Smooth optimization methods for minimax problems // SIAM Journal of Control Optimization. 1988. - Vol.26. - P. 1274-1286.

73. Revelle C., Marks D., Liebman J.C. An analysis of private and public sector location models// Management Science. 1970. - Vol.16, №11. - P.692-707.

74. Shamos M.I., Hoey D. The closest-point problems. 16th Symposium on foundations of computer science. - Berkley, 1975.

75. Shiode Sh., Ishii H., Nishida T. A minimax location problem for ambulance service station // Mathematical Japonica. 1992. - Vol.37, №3. - P.499-502.

76. Sloane N.J.A. http://www.research.att.com/~njas.

77. Thisse J.F., Ward J.E., Wendell R.E. Some properties of location problems with block and round norms // Operations research. 1984. - Vol.32, №6. -P. 1309-1327.

78. Toth G.F. Packing and covering // CRC Handbook of Discrete and Computational Geometry. Godman & O'Rourke, 1997.

79. Toth L.F. Regular figures. N.Y.: Pergamon-MacMillan, 1964.

80. Ward J.E., Wendell R.E. Using Block Norms for Location Modeling // Operation Research. 1985. - Vol.33. - P. 1074-1090.

81. Weber A. Uber den Standort der Industrien, 1909. Translated as Alfred Weber's Theory of the Location of Industries. University of Chicago, 1929.

82. Witzgall C. Optimal solution of a Central Facility: Mathematical Models and Concepts. Washington: National Bureau of Standarts, 1965.