Като технологичен консултант, работещ по Quiki, съм развълнуван да споделя прозрения за един от най-важните компоненти на нашата платформа: усъвършенстваният алгоритъм за съчетаване на пътувания. Тази сложна система е проектирана да решава комплексни проблеми с маршрутизиране на множество превозни средства и множество заявки в реално време, осигурявайки ефективни и оптимални преживявания при споделено пътуване.
Предизвикателството: Маршрутизиране на множество превозни средства и множество заявки#
Нашият алгоритъм адресира три основни предизвикателства при споделеното пътуване:
- Изчисляване на оптимално разпределение на множество заявки за пътуване към множество превозни средства с дадени капацитети.
- Позволяване на непрекъсната работа и разпределение на входящи заявки към флот от превозни средства.
- Осигуряване на преразпределение на флота от превозни средства, за да се посрещне ефективно търсенето.
Ключови компоненти на алгоритъма#
1. Двойков граф на заявка-превозно средство (RV)#
Първата стъпка включва изчисляване на:
- Кои заявки могат да бъдат комбинирани, като се вземат предвид както произходът, така и дестинацията.
- Кои превозни средства могат да обслужват кои заявки индивидуално, предвид текущите им пътници.
2. Граф на заявка-пътуване-превозно средство (RTV)#
Тази стъпка изследва RV графа, за да намери “пътувания” - групи от заявки, които могат да бъдат комбинирани и взети от превозно средство, като се спазват всички ограничения. Една заявка може да бъде част от няколко потенциални пътувания, а едно пътуване може да има множество кандидат-превозни средства.
3. Оптимално разпределение#
Последната стъпка изчислява оптималното разпределение на пътувания към превозни средства, преобразувано в Целочислено линейно програмиране (ILP) и решено инкрементално.
Математическият модел#
Нашият алгоритъм използва сложен математически модел за представяне на проблема със споделеното пътуване:
- Заявки (R): Всяка заявка r се определя от произход (o_r), дестинация (d_r), време на заявката (t_r^r) и най-късно приемливо време за вземане (t_r^pl).
- Превозни средства (V): Всяко превозно средство v се характеризира с текущата си позиция (q_v), текущо време (t_v) и текущи пътници (P_v).
- Ограничения (Z): Включват максимално време за чакане, максимално закъснение при пътуване и капацитет на превозното средство.
Процес на оптимизация#
Функция на разходите: Минимизираме функция на разходите C(Σ), която отчита закъсненията при пътуване за всички пътници и разпределени заявки, плюс наказание за неразпределени заявки.
Удовлетворяване на ограниченията: Алгоритъмът гарантира, че всички ограничения са спазени, включително максимални времена за чакане, закъснения при пътуване и капацитети на превозните средства.
Инкрементална оптимизация: Предвид NP-трудния характер на проблема, използваме инкрементален подход за бързо намиране на субоптимални решения, които могат да бъдат подобрени с течение на времето.
Усъвършенствани функции#
Непрекъсната работа: Алгоритъмът може да обработва нови входящи заявки в реално време, непрекъснато актуализирайки разпределенията.
Преразпределение на флота: Внедрили сме система за преразпределение на свободните превозни средства към райони с игнорирани заявки, минимизирайки общото време за чакане.
Мащабируемост: Нашият подход е проектиран да се мащабира ефективно с увеличаване на броя на превозните средства и заявките.
Въздействие в реалния свят#
Този усъвършенстван алгоритъм позволява на Quiki да:
- Максимизира използването на превозните средства и намалява празните пътувания.
- Минимизира времето за чакане на пътниците и закъсненията при пътуване.
- Адаптира се бързо към променящите се модели на търсене в реално време.
- Предоставя по-ефективна и икономична услуга за споделено пътуване.
Бъдещи разработки#
Докато продължаваме да усъвършенстваме нашия алгоритъм, изследваме няколко вълнуващи насоки:
- Интеграция на машинно обучение: Включване на предиктивни модели за предвиждане на моделите на търсене.
- Динамично ценообразуване: Внедряване на модели за ценообразуване при пикови натоварвания, базирани на предлагането и търсенето в реално време.
- Мултимодална интеграция: Разширяване на алгоритъма за включване на други видове транспорт за истински интегрирани решения за градска мобилност.
Сложният алгоритъм за съчетаване на пътувания в сърцето на Quiki е повече от просто техническо чудо; той е ключът към отключването на по-ефективен, устойчив и удобен за потребителите градски транспорт. Докато се подготвяме за стартирането на Quiki, сме развълнувани да видим как тази технология ще трансформира начина, по който хората се движат в градовете.
Следете за още актуализации, докато продължаваме да иновираме и разширяваме границите на възможното в технологията за споделено пътуване!