مهندسی مسیریابی در اپ‌های نقشه / تاکسی / پیک

مرحله ۱: تبدیل شهر به گراف

اپ‌ها شهر را به شکل یک گراف (Graph) مدل می‌کنند:

• تقاطع‌ها → Node
• خیابان‌ها → Edge
• طول خیابان → وزن پایه
• ترافیک → وزن پویا

در واقع مسئله این است:

[ \text{Find shortest path in weighted graph} ]

اما وزن فقط فاصله نیست. وزن واقعی این است:

[\text{Cost} = f(distance, traffic, road type, signals, accidents, restrictions)]

مرحله ۲: الگوریتم پیدا کردن مسیر

الگوریتم‌های کلاسیک:

✅ Dijkstra

قدیمی اما دقیق
برای زمانی که داده پویا کم است.

✅ A*

نسخه هوشمندتر
از یک تابع تخمین استفاده می‌کند:

[ f(n) = g(n) + h(n) ]

• ( g(n) ) = هزینه طی‌شده
• ( h(n) ) = تخمین فاصله تا مقصد

این باعث می‌شود جستجو کورکورانه نباشد.

تقریباً همه اپ‌های مدرن نسخه‌ای از A* را استفاده می‌کنند.

مرحله ۳: داده ترافیک زنده

اینجا جادو شروع می‌شود ✨

داده‌ها از کجا می‌آیند؟

• GPS کاربران
• سرعت متوسط خودروها
• گزارش تصادف
• سنسورهای شهری
• تاریخچه الگوهای ترافیکی

هر خیابان دائماً وزنش تغییر می‌کند.

پس الگوریتم باید:

• Real-time باشد
• هر چند ثانیه Recalculate کند

مرحله ۴: پیش‌بینی آینده

اپ‌ها فقط الان را نمی‌بینند؛ آینده را هم حدس می‌زنند.

مثلاً:

• ساعت ۷ عصر → اتوبان معمولاً قفل است
• پنجشنبه‌ها → الگوی متفاوت
• باران → سرعت میانگین کاهش

مدل‌های Machine Learning پیش‌بینی می‌کنند:

[ Predicted\ Time = Historical\ Pattern + Real\ Time\ Signal]

مرحله ۵: تفاوت بین نقشه، تاکسی و پیک

🚕 تاکسی آنلاین

بهینه‌سازی دوطرفه است:

• مسیر مسافر
• محل راننده‌ها
• احتمال پذیرش
• Surge pricing

اینجا مسیریابی بخشی از یک سیستم بزرگ‌تر تخصیص (Dispatch System) است.

📦 پیک (چند مقصد)

اینجا مسئله تبدیل می‌شود به:

[Traveling\ Salesman\ Problem]

یعنی:
بهترین ترتیب برای چند مقصد چیست؟

این مسئله NP-hard است و با الگوریتم‌های تقریبی حل می‌شود.