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

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

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ

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

УРОВЕНЬ ТЕХНИКИ

0002 Навигационные системы содержат помимо прочего определенные основные средства: устройство(а) ввода-вывода, блок обработки данных, навигационное вычислительное ядро, географическую базу данных, обычно содержащую улицы и интересующие места (POI) и интегральную схему системы глобального позиционирования. Кроме того, для автомобильных систем существует гироскопическая интегральная схема, которая обеспечивает направление и наличие информации о скорости. У существующих систем есть значительные недостатки. Навигационные системы, встроенные в транспортные средства компанией-изготовителем комплексного оборудования (OEMS), требуют дорогостоящих аппаратных средств и программных средств, которые устаревают намного скорее, чем автомобиль, в котором они установлены. Кроме того, бортовая географическая база данных требует использования носителя данных, такого как жесткий диск, который относительно более склонен к сбоям в работе по сравнению с другими электронными компонентами, а базу данных обязательно необходимо периодически обновлять.

0003 Навигационные системы, основанные на использовании серверов, представляют собой системы, в которых алгоритм наведения постоянно размещен на центральном вычислительном блоке или сервере. Конечные пользователи вводят навигационные места назначения с использованием различных устройств, включая мобильные телефоны, компьютеры, портативные навигационные устройства, интегрированные системы транспортных средств и мобильные терминалы данных (MDT). Запрос конечного пользователя сообщают на сервер беспроводным образом посредством мобильной телефонной сети, спутниковой сети, сети Wi-Fi или сети смешанного типа, содержащей беспроводные и проводные соединения. Линия беспроводной связи может быть прервана в определенном количестве случаев (например, туннели, бетонные впадины в центрах главных городов, в ненаселенных областях и в случаях высокой нагрузки на линию беспроводной связи). В зависимости от того, как была выполнена система, количество данных, которые необходимо передать, часто перегружает беспроводной источник. Сотовый телефон и персональная навигация имеют схожие ограничения.

0004 В любом географическом регионе существует небольшое количество источников информации из баз данных с навигационными данными. База данных с навигационными данными будет обеспечивать координаты и названия улиц, а также определение типа улиц для каждой дороги (например, населенная, коммерческая, автомагистраль, трасса и т.д.). Часто база данных с навигационными данными также будет содержать интересующие места (POI), которые представляют собой локальные компании, места гражданской и исторической значимости, школы, церкви и другие места, часто посещаемые населением. В США Бюро переписи предлагает для использования данные топологически интегрированной системы географического кодирования и привязки (данные TIGER). Данные топологически интегрированной системы географического кодирования и привязки (TIGER) не содержат полного набора улиц в США, по которым осуществляется навигация, а также не предоставляют информацию об интересующих местах (POI). Существует множество коммерческих поставщиков баз данных с навигационными данными, которые предоставляют информацию об интересующих местах (POI) и по существу полный набор улиц, по которым осуществляется навигация. Компании Navteq® и Tele Atlas® представляют собой две наиболее крупные компании в США. Если в тексте не указано обратное, использование интересующих мест (POI) в данном патенте означает общую идею, касающуюся интересующих мест, а не какую-либо отдельную подборку интересующих мест. В Корее и Японии базы данных с навигационными данными контролируются правительством. Другие юрисдикции простираются в диапазоне от правительственных организаций до частных служб, поставляющих базы навигационных данных. На рынок навигации и баз навигационных данных часто выходят дополнительные конкурирующие игроки, включая компании Apple и Google. Кроме того, революция в области общедоступных сторонних ресурсов оказывает влияние на базы данных карт. Например, МарВох работает на общедоступной совместной базе данных карт, называемой OpenStreetMap.В целом, на данном этапе практически вся транспортная навигация и навигация по мобильному телефону основана на навигационном программном обеспечении от одного источника и дополнительной базе навигационных данных от другого источника. Практически всегда, отдельная компания собирает в единое целое и продает компоненты для навигации в качестве законченного решения.

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

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

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

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

0009 Основная особенность, которую необходимо исключить из современной технологии, состоит в том, что она создает маршруты с использованием кусочной оптимизации и присвоения весовых коэффициентов. Он не создает решения в явном виде, даже в относительно локальной области несмотря на то, что современные обрабатывающие устройства и алгоритмы легко обеспечили бы возможность получения локальных решений в явном виде. Кусочная оптимизация и присвоение весовых коэффициентов создает сдвиг по отношению к пути по трассе или автомагистрали. Такие устаревшие вычислительные ядра создают действующие искажения, которые по существу влияют на технические характеристики современных навигационных систем. Эти ядра были записаны для медленных обрабатывающих устройств, таких как первое поколение обрабатывающих устройств для систем реального времени (RTOS). Эти ядра допускали намного более меньший объем данных, чем объем данных, который может обрабатываться в настоящее время (например, петабайтные системы). Эти ядра допускали, что беспроводная передача данных, при условии наличия таковой, имели бы по существу меньшие скорости по сравнению с теми, которые возможны в настоящее время.

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

