ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ИНФОРМАЦИОННОЙ СИСТЕМЫ ЗАКАЗА ТАКСИ

АННОТАЦИЯ

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

Ключевые слова: услуги такси, информационная система, диаграммы UML, критерии, разбиение на зоны, задача о назначении.

Введение

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

Информационные системы служат для принятия заказов и их обработки с последующим оформлением отчетов. Отметим программный комплекс «Диспетчер такси» разработчика F-GroupSoftware [1]. Система служит для автоматизации процессов приема, оформления заказов такси, управления водителями и формирования отчетности в таксопарках и диспетчерских службах такси Достоинством является  многопользовательский режим, возможность работы по сети под разными профилями (администратор, диспетчер, руководитель, оператора), поддержка паролей, повышение эффективности работы за счет использования четких алгоритмов действий, четкое распределение функции между профилями, есть связь с готовыми картами. Некоторым недостатком является сложность работы, функциональная избыточность, сложный интерфейс. В системе [2] диспетчер напрямую работает с клиентами, в его обязанности входит регистрация заказов с последующей передачей их водителям. После каждой смены диспетчер создает сведения и помещает информацию в общую базу отчетов. К задачам администратора относится работа с соискателями на вакансии и создание сводных отчетов.

Рассмотрим схему взаимодействия пользователя с популярной службой «Яндекс Такси» [3], являющейся самым крупным в России агрегатором, обеспечивающим таксистов большим количеством заказов. Клиент вводит начальную и конечную точки пути, выбирает тариф и вариант оплаты услуги. Заказ передаётся диспетчеру и далее — водителю, маршрут для которого строит навигатор. Пользователи мобильного приложения при заказе автомобиля могут выбрать промежуточные целевые точки, которые будут автоматически учтены при расчете маршрута. Система автоматически выбирает автомобиль, расположенный к месту нахождения пассажира с расчётным временем не более четверти часа. Предпочтение отдается водителям с более высоким рейтингом и чье транспортное средство наиболее полно отвечает требованиям клиента, указанным в деталях заказа.

Для автоматизации работы службы такси необходимы соответствующие удобные и эффективные инструментальные средства. В том числе методы рационального размещения и оптимизации назначения водителей. Удобным средством для описания процессов внутри информационной системы является язык UML [4]. Существует несколько видов UML-диаграмм: использования; классов; объектов; автоматов; последовательности; коммуникации; компонентов; деятельности; размещения. Диаграммы помогают более четко представить взаимодействия в сложной системе управления службы такси.

2. Моделирования работы службы такси на основе UML-технологи

Рассмотрим основные примеры UML-диаграмм, используемые для управления. деятельностью и ресурсами организации системы взаимосвязанных процессов на примере службы заказа такси «Сluber» [5].

На рис. 1 и рис. 2 показаны некоторые диаграммы, поясняющие процессы, протекающие в системе заказа такси.

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

2. Разбиение территории на зоны

Наиболее распространенным является подход, когда город делится на части (районы) и в каждой части (районе) организуется стоянка автомобилей такси. Разбиение территории на зоны позволяет снизить размерность решаемой задачи о назначении, распараллелить работу диспетчерской службы и упростить дальнейшую работу. Существует много способов разбить территорию на зоны, например, используя: треугольник, квадрат и гексагон (правильный шестиугольник). Особенность правильного шестиугольника— равенство его стороны и радиуса описанной окружности, в них расстояние от центра до соседних областей одинаково. [6]. На рис. 3 приведен пример покрытия территории шестиугольниками. Статическая сетка, нанесенная на территорию, позволяет связывать водителей и пассажиров, например, по принципу колец метро показан на рис. 4. [7]

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

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

3. Постановка и решение задачи о назначении такси

Задачу оптимального распределения заказов целесообразно свести к задаче о назначениях с аддитивным критерием эффективности [8,9]. Необходимо распределить полученные заявки между автомобилями такси таким образом, чтобы достичь максимальной эффективности при заданных ограничениях. Рассмотрим поиск оптимального распределения заказов венгерским методом [10]. Пусть имеется n заявок и n- машин - кандидатов на их выполнение. Пусть  – затраты (стоимость, время, значения аддитивного критерия), связанные с назначением заявки i на машину j. Введем переменные  такие, что , если заявка i назначена на машину j, и  в противном случае. Задача заключается в таком назначении, при котором суммарные затраты на выполнение всех заявок минимальны:

Рассмотрим решение задачи линейного программирования (1)-(2) венгерским методом. В соответствии с установленными ограничениями (2) каждая заявка назначается только на одну машину, и каждая машина выполняет только одну заявку.

Алгоритм описан детально в работе [9] и состоит из двух этапов.

1. Получение нулей во всех строках и столбцах матрицы.
2. Поиск оптимального решения

2.1. Этап разметки строк и столбцов. Процедура разметки строк и столбцов выполняется до тех пор, пока есть что отмечать.

2.2. Перестановка отмеченных нулей. Возврат к этапу (2):

Пусть, например, имеются 4 заявки и 4 машины. Исходные данные задачи (1)-(2) - величины затрат  содержатся в таблице 1.

Таблица 1.

Исходные данные задачи

Таблица 2.

Результаты первого этапа

Таблица 3.

Результаты заключительного этапа

В данном случае получаем решение, которое в Табл.3 отмечено нулями с подчеркиванием, для которого F=13.

Заключение

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

Список литературы:

1. F-Group Software представляет программный комплекс Такси Диспетчер. - https://present5.com/f-group-software-predstavlyaet-programmnyj-kompleks-taksi-dispetcher/.
2. Автоматизированная система управления таксомоторного парка. - https://www.bibliofond.ru/view.aspx?id=650620
3. Маркелов Н. Тонкости построения маршрута в Яндекс.Такси. - https://otaxiyandex.ru/passazhiru/yandeks-taksi-marshrut
4. Иванов Д. Ю., Новиков Ф. А. Основы моделирования на UML: Учеб. пособие. – СПб.: Изд-во Политехн. ун-та, 2010. – 249с
5. Колесова А.А. Проектирование информационной системы службы заказа такси.- Саратов, 2017. – https://vsesdal.com/order/1638681/proektirovanie-informatsionnoy-sistemy-sluzhba-taksi
6. Нурлигареев Х. Задачи замощения, 2011. – https://elementy.ru/problems/42/zamoshcheniya
7. Шестиугольный город. - https://habr.com/en/post/403639/].
8. Сонькин Д.М. Адаптивный алгоритм распределения заказов на обслуживание автомобилями такси. – Известия Томского политехнического университета, 2009. Т. 315, № 5, с. 65–69
9. Бебишев М.А., Корчевская О.В., Борисов А.С., Акинфеев Р.С., Воронов Модифицированный венгерский метод. – file:///C:/Users/User/Downloads/modifitsirovannyy-vengerskiy-metod%20(1).pdf
10. Хачумов В.М. Основные принципы моделирования сложных систем и процессов. Учебное пособие. – М.: РУДН, 2013. – 141 с. ISBN 978-5-209-04797-1