Способ и система для навигации транспортного парка, диспетчеризация и прокладка маршрута для множества транспортных средств и множества мест назначения - RU2629438C2
Код документа: RU2629438C2
Чертежи
Описание
ОБЛАСТЬ ТЕХНИКИ
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) имели бы уровень насыщения для всех транспортных средств. Комплексная система управления транспортными потоками могла бы загрузить-разгрузить все ограниченные географические регионы (BGR) в перенаселенных городских районах с обеспечением минимизации общего времени, которое тратят все транспортные средства в указанных районах для достижения их мест назначения. Данное решение увеличило бы общую пропускную способность дорожной сети.
00038 Данная система также может вмещать множество типов услуг в пределах того же самого транспортного парка. Например, пассажирская транспортная компания может иметь в распоряжении лимузины, такси и услуги на распределенные поездки. Система может просто управлять этим за оператора транспортного парка. Каждым типом услуги управляют по-отдельности: диспетчеризация лимузинов оптимизирована для заказов лимузинов, диспетчеризация такси оптимизирована для заказов такси, а диспетчеризация услуг на распределенные поездки оптимизирована для заказов на распределенные поездки. Однако система имеет одну важную особенность для транспортного парка с множеством услуг. Когда диспетчеризация не может найти маршрут для услуги без каких-либо нарушений ограничивающих условий, система, в соответствии с правилами оператора транспортного парка, может попытаться обслужить нарушения ограничивающих условий с использованием транспортных средств для других типов услуг. Например, если заказ на предоставление услуги по распределенной поездке вызывает нарушение ограничивающего условия, то оператор транспортного парка может обслужить этот заказ с использованием такси или лимузина. Кроме того, система будет предлагать диспетчеру решения с использованием такси или распределенной поездки. Таким образом, представитель службы обслуживания клиентов, пытающийся выполнить заказ на лимузин, может представить пассажиру наиболее широкое множество вариантов: сколько времени займет доставка лимузином, сколько времени займет доставка такси и сколько времени займет распределенная поездка.
00039 Распределение поездки и распределение нагрузки дополнительно осложнены тем фактом, что задание последовательности остановок представляет собой отдельную математическую задачу, вытекающую из группирования поездок, однако они связаны непосредственным образом. Порядок остановок может быть определен системой посредством следующего способа. Определяют середину всех положительных остановок (PSM). Определяют середину всех отрицательных остановок (MSM). Находят середину между положительными остановками (PSM) и отрицательными остановками (MSM). Положительная остановка, которая наиболее удалена от середины между положительными остановками и отрицательными остановками (MID), представляет собой место первой посадки. Отрицательная остановка, которая наиболее удалена от середины между положительными остановками и отрицательными остановками (MID), представляет собой место последней высадки.
00040 Для некоторых транспортных парков также необходимо организовывать транспортные средства. Например, при отсутствии текущих заказов необходимо организовывать такси или организовывать офицеров полиции при отсутствии текущих вызовов. В пределах заданной области обслуживания, каждый ограниченный географический регион (BGR) имеет зависящую от времени плотность заказов (например количество заказов в час). Зависящая от времени плотность заказов для каждого ограниченного географического региона (BGR) в области обслуживания может быть использована в качестве псевдо-заказа. Система может брать количество свободных транспортных средств и выполнять псевдо-заказы, если они представляют собой реальные заказы. Таким образом, свободные транспортные средства будут распределены в наиболее подходящих местах с учетом всех ограничивающих условий транспортного парка.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
00041 Приведено 13 релевантных чертежей. Фиг. 1 представляет собой перспективный чертеж связей системы. Фиг. 2 представляет собой перспективный чертеж связей системы согласно альтернативному варианту реализации. Фиг. 3 представляет собой перспективный чертеж связей системы согласно альтернативному варианту реализации. Фиг. 4 представляет собой перспективный чертеж связей системы согласно альтернативному варианту реализации. Фиг. 5 представляет собой перспективный чертеж связей системы согласно альтернативному варианту реализации. Фиг. 6 представляет собой перспективный чертеж связей системы согласно альтернативному варианту реализации.
00042 На фиг. 7 показана блок-схема высокоуровнего программного способа, реализованного посредством настоящей новой системы. На фиг. 8 показана блок-схема для создания ограниченных географических регионов (BGR) посредством виртуальной двумерной соты в размещающем сервере. На фиг. 9 показан альтернативный способ создания ограниченных географических регионов (BGR) в размещающем сервере. На фиг. 10 показана блок-схема пользовательской структуры транспортного парка на размещающем сервере. На фиг. 11 показана блок-схема основанного на использовании серверов способа навигации с использованием ограниченных географических регионов (BGR) и узловых пар. На фиг. 12 показана блок-схема программного процесса портативного или удаленного электронного устройства. На фиг. 13 показана Земля, вписанная в сотообразный куб.
ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ
00043 Приведенное далее описание отражает текущий предпочтительный вариант реализации настоящего изобретения. Данное описание не предназначено для ограничения настоящего изобретения, а предназначено для иллюстрации его общих принципов работы. Примеры показаны с использованием прилагаемых чертежей.
00044 На фиг. 7 показана высокоуровневая блок-схема программного способа, связанного с системой. Некоторые операции могут быть выполнены только по схеме функционирования: 99 первоначальный запуск, 26 загрузка базы данных карт, 62 создание ограниченных географических регионов (BGR) посредством подпрограммы вычисления и 56 инициализация системы. База 26 данных карт может быть приобретена у любого продавца баз данных карт или может быть использована база данных карт из источника общего пользования. Инициализация системы включает такие управленческие программы вычисления, как формирование таблицы поиска узловых пар (NPLUT), заполнение таблицы поиска узловых пар (NPLUT) любыми доступными данными, создание пользовательской базы данных, заполнение пользовательской базы данных любыми доступными данными и схожие задачи. После того, как система была запущена 56, а ограниченные географические регионы (BGR) были созданы с использованием подпрограммы 62 ограниченного географического региона (BGR), система выполнена с возможностью получения навигационных входных данных 55.
00045 На фиг. 13 показана Земля 301, заключенная в ячеистый куб 302. На компьютере виртуальная Земля 301 может быть повернута или наклонена до тех пор, пока интересующий географический земельный массив не расположен по центру. Практически во всех случаях, даже если Земля 301 представляет собой сплюснутый сфероид, интересующий географический регион может быть сделан практически параллельным лицевой стороне описывающего куба 302. Путем надлежащего выбора размера двумерной соты на кубе 302, такой размер может влиять на размер ограниченного географического региона (BGR), проецируемого на Землю 301. Данный способ называют виртуальной двумерной сотой, поскольку рисунок на Земле 301 технически не представляет собой двумерную соту, поскольку все из ограниченных географических регионов (BGR) не будут иметь те же самые формы и размеры.
00046 На фиг. 8 показан способ генерирования ограниченных географических регионов (BGR) с использованием виртуальной двумерной соты. Во-первых, система вписывает Землю в куб 44. Центр лицевой стороны 45 куба центрирован по интересующему географическому региону. Выбирают начальный размер 46 двумерной соты для лицевой стороны куба. Стандартная площадь поверхности (SSA) представляет собой целевую площадь поверхности для ограниченных географических регионов (BGR). Стандартная площадь поверхности (SSA) ограниченного географического региона (BGR), составляющая приблизительно 1 квадратный километр, считается идеальной. Затем, задают предел отклонения стандартной площади поверхности (SSA) 64. Это значение должно быть небольшим (менее 10%). Все ограниченные географические регионы (BGR) должны иметь площадь поверхности, очень близкую к стандартной площади поверхности (SSA) для минимизации вероятности наличия смешанных данных (неортогональные независимые переменные во время анализа отклонений). При необходимости, может быть изменен размер квадратов 47 двумерных сот у описывающего куба. Несмотря на то, что более сложно в вычислительном отношении, это будет минимизировать изменение стандартной площади поверхности (SSA) (только наиболее внутренняя часть представляет собой квадрат, а каждый следующий слой выполнен в виде прямоугольника с увеличивающимся соотношением сторон. Двумерные соты куба проецируют на Землю 48 для создания исходных ограниченных географических регионов (BGR). Оценивают 49 стандартную площадь поверхности (SSA) всех ограниченных географических регионов (BGR). Если результаты анализа стандартной площади поверхности (SSA) в порядке 50, то сохраняют 53 ограниченные географические регионы (BGR) и завершают 59 процесс генерирования ограниченного географического региона (BGR). Если результаты анализа стандартной площади поверхности (SSA) не в порядке 50, то удаляют 51 все из ограниченных географических регионов (BGR). Затем, система регулирует начальный размер 52 двумерных сот, регулируют 63 соотношение двумерных сот внешнего слоя (насколько быстро внешние слои лицевой стороны сотообразного куба становятся прямоугольниками с увеличивающимся соотношением сторон) и регулируют 64 предел отклонения стандартной площади поверхности (SSA). Затем весь процесс начинают 47 заново.
00047 На фиг. 9 показана блок-схема альтернативного варианта реализации для генерирования ограниченных географических регионов (BGR). Процесс начинают 58 с нахождения 65 центра интересующего географического региона. Один ограниченный географический регион (BGR) создают 66 с площадью поверхности, равной стандартной площади поверхности (SSA), и по меньшей мере с четырьмя сторонами. Задают предел отклонения стандартной площади поверхности (SSA) 64. Слой ограниченных географических регионов (BGR) создают 67 вокруг существующего ограниченного географического региона или существующих ограниченных географических регионов (BGR), в котором или которых новый слой из ограниченных географических регионов (BGR) имеет минимальный периметр. Анализируют 49 стандартную площадь поверхности (SSA) слоя. При условии, что результаты анализа стандартной площади поверхности (SSA) в порядке, добавляют дополнительные слои ограниченных географических регионов (BGR). Если результаты анализа стандартной площади поверхности (SSA) не в порядке 50, то стандартную площадь поверхности (SSA) анализируют 69 только для последнего слоя. Если последний слой содержит ограниченные географические регионы (BGR), которые перекрывают границу интересующего географического места 70, и это является единственной причиной недопустимой стандартной площади поверхности (SSA), то сохраняют 71 ограниченные географические регионы (BGR). Если это не краевое географическое место 70, то удаляют 51 последний слой ограниченных географических регионов (BGR). Допустимый максимальный периметр будет увеличен 68 на 10% по отношению к предыдущей итерации, и будет создан 67 новый слой ограниченных географических регионов (BGR). Процесс продолжается до тех пор, пока весь интересующий географический регион не охвачен ограниченными географическими регионами (BGR) 72.
00048 На фиг. 7, как только возникла программа 62 вычисления ограниченного географического региона (BGR), может возникнуть структура 61 транспортного парка (см. фиг. 10). На фиг. 10 каждый заказчик или транспортный парк зарегистрирован с использованием структуры 80 транспортного парка. Такая регистрация включает заполнение базы данных информацией о транспортных средствах 81, водителях 86 и оказываемых услугах 91. Данные, собранные о транспортных средствах 81 в транспортном парке, содержат количество 82 транспортных средств, типы 83 транспортных средств (включая тип топлива), километраж 84 транспортных средств и другие заданные пользователем данные 85 о транспортном средстве (независимая переменная или характеристические данные). Данные, собранные о водителях, содержат имя 87, номер водителя или идентификатор 88, вид 89 занятости (сотрудник, независимый контрагент, владелец/оператор и т.д.) и другие заданные пользователем данные 90 о водителях (независимая переменная или характеристические данные). Данные, собранные об услугах транспортного парка, содержат тип 92 заказчика, стандарты 93 обслуживания, область 94 обслуживания и другие заданные пользователем данные 95 по обслуживанию (независимая переменная и характеристические данные). База данных также обеспечивает возможность наличия заданных пользователем заправочных станций 96. После задания всех данных, эти заданные данные загружают в базу 97 данных, и завершают 98 программу вычисления.
00049 Согласно фиг. 7, навигационный входной запрос 32 конечного пользователя принимают посредством беспроводных средств. На фиг. 1 показан вариант реализации беспроводной связи и геопозиционирования, которой необходим для навигации. Конечный пользователь расположен в транспортном средстве 201, которое содержит встроенное или установленное удаленное электронное устройство (RED). Транспортное средство 201 определяет географическое положение посредством интегральной схемы системы глобального позиционирования (GPS), гироскопа и/или приемопередатчика спутника. Множество спутников 200 обеспечивает выдачу сигналов системы глобального позиционирования (GPS) на приемопередатчик системы глобального позиционирования (GPS) в транспортном средстве 201. Транспортное средство 201 затем выполнено с возможностью сообщения его положения на центральный сервер 203 с использованием беспроводной сети 202. Беспроводная сеть 202 может представлять собой сотовую сеть или сеть для мобильных телефонов, радиочастотную сеть или другие беспроводные средства. Передача могла бы быть также выполнена посредством сети со смешанными средствами, такой как wi-fi сеть, которая скачивает и загружает запросы на сервер посредством проводного интернет-соединения (не показано).
00050 На фиг. 2 показан альтернативный вариант реализации системы связи и геопозиционирования. На фиг. 2 транспортное средство 201 было заменено сотовым телефоном, мобильным терминалом данных (MDT) или удаленным электронным устройством (RED) 204. Сотовый телефон, мобильный терминал данных (MDT) или удаленное электронное устройство (RED 204) определяет свое географическое положение посредством спутниковой сети 200. Сотовый телефон, мобильный терминал данных (MDT) или удаленное электронное устройство (RED) 204 связывается с сервером 203 посредством беспроводной сети 202.
00051 На фиг. 3 показан альтернативный вариант реализации системы связи и геопозиционирования по фиг. 2. В этой системе беспроводную сеть 202 используют для геопозиционирования и связи с сервером. Сотовый телефон, мобильный терминал данных (MDT) или удаленное электронное устройство (RED) 204 может использовать множество башен сотовой связи или антенн для идентификации его текущего положения. Эти данные могут быть переданы вместе с навигационным запросом с использованием удаленного сервера 203.
00052 На фиг. 4 показан альтернативный вариант реализации системы связи и геопозиционирования по фиг. 2. В этой системе спутники 200 используют для геопозиционирования и связи. Несмотря на то, что спутники системы глобального позиционирования (GPS) в настоящее время не являются многозадачными для обеспечения связи, в будущем возможно, что информация о геопозиционировании и связь могли бы быть обеспечены с использованием того же самого спутника 200. Однако данная система сконструирована в соответствии с современными тенденциями в области спутников: одна совокупность спутников 200 обеспечивает информацию о геопозиционировании, а другой спутник 200 используют для связи с удаленным сервером 203.
00053 На фиг. 5 показан альтернативный вариант реализации системы связи и геопозиционирования по фиг. 1. В этой системе беспроводную сеть 202 используют для геопозиционирования и связи с сервером. Транспортное средство 201 может использовать множество башен сотовой связи или антенн для идентификации своего текущего положения. Данные данные могут быть переданы вместе с навигационным запросом с использованием удаленного сервера 203.
00054 На фиг. 6 показан альтернативный вариант реализации системы связи и геопозиционирования по фиг. 1. В этой системе спутники 200 используют для геопозиционирования и связи. Одна совокупность спутников 200 обеспечивает информацию о геопозиционировании, а другой спутник 200 используют для связи с удаленным сервером 203.
00055 На фиг. 7 навигационный запрос 32 пользователя сообщают посредством одной из систем связи и геопозиционирования, показанных на фиг. 1-6. Независимо от того, используют ли транспортное средство 201 или сотовый телефон, мобильный терминал данных (MDT) или удаленное электронное устройство (RED) 204, пользователь взаимодействует с системой посредством пользовательского программного обеспечения, обычно называемого приложением пользователя. На фиг. 12 приложение пользователя начинается 101 с обеспечения регистрации 102 пользователя. Если пользователь зарегистрирован 102, то возникают входные данные 128 о назначении. Пользователь может добавить множество назначений 127, 128, что обеспечивает уточнение порядка или обеспечивает наличие у системы порядка поездки. После того, как ввод входных данных завершен 127, данные передают 129 с использованием удаленного сервера посредством средств, показанных на фиг. 1-6. На этом этапе мы будет управлять удаленным сервером 203 в виде черного ящика, который создает навигационный маршрут при наличии входных данных 128 о месте назначения. Удаленный сервер 203 передает маршрут, который принимает 129 конечный пользователь. Через предварительно определенные интервалы, приложение 101 конечного пользователя будет передавать пакет информации 130 на удаленный сервер 203 путем передачи 126 его положения. Удаленный сервер 203 будет сравнивать пользовательское продвижение с пользовательским продвижением, которое должно следовать из прогноза удаленного сервера. Если продвижение по направлению к месту назначения расположено за пределами критерия допустимости, то удаленный сервер 203 будет передавать сигнал 125 изменения маршрута на пользовательское приложение 101. Блок конечного пользователя будет уведомлять конечного пользователя об изменении маршрута, а удаленный сервер 203 обеспечит альтернативный маршрут. Новый маршрут будет принят 126 приложением 101 конечного пользователя. В итоге, изменен маршрут или нет, конечный пользователь будет прибывать в место 124 назначения. После прибытия в место назначения, приложение 101 конечного пользователя будет передавать окончательный пакет информации 123 с использованием удаленного сервера 203 для того, чтобы удаленный сервер имел завершенную историю поездки.
00056 При запуске приложения 101 конечного пользователя, если пользователь не зарегистрирован, то блок может обеспечить возможность регистрации путем открытия аккаунта 103. После открытия аккаунта 103, пользователь выбирает частоту 104 передачи пакетов данных, навигационные предпочтения 106 и навигационные исключения 105. Пользователь должен затем включить независимые переменные, касающиеся непосредственно его самого или ее саму, и его или ее транспортное средство. Информация 107 о водителе содержит водительский стаж 108, личную карточку 109 водителя, километры 110, пройденные за год, возраст 111, семейное положение 112, домашний адрес 113, где пользователь учился водить 114, профессию 115 пользователя, пол 116 пользователя и другие заданные компанией или группой данные 117. Информация 118 о транспортном средстве содержит владельца 119 транспортного средства, производителя и модель 120, год 121 модели и километры 122 на транспортном средстве. Данные о независимых переменных должны иметь очень высокое качество, поскольку пользователь будет знать, что их точность при ответе на вопросы может относится непосредственно к тому, насколько хорошо система может осуществлять навигацию по этим данным.
00057 На фиг. 7 показано, что инструкции 60 по наведению возникают после ввода входных данных 32 конечного пользователя. На фиг. 11 инструкции 60 по наведению начинаются с выбора оптимизирующих факторов 1 навигации. Как только были созданы ограниченные географические регионы (BGR), для настоящего изобретения возможно создание навигационных решений. На фиг. 11 показано навигационное решение для одного транспортного средства. Пользователь начинает с выбора оптимизирующего фактора 1 или зависимой переменной: время, расстояние, топливо, затраты или заданная пользователем зависимая переменная. Затем, пользователь, при необходимости, исключает конкретные решения из рассмотрения 2, такие как трассы, платные автодороги, мосты или другие потенциальные маршруты. Пользователь вводит одно или большее количество мест 3 назначения с использованием устройства ввода. При вводе более одного места назначения, пользователь может выбрать 6 автоматическое 10 или ручное 5 определение порядка мест назначения. При выборе ручного 5 определения порядка, модуль 10 автоматического определения порядка мест назначения будет полагаться на ручной ввод данных. После того, как определен порядок, идентифицируют 9 место отправления и следующее место или только место назначения. Если существует только входные данные об одном месте назначения в начале 7, то навигационное ядро переходит непосредственно к идентификации места отправления и места назначения 9.
00058 Для обеспечения расчета между местом отправления и местом назначения, настоящее изобретение будет идентифицировать ограниченные географические регионы (BGR), которые расположены последовательно между местом отправления и местом назначения 8, и обозначать их как активные. Эти ограниченные географические регионы (BGR) называют Gen 1. В ограниченном географическом регионе (BGR), содержащем места отправления, места отправления задают в качестве отдельного входного узла 12. В ограниченном географическом регионе (BGR), содержащем текущее место 9 назначения, текущее место назначения задают в качестве отдельного выходного узла 13. Во всех других ограниченных географических регионах (BGR) узловые пары создают путем выбора только тех узлов, которые имеют ограниченный географический регион (BGR) на обеих сторонах 11. Навигационное ядро затем создает перечень узловых пар во всех активных ограниченных географических регионах (BGR) 16. В системе с множеством обрабатывающих устройств навигационное ядро будет одновременно создавать временный массив данных ограниченного географического региона (BGR) для всех узловых пар на рассмотрении 20 и будет изучать таблицы 14 поиска узловых пар (NPLUT) с тем, чтобы выяснить, существуют ли решения для любых узловых пар на рассмотрении 17. Если решение по узловым парам существует в таблице поиска узловых пар (NPLUT), то его размещают во временном массиве 20 данных ограниченного географического региона (BGR). Если нет, то с использованием весовых функций для каждой классификации улиц настоящее изобретение выполняет расчеты зависимых переменных для каждой узловой пары каждого ограниченного географического региона (BGR) 12, что обеспечивает захват информации о маршруте для каждого потенциального решения. Настоящее изобретение будет удалять какие-либо исключения из совокупности 21 потенциальных решений. Поскольку только ограниченную совокупность ограниченных географических регионов (BGR) используют для изначального расчета, не все узлы каждого ограниченного географического региона (BGR) являются возможным входом и/или выходом. Данные, сгенерированные из интересующих узлов, могут быть сохранены в массиве данных в формате временной базы данных или любом другом формате обработки данных, который обеспечивает возможность быстрого доступа 20. Эти временные данные могут быть сохранены в кэш-памяти, на жестком диске или любом другом типе подходящего элемента памяти. В процессорной среде с множеством ядер такие расчеты выполняются быстро, поскольку каждый из ограниченных географических регионов (BGR) может быть рассчитан независимым образом.
00059 Настоящее изобретение затем создает исходный предварительный маршрут путем нахождения исходного минимального решения от места отправления в место назначения, что обеспечивает перемещение только через ограниченные географические регионы (BGR), которые расположены последовательно между местом отправления и местом назначения 22. В качестве граничного условия для расчета первоначального маршрута, выходной узел одного ограниченного географического региона (BGR) представляет собой входной узел смежного ограниченного географического региона (BGR). Путем создания матрицы возможных решений, настоящее изобретение вырабатывает решение в явном виде.
00060 После идентификации изначального предварительного маршрута, вычислительное устройство для вычисления решений добавляет все ограниченные географические регионы (BGR), которые были расположены вплотную к ограниченным географическим регионам (BGR) 23, 18 типа Gen 1, и в целом повторяет вышеописанный процесс. Новые ограниченные географические регионы (BGR) называют Gen 2. Ограниченные географические регионы (BGR) типа Gen 1 теперь используют все узлы в расчете. Ограниченные географические регионы (BGR) типа Gen 2 используют уменьшенную совокупность узлов, поскольку не все узлы имеют смежный ограниченный географический регион (BGR), связанный с этими узлами.
00061 Для расчета предварительного маршрута типа Gen 2 исключают потенциальные решения, рассчитанные при расчете Gen 1, поскольку они расположены во временном массиве 20 данных. Настоящее изобретение снова применяет граничное условие, согласно которому выходной узел одного ограниченного географического региона (BGR) представляет собой входной узел смежного ограниченного географического региона (BGR). Путем создания матрицы возможных уникальных решений (за исключением решения Gen 1), настоящее изобретение вырабатывает решение в явном виде, предварительный маршрут 22 типа Gen 2.
00062 Процесс повторяют для Gen 3 по существу тем же самым способом, что и для Gen 223, 18. Все ограниченные географические регионы (BGR), примыкающие к ограниченным географическим регионам (BGR) типа Gen 2, добавляют к расчету. В предварительный решения исключены из совокупности потенциальных решений. Рассчитывают решение в явном виде для предварительного маршрута типа Gen 3.
00063 Оптимальное решение называют Gen А. Выходной критерий выбирают таким образом, что обеспечено завершения С расчетов, причем С=А+В, где С представляет собой общее количество расчетов, А представляет собой оптимальный расчет, а В представляет собой количество необходимый дивергентных решений, рассчитанных после оптимального решения. Например, если предварительный маршрут типа Gen 1 является предпочтительным по отношению к предварительному маршруту типа Gen 2 или типа Gen 3, то расчеты завершаются, что обеспечивает представление предварительного маршрута типа Gen 1 пользователю в качестве предпочтительного маршрута, при этом С=3, А=1 и В=2.
00064 На практике, В относится к расстоянию между местом отправления и местом назначения 23. Кроме того, выбор В может быть оптимизирован посредством простой функции ошибок по обратной связи, причем указанная ошибка относится к расстоянию. Верхний предел В задают по ограничению максимальной скорости. Другими словами, процесс завершается, когда транспортное средство должно бы превысить максимально допустимое ограничение скорости около границ для выдачи более предпочтительного решения по отношению к зависимой переменной по сравнению с доступным в настоящее время решением.
00065 В отношении осуществления навигации для множества транспортных средств и множества мест назначения (MVMD), вышеописанный процесс повторяют для всех транспортных средств. Исходные места назначения определяют путем минимизации количества пересекаемых ограниченных географических регионов (BGR) для всех транспортных средств для получения предварительного места назначения. Вышеописанный алгоритм создает маршрут для каждой пары из транспортного средства и места назначения. В первом месте назначения каждому транспортному средству снова присваивают место назначения, причем система пытается минимизировать количество пересекаемых ограниченных географических регионов (BGR) для достижения всеми транспортными средствами своих мест назначения. Таким образом, возможно управление задачами множества транспортных средств/множества мест назначения с использованием ограничивающих условий или без них.
Реферат
Изобретение относится к области расчета навигационного маршрута. Технический результат – оптимизация маршрута. Изобретение раскрывает систему и способ диспетчеризации множества транспортных средств и направления их в множество мест назначения с использованием ограничивающих условий или без них, содержащие программное ядро, которое использует ограниченные географические регионы (BGR) и узловые пары для оптимизации в явном виде необходимых пользователю зависимых переменных путем анализа отклонения в зависимости от стандарта и заданных пользователем независимых переменных. Настоящее изобретение сохраняет данные узловой пары и может использовать функцию ошибок, обратную связь и ANOVA или MANOVA для создания сильно конвергентной диспетчеризации и навигационного решения. 14 з.п. ф-лы, 13 ил.