00011 Действующие искажения, вызванные устаревшими навигационными ядрами, содержат неточные расчеты оценочного времени поступления (ЕТА), недостаток обучения, невозможность решения задачи множества транспортных средств/множества мест назначения с использованием того же самого программного обеспечения, которое используют для обычной навигации, невозможность оптимизации решения задач множества транспортных средств/множества мест назначения, невозможность предоставления обоснованной оценки, когда пользователь по существу отклонился от расчетного маршрута, невозможность осуществлять навигацию назад и вперед между устройствами (например, между блоком внутри автомобиля и сотовым телефоном).

00012 Большинство навигационных систем выполнены с возможностью выдачи оценочного времени поступления (ЕТА) с 10% вероятностью ошибки или менее в 80-90% случаев. Большинство потребителей довольны этим, поскольку (1) они не основываются на информации об оценочном времени поступления (ЕТА), так как оценивают только их время поступления, (2) информация об оценочном времени поступления (ЕТА) представляет собой более подходящую информацию по сравнению с той, которую они получают из других источников, и/или (3) конечные пользователи упорядочили свои ожидания по отношению к доступному уровню технических характеристик системы. Однако существуют категории пользователей, для которых вероятность ошибки является абсолютно неприемлемой. Например, водители транспортных средств для коммерческих перевозок, операторы коммерческого транспортного парка, люди, имеющие сжатые сроки, и люди, живущие в перенаселенных областях (где современные технологии реализуются недостаточным образом).

00013 Низкие значения оценочного времени поступления (ЕТА) частично относится к невозможности современных навигационных ядер обучаться каким-либо целенаправленным образом. Например, большинство людей знают, что в понедельник утром (за исключением праздников), трасса 405 в Лос-Анджелесе перегружается в 8:00 утра. Современные навигационные ядра не делают этого. Аналогичным образом, регулярно перегружены трасса I-696 в столичном Детройте, трасса I-90/94 в Чикаго, трасса I-95 в Бостоне и многие другие основные трассы в основных городах. Скорости движения в часы пик на этих дорогах могут в среднем изменяться от между 60 миль (96,54 км) в час и 10 милями (16,09 км) в час. Большая часть изменений является полностью предсказуемой: конкретные моменты времени, дни и условия являются относительно плохими, такие как пятничные дни и дождь. К сожалению, современные навигационные решения не выполнены с возможностью предварительной (a priori) оценки данной ситуации.

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

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

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

00017 Низкокачественные решения для осуществления навигации для множества транспортных средств/множества мест назначения приводят к многочисленным затратам пользователя и общества. Например, владельцы большого транспортного парка, которые используют продукцию с 10% ошибкой их оценочного времени поступления (ЕТА), регулярно должны выбирать между наличием большего количества транспортных средств, чем это необходимо на заданный день (дополнительные расходы), и потерей стандартов обслуживания (потерей клиентов). Для большинства людей данная проблема возникает во время домашних заявок на выполнение технического обслуживания. Компании телеграфной связи, телефонные компании и ремонтный персонал регулярно называют людям обобщенное время, такое как с 9 утра до полудня, а не предоставляют более точное время. Это приводит к возникновению растроенных клиентов и утрате бизнес-возможностей (люди, в силу необходимости, должны отказаться от заявки на выполнение технического обслуживания).

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

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

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

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

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

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

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

00024 На поверхности Земли или на любой абстрактной конструкции, отражающей часть поверхности Земли, возможно создание ограниченных географических регионов (BGR) в любой локализованной области, в которой пользователь хочет получить помощь от навигационного устройства. В пределах каждого ограниченного географического региона (BGR) будет приведено множество улиц и интересующих мест (POI). На периферии ограниченного географического региона (BGR) будут расположены узлы, отражающие пересечение улиц с границами ограниченного географического региона (BGR).

