ماتریس فاصله یک شبکه از زمانها و فواصل سفر بین چندین مبدأ و چندین مقصد است. این ساختار دادهای است که پشت هر رتبهبندی "نزدیکترین فروشگاه"، هر تصمیم dispatch تحویل و هر solver بهینهسازی مسیر قرار دارد. هر زمان که یک اپلیکیشن باید بهترین کاندیدا را از بین چندین کاندیدا بر اساس زمان رانندگی انتخاب کند، یک ماتریس فاصله دارد کار میکند.
در این راهنما توضیح میدهم ماتریس فاصله واقعاً چیست، زمان سفر چه تفاوتی با فاصله مستقیم دارد، در سیستمهای واقعی کجا ظاهر میشود و کدام دامها وقتی مجموعه ورودی از چند نقطه فراتر میرود تیمها را اذیت میکنند.
ماتریس فاصله واقعاً چیست
در سادهترین شکل، ماتریس فاصله یک جدول دو بعدی است. سطرها مبدأها هستند، ستونها مقصدها، و هر سلول دو عدد دارد: یک distance و یک duration. با N مبدأ و M مقصد، ماتریس N ضربدر M سلول دارد. درخواستی با ۲۵ راننده و ۲۵ شغل، ۶۲۵ سلول در یک فراخوانی تولید میکند.
مقادیر این سلولها از یک routing engine میآیند که گراف شبکه جادهای واقعی را پیمایش میکند. سریعترین مسیر را از هر مبدأ به هر مقصد انتخاب میکند، هزینه قطعات را جمع میزند و کل را برمیگرداند. این به طور بنیادی با محاسبه haversine متفاوت است، که بین دو مختصات یک خط مستقیم میکشد و این واقعیت را که ساختمان، رودخانه و خیابان یکطرفه وجود دارد نادیده میگیرد.
یک جفت مختصات به شما میگوید دو نقطه کجا هستند. ماتریس فاصله به شما میگوید رفتن بین آنها واقعاً چقدر هزینه دارد.
Distance در برابر Duration
سه عدد متفاوت اغلب "distance" نامیده میشوند، و قاطی کردنشان رایجترین باگ در کد مسیریابی است.
Haversine distance فاصله great-circle بین دو جفت طول و عرض جغرافیایی است. محاسبهاش سریع است، نیازی به فراخوانی شبکه ندارد، و برای هر کاری که شامل رانندگی است غلط است. ۲ کیلومتر فاصله haversine میتواند وقتی به رودخانهای که نمیشود از آن گذشت رسیدید ۷ کیلومتر رانندگی شود.
Road-network distance طول مسیر قابل رانندگی واقعی است. خیابان یکطرفه، محدودیت گردش و توپولوژی گراف جاده را در نظر میگیرد. این همان چیزی است که distance matrix API در فیلد distance برمیگرداند.
Duration with traffic زمانی است که سفر با احتساب شرایط ترافیک فعلی یا پیشبینیشده طول خواهد کشید. یک قطعه ۱۲ کیلومتری بزرگراه در ساعت ۰۲:۰۰ شش دقیقه است و در ۱۷:۳۰ بیستوپنج دقیقه. سیستمهای واقعی که به ETA اهمیت میدهند duration آگاه به ترافیک میخواهند و یک departure time پاس میدهند تا routing engine بتواند ترافیک را درست مدل کند.
برای رتبهبندی و dispatch، duration تقریباً همیشه بر distance غلبه میکند. راننده اهمیت نمیدهد که شغل نزدیکتر ۸۰۰ متر دورتر است اگر چهار دقیقه از رانندگی کم کند.
ماتریسهای فاصله کجا ظاهر میشوند
ماتریسهای فاصله بیسروصدا زیر بیشتر قابلیتهای لجستیک و آگاه به مکان اجرا میشوند.
- تخصیص راننده تحویل: هر سفارش در انتظار با هر راننده در دسترس مطابقت داده میشود. dispatcher سلولی با کمترین duration را انتخاب میکند که محدودیتهای ظرفیت وسیله نقلیه و شیفت را رعایت کند
- Dispatch و توازن مجدد ناوگان: پلتفرمهای ride-hailing و last-mile هر چند ثانیه یک ماتریس بین وسایل نقلیه و مناطق تقاضا محاسبه میکنند تا خودروها را نزدیک سواران نگه دارند
- رتبهبندی locator فروشگاه و مکان: به جای برگرداندن پنج فروشگاه نزدیک با haversine، locator یک ماتریس کوچک از موقعیت کاربر تا کاندیداها محاسبه میکند و بر اساس زمان رانندگی رتبهبندی میکند
- محاسبات ETA در مقیاس: بازارهایی با سفارشهای همزمان متعدد ETA ها را در فراخوانیهای ماتریسی دستهبندی میکنند نه اینکه هزاران درخواست تکمسیری بفرستند
- VRP solver ها: solver های مسئله مسیریابی وسیله نقلیه (OR-Tools، jsprit، optimizer های تجاری) به یک ماتریس هزینه کامل بهعنوان ورودی نیاز دارند. کیفیت راهحل مسیریابی محدود به کیفیت ماتریسی است که به آن میدهید
- انتخاب سایت و برنامهریزی قلمرو: تحلیلگرها بین مکانهای کاندیدا و خوشههای مشتری ماتریس محاسبه میکنند تا انباری را انتخاب کنند که زمان رانندگی کل را کمینه کند
در همه این موارد، ماتریس همان عنصر اولیه محاسبه گروهی است. همان چیزی است که به سیستم اجازه میدهد بدون پرداخت هزینه N ضربدر M فراخوانی مسیریابی جداگانه دربارهٔ "بهترین از بین چندتا" استدلال کند.
دامها در محصول واقعی
ماتریس فاصله در روز اول ساده است و سریع سخت میشود.
نامتقارن بودن پیشفرض است. شبکههای جادهای واقعی خیابان یکطرفه، مسیرهای جداشده و هزینههای گردش نامتقارن دارند. سلول (A, B) به ندرت برابر سلول (B, A) است. در نظر گرفتن ماتریس بهعنوان متقارن برای صرفهجویی در حافظه یکی از دلایل کلاسیک مسیریابی اشتباه در سیستمهای dispatch است.
هزینه N ضربدر M. یک ماتریس ۱۰۰ در ۱۰۰ یعنی ۱۰٬۰۰۰ سلول. ۵۰۰ در ۵۰۰ یعنی ۲۵۰٬۰۰۰ سلول. هزینهها و تأخیر به صورت درجه دو رشد میکنند. بیشتر سیستمهای واقعی ماتریسها را به قطعات (۵۰ در ۵۰ یا ۱۰۰ در ۱۰۰) دستهبندی میکنند، درخواستها را موازی میکنند و نتایجی را که زیاد تغییر نمیکنند cache میکنند، مثل ماتریس بین یک مجموعه ثابت انبار و یک مجموعه ثابت فروشگاه.
واریانس زمان روز. ماتریسی که در ۰۳:۰۰ محاسبه شده در ۱۷:۰۰ معتبر نیست. اگر منطق dispatch شما به ترافیک وابسته است، یا در زمان تصمیم یک ماتریس آگاه به ترافیک درخواست کنید یا یک مجموعه کوچک از ماتریسهای زمانبندیشده پیشمحاسبه کنید (پیک صبح، خارج از پیک، پیک عصر) و درست را انتخاب کنید.
Batching و rate limit ها. distance matrix API ها هر عنصر را شارژ میکنند نه هر درخواست را، و بیشتر providerها اندازه یک فراخوانی را محدود میکنند. از روز اول برای chunking و back-pressure برنامهریزی کنید نه اینکه در مقیاس کشف کنید.
کیفیت مختصات ورودی، آشغال خروجی. یک ماتریس فقط به اندازه مختصاتی که به آن میدهید خوب است. یک geocode که در طرف اشتباه یک بزرگراه جداشده فرود آمده duration کاملاً اشتباهی تولید میکند. مختصات ورودی را قبل از ورود به درخواست ماتریس اعتبارسنجی کنید.
ماتریسهای فاصله در MapAtlas
MapAtlas Distance Matrix API ماتریسهای کامل N در M از زمان سفر و فاصله را روی شبکه جادهای واقعی اروپایی و جهانی محاسبه میکند. از پروفایلهای ماشین، کامیون، دوچرخه و عابر پیاده پشتیبانی میکند، درخواستهای آگاه به ترافیک با departure time را میپذیرد و برای اندازههای دستهای که workload های واقعی dispatch و بهینهسازی نیاز دارند ساخته شده است.
برای workload هایی که فراتر از رتبهبندی میروند، Distance Matrix API به طور طبیعی با Optimize Route API جفت میشود، که یک ماتریس و مجموعهای از stop ها را میگیرد و یک مسیر مرتبشده برمیگرداند که زمان رانندگی کل را کمینه میکند، و با Isochrone API برای فیلترهای "هر چیز قابل دسترسی در X دقیقه" که مجموعه کاندیدا را قبل از فراخوانی ماتریس کوچک میکنند.
ماتریس فاصله جذاب نیست. فقط یک شبکه از اعداد است. اما همان شبکه از اعداد است که "پیدا کردن بهترین از بین چندتا" را از یک کابوس مسیریابی N ضربدر M به یک درخواست گروهی واحد تبدیل میکند، و درست به دست آوردن این یک قطعه داده همان چیزی است که یک محصول لجستیک واقعی را از یک دموی پنج پینی متمایز میکند.
سوالات متداول
ماتریس فاصله چیست؟
ماتریس فاصله یک شبکه N در M از زمانها و فواصل سفر بین مجموعهای از مبدأها و مجموعهای از مقصدها است. هر سلول به یک سؤال پاسخ میدهد: رفتن از مبدأ i به مقصد j چقدر طول میکشد و چه فاصلهای دارد. distance matrix API های مدرن این مقادیر را روی شبکه جادهای واقعی محاسبه میکنند نه به صورت فاصله مستقیم، پس نتیجهها خیابان یکطرفه، محدودیت گردش و هندسه قابل پیمایش را در نظر میگیرند.
تفاوت distance و duration چیست؟
Distance میزان فاصلهای است که در طول شبکه جادهای طی میکنید، به متر یا کیلومتر. Duration مدت زمانی است که طول میکشد، به ثانیه، با احتساب محدودیت سرعت، ترافیک و کلاس جاده. این دو قابل تعویض نیستند. دو مسیر میتوانند فاصله یکسان و duration بسیار متفاوت داشته باشند، و بیشتر use case های واقعی (ETA، dispatch، رتبهبندی) به duration اهمیت میدهند. یک distance matrix API خوب هر دو را برای هر سلول برمیگرداند.
چه زمانی باید به جای مسیرهای تکی از ماتریس فاصله استفاده کنم؟
هر زمان که نیاز دارید چندین کاندیدا را مقایسه کنید: رتبهبندی پنج فروشگاه نزدیک از پنجاه فروشگاه، تخصیص یک تحویل به نزدیکترین راننده در دسترس از بیست راننده، یا تغذیه یک solver مسئله مسیریابی وسیله نقلیه. فراخوانی یک endpoint مسیریابی تکی N در M بار کند و گران است. یک endpoint ماتریسی همان داده را در یک درخواست برمیگرداند، که برای محاسبه گروهی بهینه شده است.
آیا ماتریسهای فاصله متقارن هستند؟
تقریباً هیچوقت در شبکههای جادهای واقعی. رانندگی از A به B به ندرت با B به A یکی است، به خاطر خیابانهای یکطرفه، بزرگراههای جداشده، محدودیت گردش و ترافیک نامتقارن. یک distance matrix API محصولی یک شبکه کامل N در M برمیگرداند، نه نصف مثلثی. اگر ماتریس را برای صرفهجویی در حافظه نصف کنید، رانندگان را به سمت اشتباه جاده هدایت میکنید.
