| EP0821296A2 | 1998-01-28 |
| ФОРМУЛА ИЗОБРЕТЕНИЯ 1. Способ планирования маршрута из начального А населенного пункта в конечный Б населенный пункт, содержащий этапы, на которых: определяют начальную А и конечную Б точки для планирования маршрута из начального А населенного пункта в конечный Б населенный пункт; рассчитывают к кратчайших путей из начальной А точки в конечную Б точку; выбирают множество потенциальных промежуточных точек маршрута, советующих населенным пунктам, находящимся между начальной А точкой и конечной Б точкой; определяют для каждой потенциальной промежуточной точки маршрута общую оценку популярности промежуточной точки; рассчитывают суммарное значение оценки популярности маршрута для каждого пути из к кратчайших путей на основе значений общих оценок популярности выбранных промежуточных точек, которые лежат на упомянутых к кратчайших путях; выбирают путь с максимальным суммарным значением оценки популярности маршрута, который определяется как маршрут из начального А населенного пункта в конечный Б населенный пункт. 2. Способ по п. 1, отличающийся тем, что этап выбора множества потенциальных промежуточных точек маршрута, советующих населенным пунктам, находящимся между начальной А точкой и конечной Б точкой, включает этапы, на которых: определяют территориальные границы, в которых может лежать множество рассматриваемых промежуточных точек, причем границы определяются пересечением окружностей, проведенных из начального А населенного пункта и конечного Б населенного пункта маршрута, с радиусом, равным расстоянию из точки А в точку Б; выбирают множество потенциальных промежуточных точек маршрута, советующих населенным пунктам, которые находятся внутри упомянутого пересечения окружностей. 3. Способ по п. 2, отличающийся тем, что этап выбора множества потенциальных промежуточных точек маршрута, советующих населенным пунктам, находящимся между начальной А точкой и конечной Б точкой, включает этапы фильтрации, причем фильтрация осуществляется на основе критерия на отношение размера потенциального населенного пункта и среднего значения между размерами начального А населенного пункта и конечного Б населенного пункта, а оставшиеся после фильтрации населенные пункты определяются как потенциальные промежуточные точки. 4. Способ по п. 1, отличающийся тем, что общая оценка популярности промежуточной точки маршрута определяется на основе оценок остаточного спроса по всем парным направлениям, которые можно получить из множества потенциальных промежуточных точек, и рассматриваемой промежуточной точки маршрута. 5. Способ по п. 4, отличающийся тем, что оценка остаточного спроса по всем парным направлениям включает этапы, на которых: получают информацию о количестве рейсов автобусов по каждому направлению из начальной точки А до каждой потенциальной промежуточной точки, количестве проданных посадочных мест в автобусах и о количестве свободных посадочных мест; для части направлений, по которым доступна информация о количестве продаж и свободных посадочных мест, рассчитывают значения оценки совокупного спроса для каждого направления, причем упомянутое значение оценки совокупного спроса по направлению к потенциальной промежуточной точке определяется как отношение количества проданных посадочных мест в автобусах по данному направлению из начальной точки А к доле рейсов, доступных для продаж, при этом доля рейсов, доступных для продаж, определяется как отношение количества рейсов из начальной точки А к общему количеству рейсов по направлению из начальной точки А до потенциальной промежуточной точки; рассчитывают значения оценки остаточного спроса для каждого направления как отношение значения оценки совокупного спроса на направление к количеству рейсов на маршруте + коэффициент поправки. 6. Способ по п. 5, отличающийся тем, что при расчете значения оценки совокупного спроса по каждому направлению учитываются значения оценки доли продаж заданной компании в общих продажах следующим образом: Продажи по направлению - Доля рейсов, доступных для продажи Оценка доли продаж компании в общих продажах 7. Способ по п. 4, отличающийся тем, что оценка остаточного спроса по всем парным направлениям включает этапы, на которых: получают для каждого направляю данные о населенном пункте, причем данные о населенном пункте включают информацию о численности населения, удаленности от столицы, количестве поисковых запросов по направлению, а также о том, является ли населенный пункт районным центром; осуществляют построение модели для прогноза совокупного спроса на основе полученных на предыдущем этапе данных; для направлений, по которым на предыдущем этапе была недоступна информация для расчета совокупного спроса, определяют значения оценки совокупного спроса на основе коэффициентов упомянутой модели; рассчитывают значения оценки остаточного спроса для каждого направления как отношение значения оценки совокупного спроса на направление к количеству рейсов на маршруте + коэффициент поправки. 8. Система обработки информации, содержащее: базу географические данные (геоданных), устройство планирования маршрута и устройство пользователя, причем устройство планирования маршрута выполнено с возможностью осуществлять способ планирования маршрута по любому из пп. 1-7. |
УСТРОЙСТВО ДЛЯ ЕГО ОСУЩЕСТВЛЕНИЯ
ОБЛАСТЬ ТЕХНИКИ
Изобретение относится к области пассажирских перевозок, в частности, к способу и устройство прогнозирования пассажиропотока для рекомендации оптимальных маршрутов, направлений и цен для автобусных перевозчиков.
УРОВЕНЬ ТЕХНИКИ
Из уровня техники известны способ и устройство для планирования маршрута пассажирских автобусов, описанные в заявке CN 107506864 (А), опубл. 22.17.2017. В известном решении осуществляют планирование маршрута из места отправления в место назначения с учетом количества мест в автобусах, при этом используются данные по реальному пассажиропотоку в независимости от спроса, который может быть не удовлетворен.
Недостатком данного решения является отсутствие возможности оценки спроса в случае, когда реальный спрос на маршрут не известен. Также в известном решении не учитывается информация о спросе точек, находящихся на маршруте, при планировании маршрута.
РАСКРЫТИЕ ИЗОБРЕТЕНИЯ
Технической задачей, на решение которой направленно заявленное решение, является создание способа и устройства прогнозирования пассажиропотока для планирования маршрута пассажирских автобусов, обеспечивающих выбор оптимального маршрута между двумя заданными населёнными пунктами за короткое время.
Техническим результатом является повышение эффективности выбора маршрута за счет обеспечения возможности оценки популярности кратчайших путей на основе значений популярности населенных пунктов, находящихся между начальной А точкой и конечной Б точкой маршрута.
Для обеспечения достижения указанного технического результата разработан способ планирования маршрута из начального А населенного пункта в конечный Б населенный пункт, содержащий этапы, на которых: определяют начальную А и конечную Б точки для планирования маршрута из начального А населенного пункта в конечный Б населенный пункт; рассчитывают к кратчайших путей из начальной А точки в конечную Б точку; выбирают множество потенциальных промежуточных точек маршрута, советующих населенным пунктам, находящимся между начальной А точкой и конечной Б точкой; определяют для каждой потенциальной промежуточной точки маршрута общую оценку популярности промежуточной точки; рассчитывают суммарное значение оценки популярности маршрута для каждого пути из к кратчайших путей на основе значений общих оценок популярности выбранных промежуточных точек, которые лежат на упомянутых к кратчайших путях; выбирают путь с максимальным суммарным значением оценки популярности маршрута, который определяется как маршрут из начального А населенного пункта в конечный Б населенный пункт.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
Для лучшего понимания сущности изобретения, и чтобы более ясно показать, каким образом оно может быть осуществлено, далее будет сделана ссылка, лишь в качестве примера, на прилагаемый чертеж, на котором изображено:
фиг. 1 - система обработки информации.
ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ
В соответствии со схемой, приведенной на фиг. 1, система обработки информации содержит: базу географические данные (геоданных) 1, устройство планирования маршрута 2 и устройство пользователя 3.
Устройством пользователя 3 может быть любое вычислительное средство, обладающее возможностью проводной или беспроводной связи, например, мобильный телефон, смартфон, планшет, портативный или стационарный компьютер и т.д. Устройство планирования маршрута 2 может быть реализовано на базе программно-аппаратных средств, например, процессора или микроконтроллера, и для осуществления приписанных устройству ниже функций.
База геоданных 1 представляет собой базу данных, предназначенную для сбора и хранения данных из различных источников геоданных, например, источника геоданных Open Street Мар (далее OSM). Сохраненные в базе данных геоданные используются устройство планирования маршрута 2 для построения графа дорог (дорожного графа), представляющего собой сетку дорог, состоящую из множества фрагментов, которые состыкованы между собой, причем каждый из фрагментов несет информацию о своем участке дороги: географические координаты, направление движения, средняя скорость, с которой машины обычно едут на этом участке, и другие параметры, а также содержит данные о том, как участки дорог стыкуется с соседними участками— есть ли в этом месте поворот направо или налево, можно ли там развернуться в обратную сторону или разрешается ехать только прямо.
Устройство пользователя 3 оснащено специализированным программным обеспечением, предоставляющем пользователю возможность выбрать начальный А и конечный Б населенные пункты, между которыми необходимо проложить маршрут. Информация о выбранных начальном А и конечном Б населенных пунктах поступает в устройство планирования маршрута 2, которое определяет на основе полученной информации начальную А точку маршрута и конечную Б точку маршрута, после чего по графу дорог рассчитывает к кратчайших путей из А в Б посредством, например, имплементации алгоритма Yen's algorithm или k-SPwLO. Далее устройством планирования маршрута 2 переходит к этапу выбора множества потенциальных промежуточных точек для выбора кратчайшего пути из к кратчайших путей из начальной А точки в конечную Б точку.
Для выбора множества потенциальных промежуточных точек маршрута, советующих населенным пунктам, находящимся между начальной А точкой и конечной Б точкой, устройство планирования маршрута 2 определяет территориальные границы, в которых может лежать множество рассматриваемых промежуточных точек. Например, территориальные границы могут быть определены пересечением окружностей, проведенных из населенного пункта начала (начальная точка А) и окончания маршрута (конечная точка Б), с радиусом, равным расстоянию из точки А в точку Б. После этого устройство планирования маршрута 2 для дальнейшего анализа выбирает все населенные пункты, которые находятся внутри упомянутого пересечения окружностей.
Далее устройство планирования маршрута 2 определяет размеры начального А населенного пункта, конечного Б населенного пункта и выбранных потенциальных населенных пунктов, и осуществляет фильтрацию выбранных населенных пунктов в зависимости от размеров начального А населенного пункта и конечного Б населенного пункта. Фильтрация осуществляется на основе критерия на отношение размера выбранного потенциального населенного пункта и среднего значения между размерами начального А населенного пункта и конечного Б населенного пункта, например, значение отношения размера рассматриваемых выбранных промежуточных населенных пунктов к среднему размеру изначальных населенных пунктов должно лежать в диапазоне от 0,5 до 1,5. Упомянутые критерии, в частности, указанный диапазон, могут быть заранее заложены в программный алгоритм работы устройства планирования маршрута 2. Оставшиеся после фильтрации населенные пункты устройство планирования маршрута 2 определяет как потенциальные промежуточные точки и рассчитывает их популярность. Общая оценка популярности населенного пункта является составной из оценок остаточного спроса по всем парным направлениям, которые можно получить из множества потенциальных промежуточных точек, и рассматриваемого населенного пункта. Таким образом, оценивается остаточный спрос по направлениям. Для этого сначала оценивается совокупный спрос, который уже распределяется между рейсами. Соответственно, для оценки совокупного спроса по направлениям устройство планирования маршрута 2 обращается к соответствующим информационным ресурсам на предоставление информации о количестве рейсов автобусов по каждому направлению из начальной точки А до каждой 5 потенциальной промежуточной точки, количестве проданных посадочных мест в автобусах и о количестве свободных посадочных мест. Упомянутыми информационными ресурсами могут быть любые информационные ресурсы, например, сайты и базы данных, собирающие и хранящие информацию о расписании автобусных рейсов и продажах посадочных мест, выполнение с 0 возможностью предоставлять данную информацию по соответствующему запросу.
Для тех направлений, для которых устройство планирования маршрута 2 получило информацию по продажам и свободным посадочным местам в автобусах, упомянутое устройство 2 производит расчет значения оценки5 совокупного спроса по каждому направлению, причем упомянутое значение оценки совокупного спроса по направлению к потенциальной промежуточной точке определяется как отношение количества проданных посадочных мест в автобусах по данному направлению из начальной точки А к доле рейсов, доступных для продаж, причем доля рейсов, доступных для продаж, >0 определяется как отношение количества рейсов из начальной точки А к общему количеству рейсов по направлению из начальной точки А до потенциальной промежуточной точки. Дополнительно устройство планирования маршрута 2 при расчете значения оценки совокупного спроса по каждому направлению может учитывать значения оценки доли продаж >5 заданной компании в общих продажах, например, следующим образом:
Продажи по направлению
-
Доля рейсовдоступных для продажи Оценка доли продаж компании в общих продажах
Компания, значения оценки доли продаж которой будут учитываться, может быть задана непосредственно в программном алгоритме устройства планирования маршрута 2, либо информация о данной компании может поступать в процессе работы устройства 2 посредством направления соответствующего запроса пользователю.
Для тех направлений, для которых устройство планирования маршрута 2 не получило информацию по продажам и свободным посадочным местам в автобусах, а также не получило информации от информационных ресурсов о том, что данные маршруты обладают избыточным спросом, упомянутое устройство 2 производит построение модели для прогноза пассажиропотока. По данным по направлениям, для которых возможно построить оценку совокупного спроса, строится линейная регрессия (htps://ru. wikipedia. ог /ш1кл/Линейная_регрессия).
где в качестве зависимой переменной (УД выступают оценки совокупного спроса по используемым направлениям, а в качестве объясняющих характеристик используются неизменные характеристики населенных пунктов, между которыми оценивается спрос: численность населения, удаленность от столицы (например, Москвы), является ли каждый из населенных пунктов районным центром и др.; а также количество поисковых запросов по направлению ( Ci— вектор характеристик размерности 1 х ш, где m - это количество используемых характеристик, переменных в модели, для отдельного направления г, где г может принимать значения от 1 до N - количество направлений, на основе которых строится модель);
? fe - коэффициенты модели (к = 0 соответствует константе, а остальные коэффициенты переменным модели), описывающие зависимость совокупного спроса от используемых характеристик.
Коэффициенты в модели оцениваются, например, методом наименьших квадратов (htps ://ru.wikipedia.org/wiki/MeT fl наименьших квадратов).
Полученные при построении модели коэффициенты используются для прогноза совокупного спроса по оставшимся направлениям: · Для каждого направления (обозначаемого индексом г) в отдельности собирается информация по всем характеристикам, которые использовались при построении модели (составляется вектор X).
5 · В уравнение (1) подставляются собранные значения переменных и оцененные ранее значения коэффициентов регрессии.
· Полученное значение зависимой переменной (УД используется в качестве оценки совокупного спроса по направлению.
Далее для всех направлений на основе значения оценки совокупного О спроса рассчитывается остаточный спрос на конкретный рейс.
Предполагается, что перевозчики, предоставляя однородный товар, конкурирует за пассажиров по Курно
(https://ru.wikipedia.org/wiki/Qimrononroi_KypHo). Согласно модели Курно перевозчики, обладая схожими характеристиками по издержкам, будут 5 принимать одинаковые ценовые решения. Между рейсами с одинаковой ценой и схожими остальными характеристиками пассажиры должны распределяться равномерно. Таким образом, значения оценки остаточного спроса на конкретный рейс рассчитывается устройством планирования маршрута 2 как отношение значения оценки совокупного спроса на направление к количеству О рейсов на маршруте + коэффициент поправки, равный 1 , который добавится, если рассматриваемый потенциальный маршрут будет выбран в результате работы алгоритма и запущен перевозчиком.
Далее устройство планирования маршрута 2 определяет для каждой потенциальной промежуточной точки маршрута, соответствующей
5 оставшемуся после фильтрации населенному пункту, общую оценку популярности, как сумму из полученных ранее оценок остаточного спроса по всем парным направлениям, которые можно получить из множества потенциальных промежуточных точек, и рассматриваемой промежуточной точки маршрута. На следующем этапе устройство планирования маршрута 2
О накладывает потенциальные промежуточные точки на граф дорог и выбираются только те потенциальные точки маршрута, которые лежат на определенных ранее к кратчайших путях из начальной А точки в конечную Б точку, после чего устройство планирования маршрута 2 рассчитывает суммарное значение оценки популярности маршрута для каждого пути из к 5 кратчайших путей на основе значений общих оценок популярности выбранных промежуточных точек - населенных пунктов, которые лежат на упомянутых к кратчайших путях. Далее устройство планирования маршрута 2 выбирает путь с максимальным суммарным значением оценки популярности маршрута, который определяется как маршрут из начальной А точки в 0 конечную Б точку, причем если таких маршрутов несколько, то выбирается кратчайший из них. Информация о выбранном маршруте может быть направлена на устройство пользователя 1 для отображения маршрута из начального А населенного пункта в конечный Б населенный пункт, сформированный на основе начальной А точки и конечной Б точки.
5 Таким образом, поскольку при планировании маршрута осуществляется оценка популярности кратчайших путей на основе значений популярности населенных пунктов, находящихся между начальной А точкой и конечной Б точкой маршрута, повышается эффективности выбора маршрута.
0 5