00025 При навигации в пределах ограниченного географического региона (BGR), существуют только четыре возможности: (1) пользователь вводит ограниченный географический регион (BGR) в одном узле и существует ограниченный географический регион (BGR) через другой узел, (2) пользователь дает начало поездке в ограниченном географическом регионе (BGR) и существует ограниченный географический регион (BGR) через узел, (3) пользователь вводит ограниченный географический регион (BGR) через узел, а место назначения находится в указанном ограниченном географическом регионе (BGR), или (4) место отправления и место назначения находятся в ограниченном географическом регионе (BGR). В случае 2 место отправления будет обработано в качестве узла для выполнения расчетов. В случае 3 место назначения будет обработано в качестве узла для выполнения расчетов. В случае 4 место отправления и место назначения будут обработаны в качестве узла для выполнения расчетов. Таким образом, в каждом ограниченном географическом регионе (BGR) возможна идентификация точного количества узловых пар, отражающего общую совокупность возможных решений для пересечения ограниченного географического региона (BGR). Кроме того, ограниченные географические регионы (BGR) имеют такой размер, что для каждой узловой пары возможно быстрое решение в явном виде.

00026 Настоящее изобретение будет оптимизировать некоторые заданные пользователем зависимые переменные для конечного пользователя: (1) время, (2) расстояние, (3) топливо, (4) затраты или (5) другую коммерчески значимую, заданную пользователем зависимую переменную. Настоящее изобретение будет осуществлять это путем создания оценочной функции, которая может быть использована для обеспечения значения для каждой узловой пары. Оценочная функция будет использовать весовые коэффициенты в зависимости от типа дороги из базы данных для навигационных данных, а также накопленные данные для создания значения для каждой узловой пары.

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

00028 После расчета решения для узловой пары, это решение сохраняют в таблице поиска узловых пар (NPLUT). Таблицу поиска узловых пар (NPLUT) сортируют по ограниченному географическому региону (BGR) таким образом, что в любой заданный момент времени, только большинство локальных решений выдано на обрабатывающий блок, что обеспечивает улучшение скорости и эффективности. Этот блок может сравнивать фактические технические характеристики с рассчитанным значением для каждой узловой пары. С использованием функции ошибок, этот блок может регулировать сохраненное решение для узловой пары. Кроме того, таблица поиска узловых пар (NPLUT) может сохранять переменные данные и характеристические данные (цифровой результат или метку), что обеспечивает возможность полных факторных расчетов ANOVA или расчетов MANOVA в зависимости от интересующих зависимых переменных. Таблица поиска узловых пар (NPLUT) может использовать факторы, включающие, без ограничения, время дня, день недели, дату, водителя, возраст водителя, место, в котором водитель научился водить (водители из Бостона всегда быстро ездят), возникновение конкретного события (например, проведение футбольного матча поблизости), структуру, атмосферные осадки, температуру и т.д.

00029 В таблице поиска узловых пар (NPLUT) каждый ограниченный географический регион (BGR) и узловая пара имеет уникальное обозначение или имя. Для обоих возможны многочисленные схемы нумерации. Ограниченные географические регионы (BGR) могут быть расположены в определенном порядке с использованием порядковой схемы нумерации, количественной схемы нумерации, алфавитно-цифровой схемы нумерации (со значимостью или без нее) или схемы идентификации на основании широты и долготы ограниченного географического региона (BGR). Порядковая схема нумерации должна быть нацелена на базу данных и вычислительную эффективность. Значения, используемые для схемы расположения в определенном порядке ограниченного географического региона (BGR), не должны быть представлены конечному пользователю. В случае, в котором предпочтительно представление нумерации или порядка ограниченного географического региона (BGR) конечному пользователю, преобразование может быть выполнено с тем, чтобы показать конечному пользователю ограниченные географические регионы (BGR) просто по ссылочным кодовым обозначениям (например, 1, 2, 3 и т.д.) Это может быть полезно для конкретных применений в автотранспортном хозяйстве, таких как транспортное средство, сдаваемое в аренду, где в настоящее время зоны используют для распределения транспортных средств и заказов.

00030 Каждому узлу для каждого ограниченного географического региона (BGR) необходимо присвоить уникальное кодовое обозначение. Кодовое обозначение узловой пары могло бы затем представлять собой уникальное кодовое обозначение для обоих узлов, а также кодовое обозначение для соответствующего ограниченного географического региона (BGR). Для полного описания узловой пары было бы необходимо одно кодовое обозначение для идентификации ограниченного географического региона (BGR) и узловой пары. Часть узла кодового обозначения узловой пары сообщалась бы системе. В реальном мире, каждый узел отражает место на дороге, поскольку он проходит через границу ограниченного географического региона (BGR). Таким образом, кодовое обозначение узловой пары будет обеспечивать два положения, на той же самой дороге или на других дорогах, которые расположены на границе конкретного ограниченного географического региона (BGR).

