Содержание к диссертации
Введение
Глава 1. Анализ функционирования современных систем массового обслуживания 24
1.1. Зарубежные систем бронирования, продаж и комплексного обслуживания 24
1.2. Организация зарубежных систем бронирования 25
1.3. Процесс бронирования и продаж 28
1.4. Управление доходами 33
1.5. Управление выручкой и взаиморасчетами 35
1.6. Заключение 37
Глава 2. Источники дополнительного дохода в системах массового обслуживания 39
2.1. Задачи управления доходами на авиалиниях 40
2.1.1. История вопроса 40
2.1.2. Основные задачи 43
2.2. Экономические посылки использования многих тарифов...44
2.3. Классические методы распределения мест 54
2.3.1. Метод ожидаемой предельной полезности 54
2.3.2. Управление тарифами в случае рейсом с промежуточными посадками 56
2.4. Эвристические методы 59
2.4.1 Использование тарифных корзин 62
2.4.2 Ценовые корзины 64
2.4.3 Корзины по теневым ценам (shadow price) 65
2.4.4 Заявочная цена (bid price) 67
2.5. Заключение 68
Глава 3. Стационарное решение экстремальных задач 69
3.1. Стационарное решение задачи оптимального уровня защиты для простого рейса и двух тарифов 70
3.2. Стационарное решение задачи оптимального уровня сверхнормативного распределения ресурс 76
3.3. Стационарное управление при не пакетном обслуживаниии.79
3.3.1. Экспоненциально распределенное время обслуживания 79
3.3.2. Произвольно распределенное время обслуживания (пребывания) 82
3.4. Заключение 87
Глава 4. Динамическое решение экстремальных задач 88
4.1. Задача сверхбронирования 88
4.2. Поиск динамического приоритета нахождением распределения 90
4.2.1. Задача непринятия в очередь 91
4.2.2. Задача выбора на обслуживание из двух потоков требований 96
4.3. Решение задач управления методами динамического программирования 103
4.3.1. Задача выбора на обслуживание 103
4.3.2. Динамическое управление тарифными классами... 106
4.4. Решение экстремальной задачи методом вариации управления 117
4.5. Заключение 125
Заключение 126
Приложение 1 128
- Организация зарубежных систем бронирования
- Управление тарифами в случае рейсом с промежуточными посадками
- Стационарное решение задачи оптимального уровня сверхнормативного распределения ресурс
- Задача выбора на обслуживание из двух потоков требований
Введение к работе
Типичные представители современных систем массового обслуживания. Развитие человеческих взаимоотношений привело к тому, что практически каждый день мы стали сталкиваться с системами массового обслуживания (СМО). Это неизбежно, т.к. мы пользуемся результатами труда других людей, при этом желаем это делать в удобное для себя время. В результате возникает все больше систем со случайными потоками требований и дисциплинами обслуживания. Мы пользуемся общественным транспортом, ходим в театры, покупаем продукты в магазинах, говорим по телефону. Все это возможно благодаря использованию СМО.
Историческое развитие теории массового обслуживания. Практические требования в первую очередь телефонного дела, физики и рациональной организации массового обслуживания (билетные кассы, магазины, автоматы и пр.) выдвинули в начале прошлого века ряд интересных математических задач нового типа. На первичное развитие этой теории особое влияние оказали работы гениального датского ученого А. К. Эрланга (1878-1929) - многолетнего сотрудника Копенгагенской телефонной компании. Основные его исследования в этой области относятся к 1908-1922 гг. С того времени интерес к проблемам, выдвинутым Эрлангом, необычайно возрос. В результате, значительно увеличилось число математиков, экономистов и инженеров, интересующихся и разрабатывающих подобные проблемы. Оказалось, что задачи типа телефонных возникают в самых разнообразных направлениях исследований: на транспорте, в экономике, военном деле. Более того, подобные задачи возникали гораздо раньше, но не решались столь эффективно ввиду кажущейся
неактуальности и отсутствия надлежащего математического и вычислительного аппаратов.
Требования практики выдвигают перед теорией массового обслуживания (ТМО) все новые и новые задачи. Их рассмотрение необходимо для приложений, для постепенного приближения условий, в которых они решаются к истинной картине изучаемых явлений, для исключения ручного человеческого управления из процесса принятия решения, для создания методов, способных повысить эффективность уже существующих систем.
Понятие эффективности работы системы в каждом случае определяется индивидуально. Это может быть как один, так и несколько критериев, важность которых ясна из самих целей и задач системы. Так, для систем, обслуживающих лиц, попавших в уличные катастрофы, важнейшими характеристиками являются время до прибытия на место происшествия врачей и время транспортировки всех пострадавших до отделений скорой помощи. Для систем противовоздушной защиты основным критерием является вероятность поражения всех целей противника. Для систем, рассматриваемых в данной диссертации, под эффективностью понимается интегрированная величина способности системы максимизировать доход от наиболее полного использования собственного ресурса и степени автоматизации управления при этом.
Литературный обзор. Основные аспекты теории массового обслуживания освещены во многих книгах. Строгое изложение основ ТМО и теоретическое обоснование используемых в ней аналитических методов посвящена книга Гнеденко Б. В. и Коваленко И. Н. [15]. Хорошо известная книга Саати Т. Л. [54] охватывает широчайший круг прикладных вопросов, а также выделяется подробностью технических выкладок. Следует отметить и весьма обширный литературный обзор в
этой книге, дополненный в русском издании редакторами. К обобщающим, работам проблемно-ориентированного характера следует отнести книги Клейнрока Л. [37-38], способные дать наглядную важность изложенных задач неспециалистам. Книга известного специалиста по теории очередей Джейсуола Н. [18], посвящена, хотя и частной, но весьма важной и часто встречающейся проблеме СМО с приоритетным обслуживанием. Общие вероятностные и аналитические методы, позволяющие делать о системах выводы собирательного характера, изложены в монографиях А. А. Бровкова [9-10]. Там же и дана классификация СМО, расширяющая классификацию Д. Кендалла.
В качестве учебных пособий отметим книги Г. И. Ивченко, В. А. Каштанова и И. Н. Коваленко [31], П. П. Бочарова, А. В. Печенкина [8], и книгу В. Ф. Матвеева, В. Г. Ушакова [45]. Развитию приложений теории массового обслуживания много способствовало изложение се основ в известном учебнике Е. С. Вентцель "Теория вероятностей", книгах Л. А. Очарова "Прикладные задачи теории массового обслуживания", Феллера [64-65], В. Я. Розенберга и А. И. Прохорова "Что такое теория массового обслуживания".
Различным вопросам практического функционирования разнообразных современных автоматизированных систем массового обслуживания (АСМО) посвящены работы ИПУ [21], [23-24].
В первых работах по ТМО А. К. Эрланг [74] использовал допущение о том, что входящий поток пуассоновскии, а время обслуживания распределено по показательному закону. В этих предположениях число требований в системе образуют марковскую цепь. В случае эргодичности системы, для стационарного режима работы он и выводил свои знаменитые формулы (для переходного процесса решение было получено Кларком в 1953 г.). Эрланг осознавал
грубость подобных предположений и разработал обобщающий метод, названный методом этапов Эрланга. В развитии направлений подобных исследований было получено много интересных результатов. Теория последовательно-параллельных этапов и марковских сетей подробно описана в книгах Кокса [43], и Джексона [19-20].
Однако оказалось, что хотя большинство практических задач и не укладывается в подобную схему, большие расхождения случались куда реже ожидаемого. Объяснение этих фактов можно найти в работах Пальма [49], Реньи [53], А. Я. Хинчина [67], Г. А. Ососкова [47], Б. И. Григелиониса [17].
Теоретическим аппаратом для исследования марковских моделей и марковских случайных процессов служит теория цепей Маркова с конечным и счетным множеством состояний. Условия эргодичности цепи Маркова в легко применимом для ТМО виде, выяснены Фостером [66]. В работе Ходжеса и Розенблатта [71] исследовано распределение времени возвращения при случайном блуждании. Предельная теорема о распределении времени пребывания в различных состояниях в случае однородного марковского процесса с конечным множеством состояний получена в работе Сираждинова [55].
Практические задачи, связанные с марковскими моделями систем массового обслуживания связаны с решением систем линейных уравнений больших размерностей. Нашли применение, как общие вычислительные методы, так и были специально разработаны методы для анализа СМО (см. Д. К. Фаддеев, В. Н. Фаддеев [62], М. А. Шнепс [73], Г. П. Башарин и А. И. Громов [5], Шветлик [72]).
В немарковской модели может быть либо время обслуживания распределено по закону, отличному от экспоненциального, либо поток не пуассоновский, либо и то и другое. Для исследования немарковских
моделей были развиты методы вложенных цепей Маркова, этапов, дополнительной переменной, случайного блуждания, функции Грина, уравнений Линдли и комбинаторные методы.
Первое решение задачи о среднем числе требований, находящихся в очереди и среднего времени ожидания для стационарного состояния системы с пуассоновским входящим потоком и произвольным временем обслуживания при обслуживании требований в порядке поступления сделал наш соотечественник, один из основателей ТМО А. Я. Хинчин [68] в 1932 г., а затем в несколько измененной форме в [69]. В более широких предположениях эта задача изучалась позднее иными приемами Линдли [44], Поллачеком [50], Смитом [56], Такачем [60] и др.
А. Я. Хинчин для анализа подобных систем предложил рассматривать не все, а только такие моменты времени, в которых процесс образует марковскую цепь (моменты регенерации). Этот метод был подробно разработан известным специалистом в области ТМО Кендаллом [34]. В литературе можно встретить его как метод Кендалла, вложенных или скрытых цепей Маркова, полумарковского процесса.
Однако иногда требуется получить характеристики процесса, зависящие, в том числе, и от времени между регенерациями. В некоторых случаях характеристики стационарного режима совпадают с характеристиками в моменты регенерации. Этот факт А. Я. Хинчин назвал математическим законом стационарной очереди. Вообще же, для этих исследования используют схему Кокса [42] - т. н. метод введения дополнительных переменных. Схема кусочно-линейных марковских процессов, обобщает схему Кокса. Кусочно-линейные марковские процессы в различных вариантах общности предлагались И. Н. Коваленко [39-41], В. В. Калашниковым [32], Тьеном [61].
Анализ общих систем типа G/G/1 весьма сложен. Для этих систем не известно даже среднее время ожидания. Для уравнений этой системы применим спектральный метод. Имеются также и другие подходы. Лестничные индексы изучал Андерсон [2-4] и продолжил его работу Спитцер [57-58], что привело в результате к весьма важному в ТМО тождеству Спицера. Полячек [51] рассматривал формальный подход к решению таких систем, и его подход называется сейчас методом Полячека. Позже Кингман [36] построил алгебру очередей, которая определила место каждого из этих методов в общем здании и вскрыла их внутреннюю сущность. Выяснилось, где и почему решения наталкиваются на трудности, но, к сожалению, и неприменимость к много линейным системам массового обслуживания. Кейлсон [33] применял метод функции Грина. Бенеш [6] изучал систему G/G/1 с использованием незавершенной работы и других смежных понятий.
Для установления характеристик сложных систем, плохо поддающихся аналитическому решению, на практике используют статистическое моделирование системы на ЭВМ. Использование случайных испытаний при решении главным образом вычислительных задач, называется методом Монте-Карло.
Проблемы, затрагиваемые в данной работе, наиболее тесно связаны с решением задач максимизации доходов при функционировании СМО. Экономический аспект (доходы) в СМО естественно возникает, когда, например, поступающее требование при обслуживании приносит системе определенную сумму денег. Если оно ожидает в очереди, эта сумма может уменьшаться, а если ожидает более определенного срока, требование покидает систему не обслуженным и требованию выплачивается неустойка. Различные виды управления появляются, если есть возможность поступающее требование
отвергнуть (не принять в очередь), возможность увеличивать интенсивность поступления требований (путем снижения платы за обслуживание), возможность выбора требования из очереди на обслуживание в произвольном порядке, а не в порядке поступления и пр. Понятно, что вопросы получения максимального дохода приводят к разного рода экстремальным задачам в СМО.
Вообще, задачи экстремального управления в управляемых системах массового обслуживания в первую очередь касались систем массового обслуживания с несколькими входящими потоками и несколькими различными обслуживающими приборами, в которых появлялся принципиально новый для систем элемент - дисциплина обслуживания и приоритет. Примеров таких систем можно привести много. Этому посвящена книга А. М. Горцев, А. А Назаров, А. Ф. Терпугов [16]. В диссертационной работе будут рассматриваться системы с динамическими приоритетами, системы с формированием очереди и др.
В значительной мере, первоначальный интерес в нашей стране к указанной области исследований был вызван известной книгой Ховарда [70], в которой весьма доступно излагаются методы исследования задач принятия решения при стохастических условиях функционирования систем. Работы над вопросами определения оптимального управления системами массового обслуживания были начаты О. И. Бронштейном, А.Л. Райкиным и В. В. Рыковым [11]. Задачи этого типа также рассматривались И. Н. Коваленко и Г. П. Климовым.
Особенно остро необходимость анализа и синтеза таких систем появился с разработкой компьютерных автоматизированных систем управления, вычислительных центров коллективного пользования, описанных в книгах Жожикашвили В. А., Вишневского В. М. [22] и
Вишневского В. М. [13]. Для этих систем характерно то, что управляющее воздействие (выбор заявки на обслуживание, включение заявки в ту или иную очередь, включение или выключение резервного прибора) должно происходить без явного вмешательства человека.
Большое число зарубежных исследований посвящено решению весьма злободневных практических задач подобного типа. Среди доступных автору работ последних лет необходимо выделить исследования О'Тула [48], Бодили и Веверфорда [7], Кимса и Чейса [35]. В основном в этих работах затрагиваются вопросы управления доходами (Revenue Management), о которых мы будем говорить очень подробно в Главе 2 (в России исследованием и применением управления доходами занимается А. М. Протасов). Revenue management - это методы решения и автоматизации решения как правило целого комплекса связных экономических задач, возникающих в какой то определенной системе массового обслуживания и в своих постановках максимально приближенны к реальным. Ввиду столь объемлющих задач, как правило, эти методы носят эвристический характер и не отличаются строгостью. Однако во многом они весьма изящны. Их эффективность проверяется компьютерным моделированием и на накопленных прошлых статистических данных. Первоначально, для каждой системы подходы придумывались специально. К настоящему моменту наиболее отработана система управления доходами при авиаперевозках и потому сейчас разрабатываются приемы перенесения этих наработок на управление гостиницами, ренту машин и т.п.
Проблемы развития и автоматизации систем массового обслуживания. С развитием общества развивались и усложнялись СМО. Участвовать, обслуживать, управлять ими становится все
сложней и сложней. В авангарде процесса развития СМО находятся автоматизированные системы массового обслуживания (АСМО).
АСМО представляют собой обширный класс компьютерных систем, охватывающих самые разнообразные сферы обслуживания населения. Системы этого класса используются, в банковском деле, в медицине, в информационно-справочном обслуживании населения, в торговле и т.д. Исторически первыми АСМО явились компьютерные системы резервирования на транспорте, получившие в англоязычной литературе наименование CRS, что означает "Computerised Reservation Systems". Типичным примером АСМО в России является система бронирования мест и продажи авиабилетов "Сирена". Эта система прошла несколько стадий модернизации, при которых непрерывно совершенствовалась и развивалась. Она постоянно находится в эксплуатации с начала 70-х годов по настоящее время.
Другими примерами АСМО являются системы бронирования мест в гостиницах, системы электронного заказа книг в библиотеках и заказа лекарств в аптеках, сети продажи и резервирования билетов на междугородные автобусы, система "Сберкасса", системы туристического обслуживания. В самое последнее время АСМО охватили обширные области торговли в форме систем электронной коммерции.
Все СМО, разработанные в СССР и в передовых западных странах в 60-е и 70-е годы, относят к СМО первого поколения (см. М.П.Фархадов [63]). Характерными отличительными признаками-недостатками этих СМО является то, что они не предусматривали оперативного управления экономическими параметрами продаж -ценообразованием или дисциплиной обслуживания. Управление было минимально по целому ряду причин, основными из которых являлись
несовершенство экономических законов и примитивная, по современным меркам, техническая реализация. Вторым очевидным недостатком являлось то, что взаимодействовать с такими системами можно было только через зарегистрированных в них специально обученных операторов-профессионалов.
В свое время эти системы по многим показателям (большое количество терминалов, одновременно обслуживаемых центральными ЭВМ, высокие показатели по надежности и достоверности, малое время реакции и т.д.) занимали передовые позиции среди компьютерных систем, и почти полностью удовлетворяли тогдашним запросам. В настоящее время системы первого поколения уже полностью устарели.
Вопросам проектирования автоматизированных систем и сетей массового обслуживания посвящено значительное количество работ отечественных и зарубежных авторов. Подробный обзор можно найти в статье С. Аверина [1].
Со времени возникновения СМО первого поколения, экономические законы взаимодействия с клиентами становились более свободными. В частности, в авиабизнесе это вылилось в первую очередь в следующие возможности для перевозчика:
-снять жесткую привязку стоимости перелета к ее километражу,
вводя множество тарифов практически почти на одну услугу;
-многократно менять цену за тариф в зависимости от времени до
вылета;
-бронировать большее число билетов, чем позволяет физическая
вместимость салона (т.н. сверхбронирование). Аналогичные ограничения были сняты с функционирования и многих других СМО, но именно у авиакомпаний имелись к тому времени наибольшие ресурсы для наилучшего использования новых условий
игры. Для извлечения из всего перечисленного дополнительной прибыли нужно решать множество задач так называемого управления доходами (Revenue Management), что привело к появлению АСМО второго поколения, в которых этим занимаются специальные маркетинговые отделы.
Однако, например в авиакомпаниях, в подобных маркетинговых отделах, по сей день, каждый менеджер отслеживает огромные объемы информационных данных (30-40 рейсов) и управляет огромными денежными потоками. Процесс расчета управления продажами происходит почти вручную, носит эвристический характер и является офлайновыми (в работе такие методы названы стационарными). Естественно это сказывается как на качестве обработки информации, так и, в конечном счете, на стоимости билетов и прибылях авиакомпаний. К тому же, как правило, результаты этих расчетов настолько сложны и плохо структурированы, что для интерпретации их к каждому конкретному требованию клиента, опять же нужны посредники - кассиры-операторы. Во многих других АСМО положение не лучше.
Значительный прогресс техники коммуникаций, привели к созданию СМО второго поколения, главной особенностью которых является возможность прямого доступа клиентов к базам данных СМО с персональных компьютеров через сеть Интернет, а развитие конкурентной борьбы породили стремление сделать СМО более привлекательными для масс населения.
Таким образом, прогресс в области компьютерной техники и телекоммуникаций, с одной стороны, и требования рынка, с другой, представляют собой две главные причины возникновения СМО второго поколения. Они позволили существенно расширить круг пользователей,
предоставив в интересах увеличения доходов непосредственный допуск к базам данных необученным пользователям. Это означает, что услугами СМО может воспользоваться любой человек (физическое лицо) путем непосредственного обращения к удаленным базам данных, с помощью персонального компьютера, находящегося в его квартире.
Происходит значительное укрупнение АСМО. Как показывает практика, СМО второго поколения присущи серьезные недостатки, ограничивающие масштабы и эффективность их использования. Увеличение типов клиентов и предоставляемых услуг приводят к следующей трудности. Никакой маркетинговый отдел уже не в состоянии вручную охватить все разнообразие и полноту предоставляемых фирмой услуг в разумное время и произвести надлежащее управление ресурсами. В первую очередь это ощущают обычные граждане. В результате, потенциально наиболее массовые пользователи систем не могут воспользоваться услугами данной фирмы. Т.к. современные СМО существуют в условиях конкуренции и возможности выбора услуг, чего не существовало в СССР, фирма недополучает прибыль.
Причины отмеченных недостатков и ограничений коренятся в несовершенстве используемого в СМО первого и второго (современные СМО) поколения технико-экономического управления.
Вместе с тем анализ показывает, что продолжающийся прогресс в области компьютерных и коммуникационных технологий позволит усовершенствовать СМО второго поколения, снять присущие им ограничения и повысить эффективность использования, внедряя в них онлайновое управление (в диссертации оно названо динамическим) и аппарат ТМО. Идеальный прототип будущих СМО называется "СМО нового поколения", или CMO-XXI. Ограничения, свойственные СМО
первого и второго поколения в основном преодолены, кроме управления доходами. Управление доходами особенно слабо развито в России, где необходимость получения дополнительного дохода в условиях конкурентной борьбы и возможность свободного выбора клиентом вида услуги возникла только в последние годы. Именно ей в общей структуре CMO-XXI и посвящена настоящая диссертация.
Актуальность темы диссертации. Благодаря развитию вычислительной техники именно сейчас появляется возможность внедрения математического аппарата (в частности теории массового обслуживания) в решение экономических задач управления СМО в реальном времени и автоматизации процессов управления. Появилось множество новых типов услуг, а стало быть, задач управления, которые ждут своей, во-первых, формализации, во-вторых, классификации, в-третьих, решения и, наконец, в-четвертых, внедрения.
Основные тезисы диссертации. Для повышения эффективности АСМО, необходимо автоматизировать технико-экономического управление, опирающееся на использование существующих математических методов и разработать новые методы управления доходами, которые приведут к сокращению экономических потерь.
Цель работы.
Цель работы состоит в разработке робастных методов управления доходами, способных повысить эффективность функционирования АСМО, при этом эти методы:
смогут охватить большее число видов услуг, предоставляемых различными АСМО;
уменьшат управление экономическими характеристиками АСМО ручными методами и повысят их автоматизацию;
- могут быть реализованы в существующих АСМО либо в
ближайшем будущем в СМО нового поколения.
Для достижения поставленных целей в работе решались следующие задачи:
исследование функционирования современных CRS;
исследование источников дополнительной прибыли при управлении доходами;
классификация основных существующих задач управления доходами;
исследование существующих методов управления доходами в АСМО первого и второго поколения;
выявление ограничений применимости существующих эмпирических методов управления доходами;
разработка новых стационарных методов решения существующих задач управления СМО;
постановка и решение задач динамического управления доходами, способных быть реализованными в СМО нового поколения;
анализ эффективности предложенных методов управления доходами.
Методы исследования. В диссертационной работе применены методы теории систем массового обслуживания, линейного и динамического программирования, вариационного исчисления и оптимального управления.
Структура диссертационной работы. Поставленная цель и задачи определили структуру диссертационной работы.
В первой главе исследованы современные компьютерные системы резервирования, как прототип СМО нового поколения.
Описана структура этих СМО: хранения, обновления и получения информации, структура распространения ресурса, распределения финансовых потоков. Из этого становится ясным та сложность внедрения динамического управления доходами в автоматизированные системы, которую предстоит преодолеть.
Структура последующих глав определяется вводимой структурой задач управления доходами:
ЗАДАЧИ УПРАВЛЕНИЯ ДОХОДАМИ
СВЕРХНОРМАТИВНОЕ
РАСПРЕДЕЛЕНИЕ
РЕСУРСА
(сверхбронирование и пр.)
УПРАВЛЕНИЕ
ТАРИФАМИ
(распределение ресурса
между потоками разной
доходности)
ЦЕНОВОЕ
УПРАВЛЕНИЕ
(для систем с
управляемым
входящим потоком)
и методами их решения:
МЕТОДЫ УПРАВЛЕНИЯ ДОХОДАМИ И РЕШЕНИЯ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ
СТАЦИОНАРНОЕ УПРАВЛЕНИЕ
ДИНАМИЧЕСКОЕ УПРАВЛЕНИЕ
МЕТОД
ДИФФЕРЕНЦИРОВАНИЯ
ФУНКЦИИ ОЖИДАЕМОГО
ДОХОДА
ЭМПИРИЧЕСКИЕ МЕТОДЫ
МЕТОД
НАХОЖДЕНИЯ
РАСПРЕДЕЛЕНИЯ
СОСТОЯНИЙ
СИСТЕМЫ
МЕТОД
ВАРИАЦИИ
УПРАВЛЕНИЯ
МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
МЕТОД
НАХОЖДЕНИЯ
РАСПРЕДЕЛЕНИЯ
СОСТОЯНИЙ
СИСТЕМЫ
МЕТОД ПЕРЕБОРА
Во второй главе объяснены источники получения дополнительной прибыли при использовании управления доходами в CRS и аналогичных системах. Описаны задач управления доходами и существующие методы их решения в СМО второго поколения. Выявлены недостатки существующих стационарных методов управления доходами, основанных на т.н. EMR (Expected Marginal Revenue) принципе Литлвуда (Littelwood) применительно к системам с нераздельными потоками разной доходности или не пакетным обслуживанием.
В третьей главе подробно исследованы стационарные методы управления доходами. Доказана правомочность расчетов, основанных на эвристическом EMR принципе ожидаемой предельной полезности Литлвуда (Littelwood) для системы с разделенными потоками разной доходности и пакетным обслуживанием. Разработан стационарный метод управления (многомерных уравнений Эрланга) для систем с не пакетным обслуживанием.
В четвертой главе рассматривается класс задач, названный в работе задачами динамического управления доходами. Эти методы могут быть реализованы и должны найти применение в СМО нового поколения. В числе прочего разработан динамический метод управления доходами для систем с пакетным обслуживанием и нераздельными потоками разной доходности (для них неприменимы стационарные методы, основанные на EMR принципе) и систем с управляемым входящим потоком требований (методом вариации управления). Выполнен теоретический анализ и проведено компьютерное моделирование эффективности предложенных методов.
Научная новизна. Был разработан новый класс методов управления доходами, названный в диссертации методами
динамического управления. Подробно описан новый класс больших компьютерных систем, сформулированы его основные свойства и принципиальные отличия, определены основные задачи разработки, развития и совершенствования этих систем с точки зрения управления доходами. Исследованы и экономически объяснены источники получения дополнительной прибыли от управления доходами в различных СМО.
Основные научные результаты работы заключаются в следующем:
исследованы современные западные глобальные CRS, выявлены сложности внедрения динамических методов;
объяснены источники получения дополнительной прибыли при использовании управления доходами в CRS и аналогичных системах;
описаны и классифицированы задачи управления доходами в современных CRS;
доказана правомочность расчетов, основанных на эвристическом EMR (Expected Marginal Revenue) принципе ожидаемой предельной полезности Литлвуда (Littelwood) для стационарного управления доходами;
показаны ограничения использования эвристических методов, основанных на EMR принципе для систем с не пакетным обслуживанием или нераздельными потоками разной доходности;
разработан стационарный метод {многомерных уравнений Эрланга) управления для систем с не пакетным обслуживанием;
выявлен новый класс задач управления доходами, названных динамическими;
разработан динамический метод управления доходами для
систем с пакетным обслуживанием и нераздельными потоками;
разработан метод управления доходами {метод вариации управления) для систем с управляемым входящим;
выполнен теоретический анализ и проведено компьютерное моделирование эффективности предложенных методов с точки зрения ожидаемой доходности.
Практическая ценность и реализация результатов работы. Использование результатов работы позволяет существенно (3-5%) повысить доходность систем массового обслуживания, предоставив им удобные и универсальные подходы к автоматическому решению задач управления доходами.
Разработанные алгоритмы и программы могут быть использованы для дальнейшего развития и совершенствования различных систем массового обслуживания.
Результаты диссертационной работы использованы в работах, проводимых ИПУ РАН в области модернизации и совершенствования систем массового обслуживания в рамках "проекта CMO-XXI".
Апробация работы. Основные результаты диссертационной работы являлись основой читаемого в течение двух лет автором спецкурса в Московском Государственном Авиационном Институте на факультета прикладной математики и физики.
Публикации. По основным результатам диссертационной работы опубликовано 5 работ.
Организация зарубежных систем бронирования
Современные системы массового обслуживания имеют дело не только с задачами, связанными с обслуживанием большого числа клиентов, но и с предоставлением им множества связанных между собой услуг (комплекса услуг), причем само предоставление каждой из них осуществляется соответствующей независимой компанией. Потому, возникающие в них задачи управления доходами зачастую решаются для каждого звена системы в отдельности. Системы, решающие такого рода задачи, т.е. системы комплексного обслуживания клиентов особенно сложны. Их анализу в основном и посвящена эта глава. По всей видимости, в очень скором будущем, управление доходами в системах комплексного обслуживания в целом, станут особенно остро. Именно поэтому сейчас актуальна задача классификации задач управления доходами.
Последние 15-20 лет создается фактически новый класс автоматизированных систем массового обслуживания — глобальные системы обслуживания клиентов, обеспечивающие предоставление им комплексных услуг. Мы проанализируем принципы организации работы одного из видов зарубежных систем предоставления комплексных услуг — систем автоматизации бронирования и продажи пассажирских авиаперевозок, а также услуг, связанных с ними. Во многом их опыт универсален. Рассмотрены в первую очередь системы поиска информации, бронирования и продажи ресурсов, а также финансовых расчетов — управление расчетами и распределение доходов. 1.2. Организация зарубежных систем бронирования. Задачей всех систем, которые мы затронем, является автоматизация бронирования (резервирования) и последующей продажи ресурсов, которыми располагают компании, занимающиеся разными видами деятельности. Для авиакомпаний такими ресурсами являются места на авиарейсы, для гостиниц — номера, для компаний, сдающих в аренду автомобили, — эти автомобили и т. д. Общим, для всех этих видов ресурсов является то, что они весьма скоропортящиеся. Доход от несданного номера или пустого кресла в салоне самолета потеряны безвозвратно. Объемы ресурсов, которыми необходимо управлять, огромны и продолжают расти с каждым годом. Именно поэтому, задачи оптимальной автоматизации бронирования и продажи для них стоят очень остро.
В принципе, каждый из указанных выше видов компания может иметь собственные системы распределения ресурсов, и крупные компании их имеют. В то же время, поскольку авиация всегда среди них была технологическим лидером и в вопросах автоматизации продаж продвинулась дальше всех, а ее системы распределения ресурсов являются очень мощными и хорошо структурированными, достаточно большая доля ресурсов гостиниц и автомобильных компаний также распределяются именно через авиационные системы автоматизации. Именно вокруг авиационных систем автоматизации и создавались системы комплексного обслуживания.
Все существующие в настоящее время компьютерные системы бронирования авиаперевозок, или CRS (Computer Reservation System), можно разделить на два вида: первые — это системы, предназначенные для хранения ресурсов авиакомпаний и управления ими (такие системы носят название ресурсных или инвентарных), а вторые — для реализации этих ресурсов через обширную сеть точек продаж (распределительные или дистрибьюторные системы). В настоящее время в мире существует большое число и тех и других.
Создание CRS началось тогда, когда рост объемов авиаперевозок заставил авиакомпании всерьез заняться отслеживанием состояния своих ресурсов и управлением ими с целью повышения своей доходности. К началу 70-х годов свои системы автоматизации начали развивать все крупнейшие авиакомпании. Первоначально эти системы выполняли чисто инвентарные функции и к их ресурсам имели доступ только кассиры — сотрудники этих компаний. Однако уже в конце 70-х, будучи весьма заинтересованными в увеличении загрузки рейсов, авиакомпании начали предоставлять возможность распределения (дистрибуции) своих ресурсов и независимым трэвел-агентствам. При этом рост числа задач потребовал создания распределительных надстроек над CRS-системами, оснащенных специализированным ПО. Распределительные надстройки постоянно развивались, агенты получали все больше возможностей, и в результате CRS одних авиаперевозчиков стали предоставлять информацию о рейсах других и даже бронировать билеты на них.
Однако спустя некоторое время между авиакомпаниями и трэвел-агентствами вполне закономерно начали возникать конфликты: первые как владельцы CRS, естественно, были заинтересованы в первоочередной реализации собственных ресурсов, которые по этой причине занимали в их системах привилегированное положение. Для трэвел-агентств же важно иметь полноценный доступ к ресурсам максимального числа авиаперевозчиков и возможность выбора оптимального для пассажира маршрута. Сложившуюся ситуацию в итоге разрешил выход инвентарных систем из прямой собственности авиакомпаний, а также интеграция некоторых из них между собой путем создания систем коллективного пользования (самая известная из таких систем — Gabriel) при одновременном обособлении их распределительных надстроек, расширении функций последних и постепенном превращении их в самостоятельные системы.
Понемногу через эти самостоятельные системы свои услуги начали реализовывать гостиницы и фирмы по аренде автомобилей, появилась возможность бронирования через них железнодорожных и автобусных перевозок, а сами они в связи с этим стали широко использоваться в индустрии путешествий. Итогом этого процесса явилось формирование современных глобальных распределительных систем, ГРС (Global Distribution System, GDS), задача которых — обслуживание трэвел-агентов по всему миру (последнее принципиально для систем, претендующих на наименование глобальных).
Сегодня в мире "на слуху" несколько названий ГРС, причем исключительно распределительной из них является только Amadeus. Остальные системы распределительными являются только частично. Так, сегодня крупнейшей распределительной системой считается Sabre, при том что она имеет и мощную инвенторную часть. Небольшую инвенторную часть имеет и система Galileo.
Управление тарифами в случае рейсом с промежуточными посадками
Первые теоретические работы по проблеме распределения мест между различными ценовыми классами относятся к началу 70-х годов. В 1982 году Литлвудом (Littelwood) была предложена концепция использования ожидаемой предельной полезности посадочного места (EMR - expected marginal revenue). До настоящего времени эта концепция является основной для решения практических задач.
Используя ожидаемую предельную полезность, мы отвечаем на следующий вопрос: принять или отказать в продаже билета по соответствующему тарифу. Ожидаемая предельная полезность от продажи места по данному тарифу это произведение вероятности заполнения этого места по данной цене на данную цену. Продажа по цене С, хотя бы S мест возможна, только если число требований по данному тарифу будет не меньше S (поступивших до момента вылета). Значит, вероятность потенциально продать S OQ место есть вероятность того, что число желающих приобрести билеты по данному тарифу будет не меньше S. Если (Зсі-функция распределения числа поступивших требований (здесь и далее иногда в целях упрощения записи и выкладок мы будем заменять дискретные случайные величины, такие как число мест и т.д. их непрерывными аналогами) на приобретение билета по цене СІ (о сложностях и методах ее нахождения стоит говорить отдельно в Приложении 2), предельная полезность от продажи S-oro места по тарифу С, равна: EMRi(S)=Ci(l-Fi(S)).
Очевидно, эта введенная функция монотонно убывает. Характер ее убывания зависит от характера возрастания функции распределения Максимально возможное принимаемое значение равно С,. Примерный ее вид приведен на следующем рисунке
Основываясь на введенной функции EMR(S) , в предположении, что дешевые клиенты приходят раньше дорогих, т.е на раздельности потоков требований разной доходности, задача с двумя классами на простом рейсе решается следующим образом. Ожидаемый доход будет максимален, если доход от дополнительно проданного дешевого билета больше ожидаемой предельной полезности от этого билета, оставленного для дорогих клиентов. Это правило должно действовать следующим образом. Пусть приходит дешевый клиент и просит продать ему билет по цене Cj. Нами продано уже S-1 мест. Если ожидается, что доход от оставления этого билета для дорогих клиентов, меньше С2, то билет следует продать. Математически это записывается так. -ый билет следует продать дешевому клиенту, если выполняется условие Сг С](1-F](S)). Значит, условие на уровень защиты N2 в случае двух тарифов, выражается формулой: C2/C]=z(J-Fl(N2)). (Заметим, что эта формула не зависит от функции распределения поступления дешевых клиентов.)
К сожалению, построить по такому же принципу точные формулы для трех и более тарифов, в предположении независимости спросов, весьма проблематично. Эти задачи независимо решались Брюмеллем (Brumelle), МкГиллом (McGill), Карри (Curry) и Волмером (Wollmer). На самом деле даже при отсутствии уровней защиты, простой подсчет ожидаемой прибыли при нескольких различных тарифах, как будет видно из Приложения 1 является весьма непростой вычислительной задачей. Однако и приближенные формулы давали удовлетворительный для практических целей результат.
Большинство авиаперевозчиков и продаваемых программных продуктов по управлению тарифами в своей основе используют описанный выше метод. Как правило, он упоминается как МК-метод. Столь широкая популярность этого метода обусловлена несколькими причинами. Этот метод очень прост в применении и дает относительно неплохие и надежные результаты. Кроме того, во многих случаях его можно не только строго доказать математически, но и объяснить "на пальцах".
Используя традиционные методы операционного исчисления, задачу управления тарифами можно свести к задаче линейного программирования. Для этого нужно ввести целевую функцию, которую требуется максимизировать и множество ограничений, накладываемых на входящие в целевую функцию переменные. В качестве целевой функции будем рассматривать полную выручку от всех связных перелетов (в случае рейса с промежуточными посадками или рейсов с пересадками), которая включает в себя все возможные тарифы по всем возможным комбинациям вылет-посадка. Что же касается ограничений, то они имеют под собой две причины. Во-первых, это ограничения на физическую вместимость судна. Во-вторых, это ограничения, связанные с ограниченным спросом на каждый тариф для каждого вида перелета (взлет-посадка). Далее будет предполагаться независимость этих спросов.
Конечно, ограничения второго рода носят только вероятностный характер и могут быть только предсказаны. Однако, при самых грубых оценках, так называемом детерминированном случае, можно считать, что ограничения на максимальный спрос имеют вероятность единицу. Как правило, принимают в качестве ограничения среднюю величину спроса.Таким образом, нам необходимо максимизировать целевую функцию вида
Стационарное решение задачи оптимального уровня сверхнормативного распределения ресурс
Сейчас рассмотрим задачу, использующую метод предыдущего пункта и имеющую большое практическое значение. Несмотря на все утрирующие предположения, которые мы сделаем при ее постановке, правильное применение результатов этого пункта на практике способно приносить вполне ощутимую прибыль. Однако, мы упомянем и неправильный пример применения вполне разумных идей сверхнормативного распределения ресурсов.
Напомним, откуда и как в предыдущей главе возникла идея сверхбронирования. Предположим, что авиакомпания принимает заказы на бронирование, но не более количества оставшихся свободных мест на рейсе. После того, как все места забронированы, поступающим еще требованиям отказывается. Тогда, совершенно естественно, что не все заказанные на рейс билеты будут выкуплены, и в результате самолет полетит недостаточно заполненным. Воплощение естественно возникающей идеи сверхбронирования билетов (overbooking), т.е. бронирования большего числа пассажиров, чем имеется физически мест, связано с риском того, что авиакомпания не сможет выполнить принятых на себя обязательств по перевозке граждан и выплатой им неустоек. Поэтому актуальна задача нахождения оптимального уровня сверхбронирования (т.е. количества требований сверх физической вместимость судна, на которые принимается бронь), максимизирующего доход.
Сформулируем задачу в максимально жестких предположениях. Авиакомпания предлагает свои услуги так: бронируются билеты на рейс, срок выкупа билетов непосредственно перед вылетом. Таким образом, места, на которые билеты не выкуплены, остаются уже пустыми, а всем желающим выкупить билеты, для которых нет мест, выплачивается неустойка. Требуется найти оптимальный уровень сверхбронирования.
Укажем строгую постановку задачи. Рассматривается система с пакетным обслуживанием и дискретным временем обслуживания пакета. Прибор может обслужить пакет из не более N требований. Длина очереди М. С - доход от обслуживания требования. Ожидающее требование в очереди, не обслуженное после первого освобождения прибора, покидает систему и ему система выплачивает неустойку в размере L. Случайное число требований w покидает очередь в момент перед началом обслуживания, с плотностью вероятности / и функцией распределения F. То есть, F(w) - вероятность того, что очередь покинут не более w требований. Требуется определить оптимальную длину очереди М (N+сверхбронирование). Как и в предыдущем пункте будем считать, что число пассажиров непрерывно меняющаяся величина. Для нахождения оптимального М , выпишем ожидаемый доход в случае, когда все Ммест очереди будут заняты :
Число обслуженных требований не может превышать размер пакета N и, кроме того, оно не может превышать того числа требований в очереди, которое останется после того, как часть требований очередь покинет. Число требований, которым будет выплачена неустойка, равно числу требований в очереди сверх N, не считая покинувших очередь, и, кроме того, оно не может быть отрицательным.
Запишем формулу для среднего ожидаемого дохода: Действительно, первый интеграл соответствует тому доходу, который получит система, в случае, если число требований х, которые будут обслужены, после того как М-х требований покинет очередь, не превосходит N Если их число превосходит N, то все равно, прибор сможет обслужить только N требований. Если число требований х, после ухода части требований из очереди, превосходит N, то x-N требованиям выплачивается неустойка в размере L. Преобразуем выписанную формулу, сделав следующую замену переменной: Это значит, что ожидаемый доход максимален, если длина очереди будет удовлетворять уравнению С-ІС+ЦЩМ-N) или Объясним полученный результат с точки зрения систем резервирования. Пусть приходит М-ый клиент и хочет забронировать билет стоимостью С. Если мы не сможем его удовлетворить и он не полетит, то нам придется вернуть ему деньги и еще выплатить неустойку, т.е. всего (C+L). Это произойдет, если не выкупят бронь менее M-N клиентов, вероятность чего равна F(M-N). В недалеком прошлом, одна авиакомпания, узнав о возможности сверхпродажи и сверхбронирования, решила применить подобную технологию и у себя. Но вскоре, вопреки ожиданиям, начала нести убытки. Рассуждения менеджеров в расчетах были просты перепродавать столько билетов, сколько в среднем и возвращается билетов. Однако посмотрим на нашу формулу F(M-N) = . Неустойка, как правило, не меньше цены за билет и потому правая часть равенства уж точно меньше 0,5. Отсюда, как легко сообразить, следует, что M-N, то есть сверхпродажа, должна быть меньше среднего числа возвращаемых билетов.
Задача выбора на обслуживание из двух потоков требований
Снова посмотрим на проблему, описанную в 3.1. - продажу ресурса по нескольким тарифам, но попробуем сейчас решить ее динамически. В настоящий момент многие авиакомпании пытаются реализовать способы расчета и управления, учитывая поведение клиентов «в динамике» т.е. принимать решение «закрыть или открыть продажу дешевых билетов» непосредственно в момент поступления заказа на билет. Несомненно, что подобный метод дает неоспоримые преимущества. Однако есть и недостатки. К ним, прежде всего, отнесем сложность математической модели.
Предположим, что авиакомпания может продавать билеты на одно и то же место на один и тот же рейс по высокой и низкой цене. Условие раздельность потоков разной доходности не требуется. Но хотя требования на дешевые и дорогие билеты поступают случайно, из накопленной статистики известна интенсивность их поступления.
Вопрос, который необходимо решать авиакомпании заключается в следующем: открывать ли продажу дешевого тарифа, исходя из оставшегося времени до вылета и числа незаполненных мест.
Прибор может обслужить пакет из не более N требований, двух типов, доходностью С/ и меньшей С2 . Время обслуживания пакета дискретно и равно \Т\. Длина очереди N. Потоки требований каждого типа Пуассоновские с интенсивностями Д,(/) и A2(t), где t - отражает оставшееся время до следующего освобождения прибора (считаем, что T t 0). Естественно, возникает вопрос: принимать ли в очередь дешевое требование в момент времени t, если в очереди осталось еще п свободных мест. Для ответа на этот вопрос мы введем величину R(t,n) - средний ожидаемый доход от оптимального управления п свободными местами очереди в зависимости от времени, до освобождения прибора. Под оптимальностью мы как раз и будем подразумевать, что решение о принятии в очередь дешевых требований принималось так, что средний ожидаемый доход максимален. Опуская вопрос существования этой функции, запишем для нее разностное уравнение: Действительно, здесь записанное для R(t,n) условие означает условие оптимальности. А именно, выбирается максимум из доходов при двух возможных сценариях: в момент времени / прием в очередь дешевых требований открыт и в момент времени t прием в очередь дешевых требований закрыт. В пределе, при А - 0 разностные уравнения можно преобразовать в дифференциальные. Тогда, для каждого t, R(t,n) будет являться максимумом из решений следующих дифференциальных уравнений: Здесь Ri(t,n) и первое уравнение соответственно написано для случая, если принимаются в очередь только дорогие требования, aR2(t,n) и второе уравнение соответственно написано для случая, если принимаются в очередь дорогие и дешевые требования. Таким образом, если Ri(t,n) R2(t,n), то следует принимаются в очередь только дорогие требования, ну, а если Ri(t,n) R2(t,n), то следует принимаются в очередь дорогие и дешевые требования. Для решения исходной задачи, аналогичные написанным дифференциальным уравнениям, уравнения необходимо записать для всех п (для и=1 несуществующие слагаемые пропадут) с граничными условиями R(0,n)=0 и выбирать в них максимальные решения. Заметим, что для определения R(t,n) для каждого t необходимо выбрать максимальное значение из решений двух уравнений, в которые входят R(t,n-1). Это значит, что сначала необходимо определить R(t,l), потом, используя R(t,l) найдем R(t,2), потом, используя R(t,2) найдем R(t,3) и т.д. Покажем, как все это должно работать на конкретном примере. Пусть С;= 400$ и С2=280$. Число мест в салоне JV=200. Продажа открывается за два месяца до вылета. Для начала определим Л,(/) и Я2(/). В Приложении 3 приведена статистика подачи заявок на билеты первого и второго классов на десять разных рейсов, независимых между собой. Проиллюстрируем картину подачи заявок на гистограмме, где по горизонтали отмечаются дни до вылета, а по вертикали отмечается среднее число заявок по десяти рейсам за данный день. Для дорогих билетов имеем: Из рисунка видно, что в рассматриваемом примере число требований на дорогие билеты постепенно увеличивается к вылету и максимально примерно за неделю до рейса. Для дешевых билетов имеем: Видно, что среднее число требований на дешевые билеты велико сразу с момента открытия продаж и постепенно уменьшается к вылету. На следующем шаге нужно из данных гистограмм определить Я, (г) и A2(t), произведя какое либо сглаживание. При выборе сглаживания нужно позаботиться о том, чтобы при этом не изменилось среднее число заявок. А именно, для определенных Я,(і) и я,(г) необходимо, чтобы соответствующие тарифы. Покажем результат выполнения сглаживания, произведенный при помощи программы Mathematica 4.1.
Похожие диссертации на Разработка динамических методов повышения эффективности автоматизированных систем массового обслуживания (основной пример-компьютерные системы резервирования)
