Книги, научные публикации
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ ПРИМЕНЕНИЕ КОМБИНАТОРНЫХ АУКЦИОНОВ ДЛЯ ПЛАНИРОВАНИЯ МАРШРУТОВ В МОДЕЛИРОВАНИИ ЗАДАЧИ ТРАНСПОРТ ПО ЗАПРОСУ С.В. Сатунин, магистр,
младший научный сотрудник лаборатории ТАПРАРЕСС Нижегородского филиала Государственного университета-Высшей школы экономики.
Адрес: г. Нижний Новгород, ул. Б. Печерская, д. 25/12, e-mail: sergey.satunin@gmail.com.
В работе рассматривается агентный подход к моделированию интеллектуальных тран спортных систем на примере модели Транспорт по запросу. Исследуется применимость механизма комбинаторных аукционов для динамической генерации эффективных маршрутов транспортных средств в таких системах. Описываются проблемы, возникающие при модели ровании, приводится обзор алгоритмов, позволяющих построить жизнеспособную модель.
Ключевые слова: комбинаторные аукционы, многоагентный подход, интеллектуальные транспрортные системы, многоагентные модели, транспорт по запросу, алгоритмы маршрутизации.
Введение задач. В данной статье внимание сосредотачивается на модели транспорт по запросу (DRT - Demand условиях бурного развития городов и ра Responsive Transport). Суть решения состоит в том, стущей нагрузки на транспортную сеть все что для некоторой транспортной сети маршруты, В большее внимание начинает уделяться ис время отправления, средства передвижения, и про следованию новых, перспективных моделей город чие параметры устанавливаются динамически, в ского транспорта. Стимулы к подобным исследо зависимости от существующего спроса. Это созда ваниям могут быть различны: забота об экологии, ет ориентированную на потребителя и эффектив стремление увеличить удовлетворенность потре ную в плане затрат транспортную систему.
бителей услуг, желание оптимизировать расходы Поскольку такая система, очевидно, сложна, и в транспортных компаний там, где существующие ней должны взаимодействовать несколько типов системы перестают быть эффективными. Для до- участников с различными целями, разумным вы стижения таких целей необходимы более гибкие глядит применение агентного подхода[1].
подходы к решению классических транспортных Этот подход хорошо зарекомендовал себя для БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ решения задач, которые сложно или невозможно решения определяются динамически, в зависи решить с помощью одного агента или монолитной мости от сложившейся в некоторой транспортной системы, без учета слабо формализуемых связей, сети ситуации. Проблема понимается в достаточно существующих в системе, и возможного самоорга- широком смысле, поэтому можно встретить раз низующегося поведения. личные трактовки задачи DRT. Одной из наиболее Одной из ключевых проблем при решении задачи часто встречающихся формальных постановок яв DRT является эффективная генерация транспорт- ляется следующая [4]:
ных маршрутов, т.е. фактически задача эффектив- Пусть существует некоторая транспортная сеть, ного распределения ресурсов транспортной сети представленная ориентированным графам, узлы с учетом известной в данный момент времени ин- которого представляют собой остановки, а дуги - формации. Анализ современных публикаций, по- участки дорог, ассоциированные с расстояниями священных эффективному распределению ресур- между остановками. M - множество всех пасса сов, показывает, что при решении подобных задач, жиров, N - множество всех транспортных средств.
все большее распространение получают так назы- P(t) - множество пассажиров, не приписанных ни ваемые комбинаторные аукционы. к одному транспортному средству в момент вре Комбинаторный аукцион - это аукцион в ко- мени t. Каждый клиентский запрос от пассажира z M определяется четверкой параметров тором каждый участник может делать ставку не только на отдельный объект, но и на некоторую (StartTime, EndTime, StartPoint, EndPoint ) zz z z, их совокупность. Этот механизм эффективен в тех случаях, когда наборы товаров представляют из где - начальная и конечная StartPoint, EndPoint себя большую ценность с точки зрения покупателя, zz точки маршрута, чем элементы этих наборов по отдельности. При StartTime, EndTime - желаемое время начала и менение комбинаторных аукционов позволяет по zz окончания исполнения запроса соответственно.
купателям более четко выражать свои предпочте Каждое транспортное средство i N опредеяется ния и, как следствие, увеличивают экономическую набором эффективность распределения ресурсов.
В настоящее время такие аукционы получают все, (Pointi, Speedi,Capacityi ) (1) большее распространение на практике: они исполь зуются для продажи радиочастот, транспортных Pointi где - текущая точка, в которой находится маршрутов, эффективного управления поставками транспортное средство, и т.д. [2] Также их применение можно встретить в Speedi - его средняя скорость, робототехнике, электронной коммерции и многих Capacityi - максимальная вместимость.
других областях [3] Целевая функция задается следующим образом:
Если в задаче DRT рассматривать контракты на обслуживание пассажиров как предмет торгов, то, - lengthi + StartDelayj + EndDelayj min очевидно, некоторые группы пассажиров будут i=1..M j=1..M j=1..M представлять для транспортных средств больший i N,t Ci (t) Capacityi, интерес в виде единого набора контрактов. Такими привлекательными с точки зрения транспорт где,, - экспериментальные коэффициенты, ных средств наборами являются, например, груп - километраж i-го транспортного средства lengthi пы пассажиров, находящихся на одной остановке, (отражает затраты транспортной компании), которым необходимо попасть в достаточно близкие StartDelay, EndDelay - время задержки начала и точки транспортной сети. С учетом данной специ окончания выполнения контракта.
фики можно предположить, что применение ком Ci (t) - количество пассажиров в i-ом транспорт бинаторных аукционов окажется эффективным и ном средстве в момент времени t.
для такой модели.
В применении к общественному транспорту в профиль пассажира следует включить переменную Задача оптимизации в модели price - т.е. сумму, которую пассажир готов уплатить транспорт по запросу за свой проезд, а параметры StartTimez, EndTimez DRT-сервис предоставляет услуги транспорта по можно заменить на один параметр - время ожи запросу, так, что маршруты, количество задейство- дания транспорта - wt. Тогда контракт можно ванных транспортных средств и другие параметры будет формализовать следующим набором:
БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ ляющий организовать обмен информацией между (StartPoint, EndPoint, price, wt ) (2)агентами и использовать вновь полученные данные zz z z а целевую функцию переписать так: в процессе оптимизации.
Поскольку поиск оптимального решения в задаче - rewardi + lengthi + wti min (3) DRT сводится к поиску оптимального разбиения i=1..M i=1..N i=1..M множества пассажирских контрактов между транс Данная целевая функция учитывает как доходы портными средствами, в качестве третейского и расходы транспортной компании, так и степень судьи можно выбрать механизм аукционного рас удовлетворенности клиентов, за счет включения пределения пассажиров.
времени ожидания пассажиров.
Таким образом в модель вводится третий тип Наиболее известные подходы к решению задач агентов:
такого класса описаны в работе [4]:
3) Аукционист - агент, отвечающий за распреде Точные методы включают полный перебор на ление пассажиров между транспортными средства множестве маршрутов и решение методом динами ми на основе механизма аукциона.
ческого программирования.
Чтобы учитывать предпочтения транспортных Приближенные решения базируются на исполь средств наиболее полно, будем считать, что агент зовании генетических алгоритмов и различных эв аукционист способен поддерживать проведение ристик для уменьшения вычислительной нагрузки комбинаторных аукционов. Идея применения ком Приближенные методы выглядят предпочти бинаторных аукционов состоит в том, чтобы транс тельнее, поскольку задача построения модели об портные средства добавляли контракты в свои спи щественного транспорта предполагает реальный ски не по одному, как это принято в большинстве режим времени. Точные вычисления в данных известных моделей, а сразу в виде некоторого, бо условиях становятся слишком накладными и не лее предпочтительного, набора.
успевают за стремительно меняющейся ситуаци Решение задачи в рамках такой модели может вы ей, в то время как приближенные позволяют полу глядеть следующим образом:
чать приемлемые решения в разумные сроки.
Все транспортные средства со свободными места ми просматривают все нераспределенные контрак Задача DRT как многоагентная модель ты и их совокупности (количество контрактов в наборе ограничено числом свободных мест в транс Если представить задачу DRT в виде многоагент портном средстве). Для каждого набора контрактов ной системы, то можно выделить следующие два строится оптимальный (в смысле значения целевой типа агентов:
функции (3)) маршрут при возможном включении 1) Транспортные средства (описываются профи контракта в список исполняемых. Неэффективные лем (1)) маршруты удаляются из рассмотрения. Возможные 2) Пассажиры (описываются профилем (2)) маршруты упорядочиваются по предпочтитель Налицо некая конкурентная среда, в которой ности. Таким образом для каждого транспортного агенты-транспортные средства должны бороться за средства мы получаем упорядоченный список на право обслужить агентов-пассажиров с максималь боров контрактов, которые его интересуют. На дан ной для себя выгодой. Пассажиры же, в свою оче ном этапе мы каждое транспортное средство фор редь, заинтересованы в получении качественных мирует эффективные, с его точки зрения, ставки.
услуг в кратчайшие сроки. Финансовые ожидания Проводится аукцион по предпочтениям транс агентов диаметрально противоположны: транс портных средств, победители включают выигран портные средства заинтересованы в получении ные контракты в свои исполняемые маршруты.
максимальной прибыли, пассажиры же хотели бы Шаги 1-2 повторяются до тех пор, пока все кон заплатить как можно меньше.
тракты не будут распределены, или не закончатся Те и другие обладают некоторой информацией, те и другие имеют некоторые предпочтения. По- свободные места в транспортных средствах. Во вто ром случае система ожидает освобождения ресурсов.
желания агентов аггрегируются целевой функцией (3). Данная целевая функция стремиться учесть ин тересы всех участников системы и оптимизировать Вышеописанная модель ставит несколько задач, некую суммарную величину, которая отражает по- требующих решения:
лезность системы в целом. Для нахождения опти- 1) Агенты-транспортные средства должны уметь мального решения необходим механизм, позво- выражать свои предпочтения в форме ставок на на БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ боры пассажиров (т.е. вычислять значения целевой необходимо иметь возможность оценки привлека функцию вида (3) для каждого набора пассажиров, тельности наборов пассажиров.
который их интересует).
2) Требование 1) подразумевает, что транспорт- Pickup And Delivery Problem ное средство способно построить оптимальный Суть задачи состоит в том, чтобы построить опти маршрут, обслуживающий некоторый набор пас мальный (в смысле значения целевой функции сажиров. Эта задача относится к классу Pickup And (3)) маршрут, обслуживающий множество кон Delivery Problem.
трактов, заданных профилем вида (2). С дополни 3) Аукционист должен предоставлять механизм тельным ограничением: для всех контрактов точка проведения аукциона (возможны различные вари StartPoint должна быть посещена раньше, чем точ z анты дизайна аукциона) и уметь находить реше ка (4).
EndPoint ния проблемы определения победителей (WDP - z Анализ публикаций, посвященных этой пробле Winner Determination Problem).
ме показывает, что в качестве основы для прибли Каждая из приведенных выше задач с ростом раз женного решения используется алгоритм Соломо мерности дает огромную вычислительную нагруз на, описанный в работе [8]. Суть алгоритма состоит ку, поэтому приближенные методы решения с ис в последовательном формировании маршрута.
пользованием различных эвристик вновь выходят 1) На первом шаге рассматриваются все одиноч на первый план. Рассмотрим варианты решения ные контракты, вычисляется значение целевой поставленных задач.
функции для маршрута, включающего каждый оди ночный контракт. Контракт, для которого целевая Методы выражения предпочтений функция приняла наилучшее значение становится агентов-транспортных средств.
стартовым отрезком маршрута.
Полный перебор на множестве контрактов с це 2) Для каждого из оставшихся контрактов рассма лью выявления наиболее предпочтительных набо триваются все его возможные включения в марш ров представляется неосуществимым в реальном рут, полученный на предыдущем шаге так, чтобы режиме времени. Различные эвристики для сокра удовлетворялось условие (4). Выявляется наилуч щения объемов поиска на множестве контрактов шее возможное включение в текущий маршрут для описаны, например, в работе [3], где комбинатор каждого контракта. Из этих возможных маршрутов ные аукционы применялись для построения марш выбирается наилучший, он и становится текущим рутов агентов-роботов с целью поиска на частично маршрутом.
неизвестной территории. Контрактом в этой задаче 3) Шаг 2) повторяется до тех пор, пока все кон являлось обязательство посетить некоторую из тракты не будут включены в маршрут или не будет вестную точку (цель). В работе были предложены достигнуто ограничение по максимальной вмести следующие варианты эвристик:
мости транспортного средства.
Ограничить число контрактов в наборе, на ко Алгоритм Соломона хорошо зарекомендовал себя торые можно делать ставки. Для небольших раз на практике и зачастую используется как метод по мерностей использовался один из точных методов строения базового решения для применения других решения.
эвристик (например с использованием генетиче Рассматривать ставки только на хорошие по ских алгоритмов)[9].
следовательности контрактов. Понятие хорошей последовательности определяется рекуррентно:
Механизмы проведения каждая отдельная цель представляет собой хоро комбинаторных аукционов шую последовательность. Добавление новой цели t Существует множество элементов дизайна КА, с к хорошей последовательности, заканчивающейся целью s, образует новую хорошую последователь- помощью которых можно наиболее удобный в рам ках некоторой задачи механизм распределения ре ность, если вознаграждение за посещение новой последовательности больше, чем за посещение ста- сурсов. Сюда относятся в частности:
рой и t - ближайшая к s цель среди всех целей, не Количество раундов.
входящих в старую последовательность. Аукцион может проводиться в один или несколь Использовать различные алгоритмы табу- ко раундов. Во втором случае обычно на каждом поиска по дереву целей раунде определяются промежуточные победители После того, как пространство поиска сокращено, и предварительное распределение лотов.
БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ Время приема ставок. учитывает основную идею КА и избавляет участ Непрерывное - когда любой участник может сде- ников и организаторов торгов от необходимости лать ставку в любой момент проведения аукциона рассмотрения различных аспектов дизайна, услож и дискретное - когда все участники могут делать няющих модель. Единственным минусом этого подхода является незащищенность от возможных ставки только в определенный момент - до начала манипуляций участников торгов.
нового раунда аукциона.
Proxy - аукцион примечателен правилами пове Язык выражения предпочтений.
Ставки могут быть сложными объектами, свя- дения участников. Такой аукцион проходит в не сколько раундов. Пусть [0,1,...L] - множество участ занными логическими операторами. Если внутри ников аукциона. 0 - продавец, 1 L - покупатели.
одного набора все элементы связаны, очевидно, Xl - конечный набор контрактов, доступных поку логическим AND, то предпочтения для многих пателю l. Распределение контрактов описывается наборов могут быть выражены через AND, OR или набором x = (x1...xl ). Доступное распределение - XOR. Таким образом покупатель может заявить, что элемент непустого множества F = X1... Xl.
его интересуют все наборы, один или несколько на Предполагается, что каждый покупатель может боров или только один из наборов соответственно.
упорядочить все возможные распределения, бази Критерий остановка.
руясь только на доставшихся ему в рамках этих рас Данная проблема специфична для многораундо пределений контрактах. Таким образом, покупате вых аукционов. Необходимо определить критерии, ли выстраивают строгий порядок на множестве при соблюдении которых аукцион считается завер Xl.
шенным.
На каждом раунде состояние аукциона определя Правила приема ставок.
t x ется предварительным распределением и мно Для многораундовых аукционов на каждом раун жеством ставок (Blt )l =1...L. Изначально множество де могут быть определены так называемы запра ставок пусто, предварительное распределение при шиваемые цены как на отдельные товары, так и писывает каждому покупателю нулевой контракт.
на их наборы. Эти цены обычно определяются по Каждый раунд аукциона включает в себя следую результатам предыдущего раунда. Кроме того мо щие шаги:
гут быть наложены дополнительные ограничения каждый покупатель определяет свои доступные на поведение покупателей. Например в некоторых ставки на текущий раунд:
аукционах временные победители обязаны повто рить свои ставки с предыдущего раунда в следую щем раунде.
каждый покупатель, который не является те l [2] дает полное описание теории комбинаторных кущим победителем и не исчерпал свои доступные аукционов. Там же рассматриваются наиболее рас ставки, предлагает свою наиболее предпочтитель пространенные на практике механизмы КА:
ную ставку на текущий раунд:
1) Однораундовый аукцион с закрытыми ставками t 2) Аукцион VCG (Vickrey Clarcke Grove) [x0l =0l, Alt ] Blt = Blt -1 {max Alt} 3) Proxy аукцион все остальные покупатели не делают новых ставок Остановимся подробнее на первом и третьем ти пах аукционов, т.к. они были реализованы в про Blt = Blt - граммном прототипе.
если на раунде t нет новых ставок, то аукцион за Однораундовый аукцион с закрытыми ставками канчивается, в противном случае продавец опреде является самым простым и наиболее распростра ляет лучшее на данном этапе разбиение, и начина ненным на практике. Аукцион проводится в один ется новая итерация.
раунд. Все участники предоставляют аукционисту все свои комбинаторные ставки одновременно, с Задача определения победителей учетом заранее определенного языка выражения предпочтений, ни одному из участников не из- Независимо от дизайна аукциона перед аук вестны чужие ставки. Решается задача определения ционистом встает задача определения победите победителей, победившим участникам сообщается лей (в англоязычной литературе WDP - winner информация о выигрыше, после чего производится determination problem). Необходимо найти опти оплата. Несмотря на кажущуюся простоту, этот тип мальное разбиение множества продаваемых объ аукциона зарекомендовал себя очень хорошо. Он ектов на непересекающиеся подмножества с целью БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ оптимизации выручки. Число разбиений множе- Программный прототип модели DRT ства из n элементов на k непустых подмножеств с использованием КА.
определяется числом Стирлинга второго рода:
По описанной модели был разработан программ i k - k ный прототип, с использованием технологий.Net и S(n, k) = (-1) (k - i)n i k! Google Maps.
i= С помощью разработанной программной среды А полное число возможных разбиений множества был поставлен ряд практических экспериментов с продаваемых объектов M будет определяться по целью подтверждения жизнеспособности модели.
формуле:
В качестве алгоритма выражения предпочтений m агентов-транспортных средств выбран последова S(m,i) i= тельной генерации маршрутов на основе последо вательностей, Pickup And Delivery Problem решает Задача определения победителей является np ся с помощью алгоритма Соломона. В результате полной. Способ решения задачи определения по каждое транспортное средство может, при необ бедителя является одним из элементов дизайна ходимости, предоставить агенту-аукционисту свой аукциона. Варианты здесь могут быть различны - набор комбинаторных ставок, упорядоченных по от полного перебора на небольших размерностях до предпочтительности. В качестве механизма прове сведения к задаче линейного программирования (с дения комбинаторного аукциона может быть вы наложением некоторых дополнительных ограниче бран либо однораундовый аукцион с закрытыми ний на ставки), построения деревьев решений, ис ставками, либо proxy-аукцион.
пользования алгоритма распределенного определе Далее описаны параметры одного из эксперимен ния победителей (PAUSE) и т.д. Для программной тов с использование однораундового аукциона и реализации был выбран алгоритм построения дере полученные результаты. Программа тестировалась ва решений, описанный в работе [7].
на статическом наборе пассажиров, сгенерирован Для успешной работы алгоритма необходимо на ных случайным образом.
ложение следующего дополнительного ограниче Количество транспортных средств: ния: если некоторый отдельный лот не вошел ни в Параметры транспортных средств: вместимость - одну из предложенных участниками комбинатор 6 мест, модельная скорость - 40 км/ч.
ных ставок, ко множеству ставок добавляется ну Пассажиры - 17 человек (начальная точка - ко левая ставка на этот одиночный лот. Далее дерево нечная точка):
решений строится по следующим правилам:
1-10, 1-10, 2-15, 3-9, 3-15, 4-14, 4-14, 5-18, 7-12, 1) Каждый узел является ставкой, каждый путь от 9-7, 10-8, 11-14, 12-4, 13-14, 13-1, 14-2,17-1.
корня к листовой вершине представляет собой на Результаты:
бор ставок, в которых элементы не пересекаются.
3 транспортных средства с использованием опи 2) Все вершины, отстоящие на один шаг от корня, санных выше алгоритмов полностью выполняют представляют собой ставки, содержащие первый элемент. Все последующие вершины - ставки, со- все контракты за 36 минут. Среднее время ожида ния составляет 3.76 минуты.
держащие следующий по порядку элемент, и так до Таблица1.
тех пор, пока не получатся листовые вершины.
Статистика транспортных средств:
Пример построенного дерева решений для 5 эле ментов с учетом принятых ставок приведен на рис. 1:
№ транспортного средства Пройденное расстояние Выручка 1 21.2 3 24 12 135 14 3 13.2 35 3 2 25 2 25 Опыт показывает, что proxy - аукцион в сочета 4 4 4 3 35 3 3 35 нии с методом ставок на хорошие последователь 5 5 4 4 ности дает не лучший результат. Дело в том, что в 35 векторе ставок большинство ставок содержат одни и те же контракты, что следует из метода построе Рис. ния хорошей последовательности. Если транс БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БИЗНЕС-ИНФОРМАТИКИ портное средство проигрывает наиболее предпо- ет простор для дальнейших исследований. Сто чтительную ставку, велика вероятность, что оно ит однако отметить, что данный подход весьма проиграет и все остальные. сложен для практической реализации. Он под Тем не менее использование proxy-аукциона разумевает, например, техническую безотказность представляется эффективным в задаче DRT, т.к. агента-аукциониста, не учитывает практических теоретически такой механизм проведения аукцио- особенностей существующего дорожного движе на позволяет проигрывающим не выключаться из ния: пробок, ремонтных работ и т.д. Необходимо борьбы и распределять транспортную нагрузку бо- сместить акцент исследований на разработку де лее равномерно. Скорее всего, в сочетании с proxy- централизованной модели, которая позволяла бы аукционом необходимо использовать другой алго- учитывать реальную дорожную обстановку и сни ритм решения pickup and delivery problem. жала зависимость системы от надежности работы Вопрос поиска более удачного сочетания алго- центрального звена. Поскольку список задач, воз ритма выражения предпочтений и дизайна КА яв- никающих при моделировании, будет во многом ляется предметом текущих исследований. совпадать с задачами, приведенными в статье, то В целом же можно утверждать, что разработан- следует надеяться, что описанные подходы к их ный прототип подтверждает жизнеспособность решению окажутся эффективными также и для описанной в данной статье модели и открыва- децентрализованной модели.
Литература 1. Xu Jin, Habib Abdulrab, Mhamed Itmi, A multi-agent based model for urban demand-responsive passenger transport services //Neural Networks, 2008. IJCNN 2008. (IEEE World Congress on Computational Intelligence).
2. P.Cramton, Y.Shoam, R. Steinberg: Combinatorial Auctions //The MIT press Cambridge, 2005.
3. M. Berhault, H. Huang, P. Keskinocak, S. Koenig, W. Elmaghraby, P. Griffin, A. Kleywegt, Robot Exploration with Combinatorial Auctions // Intelligent Robots and Systems, conference 2003. (IROS 2003). Volume 2, 27-31 Oct. 2003 Page(s):1957 - 1962.
4. R'emy Chevrier, Philippe Canalda, Pascal Chatonnay and Didier Josselin, Comparison of three algorithms for solving the Convergent Demand Responsive Transportation Problem // Proceedings of the IEEE ITSC IEEE Intelligent Transportation Systems Conference Toronto, Canada, September 2006, 17-20.
5. Miyamoto,T., Nakatyou,K., Kumagai,S. Route planning method for a dial-a-ride problem //Systems, Man and Cybernetics, 2003. IEEE International Conference on Volume 4, 5-8 Oct. 2003 Page(s):4002 - 4007.
6. David Portera, Stephen Rassentia, Anil Roopnarinec and Vernon Smitha: Combinatorial auction design, www.pnas.org/cgi/doi/10.1073/pnas.1633736100 (дата обращения 05.11.2009).
7. Jos'e M Vidal: Fundamentals of Multiagent Systems Multiagent-Systems (дата обращения 05.11.2009).
8. Marius M. Solomon Algorithms for the vehicle routing and scheduling problems with time window constraints //Operations Research Society of America Vol. 35, No. 2, March-April 1987.
9. Haibing Li and Andrew Lim A Metaheuristic for the Pickup and Delivery Problem with Time Windows // International Journal on Artificial Intelligence Tools;
Jun2003, Vol. 12 Issue 2, p. 73, p. 14.
БИЗНЕС-ИНФОРМАТИКА №4(10)Ц2009 г.