00031 В таблице поиска узловых пар (NPLUT), ссылка на каждую узловую пару будет иметь значение для каждой зависимой переменной (например, времени, расстояния, потребления топлива, навигации по дорогам с твердым покрытием и т.д.). С использованием каждой навигации, пересекающей узловую пару, будет измерено или оценено фактическое значение. Фактическое значение будет затем сохранено в таблице поиска узловых пар (NPLUT) вместе с независимыми переменными, касающимися поездки, такими как возраст водителя, пол водителя, профессия водителя, тип транспортного средства, срок службы транспортного средства, время дня, день недели, дата, погода и т.д. После осуществления каждой навигации, средние значения ANOVA и MANOVA (то есть сумма, сумма квадратов и т.д.) могут быть сохранены и связаны с поездкой по узловой паре. Таким образом, когда конкретный пользователь осуществляет навигацию, для каждой узловой пары может быть представлено скорректированное значение.

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

00033 Ограниченные географические регионы (BGR), узловые пары и независимые переменные могут быть использованы способами, которые в настоящее время являются недоступными, вследствие того, что навигация основана на сервере. Например, если погода начинает воздействовать на транспортные потоки в Чикаго, то это обычно будет доходить до Детройта в пределах заданного периода время. Простой вспомогательный процесс может быть присоединен к системе, которая на основании независимых переменных оценивает время ожидания между погодой в Чикаго, например, и Детройтом, а зависящая от времени вероятность погоды из Чикаго становится погодой, которая влияет на транспортные потоки в Детройте. Система может затем создавать оценочное время поступления (ЕТА) для будущих поездок на основании предстоящей погоды или других прогнозируемых будущих событий. Оценочное время поступления для будущих поездок может затем периодически обновляться, поскольку корреляция данных становится более точной.

00034 Осуществление навигации для множества транспортных средств и множества мест назначения (MVMD) представляет собой обобщение одного транспортного средства, сталкивающегося с задачей одного места назначения. Множество транспортных средств и множество мест назначения (MVMD) обычно связаны с парками транспортных средств. Существуют различные виды задач множества транспортных средств и множества мест назначения (MVMD). У компаний по доставке, таких как Fedex или Post Office, есть задача множества транспортных средств и множества мест назначения (MVMD). У компаний по грузовым перевозкам есть задача множества транспортных средств и множества мест назначения (MVMD). У такси и лимузинов есть задача множества транспортных средств и множества мест назначения (MVMD). Мы задаем задачу как предоставление одному транспортному средству одного или большего количества мест назначения. Последовательность мест назначения, присвоенных одному транспортному средству, называют маршрутом. Мы задаем ограничивающее условие в качестве ограничения в отношении последовательности мест назначения для одного или большего количества транспортных средств.

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

00036 Процесс генерирования маршрутов для транспортных средств называют диспетчеризацией. Отдельные записи базы данных, требующие того, чтобы транспортное средством ехало в место назначения, называют заказом. Заказ может содержать единственное место отправления и единственное место назначения, единственное место отправления и несколько мест назначения или несколько мест отправления и единственное место назначения. Что касается настоящего изобретения, то маршрутизация 2 или 2000 транспортных средств выполняется таким же образом. Во-первых, необходимо выбрать зависимые переменные для транспортного парка. Все места назначения для всех заказов и все транспортные средства вводят в диспетчерскую базу данных. Система начнет работу с минимизации ограниченных географических регионов (BGR), пересекаемых всем транспортным парком при выезде каждого транспортного средства в первое место назначения с одновременным соблюдением всех ограничивающих условий. Это заканчивается простой матричной математикой ввиду способа, которым организованы ограниченные географические регионы (BGR) и узловые пары. С каждым дополнительным местом назначения обходятся точно таким же образом, при этом предыдущее место назначение выступает в качестве нового места отправления. Если диспетчеризация невозможна вследствие того, что маршрут нарушает ограничивающее условие, то система будет выполнять итерацию с предоставлением предпочтения месту назначения или местам назначения, которые вызвали нарушение ограничивающего условия. Таким образом, система быстро идентифицирует потенциальные нарушения ограничивающих условий и будет пытаться выполнить оптимизацию для обеспечения отсутствия каких-либо нарушений ограничивающих условий. Иногда не будет существовать какого-либо решение, которое не будет нарушать ограничивающее условие. Система выполнена с возможностью обеспечения возможности оптимизированного решения с минимальным количеством нарушений уграничивающих условий. В случае необходимости для конкретного транспортного парка, система может обеспечить возможность дополнительных оптимизированных решений, которые имеют большее количество нарушений ограничивающих условий. Таким образом, оператор транспортного парка может определить целесообразный баланс между оптимизацией прокладки маршрута и наличием отклонений в сервисе (ограничения ограничивающих условий).

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