نقشه راه GIS

درخواست مشاوره

09120049370

8 صبح تا 12 شب

09120049370

Telegram Whatsapp Youtube
کاربرد جی ای اس

خلاصه

بهینه سازی مسیریابی خودرو (VRO) بهترین مسیرها را برای کاهش هزینه سفر، مصرف انرژی و انتشار کربن طراحی می کند. به دلیل پیچیدگی سخت چند جمله ای زمان (NP-hard) غیر قطعی، بسیاری از VRO های درگیر در برنامه های کاربردی دنیای واقعی به تلاش محاسباتی زیادی نیاز دارند. کوتاه کردن زمان محاسبات برای VRO یک چالش بزرگ برای پیشرفته ترین الگوریتم های بهینه سازی فضایی است. از دیدگاه مکانی-زمانی، این مقاله یک رویکرد اکتشافی مبتنی بر نمودار Voronoi مکانی-زمانی برای مشکلات مسیریابی وسایل نقلیه در مقیاس بزرگ با پنجره‌های زمانی (VRPTW) ارائه می‌کند. با در نظر گرفتن محدودیت های زمانی، یک فاصله ورونوی مکانی-زمانی از نمودار ورونوی مکانی-زمانی برای یافتن همسایگان نزدیک در زمینه جستجوی فضا-زمان مشتق شده است. یک استراتژی فروپاشی فاصله Voronoi که یک عملیات زمان پیچیدگی را ادغام می کند برای تسریع روندهای جستجوی محلی پیشنهاد شده است. یک جستجوی هدایت‌شده از ویژگی‌های مکانی-زمانی برای بهبود ساختارهای مسیر میکرو بی‌امید توسعه یافته است. آزمایش‌هایی روی معیارهای VRPTW و نمونه‌های واقعی برای تأیید عملکرد انجام می‌شوند. نتایج نشان می‌دهد که رویکرد پیشنهادی با روش‌های اکتشافی پیشرفته رقابتی است و راه‌حل‌هایی با کیفیت بالا برای نمونه‌های مقیاس بزرگ VRPTWs در مدت زمان کوتاهی به دست می‌آورد. این رویکرد جدید با توسعه یک روش موثر بهینه‌سازی مسیریابی وسیله نقلیه برای کاربردهای حمل‌ونقل بزرگ در بخش‌های عمومی و خصوصی، به جامعه پشتیبانی تصمیم‌گیری فضایی کمک می‌کند. یک جستجوی هدایت‌شده از ویژگی‌های مکانی-زمانی برای بهبود ساختارهای مسیر میکرو بی‌امید توسعه یافته است. آزمایش‌هایی روی معیارهای VRPTW و نمونه‌های واقعی برای تأیید عملکرد انجام می‌شوند. نتایج نشان می‌دهد که رویکرد پیشنهادی با روش‌های اکتشافی پیشرفته رقابتی است و راه‌حل‌هایی با کیفیت بالا برای نمونه‌های مقیاس بزرگ VRPTWs در مدت زمان کوتاهی به دست می‌آورد. این رویکرد جدید با توسعه یک روش موثر بهینه‌سازی مسیریابی وسیله نقلیه برای کاربردهای حمل‌ونقل بزرگ در بخش‌های عمومی و خصوصی، به جامعه پشتیبانی تصمیم‌گیری فضایی کمک می‌کند. یک جستجوی هدایت‌شده از ویژگی‌های مکانی-زمانی برای بهبود ساختارهای مسیر میکرو بی‌امید توسعه یافته است. آزمایش‌هایی روی معیارهای VRPTW و نمونه‌های واقعی برای تأیید عملکرد انجام می‌شوند. نتایج نشان می‌دهد که رویکرد پیشنهادی با روش‌های اکتشافی پیشرفته رقابتی است و راه‌حل‌هایی با کیفیت بالا برای نمونه‌های مقیاس بزرگ VRPTWs در مدت زمان کوتاهی به دست می‌آورد. این رویکرد جدید با توسعه یک روش موثر بهینه‌سازی مسیریابی وسیله نقلیه برای کاربردهای حمل‌ونقل بزرگ در بخش‌های عمومی و خصوصی، به جامعه پشتیبانی تصمیم‌گیری فضایی کمک می‌کند. نتایج نشان می‌دهد که رویکرد پیشنهادی با روش‌های اکتشافی پیشرفته رقابتی است و راه‌حل‌هایی با کیفیت بالا برای نمونه‌های مقیاس بزرگ VRPTWs در مدت زمان کوتاهی به دست می‌آورد. این رویکرد جدید با توسعه یک روش موثر بهینه‌سازی مسیریابی وسیله نقلیه برای کاربردهای حمل‌ونقل بزرگ در بخش‌های عمومی و خصوصی، به جامعه پشتیبانی تصمیم‌گیری فضایی کمک می‌کند. نتایج نشان می‌دهد که رویکرد پیشنهادی با روش‌های اکتشافی پیشرفته رقابتی است و راه‌حل‌هایی با کیفیت بالا برای نمونه‌های مقیاس بزرگ VRPTWs در مدت زمان کوتاهی به دست می‌آورد. این رویکرد جدید با توسعه یک روش موثر بهینه‌سازی مسیریابی وسیله نقلیه برای کاربردهای حمل‌ونقل بزرگ در بخش‌های عمومی و خصوصی، به جامعه پشتیبانی تصمیم‌گیری فضایی کمک می‌کند.
کلید واژه ها: 

سیستم پشتیبانی تصمیم فضایی ; مشکل مسیریابی خودرو ؛ نمودار ورونوی ; اکتشافی ; جستجوی محلی ؛ زوال فاصله

 

1. معرفی

خدمات حمل و نقل انعطاف پذیر نه تنها هزینه سفر را کاهش می دهد، بلکه نگرانی های مربوط به انرژی و زیست محیطی مانند تراکم ترافیک، مصرف انرژی و انتشار کربن را کاهش می دهد [ 1 ، 2 ]. با پیشرفت علم اطلاعات جغرافیایی (GIS)، تصمیم‌گیری مسئله مربوط به فضا در سیستم‌های پشتیبانی تصمیم‌گیری فضایی (SDSS) برای ارائه خدمات حمل‌ونقل انعطاف‌پذیر در بخش‌های عمومی و خصوصی [3]، مانند طراحی مدرسه تعبیه شده است. مسیرهای اتوبوس [ 4 ]، جمع آوری مواد زائد جامد [ 5 ، 6 ]، توزیع کالا در تجارت زنجیره ای [ 7 ]، طراحی مسیرهای گشت پلیس [ 8]]، و برنامه ریزی تحویل سریع [ 9 ]. ابزارهای عملکرد فضایی برای عملیات حمل و نقل هوشمند در بسیاری از خدمات از جمله مدیریت داده های شبکه حمل و نقل با مرجع جغرافیایی، ژئوکدگذاری نیازهای عظیم انسان، تعیین موقعیت وسایل نقلیه متحرک، و مسیریابی مسیرها برای رانندگان استفاده می شود [5 ، 6 ، 7 ، 8 ، 9 ] .
هدف بهینه‌سازی مسیریابی خودرو (VRO) طراحی مسیرهایی با کمترین هزینه برای برآوردن تقاضای انسانی توزیع‌شده جغرافیایی از طریق هوش فضایی SDSSs در زمینه حمل‌ونقل [10]، از جمله مشکل کوتاه‌ترین مسیر (SPP) [ 11 ، 12 ، 13 ]، سفر است. مشکل فروشنده (TSP) [ 14 ]، و مشکل مسیریابی وسیله نقلیه (VRP) [ 5 ، 6 ، 7 ]. یک نوع VRO به عنوان مشکل مسیریابی وسیله نقلیه با پنجره زمانی (VRPTW) مدل‌سازی می‌شود که محدودیت‌های زمانی را بر مشتریان، وسایل نقلیه و انبارها برای پذیرش یا توزیع خدمات با کیفیت بالا تحمیل می‌کند [4 ، 6 ، 14 ]]. مشخص می کند که یک مشتری فقط خدمات خاص مربوط به حمل و نقل را در یک بازه زمانی معین می پذیرد [ 15 ، 16 ، 17 ]. VRPTW از نظر محاسباتی در بسیاری از برنامه های کاربردی زندگی واقعی غیرقابل حل است [ 18 ]. الگوریتم اکتشافی تنها رویکرد موجه است زیرا می تواند راه حل های خوبی را در یک زمان معقول پیدا کند [ 16 ، 17 ]. دو نوع الگوریتم اکتشافی برای VRPTW وجود دارد که شامل جستجوی محلی و بهینه‌سازی تکاملی می‌شود. جستجوی محلی به طور مکرر ساختارهای مسیر محلی را تغییر می دهد تا کیفیت راه حل را بهبود بخشد و یک مسیر واحد را برای کشف فضای راه حل دنبال می کند [ 3 , 6 , 7]. بهینه سازی تکاملی به طور همزمان چندین بخش از کل فضای راه حل را جستجو می کند تا بر روی بهترین راه حل همگرا شود [ 5 ، 19 ، 20 ]. اخیراً، الگوریتم‌های ابتکاری پیشرفته گزارش شده‌اند که راه‌حلی با کیفیت بالا برای VRPTW با صدها مشتری ارائه می‌دهند [ 5 ، 9 ، 18 ]. برای برنامه های کاربردی VRPTW حتی بزرگتر، اکتشافی کارآمدتر مورد نیاز است.
اصل فضایی عملکرد خوبی در تصمیم گیری مسئله مربوط به فضا [ 21 ، 22 ، 23 ] در مسائلی مانند مکان ایستگاه اتوبوس [ 3 ]، برنامه ریزی مسیر همت [ 20 ] و پوشش مسیر [ 24 ] نشان داده است. برای حل کارآمد VRO، از منظر فضایی، چند استراتژی افزایش سرعت برای رسیدگی به مسائل فضایی و گسترش نمونه های VRO قابل حل تا هزاران مشتری، که شامل همسایگی دانه ای [25]، k امین نزدیکترین همسایه [26] است، توسعه داده شده است . ]، و همسایگان Voronoi حلقه ای شکل [ 27]. مخرج مشترک این استراتژی های موثر جستجوی تنها تعداد محدودی از همسایگان فضایی برای صرفه جویی در تلاش های محاسباتی است [ 28 ]. با این حال، چنین استراتژی‌های مفیدی برای VRPTW بی‌اثر می‌شوند، زیرا محدودیت زمانی تأثیر استثنایی بر نزدیکی مشتریانی که به طور متوالی در یک مسیر ارائه می‌شوند، تحمیل می‌کند. اگر دو مشتری از نظر مکانی نزدیک با پنجره های زمانی کاملاً متفاوت (مثلاً یکی از 8:00 تا 9:00 صبح و دیگری 3:00 تا 4:00 بعد از ظهر است) به طور متوالی در یک مسیر بازدید شوند، انتظار طولانی رخ خواهد داد. که انگیزه رویکردهای اکتشافی مبتنی بر مجاورت فضایی را به چالش می کشد. از این رو، اقدامات مجاورت فضایی باید برای رسیدگی به محدودیت‌های زمانی اضافی گسترش یابد [ 18]]. علاوه بر این، نحوه سرعت بخشیدن به VRO با کمک تفکر مکانی-زمانی باید بررسی شود.
نمودارهای ورونوی هم مجاورت فضایی و هم مجاورت توپولوژیکی بین اشیاء فضایی را توصیف می کنند [ 29 ، 30 ، 31 ، 32 ]. با گسترش آن به زمینه فضا-زمان، یک نمودار ورونوی مکانی-زمانی (STVD) به خوبی برای اندازه‌گیری نزدیکی مشتریان با محدودیت‌های زمانی مناسب است. بنابراین، این مقاله یک رویکرد اکتشافی مبتنی بر نمودار Voronoi فضایی-زمانی برای حل VRPTW های بسیار بزرگ را پیشنهاد می کند. یک همسایه ورونوی مکانی-زمانی مشتق شده از نمودار ورونوی برای انتخاب نامزدهای امیدوارکننده برای جستجوی محلی استفاده می‌شود. علاوه بر این، با انگیزه این حقیقت که همسایگان نزدیکتر امکان بالاتری برای خدمت رسانی متوالی در یک مسیر دارند [ 28]]، یک استراتژی فروپاشی فاصله Voronoi برای تخصیص تلاش های جستجوی معقول در همسایگان با فواصل مختلف Voronoi پیشنهاد شده است. یک جستجوی هدایت‌شده از ویژگی‌های مکانی-زمانی برای بازسازی ساختارهای ریز مسیر بی‌امید استفاده می‌شود. آزمایش‌های فشرده بر روی مجموعه داده‌های معیار (25-1000 مشتری) و VRPTW در مقیاس بزرگ در دنیای واقعی و انواع چند انبار آن (2000-10000 مشتری) برای ارزیابی عملکرد رویکرد پیشنهادی اجرا شده‌اند. این رویکرد کارآمد و مؤثر، اکتشافی‌های جستجوی محلی فعلی را قادر می‌سازد تا VRPTW‌های بزرگ مقیاس را حل کنند و به بهبود هوش فضایی برای SDSS‌های حمل‌ونقل محور کمک می‌کند.
ادامه این مقاله به شرح زیر سازماندهی شده است. بخش 2 ادبیات مرتبط را مرور می کند. بخش 3 VRPTW، STVD، فاصله زمانی-مکانی Voronoi مشتق شده و همسایگان را معرفی می کند. اکتشافی مبتنی بر نمودار ورونوی مکانی-زمانی پیشنهادی برای VRPTW و انواع چند انبار آن در بخش 4 توضیح داده شده است و جزئیات آزمایش ها، نتایج و مقایسه ها در بخش 5 گزارش شده است . بخش 6 تأثیر STVD و مجاورت مکانی-زمانی پشت بهترین راه حل های یافت شده را مورد بحث قرار می دهد. بخش آخر نتیجه گیری می کند.

2. بررسی ادبیات

این بخش به بررسی الگوریتم‌های اکتشافی برای VRPTW و ادغام بهینه‌سازی مسیریابی خودرو و GIS می‌پردازد.

2.1. الگوریتم های اکتشافی برای VRPTW

الگوریتم های اکتشافی برای VRPTW ها به دو دسته تقسیم می شوند: جستجوی محلی و بهینه سازی تکاملی. با شروع از یک راه حل اولیه، جستجوی محلی از یک راه حل فعلی به یک راه حل محله بهتر با تغییر ساده مسیرهای محلی تغییر می کند [ 33 ]. این تغییر به طور مکرر با حرکت گره ها یا تبادل کمان در یک مسیر یا بین مسیرهایی مانند تبادل 1-0، تبادل 1-1، 2-Opt و λλ-انتخاب معمولاً فرآیند تغییر در یک بهینه محلی به دام می‌افتد. برای غلبه بر نتایج بی‌امید، بسیاری از استراتژی‌های هوشمند که راه‌حل‌های بدتری را می‌پذیرند، برای بهبود بیشتر کیفیت راه‌حل، مانند بازپخت شبیه‌سازی شده [ 34 ]، جستجوی محلی تکراری [ 35 ]، جستجوی محله بزرگ [ 36 ]، جستجوی محله متغیر [ 37] توسعه یافته‌اند. ]، و جستجوی تابو [ 38 ]. آزمایش‌های متعدد روی VRPTW‌های کوچک و متوسط ​​با 25 تا 100 مشتری، عملکرد خوب اکتشافی جستجوی محلی را نشان داده‌اند [ 34 ، 36 ، 37 ].
بهینه سازی تکاملی به طور همزمان بسیاری از راه حل ها را بهبود می بخشد و منجر به راه حل های با کیفیت می شود. چهار مرحله اصلی درگیر است: بازنمایی، انتخاب، ترکیب و جهش. برخی از موفق ترین الگوریتم های بهینه سازی تکاملی برای VRPTW توسط Repoussis و همکاران ارائه شده است. [ 39 ] و ویدال و همکاران. [ 40 ]. Mester و Bräysy [ 41 ] از چارچوب بهینه سازی تکاملی استاندارد برای هدایت کاوش در فضای راه حل VRPTW با مقداردهی اولیه و تکامل راه حل استفاده کردند. گرینگ و هامبرگر [ 42] الگوریتم ژنتیک را موازی کرد و ابتدا نمونه های VRPTW را تا 1000 مشتری حل کرد. معمولاً از جستجوی محلی به عنوان مؤلفه ای در رویکرد بهینه سازی تکاملی استفاده می شود. جستجوی محلی سریع و ساده شده مبتنی بر تبادل قوس یا گره برای آموزش فرزندان در الگوریتم ژنتیک استفاده شده است [ 41 ]. بنابراین، اکتشافی جستجوی محلی کارآمدتر نیز به بهبود بهینه‌سازی تکاملی کمک می‌کند.
برای نمونه‌های بزرگ‌تر VRPTW، پیشرفت‌های اخیر چندین تکنیک شتاب‌دهنده را برای صرفه‌جویی در تلاش‌های محاسباتی و در عین حال دستیابی به راه‌حل‌های با کیفیت بالا پیشنهاد کرده‌اند. با پیروی از اصل جستجوی محلی، با در نظر گرفتن فاصله فضایی، کوردو [ 38 ] کاندیداهای جستجوی محلی را با kth نزدیکترین همسایه‌ها به کوتاه کردن زمان محاسبات محدود کرد. توث و ویگو [ 25 ] گره های ارزیابی شده جستجوی محلی را با یک آستانه فاصله ثابت انتخاب کردند. با در نظر گرفتن محدودیت های زمانی، ایباراکی [ 43 ] یک استراتژی مبتنی بر فهرست همسایگان زمان گرا برای کاهش ارزیابی جستجوی محلی پیشنهاد کرد. برخی از کاندیداهای جستجوی بی‌امید با پنجره‌های زمانی بی‌همتا حذف شدند. اما نزدیکی فضایی نادیده گرفته شده است. ناگاتا [ 44] برای جلوگیری از تجزیه و تحلیل پیچیده پنجره زمانی، برای مشتریانی که سرویس دیرهنگام داشتند، یک عملیات زمانبندی ایجاد کرد. یک تابع جریمه اضافی به اهداف اصلی اضافه شد تا اکتشافی جستجوی محلی را توجیه کند. با این حال، بعد مکانی و بعد زمانی هنوز در این اکتشافی های جستجوی محلی از هم جدا هستند.
یکی دیگر از روش‌های تسریع‌کننده مؤثر، تجزیه نمونه‌های VRPTW در مقیاس بزرگ به بسیاری از مسائل فرعی کوچک‌تر است. با استفاده از خوشه بندی فضایی، دوندو و سردا [ 45 ] VRPTW در مقیاس بزرگ را به مجموعه ای از مسائل با اندازه کوچک تقسیم کردند. مسیرهایی برای هر مشکل کوچک ایجاد شد تا راه حل اولیه با کیفیت بالا ارائه شود. چی و همکاران [ 18 ] یک اندازه گیری فاصله مکانی-زمانی موثر برای مقابله با مسائل مکانی و زمانی ایجاد کرد. یک VRPTW در مقیاس بزرگ با یک k تقسیم شدروش خوشه‌بندی مدوید برای ایجاد یک راه‌حل اولیه خوب. برای بهبود حل اولیه از الگوریتم ژنتیک استاندارد استفاده شد. عملکرد خوب این رویکردهای مؤثر توسط نمونه های VRPTW با بیش از 1000 مشتری تأیید شده است.
با توجه به نمودار Voronoi، تنها کار توسط Milthers [ 46 ] ارائه شده است که از نمودارهای Voronoi دو بعدی برای تقسیم VRPTW به بسیاری از مسائل فرعی و سپس حل آنها با اکتشافات جستجوی محله بزرگ استفاده کرد. اثربخشی نمودارهای Voronoi را در هدایت فرآیند جستجو نشان داد. با این حال، این مطالعه تنها با تجزیه VRPTW در مرحله ساخت محلول سروکار داشت. استفاده از نمودار مکانی-زمانی Voronoi در سرعت بخشیدن به جستجوی محلی برای VRPTW باید بیشتر مورد توجه قرار گیرد.

2.2. ادغام بهینه سازی مسیریابی خودرو و GIS

رویکردهای موثر برای یافتن راه حل های با کیفیت بالا برای VRPTW ها در یک SDSS مبتنی بر GIS تعبیه شده است تا با بسیاری از برنامه های کاربردی دنیای واقعی مقابله کند. به طور کلی، ادغام بین GIS و بهینه‌سازی مسیریابی وسیله نقلیه کاملاً همراه است. ابزارهای مدیریت، پردازش و تجسم داده‌های مکانی برای جمع‌آوری سفارش‌های مشتری، داده‌های مرتبط با ارجاع جغرافیایی، فعال کردن فرآیند حل و نمایش مسیرها برای VROها، مانند نرم‌افزارهای GIS مانند ArcGIS و TransCAD استفاده می‌شوند. در راستای جستجوی محلی، Weigel و Cao [ 7 ] ابتدا تلاش های خود را در اجرای یک رویکرد اکتشافی تابو در یک محیط GIS برای مقابله با VRO برای یک خرده فروش بزرگ آمریکایی گزارش کردند. با پیروی از خط بهینه سازی تکاملی، مندوزا و همکاران. [ 5] یک ماژول مسیریابی سفارشی را ادغام کرد که کیفیت راه حل را با راه حل های تجاری مانند SAP/R3 و ArcGIS برای مقابله با VRO ها در خدمات عمومی بهبود بخشید. آزمایش‌ها روی یک مورد واقعی در بوگوتا، کلمبیا با 323 تا 601 مشتری، اثربخشی بهینه‌سازی تکاملی و نرم‌افزار GIS را تأیید کردند.
اخیراً، پیشرفت GIS مربوط به رایانش ابری، ادغام GIS و VRO را به یک راه جفت آزاد منتقل می کند. با استفاده از نقشه های گوگل، سانتوس و همکاران. [ 47 ] SDSS های مبتنی بر وب کاربر پسند را توسعه دادند که VRO را برای مقابله با جمع آوری زباله های شهری در کویمبرا، پرتغال تعبیه کرد. TU و همکاران [ 48] یک چارچوب پشتیبانی تصمیم فضایی مبتنی بر GIS ابری با اکتشافات جستجوی همسایگی متغیر برای مسیریابی پویا وسایل نقلیه با استفاده از اطلاعات ترافیک تاریخی ارائه کرد. این شیوه ها تسلط VRO ها را در برنامه های حمل و نقل واقعی ثابت کرده است. با این حال، آنها همچنین نشان می‌دهند که هوش فضایی فعلی باید بهبود یابد تا توانایی SDSS در بخش‌های حمل‌ونقل برای مقابله با افزایش تعداد مشتریان افزایش یابد.
به طور خلاصه، اکتشافی های پیشرفته، از جمله جستجوی محلی و بهینه سازی تکاملی، VRPTW های کوچک و متوسط ​​را در یک زمان معقول حل می کنند. آنها تأیید شده اند که در یک محیط GIS برای موارد حمل و نقل واقعی با بیش از 1000 مشتری مؤثر هستند. برای کاربردهای واقعی با اندازه بزرگتر، الگوریتم های ابتکاری کارآمدتری برای کاهش زمان محاسبات مورد نیاز است. این مقاله با استفاده از نمودار Voronoi مکانی-زمانی، یک رویکرد مبتنی بر جستجوی محلی کارآمد را برای رسیدگی به VRPTW تا 10000 مشتری در یک زمان معقول پیشنهاد می‌کند. تفاوت با همسایگی در بافت فضایی [ 25 , 26 , 27 , 48 , 49 .]، محله مکانی-زمانی Voronoi با در نظر گرفتن فاصله مکانی و پنجره زمانی برای محدود کردن فضای جستجو پیشنهاد شده است. یک استراتژی فروپاشی فاصله Voronoi برای اختصاص تلاش‌های جستجوی بیشتر به همسایگان نزدیک‌تر ایجاد شده است. جستجوی هدایت‌شده ویژگی مکانی-زمانی برای فرار از حداقل‌های محلی استفاده می‌شود. جزئیات STVD، فاصله Voronoi، همسایگان Voronoi، و رویکرد پیشنهادی برای VRPTW در بخش‌های بعدی توضیح داده شده است.

3. VRPTW و نمودار ورونوی مکانی-زمانی

این بخش به معرفی VRPTW، STVD و فاصله Voronoi مکانی-زمانی می پردازد.

3.1. VRPTW

VRPTW دارای پنج جزء است: مشتریان، انبار، وسیله نقلیه، مسیرها و راه حل.
مشتریان : مجموعه ای از مشتریان Vج= {v1،v2, … ,vn}�ج={�1،�2،…،��}انتظار دارد خدمت شود. یک مشتری v i ( I > 0) واقع در ( xi , y i ) تقاضای منحصر به فردی دارد، q i ، مدت زمان سرویس، s i ، و یک پنجره زمان خدمات < e i , l i >. سرویس باید بعد از زمان شروع، e i و قبل از زمان پایان، l i برسد . چنین پنجره زمانی زمانی «نرم» نامیده می‌شود که ممکن است با هزینه جریمه نقض شود، و زمانی که هیچ تخلفی مجاز نباشد، «سخت» نامیده می‌شود.
انبار : انبار v0�0واقع در ( x 0 , y 0 ) خدمات را در یک پنجره زمانی < e 0 , l 0 > ارائه می دهد.
وسایل نقلیه : ناوگانی از K وسایل نقلیه یکسان با ظرفیت Q در انبار قرار دارد. هر وسیله نقلیه از انبار خارج می شود، به چندین مشتری خدمات رسانی می کند و به انبار باز می گردد. مسافت سفر و زمان بین گره ها (شامل مشتریان و انبار می شود) i , j به ترتیب با d ij و t ij مشخص می شوند که در آنمن ≠ jمن≠�.
مسیرها : یک مسیر r = ⟨v0،v1،v2، … ، vآر، vR + 1⟩�=〈�0،�1،�2،…، �آر، �آر+1〉توسط دنباله ای از مشتریان بازدید شده تشکیل می شود که نشان دهنده روند خدمات یک وسیله نقلیه است که در آن R تعداد مشتریان بازدید شده را نشان می دهد. vR + 1=v0�آر+1=�0، به طوری که وسیله نقلیه باید به انبار بازگردد. اولین زمان حرکت در انبار v0 �0 است آr��، اولین زمان ارائه خدمات به مشتری vمن �من است آvمن��من، و زودترین زمان بازگشت در انبار است آvR + 1���+1، که به صورت بازگشتی به صورت زیر تعریف می شوند:

{آv0=آr آvمن= حداکثر {آvمن – 1+سvمن – 1+تیi − 1 ، i،هvمن} ، ( i = 1 ، … ، R + 1  ){آ�0=آ� آ�من=حداکثر{آ�من–1+س�من–1+تیمن–1،من،ه�من}،(من=1،…، آر+1)
یک مسیر زیر دو محدودیت مشخص می شود: (1) مدت زمان مسیر آvR + 1–آrآ�آر+1–آ�نباید بیش از حداکثر مدت زمان T max باشد . (2) کل تقاضای خدمت شده ∑آرi = 1qمن∑من=1آر�مننباید بیش از ظرفیت خودرو Q باشد . کل مسافت طی مسیر به صورت تعریف شده است ∑آرi = 0دvمنvمن + 1∑�=0������+1. یک مسیر در صورتی امکان پذیر است که پنجره زمانی خدمات مشتری، مدت زمان مسیر و ظرفیت وسیله نقلیه برآورده شود.
راه حل VRPTW : یک راه حل برای یک نمونه VRPTW مجموعه ای از مسیرهای امکان پذیر است. r1،r2،r3، … ، rک�1,�2,�3,…, ��به طوری که یک وسیله نقلیه به هر مشتری یک بار مراجعه می کند. سلسله مراتبی از اهداف VRPTW در این مقاله دنبال می شود. تعداد وسایل نقلیه استفاده شده ابتدا به حداقل می رسد و سپس مسافت کل سفر کاهش می یابد.

3.2. نمودار ورونوی مکانی-زمانی برای VRPTWs

اجزای VRPTW، مانند مشتریان، انبار، وسایل نقلیه و مسیرها، دارای ویژگی‌های مکانی و زمانی هستند. ویژگی‌های فضایی به مکان‌های مشتریان، محل انبار و مسیرهای وسیله نقلیه اشاره دارد. ویژگی های زمانی به پنجره زمانی، زمان سرویس، زمان سفر و مدت زمان مسیر اشاره دارد. برای نمایش همزمان آنها، یک سیستم مختصات مکانی-زمانی با در نظر گرفتن بعد زمانی عمود بر صفحه مسطح XY ساخته می شود. بنابراین، پنجره های زمانی مشتریان و انبار به صورت خطوط عمودی که ریشه در مکان آنها دارند، مدل سازی می شوند.
شکل 1 یک VRPTW با اندازه کوچک با پنج مشتری ( v 1 تا v 5 )، یک انبار ( v 0 ) و دو مسیر ( R1 , R2 ) را نشان می دهد. مشتریان ( v 1 – v 5 ) و انبار ( v 0 ) به عنوان خطوط عمودی از نقطه شروع تا نقطه پایان آن، به عنوان بخش های خط L 1 – L 5 و L 0 مدل می شوند.. پیش‌بینی‌ها در صفحه XY نشان‌دهنده مکان‌های فضایی آن‌ها هستند، در حالی که پیش‌بینی‌ها در بعد زمانی نشان‌دهنده پنجره‌های زمانی و زمان خدمات واقعی آن‌ها هستند. حمل و نقل بین مشتریان نشان دهنده فرآیند خدمات در مسیرها ( R1 یا R2 ) است.
فاصله در این سیستم مختصات به صورت معادله (2) تعریف می‌شود، که در آن ( xi , y i ) و ( xj , y j ) مکان مکانی i و j را نشان می‌دهند و t i و t j نشان‌دهنده زمان i و j _ v¯�¯میانگین سرعت سفر است:

د(vمن،vj) =(ایکسمن–ایکسj)2+(yمن–yj)2+(v¯(تیمن–تیj) )2–––––––––––––––––––––––––––––√�(��,��)=(��−��)2+(��−��)2+(�¯(��−��))2
نمودار ورونوی فضای پارتیشن را به سلول های ورونوی مجاور با نقاط داده شده [ 30 ] ترسیم می کند. با پیروی از این اصل، یک نمودار ورونوی فضایی-زمانی فضای زمانی- مکانی را به سلول های زیادی تقسیم می کند. برای ایجاد یک نمودار Voronoi برای VRPTW، نقطه مرکزی مکانی-زمانی خط زمانی مکانی مشتری، ( xi , y i , ( e i + l i )/2.0) که نقطه قرمز در شکل 1 است ، برابر است با به عنوان نقطه بذر استفاده می شود. STVD برای VRPTW ها توسط الگوریتم سریع Quickhull [ 50 ] ساخته شده است.
در STVD، یک جفت نقطه که سلول‌های آن‌ها یک مرز مشترک دارند (ورونویی یا لبه ورونوی) همسایه‌های Voronoi [ 30 ] هستند. فاصله ورونوی مکانی-زمانی از یک نقطه معین i تا نقطه j ، vd ( i ، j )، به عنوان حداقل تعداد عبور از مرز ورونوی مکانی-زمانی در هر مسیری از i تا j تعریف می‌شود [ 27 ، 31 ] . شکل 2 مثالی را ارائه می دهد که فاصله ورونوی را نشان می دهد. فاصله ورونوی از P1 تا P3برای دو گذرگاه مرزهای ورونوی (C1-C2) 2 است. فاصله Voronoi از P1 تا P13 نیز 2 برای گذرگاه C3-C4 است. فاصله ورونوی از P1 تا P12 برای گذرگاه C5-C7 3 است. بنابراین، همسایگان Voronoi با مجاورت مکانی-زمانی متفاوت را می توان اندازه گیری کرد. از آنجایی که هم فاصله مکانی و هم پنجره های زمانی در نظر گرفته می شود، برای تسریع جستجوی محلی برای حل VRPTW مناسب است. با استفاده از این تعاریف مفید، این مقاله یک اکتشافی جستجوی محلی کارآمد را برای رسیدگی به VRPTW های مقیاس بزرگ پیشنهاد می کند.
Ijgi 04 02019 g001 1024
شکل 1. نمایش مکانی- زمانی VRPTW.
Ijgi 04 02019 g002 1024
شکل 2. نمودار ورونوی مکانی – زمانی و فاصله ورونوی مکانی – زمانی.

4. اکتشافی مبتنی بر نمودار ورونوی فضایی-زمانی

این بخش اکتشافی مبتنی بر نمودار Voronoi فضایی-زمانی (STVDH) را برای VRPTW های مقیاس بزرگ معرفی می کند. اصل STVDH سرعت بخشیدن به روند جستجوی محلی با استفاده از تفکر فضایی مفید، از جمله همسایگان Voronoi مکانی-زمانی، استراتژی جستجوی فروپاشی فاصله، و ویژگی‌های مسیر محلی است. چارچوب کلی اکتشافی پیشنهادی در شکل 3 خلاصه شده است. پس از ساخت یک راه حل اولیه (مرحله 1-1)، یک جستجوی اکتشافی محلی مبتنی بر همسایگی Voronoi مکانی-زمانی برای بهبود کیفیت راه حل دنبال می شود (مرحله 1-1 تا مرحله 1-4). یک استراتژی فروپاشی فاصله ورونوی مکانی-زمانی برای اختصاص تلاش‌های جستجوی معقول بر روی همسایگان با فواصل مختلف (مرحله 1-2) ایجاد شده است. ویژگی‌های مسیر مکانی-زمانی شناسایی شده و فرآیند جستجو را از حداقل‌های محلی فرار می‌دهد (مرحله 1-3). شرط توقف یک محدودیت در تعداد تکرار است (مرحله 1-4). در نهایت بهترین راه حل یافت شده گزارش می شود (مرحله 1-5).
Ijgi 04 02019 g003 1024
شکل 3. چارچوب الگوریتم اکتشافی مبتنی بر نمودار ورونوی مکانی-زمانی.

4.1. الگوریتم ساخت و ساز

الگوریتم ساخت و ساز به طور مکرر یک گره مسیریابی نشده را در موقعیت مناسب قرار می دهد تا زمانی که همه مشتریان مسیریابی شوند. در حین درج، به جای ارزیابی همه گره های مسیریابی نشده، مشتریان همسایه در یک فاصله Voronoi معین به عنوان نامزد گره های درج شده بعدی انتخاب می شوند. جزئیات الگوریتم ساخت در شکل 4 توضیح داده شده است . ابتدا، مشتریان بر اساس پنجره زمان شروع مرتب شده و در یک صف L ذخیره می شوند (مرحله 2-0). سپس، گره مسیریابی نشده جلویی L به عنوان گره عمل شده بیرون می آید μ � (مرحله 2-1). یک مسیر خالی r با u راه اندازی می شود (مرحله 2-2). یکی دیگر از مشتریان بدون مسیریابی v به طور تصادفی انتخاب می شود μ�همسایگان ورونوی. گره v قبل یا بعد از یک گره مسیریابی شده i در مسیر r درج می شود (مرحله 2-3). اگر درج انجام شود، u با v به روز می شود . بهترین مکان درج به عنوان جایی تعریف می شود که طول کل سفر اضافه شده و مقدار کل نقض پنجره زمان پایان را به حداقل می رساند، به عنوان معادله (3)، که در آن j نشان دهنده گره بازدید شده بعدی از i است . λ � یک مقدار تصادفی در [0.5, 2] است. لازم به ذکر است که زمان رسیدن در v , j نباید قبل از زمان شروع باشد، مانند معادلات (4) و (5):

Δ F= (دمن v+دv j– λدمن ج) +v¯(آمن+سمن+تیمن v–لv)Δ�=(���+���−λ���)+�¯(��+��+���−��)
آمن+سمن+تیمن v>هv��+��+���>ه�
آمن+سمن+تیمن v+سv+تیv j>هj��+��+���+س�+تی��>ه�
Ijgi 04 02019 g004 1024
شکل 4. الگوریتم ساخت.
در طول درج، چندین محدودیت از جمله پنجره زمان شروع، زمان طول مسیر، ظرفیت وسیله نقلیه و حداکثر طول مسیر باید رعایت شود. اگر جایی برای درج یافت نشد، گره جلویی L را به صورت u می‌زنیم ، آن را در مسیر جدیدی قرار می‌دهیم و آن را به‌عنوان مسیریابی برچسب‌گذاری می‌کنیم (مرحله 2-2 و مرحله 2-3). در صورتی که همه مشتریان به عنوان مسیریابی برچسب گذاری شده باشند، درج به پایان می رسد (مرحله 2-5). در نهایت، به دست آوردن تمام مسیرها راه حل اولیه است.

4.2. جستجوی محلی

جستجوی محلی به طور مکرر فضای راه حل را برای بهبود کیفیت راه حل بررسی می کند. معمولاً کاوش با استفاده از اپراتورهای جستجوی محلی لبه هایی را از راه حل فعلی حذف یا اضافه می کند. سه اپراتور جستجوی محلی معمولی، از جمله حرکت تبادل 1-0، حرکت تبادل 1-1، و حرکت 2-Opt [ 51 ]، برای کشف راه حل همسایگی در این مقاله استفاده می شود.

  • حرکت تبادل 1-0 یک گره را از محل اصلی تزریق می کند و آن را پس از دیگری وارد می کند. همانطور که شکل 5 a نشان می دهد، گره b از موقعیت فعلی خود حذف شده و قبل از گره i درج می شود .
  • حرکت مبادله 1-1 موقعیت های یک جفت گره را تعویض می کند. همانطور که شکل 5 b نشان می دهد، مکان گره های b و i با هم عوض می شوند.
  • 2-Opt move انتهای دو مسیر را بعد از موقعیت های یک جفت گره عوض می کند. همانطور که شکل 5 c نشان می دهد، مسیرهای جزئی بعد از b و i مبادله می شوند.
Ijgi 04 02019 g005 1024
شکل 5. اپراتورهای جستجوی محلی ( a ) تبادل 1-0; ( ب ) تبادل 1-1. و ( ج ) 2-انتخاب.
پیچیدگی محاسباتی این سه عملگر به دو جنبه بستگی دارد: گره های عملیاتی و ارزیابی جستجوی محلی. همانطور که در شکل 5 نشان داده شده است ، دو گره عملیاتی، به نام های b و i درگیر هستند . بنابراین، تعداد نامزدهای عملیاتی n ( n – 1) است، که در آن n تعداد مشتریان است. پیچیدگی زمانی است ای (n2)�(�2). برای هر جفت نامزد، ارزیابی جستجوی محلی، پنجره زمانی هر مشتری درگیر، مدت زمان کل، و ظرفیت وسیله نقلیه را برای هر مسیر بررسی می‌کند. با توجه به اثر آبشاری زمان رسیدن، به طور متوسط ​​طول می کشد O ( n / 2 R )�(�/2�)زمان، جایی که R تعداد مسیرها است. برای استفاده موثرتر از تلاش محاسباتی محدود، ما یک استراتژی فاصله-واپاشی Voronoi فضایی-زمانی را برای اختصاص تلاش‌های جستجو بر روی نامزدهای انتخاب شده پیشنهاد می‌کنیم. یک عملیات Warp زمان نیز برای کوتاه کردن زمان محاسبات برای هر نامزد استفاده می شود.

4.2.1. استراتژی فروپاشی فاصله مکانی-زمانی

متفاوت از شدت جستجوی مساوی k نزدیکترین همسایه [ 26 ] و حلقه k همسایگان Voronoi [ 27 ، 48 ]، استراتژی فروپاشی فاصله ورونوی فضایی-زمانی بیشتر در همسایگان نزدیکتر جستجو می کند تا همسایگان بیشتر برای متعادل کردن کیفیت راه حل و محاسبات. زمان. برای همسایگان Voronoi مکانی-زمانی با فاصله Voronoi k ، احتمال جستجو Pk به عنوان معادله (6) تعریف می شود. با افزایش فاصله k ، احتمال جستجو P kکاهش خواهد یافت. بنابراین، بیشتر تلاش های محاسباتی بر روی همسایگان نزدیک متمرکز خواهد شد، اما برخی تلاش های لازم برای همسایگان بعدی باقی مانده است.

پک=α– ک∑کm a xk = 1α– ک��=�−�∑�=1�����−�

که در آن k = 1، …، k max ، و k max حداکثر فاصله Voronoi قابل جستجو است، α ∈ [ 1 , ∞ ) �∈[1,∞) مقداری است که سرعت فروپاشی فاصله مکانی-زمانی را کنترل می کند. به عنوان ارزش α�افزایش می یابد، سرعت پوسیدگی سریعتر می شود.

محدوده احتمال [ TP k -1 ، TP k ] ( k = 1، 2، …، k max ) برای همسایگانی که از فاصله ورونوی k دورتر نیستند، به عنوان معادله (7) محاسبه می شود، که در آن TP 0 = 0 است.

تیپک=∑i = 1کپمن���=∑�=1���
برای اجرای استراتژی کاهش فاصله Voronoi، جستجوی محلی به طور تصادفی مقداری از تولید می کند δ δ بین (0، 1)، محدوده احتمالی را پیدا می کند که در آن δδقرار می گیرد و سپس همسایگان Voronoi با فاصله k مربوطه را به عنوان نامزد برای ارزیابی انتخاب می کند. از آنجایی که از ارزیابی همه همسایگان اجتناب می‌کند، این استراتژی مفید تلاش‌های بیشتری را برای جستجو در گره‌های نزدیک‌تر انجام می‌دهد و بنابراین به طور قابل توجهی جستجوی محلی را تسریع می‌کند. همانطور که تعداد همسایگان Voronoi ثابت است، پیچیدگی محاسبات کاهش می یابد ای (n2)�(�2)به O ( n )�(�).

4.2.2. عملیات زمان تاب

جستجوی محلی محدودیت‌های فاصله و زمانی را برای مشتریان و مسیرها ارزیابی می‌کند که بیشترین هزینه محاسباتی را دارد [ 43 ]. ناگاتا [ 45 ] یک تابع جریمه جدید پیشنهاد کرد که در آن تغییر را می توان در زمان O(1) برای VRPTW محاسبه کرد. هنگامی که یک سرویس بعدی برای مشتری اتفاق می افتد، یک عملیات زمان تاب انجام می شود به طوری که زمان رسیدن به انتهای پنجره زمانی تنظیم می شود و یک جریمه به هدف اصلی اضافه می شود. شکل 6 نمونه ای از زمان تاب را نشان می دهد. هزینه جریمه اضافی به عنوان تاب زمانی استفاده شده در معادلات (8) و (9) تعریف می شود، که در آن tw i ارزش هزینه در مشتری i است ، و ( a i – e i)) + یک مقدار غیرمنفی سرویس دیر هنگام در i است . بنابراین، هدف برای به حداقل رساندن تعداد کل مسیر، طول کل مسیر و مجموع هزینه جریمه TW(های) تغییر می کند . برای O(1) زمان مصرف شده، عملیات زمان تاب بسیار سریع است.

تیدبلیو( ها ) =∑i = 1nتیwمنتیدبلیو(س)=∑من=1�تی�من
تیwمن=(آمن–همن)+تی�من=(آمن–همن)+
Ijgi 04 02019 g006 1024
شکل 6. زمان انتظار و پیچیدگی زمان در مشتری.

4.2.3. معیار پذیرش

جستجوی محلی به طور طبیعی به حداقل های محلی کاهش می یابد. برای فرار از معیار پذیرش آستانه استفاده می شود. اگر راه حل یافت شده 0.5% بدتر از راه حل فعلی نباشد، به عنوان راه حل جدید پذیرفته می شود. در غیر این صورت رد خواهد شد. اگر بهترین راه‌حل در تکرارهای Z max بهبود نیابد ، جستجوی هدایت‌شده ویژگی‌های مکانی-زمانی آغاز می‌شود.

4.3. ویژگی های مکانی-زمانی-جستجوی هدایت شده

با توجه به استفاده از همسایه‌های Voronoi مکانی-زمانی، جستجوی محلی نسبت نسبتاً کمی از راه‌حل‌های محله را بررسی می‌کند. برخی از راه‌حل‌های بالقوه محله به دلیل محدودیت‌های مکانی و زمانی، مانند مدت زمان مسیر، پنجره زمانی و ظرفیت وسیله نقلیه رد خواهند شد. متفاوت از آشفتگی‌های تصادفی سنتی [ 37 ]، جستجوی هدایت‌شده ویژگی‌های مکانی-زمانی ساختارهای بی‌امید تعریف‌شده توسط قوانین مکانی-زمانی را از بین می‌برد و بخشی از راه‌حل فعلی را برای فرار از حداقل‌های محلی بازسازی می‌کند. همچنین احتمال جستجو برای راه حل های محله دورتر را افزایش می دهد. سه مؤلفه عبارتند از ویژگی های مکانی- زمانی، الگوریتم حذف و الگوریتم درج مجدد.

4.3.1. ویژگی های مکانی- زمانی

سه نوع ویژگی مکانی-زمانی در این مقاله تعریف شده است که شامل گره های نقض پنجره زمانی می شود φتی�تی، دورترین گره ها φل�لو کوچکترین گره های مسیر φس�س. تعاریف آنها در زیر توضیح داده شده است.
  • گره های نقض پنجره زمانی
عملیات Warp زمان تاخیر پنجره زمانی را معرفی می کند که در آن زمان رسیدن به مشتری ممکن است دیرتر از زمان پایان پنجره زمانی آن باشد. با این حال، این ویژگی مسیر نباید به بهترین راه حل تعلق داشته باشد. چنین گره‌های بی‌امیدی را از راه‌حل فعلی حذف می‌کنیم و بعداً دوباره آن‌ها را وارد می‌کنیم. به طور رسمی، گره های نقض پنجره زمانی φتی��به عنوان معادله (10) تعریف می شوند:

φتی= {vمن|تیمن>لمن،vمن∈Vج}��={��|��>��,��∈��}
  • گره های دورترین فاصله
برای همکاری با پنجره زمانی، برخی از بخش های طولانی ممکن است در مسیرها نگه داشته شوند و جایگزینی آنها در جستجوی محلی دشوار باشد، که منجر به افزایش طول کل مسیر می شود [ 27 ]. گره های دورترین فاصله φل��نقاط انتهایی قطعه طولانی هستند که به عنوان معادله (11) تعریف می شوند، که در آن S نشان دهنده راه حل فعلی است، e ij یا e ji نشان دهنده یک قطعه در S است . ه¯ �¯ نشان دهنده میانگین فاصله فضایی همسایگان ورونوی با فاصله ورونوی 1 است. طول بخش طولانی بیش از سه برابر است. ه¯�¯.

φل= {vمن|دمن ج> 3ه¯،همن ج∈ اس| |هj i∈ اس،vمن∈Vج}��={��|���>3�¯,���∈�||���∈�,��∈��}
  • کوچکترین گره های مسیر
در برخی راه‌حل‌ها، مسیرهای کوچک تنها به یک، دو یا سه مشتری در نزدیکی انبار خدمات می‌دهند که به وسایل نقلیه بیشتری نیاز دارد [ 48 ]. معمولاً این ویژگی برای ویژگی زیر بهینه نگه داشته می شود. گره های مسیر کوچک به این صورت تعریف می شوند φس��، به عنوان معادله (12)، که در آن | r | تعداد مشتریان بازدید شده در مسیر r را نشان می دهد :

φل= {vمن|vمن∈ r , | r | ≤ 3 ،vمن∈Vج}��={��|��∈�,|�|≤3,��∈��}

4.3.2. الگوریتم حذف

برای افزایش تنوع جستجوی هدایت شده، گره های بیشتری از راه حل فعلی در این مطالعه حذف می شوند. گره های اضافی φآ �آ همسایگان Voronoi از ویژگی های تعریف شده هستند، درست مانند:

φآ= {vمن| v d(vمن،vj) = 1 ،vj∈ (φتی∪راφل∪راφس) ،vمن∉ (φتی∪راφل∪راφس) ،vمن∈Vج}�آ={�من|�د(�من،��)=1،��∈(�تی∪را�ل∪را�س)،�من∉(�تی∪را�ل∪را�س)،�من∈�ج}
بنابراین، گره ها حذف شدند φ�گره های ویژگی های مکانی-زمانی و همسایگان Voronoi آنها هستند φآ�آمانند معادله (14). الگوریتم حذف به طور متوالی تمام گره های متعلق به آن را خارج می کند φ�و یک محلول جزئی برای درج باقی می گذارد.

φآ= {vمن∣∣vمن∈ (φتی∪راφل∪راφس∪راφآ) ،vمن∈Vج}�آ={�من|�من∈(�تی∪را�ل∪را�س∪را�آ)،�من∈�ج}

4.3.3. الگوریتم درج

این الگوریتم تمام گره های حذف شده را در مکان های جدید در حل جزئی قرار می دهد. ابتدا، تمام گره های حذف شده به طور تصادفی در یک صف L قرار می گیرند . سپس، گره جلویی L بیرون می‌آید و در بهترین مکان قبل یا بعد از همسایه‌های Voronoi خود قرار می‌گیرد تا مجاورت مکانی-زمانی را حفظ کند، که هزینه درج را به عنوان معادله (3)، تحت محدودیت مدت زمان کل، پنجره زمانی، به حداقل می‌رساند. و ظرفیت وسیله نقلیه قابل توجه است که پنجره های زمان پایانی نباید نقض شود. در صورت عدم وجود مکان مناسب، مسیر جدیدی ایجاد می شود و گره جلویی Lبیرون می آید و به عنوان اولین مشتری ارائه می شود. عملیات درج تا زمانی که تمام گره های حذف شده در مکان های مناسب قرار گیرند تکرار می شود. با توجه به بهترین انتخاب در هر درج، راه حل نهایی تا دنباله گره در صف است. در این مقاله، دنباله به طور تصادفی 50 بار مرتب شده است تا راه حل های بازسازی متفاوتی به دست آید. در نهایت، نتیجه به دست آمده از جایگشت که هدف کل را به حداقل می رساند به عنوان راه حل نهایی پذیرفته می شود.

4.4. توسعه الگوریتم حل برای MDVRPTW

MDVRPTW نوعی از VRPTW است که بیش از یک انبار دارد تا به مشتریان پراکنده جغرافیایی خدمات ارائه دهد. در مقایسه با VRPTW، MDVRPTW یک مشکل اضافی در مورد نحوه تخصیص مشتریان به انبار مناسب دارد. پارتیشن Voronoi که یک منطقه مورد مطالعه را با اشیاء داده شده به بسیاری از مناطق تقسیم می کند، یکی دیگر از عملکردهای معمولی نمودار Voronoi است. برای اثربخشی، به طور گسترده در تجزیه و تحلیل منطقه خدمات استفاده شده است [ 32 ]. با استفاده از ویژگی‌های پارتیشن Voronoi نمودار Voronoi مکانی-زمانی انبارها، ما مشتریان را تعیین می‌کنیم که توسط انبار مناطق ورونوی واقع در آن خدمات ارائه کنند. به این ترتیب، STVDH ارائه شده برای مقابله با یک MDVRPTW در مقیاس بزرگ با تجزیه آن به بسیاری از VRPTW های کوچکتر، آسان است.
شکل 7 گردش کار انطباق STVDH برای MDVRPTW را نشان می دهد. نمودار مکانی-زمانی ورونوی انبارها برای تخصیص مشتریان به انبار واقع شده ساخته شده است به طوری که MDVRPTW به چندین VRPTW تقسیم می شود که هر یک دارای یک انبار و تعداد زیادی مشتریان اختصاص یافته است. مسیرها برای هر VRPTW ابتدا با استفاده از الگوریتم ساخت در بخش 4.1 مقداردهی اولیه می شوند و سپس به طور جداگانه توسط اکتشافی جستجوی محلی مبتنی بر نمودار Voronoi مکانی-زمانی در بخش 4.2 و بخش 4.3 بهبود می یابند.. برای غلبه بر اثر مرزی نمودار Voronoi، یک بهبود اضافی بین انبارها برای جابجایی یا تبادل گره‌ها بین مسیرهایی که توسط انبارهای مختلف ارائه می‌شوند استفاده می‌شود. این کار با استفاده از مبادلات 1-0 و 1-1 برای جابجایی گره ها بین مسیرهایی که توسط انبارهای مختلف ارائه می شوند، پس از جستجوی هدایت شده ویژگی های مکانی-زمانی انجام می شود. جزئیات این فرآیند به TU و همکاران ارجاع داده شده است. [ 49 ]. شرایط توقف مانند STDVH است. در نهایت بهترین راه حل یافت شده گزارش شده است.
Ijgi 04 02019 g007 1024
شکل 7. سازگاری STVDH برای MDVRPTW.

5. آزمایش و مقایسه

برای ارزیابی عملکرد STVDH، آزمایش‌هایی با مشکلات معیار و مشکلات دنیای واقعی VRPTW و MDVRPTW در مقیاس بزرگ در شانگهای، چین انجام شد. الگوریتم STDVH با C++ اجرا شد که بر روی سیستم 64 بیتی ویندوز 7 با پردازنده Intel Core i7-3.4G و حافظه 16 گیگابایتی اجرا می‌شد. این بخش مجموعه داده های آزمایشی، تنظیم پارامترها، نتایج محاسباتی و مقایسه با سایر الگوریتم های اکتشافی را گزارش می دهد. زمان های محاسبه الگوریتم های مقایسه شده به پلت فرم محاسباتی STVDH با فاکتور Dongarra [ 52 ] تبدیل می شوند.

5.1. مجموعه داده مشکل VRPTW و MDVRPTW را آزمایش کنید

دو نوع از مجموعه داده‌های مشکل VRPTW و MDVRPTW آزمایش می‌شوند. اولین مجموعه داده شامل معیارهای VRPTW Solomon [ 15 ] و Gehring و Homberger [ 53] است.]. بنچمارک های Solomon دارای 56 مشکل با 100 مشتری هستند. آنها به شش گروه با هشت تا دوازده مشکل به نام‌های R1، R2، C1، C2، RC1 و RC2 تقسیم می‌شوند. در صفحه اقلیدسی، مشتریان به طور تصادفی (R1 و R2)، توزیع خوشه ای (C1 و C2) یا توزیع نیمه خوشه ای (RC1 و RC2) توزیع می شوند. هر نمونه دارای یک انبار واحد در حوزه فضایی مشتریان است. زمان سفر بین گره ها برابر با فاصله اقلیدسی مربوطه است. R1، C1 و RC1 افق زمان‌بندی کوتاهی دارند، در حالی که R2، C2 و RC2 افق زمان‌بندی طولانی دارند. مشابه مشکلات VRPTW Solomon، معیارهای VRPTW Gehring و Homberger [ 53 ] دارای 300 نمونه VRPTW با 200، 400، 600، 800 یا 1000 مشتری هستند [ 54] .]. مشتریان توزیع های مشابهی دارند.
مجموعه داده دوم یک مجموعه داده مشکل VRPTW و MDVRPTW در مقیاس بزرگ در شانگهای، چین است [ 55]. پنج نمونه VRPTW (Sh1a–Sh5a) و 5 نمونه MDVRPTW (Sh1b–Sh5b) با 2000 تا 10000 مشتری و یک تا شش انبار برای شبیه‌سازی خدمات تحویل بسته روزانه یک شرکت لجستیک در شانگهای، چین تولید می‌شوند. مشتریان به طور تصادفی از نقاط تجاری مورد علاقه (POI) با استفاده از یک نقشه ناوبری دیجیتال حرفه ای برای به دست آوردن مکان های فضایی در دنیای واقعی انتخاب می شوند. پنجره زمانی هر مشتری یک مقدار تصادفی در دقیقه است که با 30 و 60 محدود شده است و مدت زمان خدمات یک مقدار تصادفی از 1 تا 4 دقیقه است. تقاضا یک مقدار تصادفی در بازه [1، 100] است. انبارها در مناطق لجستیک حرفه ای در شهر واقع شده اند. همه وسایل نقلیه دارای ظرفیت یکسان، 2000 و حداکثر طول مسیر، 480 دقیقه هستند. میانگین سرعت سفر 45 کیلومتر در ساعت تعیین شده است.

5.2. تنظیم پارامتر

همانطور که در شکل 3 نشان داده شده است، چهار پارامتر باید در الگوریتم STVDH ارائه شده تنظیم شوند . به دنبال رویکرد کالیبراسیون Coy [ 56 ]، یک آزمایش مقدماتی بر روی یک نمونه در مجموعه داده مشکل برای یافتن بهترین تنظیمات پارامتر انجام می‌شود. فرآیند تنظیم در ابتدا دو پارامتر اول مربوط به شرایط توقف و سپس دو پارامتر آخر مربوط به استراتژی فروپاشی فاصله Voronoi را شناسایی می کند. دو پارامتر اول، حداکثر تعداد تکرار، N max ، و حداکثر تعداد تکرار برای شروع ویژگی‌های مکانی-زمانی هدایت شده جستجوی محلی، Z max ، خروجی STVDH را کنترل می‌کند. پس از آزمایش های فشرده با شرایط توقف مختلف،N max باید روی 5000 N تنظیم شود تا روی یک راه حل با کیفیت بالا با ثبات همگرا شود، جایی که N تعداد مشتریان است. Z max روی 100 نیوتن تنظیم شده است تا جستجوی هدایت شده با ویژگی مکانی-زمانی آغاز شود.
دو پارامتر آخر استراتژی افزایش سرعت مبتنی بر نمودار Voronoi را کنترل می کنند. پارامتر سوم، کm a xکمترآایکس، حداکثر همسایگان Voronoi قابل جستجو را نشان می دهد. به عنوان ارزش کm a xکمترآایکسافزایش می یابد، جستجوی محلی همسایگان بیشتری را ارزیابی می کند، که به تلاش های محاسباتی بیشتری نیاز دارد. با توجه به توزیع همسایگان ورونوی، کm a xکمترآایکسنباید بیشتر از 5 باشد [ 49 ]. آخرین پارامتر،  α �، سرعت فروپاشی فاصله را تعیین می کند. مقدار بالا نشان دهنده تمایل به پوسیدگی سریع است. ارزش مناسب از α�در محدوده [ 1 ، 4 ] قرار دارد. فضای مقدار پارامترها در جدول 1 خلاصه شده است .
جدول
جدول 1. تنظیمات پارامتر الگوریتم STDVH.
آزمایش‌ها بر روی برخی از نمونه‌های VRPTW انتخاب شده برای تنظیم مقادیر پارامتر برای یک نوع مجموعه داده VRPTW انجام می‌شود. با در نظر گرفتن دومین مجموعه داده VRPTW به عنوان مثال، ما Sh2a را با تمام ترکیبات دو پارامتر آخر حل کردیم. بالاخره تنظیم کردیم کm a xکمترآایکس= 3 و = 2 برای بهترین عملکرد در آزمایش. بدون از دست دادن کلیت، مقادیر پارامتر یکسان برای هر نمونه تنظیم شد. تأثیر نمودار ورونوی در بخش 6 مورد بحث قرار خواهد گرفت . خلاصه ای از تنظیمات پارامتر در جدول 1 فهرست شده است . با در نظر گرفتن Sh2a به عنوان مثال، شکل 8 همگرایی تعداد مسیرها و طول کل مسیرها را با تنظیمات پارامتر مورد استفاده در حل Sh2a نشان می دهد.

5.3. نتایج معیارهای سولومون [ 15 ] و گرینگ و هامبرگر [ 53 ] VRPTW

تنظیم پارامتر برای این معیارهای VRPTW به این صورت است: N max = 5000 N , Z max = 100 N , کm a xکمترآایکس= 2 و α�= 1.5. برای هر مشکل، STDVH 10 بار اجرا شد. هدف کل، طول کل مسیرها و زمان محاسبه ثبت شد. نتایج سه روش پیشرفته، از جمله الگوریتم تکاملی هدایت‌شده با قوس (AGEA) [ 39 ]، الگوریتم ژنتیک ترکیبی با مدیریت تنوع تطبیقی ​​(HGASDC) [ 40 ]، و اکتشافی مبتنی بر جستجوی محلی VRPEJ [ 57] ]، که فضای جستجو را با kامین استراتژی نزدیکترین همسایه محدود می کند ، با STVDH مقایسه می شود.
Ijgi 04 02019 g008 1024
شکل 8. همگرایی تعداد کل مسیرها و طول کل مسیرها (Sh2a).
جدول 2 و جدول 3مقایسه نتایج بر روی معیارهای Soloom و Gehring و Homberger VRPTW به ترتیب ارائه شده است. هر ورودی میانگین نتایج محاسباتی یک گروه را گزارش می‌کند (میانگین زمان محاسبات | میانگین طول کل مسیرها). آنها نشان می دهند که STVDH ارائه شده قادر به دستیابی به راه حل های با کیفیت بالا از VRPTW ها با بیش از 1000 مشتری در یک زمان محاسباتی نسبتاً کوتاه است. از نظر تعداد مسیرها، STVDH کمترین مسیرها را در معیارهای VRPTW Solomon (مجموع 405 مسیر) و Gehring و Homberger (مجموع 10296 مسیر) به دست می‌آورد. از نظر طول کل مسیر، STVDH عملکرد بهتری نسبت به VRPEJ برای تمام نمونه‌های VRPTW دارد، فقط در معیارهای Solomon نسبت به AGEA پایین‌تر است، اما در معیارهای Gehring و Homberger برتر از AGEA است. با این حال، نتایج STVDH هنوز بدتر از HGSADC است. برای بهره وری محاسباتی، STVDH کمترین زمان محاسباتی را در هر شش نمونه VRPTW اندازه (100 تا 1000) مصرف می کند. بنابراین، STDVH پیشنهادی عملکرد خوبی را در معیارهای VRPTW Solomon و Gehring و Homberger نشان می‌دهد.
جدول
جدول 2. مقایسه نتایج روی معیارهای Solomon VRPTW [ 15 ].
جدول
جدول 3. مقایسه نتایج روی معیارهای گرینگ و هامبرگر VRPTW [ 53 ].

5.4. نتایج مشکل VRPTW و MDVRPTW در مقیاس بزرگ در شانگهای، چین

تنظیم پارامتر برای این مشکل VRPTW و MDVRPTW در مقیاس بزرگ به شرح زیر است: N max = 5000 N ، Z max = 100 N ، کm a xکمترآایکس=3 و α�= 2. برای هر مشکل، الگوریتم STVDH نیز 10 بار اجرا شد. کل مسافت سفر، تعداد وسایل نقلیه استفاده شده و زمان محاسبات ثبت شد. نتایج به دست آمده در جدول 4 ( https://github.com/spatialsmart/VRPTW/tree/master/Shanghai/Solution ) خلاصه شده است.
به عنوان جدول 4نشان می دهد، الگوریتم STVDH بهترین راه حل یافت شده را برای VRPTW های بزرگ تا 10000 مشتری در 139.5 دقیقه (حدود 2.32 ساعت) گزارش می دهد. با افزایش تعداد مشتریان از 2000 به 10000، زمان محاسبه STVDH از 15.7 دقیقه به 120.8 دقیقه افزایش می یابد، در حالی که برای MDVRPTW، زمان از 16.1 دقیقه به 139.5 دقیقه افزایش می یابد. در مقایسه با VRPTW، به دلیل تخصیص بیشتر مشتری بین انبارها، تلاش های محاسباتی بیشتری برای MDVRPTW مورد نیاز است. از نظر کیفیت راه حل، STVDH به طور متوسط ​​از 847.1 مسیر کل استفاده می کند که 30184.725 کیلومتر را طی کرده است تا به همه مشتریان در پنج مورد VRPTW خدمات ارائه دهد. برای پنج نمونه MDVRPTW، 906.4 مسیری که 26353.572 کیلومتر را طی کرده اند برای برآوردن نیازهای مشتری مورد نیاز است. لازم به ذکر است که عملکرد STVDH قوی است، همانطور که با فاصله بین نشان داده می شودS avg و S بهترین (-1.60٪ برای VRPTW و -1.73٪ برای MDVRPTW). بنابراین، STVDH پیشنهادی نتایج امیدوارکننده‌ای را برای VRPTW و VRPTW در مقیاس بزرگ در زمان‌های محاسباتی معقول ارائه می‌کند.
با در نظر گرفتن مشکل Sh1a به عنوان مثال، شکل 9 بهترین راه حل پیدا شده و مسیر مکانی-زمانی وسیله نقلیه را با ArcScene نشان می دهد. این بهترین سازش مسیر بین مجاورت فضایی و محدودیت‌های زمانی را نشان می‌دهد. همانطور که شکل 9 ب نشان می دهد ، همان وسیله نقلیه ممکن است هنوز به مشتریان نزدیک به مکانی خدمات ارائه ندهد .
برای ارزیابی کیفیت حل نتایج به دست آمده، آنها را با راه حل های گزارش شده توسط دو الگوریتم اکتشافی مقایسه می کنیم. یک راه حل با حل نمونه های شبیه سازی شده با ماژول تحلیل شبکه در ArcGIS TM 10.2 به دست می آید که از یک الگوریتم اکتشافی تابو برای حل مسائل پیچیده VRPTW در دنیای واقعی استفاده می کند. راه حل مقایسه شده دیگری با استفاده از VRPEJ [ 55 ] محاسبه می شود. سایر فراابتکاری ها مانند AGEA و HGSDAC به دلیل در دسترس نبودن مقایسه نمی شوند. هر الگوریتم 10 بار برای یافتن بهترین نتیجه اجرا شد.
جدول
جدول 4. نتایج حاصل از نمونه های VRPTW و MDVRPTW در مقیاس بزرگ در شانگهای، چین.
Ijgi 04 02019 g009 1024
شکل 9. نتیجه مشکل VRPTW در مقیاس بزرگ Sh1a. ( الف ) بهترین راه حل نهایی؛ و ( ب ) یک مسیر مکانی- زمانی.
جدول 5 نتایج به دست آمده را با هم مقایسه می کند. این نشان می دهد که STVDH ارائه شده در این مطالعه از ArcGIS و VRPEJ بهتر عمل می کند. از نظر کارایی، مقایسه با ArcGIS (مجموع 2141.1 دقیقه) و VRPEJ (مجموع 2355.3 دقیقه) نشان می دهد که STVDH کمترین تلاش محاسباتی را هزینه می کند (مجموع 703 دقیقه). از نظر کیفیت راه حل، STVDH به 1729 مسیر با مسافت 55990.55 کیلومتر نیاز دارد تا در 10 مورد به همه مشتریان خدمات ارائه دهد. ArcGIS به وسایل نقلیه بیشتری (1764 مسیر) نیاز دارد که مسافت بیشتری (62047.809 کیلومتر) را برای ارائه خدمات مشابه طی کنند. VRPEJ، که از kth نزدیکترین همسایه فضایی استفاده می کنداستراتژی، به بیشترین مسیرها (1893 مسیر) نیاز دارد که 63659.365 کیلومتر را طی کرده است. از این رو، تأیید می کند که استراتژی همسایه Voronoi مکانی-زمانی در STVDH ارائه شده بسیار بهتر از استراتژی همسایه فضایی برای جستجوی محلی برای حل VRPTW های مقیاس بزرگ است.
جدول
جدول 5. مقایسه نتایج STVDH با سایر الگوریتم های اکتشافی.

6. بحث

با در نظر گرفتن مقیاس بزرگ VRPTW و MDVRPTW در شانگهای، چین، این بخش تاثیر نمودار ورونوی مکانی-زمانی و مجاورت مکانی-زمانی پشت بهترین نتایج یافت شده را مورد بحث قرار می دهد.

6.1. تاثیر نمودار ورونوی مکانی-زمانی

برای ارزیابی تاثیر نمودار ورونوی، این مطالعه تعادل کیفیت راه حل و زمان محاسبه را با مقادیر مختلف برای پارامترها بررسی کرد. کm a xکمترآایکسو α�. همانطور که شکل 10 نشان می دهد، با توجه به همسایگان ورونوی مکانی-زمانی، افزایش در  کm a x کمترآایکسکیفیت راه حل را بهبود می بخشد اما کارایی محاسبات را کاهش می دهد زیرا همسایگان Voronoi فضایی-زمانی بیشتری در رویه های جستجوی محلی درگیر هستند. با توجه به تأثیر استراتژی فروپاشی فاصله Voronoi، همانطور که شکل 10 a نشان می دهد، هر دو سرعت واپاشی آهسته ( α�= 1) و سرعت پوسیدگی سریع ( α�= 3) نتایج بدتری ایجاد می کند. با این حال، همانطور که شکل 10 ب نشان می دهد، از آنجایی که سرعت واپاشی سریع به ارزیابی کمتری در همسایگان دور ورونوی نیاز دارد، STVDH به عنوان پارامتر، تلاش های محاسباتی کمتری را مصرف می کند. α�افزایش.
Ijgi 04 02019 g010 1024
شکل 10. تاثیر نمودار ورونوی مکانی-زمانی بر STVDH. ( الف ) انحراف به بهترین راه حل. و ( ب ) زمان محاسبه.

6.2. تجزیه و تحلیل مجاورت مکانی-زمانی بر روی بهترین نتایج یافت شده

برای درک مجاورت مکانی-زمانی پشت نتایج به‌دست‌آمده، ما تحلیلی را بر روی فاصله Voronoi بین مشتریانی که متوالی بازدید کرده‌اند در مسیر بهترین راه‌حل‌های یافت شده در بخش 5.2 انجام دادیم . شکل 11 میانگین درصد فاصله Voronoi را در بهترین راه حل های یافت شده نشان می دهد. دو ویژگی معمولی در زیر نشان داده شده است.

  • تعداد فواصل بزرگتر ورونوی تنها بخش کوچکی از بهترین نتایج یافت شده است. همانطور که شکل 11 نشان می دهد، درصد فواصل Voronoi بزرگتر از سه در راه حل های VRPTW و MDRPTW به ترتیب تنها 1.77٪ و 1.58٪ است. چنین توزیعی با تنظیم پارامتر مطابقت دارد کm a xکمترآایکس( کm a x= کمترآایکس= 3) در بخش 5.2 . بنابراین، محله مکانی-زمانی Voronoi در راه حل یافت شده بسیار معمولی است.
  • با افزایش فاصله Voronoi این درصد به شدت کاهش می یابد. برای مجموعه داده VRPTW در مقیاس بزرگ (Sh1a–Sh5a)، درصد فواصل Voronoi 1، 2، 3، و >= 4 به ترتیب 59.44، 30.13، 8.66 درصد و 1.77 درصد است که مشابه توزیع است. در راه حل MDVRPTW. این تأیید می کند که یک ساختار فشرده محلی مکانی-زمانی در مسیرهای بهترین راه حل های یافت شده وجود دارد. در مقایسه با شدت جستجوی نظری (به عنوان معادله (7) در بخش 4.2.1 که در آن کm a x= 3 ، α = 2 کمترآایکس=3، �=2) در استراتژی فروپاشی فاصله ورونوی، این درصدها به طور سیستماتیک کمی به فواصل کوچک ورونوی تغییر می کنند. این نتیجه اثربخشی استراتژی واپاشی فاصله ورونوی را نشان می‌دهد، که در جستجوی محلی بیشتر در همسایگان نزدیک جستجو می‌کند اما همچنان تلاش‌های لازم را برای همسایگان دور انجام می‌دهد.
به طور خلاصه، تجزیه و تحلیل بهترین نتایج یافت شده دلایلی را نشان می دهد که چرا نمودار Voronoi مکانی-زمانی در الگوریتم STVDH موثر است.
Ijgi 04 02019 g011 1024
شکل 11. میانگین درصد فاصله ورونوی در بهترین راه حل های یافت شده.

7. نتیجه گیری

مسیریابی وسایل نقلیه کم هزینه ترین مسیرها را برای ارضای توزیع جغرافیایی نیازهای انسان طراحی می کند. تعبیه شده در محیط GIS، نه تنها برای تصمیم گیری حمل و نقل برای بخش های دولتی و خصوصی سودمند است، بلکه ارزش اطلاعات جغرافیایی را با کمک خدمات مبتنی بر مکان، غنی می کند. این مقاله با الهام از مجاورت مکانی-زمانی، یک رویکرد اکتشافی مبتنی بر نمودار Voronoi فضایی-زمانی جدید برای حل سریع VRPTW های مقیاس بزرگ ارائه می دهد. محله مکانی-زمانی مشتق شده Voronoi نزدیکی را با توجه به مسائل مکانی و زمانی اندازه گیری می کند. همسایگان Voronoi استفاده شده فضای جستجو را در الگوریتم ساخت و ساز، جستجوی محلی، و جستجوی هدایت شده با ویژگی مکانی-زمانی محدود می کند. علاوه بر این،
آزمایش‌ها بر روی معیارهای VRPTW و نمونه‌های VRPTW در مقیاس بزرگ در شانگهای، چین با 2000 تا 10000 مشتری، عملکرد خوبی را در مشکلات VRPTW و MDVRPTW در اندازه‌های مختلف نشان داده‌اند. نتایج به‌دست‌آمده نشان می‌دهد که STVDH ارائه‌شده در این مطالعه می‌تواند راه‌حل‌هایی با کیفیت بالا برای VRPTW‌های مقیاس بزرگ در یک زمان معقول با کمک نمودار Voronoi مکانی-زمانی ارائه دهد. همچنین تأیید می کند که مجاورت مکانی-زمانی در بهترین راه حل های یافت شده بسیار معمول است زیرا 98٪ از بخش ها فاصله Voronoi کمتر از سه داشتند.
سهم اصلی این مقاله دوگانه است. ابتدا، با در نظر گرفتن هر دو پنجره زمانی و مکان‌های مکانی، نمودار Voronoi مکانی-زمانی برای تسریع فرآیند حل برای VROs پیشنهاد شده‌است. برخلاف راهبردهای افزایش سرعت مبتنی بر مجاورت فضایی [ 25 , 26 , 27]، از همسایه Voronoi مکانی-زمانی برای کاهش بیشتر تلاش محاسباتی برای اکتشافات مبتنی بر جستجوی محلی استفاده می‌کند. ایده پشت رویکرد ارائه شده که از اصول فضایی برای تسریع فرآیندهای بهینه سازی پیچیده استفاده می کند، می تواند برای تسهیل سایر مشکلات تصمیم گیری مرتبط با فضا مانند پاسخ اضطراری در زمان واقعی و مکان یابی تسهیلات در مقیاس بزرگ گسترش یابد. دوم، یک اکتشافی مبتنی بر نمودار Voronoi فضایی-زمانی برای حل VRPTWهای مقیاس بزرگ توسعه داده شد. این رویکرد جدید عملکرد خوبی را در VRPTWهای فوق‌العاده بزرگ تا 10000 مشتری نشان می‌دهد که می‌تواند با چالش‌های بسیاری از برنامه‌های پیچیده حمل‌ونقل و لجستیک در دنیای واقعی مقابله کند.
در میان پیشرفت‌های آتی که قصد انجام آن را داریم، قصد داریم رویکرد ارائه‌شده را با موقعیت‌یابی همه جا در فضای باز/داخلی و فناوری‌های ناوبری دوستانه برای وسایل نقلیه با GIS ابری ادغام کنیم. رویکرد موثر ارائه شده برای ارتقاء ماژول تحلیلگر شبکه در SDSS ها برای ارائه خدمات حمل و نقل انعطاف پذیرتر برای فعالیت های لجستیک و توزیع روزانه در مقیاس بزرگ استفاده خواهد شد. این امر هوش فضایی کاربردهای حمل و نقل و لجستیک مدرن را بیشتر افزایش می دهد.

منابع

  1. میلر، اچ جی; Shaw, SL سیستم های اطلاعات جغرافیایی برای حمل و نقل: اصول و کاربردها ; انتشارات دانشگاه آکسفورد: آکسفورد، انگلستان، 2001. [ Google Scholar ]
  2. لی، ای. Oduor، P. استفاده از عوامل تصمیم چند ویژگی برای یک تخصیص ترافیک اصلاح شده همه یا هیچ. ISPRS Int. J. Geo-Inf. 2015 ، 4 ، 883-899. [ Google Scholar ] [ CrossRef ]
  3. هوانگ، ز. لیو، ایکس. یک رویکرد سلسله مراتبی برای بهینه سازی توزیع ایستگاه اتوبوس در شهرهای بزرگ و سریع در حال توسعه. ISPRS Int. J. Geo-Inf. 2014 ، 3 ، 554-564. [ Google Scholar ] [ CrossRef ]
  4. Schittekat، P. کینبل، جی. سورنسن، ک. سووکس، ام. اسپیکسما، اف. Springael, J. فراابتکاری برای مسئله مسیریابی اتوبوس مدرسه با انتخاب ایستگاه اتوبوس. یورو جی. اوپر. Res. 2013 ، 229 ، 518-528. [ Google Scholar ] [ CrossRef ]
  5. مندوزا، جی. مداگلیا، آل. Velasco، N. یک سیستم پشتیبانی تصمیم گیری مبتنی بر تکامل برای مسیریابی خودرو: مورد یک ابزار عمومی. تصمیم می گیرد. حمایت کردن. سیستم 2009 ، 46 ، 730-742. [ Google Scholar ] [ CrossRef ]
  6. آریباس، کالیفرنیا؛ بلازکز، کالیفرنیا؛ Lamas, A. سیستم جمع آوری زباله های جامد شهری با استفاده از مدل سازی ریاضی و ابزار سیستم های اطلاعات جغرافیایی. هدر. مدیریت کنید. Res. 2010 ، 28 ، 355-363. [ Google Scholar ] [ CrossRef ] [ PubMed ]
  7. وایگل، دی. کائو، ب. بکارگیری تکنیک‌های GIS و OR برای حل مشکلات تکنسین- اعزام و تحویل در خانه. رابط ها 1999 ، 29 ، 112-130. [ Google Scholar ] [ CrossRef ]
  8. کو، پی.-ف. لرد، دی. والدن، TD استفاده از سیستم های اطلاعات جغرافیایی برای سازماندهی مسیرهای گشت پلیس به طور موثر با گروه بندی نقاط داغ داده های تصادف و جرم. J. Transp. Geogr. 2013 ، 30 ، 138-148. [ Google Scholar ] [ CrossRef ]
  9. یانسنز، جی. ون دن برگ، جی. سورنسن، ک. Cattrysse، D. مسیریابی وسایل نقلیه مبتنی بر ریزمنطقه چند هدفه برای شرکت های پیک: از برنامه ریزی تاکتیکی تا عملیاتی. یورو جی. اوپر. Res. 2015 ، 242 ، 222-231. [ Google Scholar ] [ CrossRef ]
  10. سیستم های اطلاعات جغرافیایی تیل، JC برای حمل و نقل در چشم انداز. ترانسپ Res. سی امر. 2000 ، 8 ، 3-12. [ Google Scholar ] [ CrossRef ]
  11. Antikainen، H. استفاده از الگوریتم مسیریابی سلسله مراتبی A* در GIS برای یافتن مسیرهایی از طریق رسترها با هزینه پیمایش غیریکنواخت. ISPRS. بین المللی J. Geo.-Inf. 2013 ، 2 ، 996-1014. [ Google Scholar ] [ CrossRef ]
  12. وانهاو، اس. Fack، V. یک اکتشافی موثر برای محاسبه بسیاری از جایگزین‌های کوتاه‌ترین مسیر در شبکه‌های جاده‌ای. بین المللی جی. جئوگر. Inf. علمی 2012 ، 23 ، 1031-1050. [ Google Scholar ] [ CrossRef ]
  13. لی، آر. لئونگ، ی. هوانگ، بی. لین، اچ. یک الگوریتم ژنتیک برای برنامه ریزی مسیر کالاهای خطرناک چندهدفه. بین المللی جی. جئوگر. Inf. علمی 2012 ، 27 ، 1073-1089. [ Google Scholar ] [ CrossRef ]
  14. کرتین، KM; وویکو، جی. برنج، MT; استفانیدیس، A. تحلیل مقایسه ای راه حل های فروشنده دوره گرد از سیستم های اطلاعات جغرافیایی. ترانس. GIS. 2014 ، 18 ، 286-301. [ Google Scholar ] [ CrossRef ]
  15. الگوریتم‌های سولومون، MM برای مشکلات مسیریابی و زمان‌بندی خودرو با محدودیت‌های پنجره زمانی. اپراتور Res. 1987 ، 35 ، 254-265. [ Google Scholar ] [ CrossRef ]
  16. برایسی، او. Gendreau، M. مشکل مسیریابی خودرو با پنجره‌های زمانی، بخش اول: ساخت مسیر و الگوریتم‌های جستجوی محلی. ترانسپ علمی 2005 ، 39 ، 104-118. [ Google Scholar ] [ CrossRef ]
  17. بریسی، او. Gendreau، M. مشکل مسیریابی وسیله نقلیه با پنجره های زمانی، بخش دوم: فراابتکاری. ترانسپ علمی 2005 ، 39 ، 119-139. [ Google Scholar ] [ CrossRef ]
  18. چی، م. لین، W.-H. لی، ن. Miao, L. یک رویکرد پارتیشن بندی فضایی و زمانی برای مشکلات مسیریابی وسایل نقلیه در مقیاس بزرگ با پنجره های زمانی. ترانسپ Res. E-Log. 2012 ، 48 ، 248-257. [ Google Scholar ] [ CrossRef ]
  19. Ray, JJ یک سیستم پشتیبانی تصمیم گیری فضایی مبتنی بر وب، مسیرها را برای وسایل نقلیه بزرگ و دارای اضافه وزن در دلاور بهینه می کند. تصمیم می گیرد. حمایت کردن. سیستم 2007 ، 43 ، 1171-1185. [ Google Scholar ] [ CrossRef ]
  20. هوانگ، بی. Cheu، RL; Liew، YS GIS و الگوریتم های ژنتیک برای برنامه ریزی مسیر hazmat با ملاحظات امنیتی. بین المللی جی. جئوگر. Inf. علمی 2004 ، 18 ، 769-787. [ Google Scholar ] [ CrossRef ]
  21. هوانگ، بی. فری، پ. شو، ال. وانگ، ی. جستجوی جبهه پارتو برای مسائل بهینه سازی فضایی چندهدفه. بین المللی جی. جئوگر. Inf. علمی 2008 ، 22 ، 507-526. [ Google Scholar ] [ CrossRef ]
  22. رایت، دی جی؛ وانگ، اس. ظهور زیرساخت سایبری فضایی. P. Natl. آکادمی علمی 2011 ، 108 ، 5488-5491. [ Google Scholar ] [ CrossRef ] [ PubMed ][ نسخه سبز ]
  23. تانگ، دی. موری، AT بهینه سازی فضایی در جغرافیا. ان عامر Geogr. 2012 ، 102 ، 1290-1309. [ Google Scholar ] [ CrossRef ]
  24. لی، ایکس. او، جی. لیو، ایکس. هوش مورچه برای حل مسائل بهینه پوشش مسیر با چند هدف. بین المللی جی. جئوگر. Inf. علمی 2009 ، 23 ، 839-857. [ Google Scholar ] [ CrossRef ]
  25. توث، پی. ویگو، دی. جستجوی ریز تابو و کاربرد آن در مسئله مسیریابی وسیله نقلیه. Inf. جی. کامپیوتر. 2003 ، 15 ، 333-346. [ Google Scholar ] [ CrossRef ]
  26. لی، اف. گلدن، بی. Wasil، E. مسیریابی وسایل نقلیه در مقیاس بسیار بزرگ: مشکلات آزمایشی، الگوریتم‌ها و نتایج جدید. محاسبه کنید. اپراتور Res. 2005 ، 32 ، 1165-1179. [ Google Scholar ] [ CrossRef ]
  27. نیش، ز. تو، دبلیو. لی، کیو. شاو، اس.-ال. چن، اس. چن، توسط یک جستجوی اکتشافی مبتنی بر محله Voronoi برای مسافت/ظرفیت، مشکلات مسیریابی وسیله نقلیه بسیار بزرگ را محدود کرد. بین المللی جی. جئوگر. Inf. علمی 2013 ، 27 ، 741-764. [ Google Scholar ] [ CrossRef ]
  28. تو، دبلیو. نیش، ز. لی، Q. تجزیه و تحلیل تجربی همسایگی Voronoi از راه حل های اکتشافی برای مشکلات مسیریابی خودرو. در مجموعه مقالات سمپوزیوم بین المللی 2013 در مورد پیشرفت های اخیر در مدل سازی حمل و نقل، گلدکوست، استرالیا، 21-23 آوریل 2013.
  29. اوکابه، ا. چکمه، بی. سوگیهارا، ک. Chiu, SN Spatial Tessellations: Concepts and Applications of Voronoi Diagrams ; جان وایلی و پسران: هوبوکن، نیوجرسی، ایالات متحده آمریکا، 2000. [ Google Scholar ]
  30. چن، جی. ژائو، آر. روابط همسایه k-order مبتنی بر Li، Z. Voronoi برای تحلیل فضایی. ISPRS. J. Photogram. Remote Sens. 2004 ، 59 ، 60-72. [ Google Scholar ] [ CrossRef ]
  31. ژائو، آر. چن، جی. Li، Z. همسایگان فضایی مرتبه K بر اساس نمودار ورونوی: توضیحات، محاسبات و کاربردها. بین المللی قوس فتوگرام. حسگر از راه دور اسپات. Inf. علمی 2002 ، 34 ، 10-15. [ Google Scholar ]
  32. تو، دبلیو. لی، کیو. Fang, Z. بهینه‌سازی مسیریابی لجستیک چند انباری در مقیاس بزرگ بر اساس نمودار Voronoi شبکه. Acta Geod. et Cartogr. گناه 2014 ، 43 ، 1075-1082. [ Google Scholar ]
  33. لاپورت، جی. پنجاه سال مسیریابی وسایل نقلیه. ترانسپ علمی 2009 ، 43 ، 408-416. [ Google Scholar ] [ CrossRef ]
  34. بانوس، آر. اورتگا، جی. گیل، سی. فرناندز، آ. de Toro، F. یک رویکرد چند هدفه موازی مبتنی بر بازپخت شبیه سازی شده برای مشکلات مسیریابی خودرو با پنجره های زمانی. کارشناس. سیستم Appl. 2013 ، 40 ، 1696-1707. [ Google Scholar ] [ CrossRef ]
  35. علاباس-اوسلو، سی. Dengiz، B. یک الگوریتم جستجوی محلی خود تطبیقی ​​برای مسئله مسیریابی خودرو کلاسیک. کارشناس. سیستم Appl. 2011 ، 38 ، 8990-8998. [ Google Scholar ] [ CrossRef ]
  36. روپکه، اس. Pisinger، D. اکتشافی جستجوی محله بزرگ تطبیقی ​​برای مشکل تحویل و تحویل با پنجره های زمانی. ترانسپ علمی 2006 ، 40 ، 455-472. [ Google Scholar ] [ CrossRef ]
  37. پولاک، ام. بنکنر، اس. Doerner، KF; Hartl, RF یک جستجوی همسایگی متغیر تعاونی و تطبیقی ​​برای مشکل مسیریابی وسیله نقلیه چند انبار با پنجره های زمانی. Bur-Business Res. 2008 ، 1 ، 207-218. [ Google Scholar ] [ CrossRef ]
  38. کوردو، جی اف. لاپورت، جی. Mercier، A. یک اکتشافی جستجوی یکپارچه تابو برای مشکلات مسیریابی خودرو با پنجره های زمانی. جی. اوپر. Res. Soc. 2001 ، 52 ، 928-936. [ Google Scholar ] [ CrossRef ]
  39. Repoussis، PP; تارانتیلیس، سی دی; Ioannou، G. الگوریتم تکاملی هدایت‌شده با قوس برای مسئله مسیریابی وسیله نقلیه با پنجره‌های زمانی. IEEE. ترانس. تکامل. محاسبه کنید. 2009 ، 13 ، 624-647. [ Google Scholar ] [ CrossRef ]
  40. ویدال، تی. کرینیک، TG; جندرو، م. Prins، C. یک الگوریتم ژنتیک ترکیبی با مدیریت تنوع تطبیقی ​​برای کلاس بزرگی از مشکلات مسیریابی خودرو با پنجره‌های زمانی. محاسبه کنید. اپراتور Res. 2012 ، 40 ، 475-489. [ Google Scholar ] [ CrossRef ]
  41. مستر، دی. Bräysy، O. استراتژی‌های تکامل هدایت‌شده فعال برای مشکلات مسیریابی وسایل نقلیه در مقیاس بزرگ با پنجره‌های زمانی. محاسبه کنید. اپراتور Res. 2005 ، 32 ، 1593-1614. [ Google Scholar ] [ CrossRef ]
  42. گرینگ، اچ. Homberger, J. موازی سازی یک فراابتکاری دو فازی برای مسیریابی مسائل با پنجره های زمانی. J. اکتشافی. 2002 ، 8 ، 251-276. [ Google Scholar ] [ CrossRef ]
  43. ایباراکی، تی. ایماهوری، س. کوبو، م. ماسودا، تی. یونو، تی. Yagiura، M. الگوریتم‌های جستجوی محلی مؤثر برای مشکلات مسیریابی و زمان‌بندی با محدودیت‌های پنجره زمانی کلی. ترانسپ علمی 2005 ، 39 ، 206-232. [ Google Scholar ] [ CrossRef ]
  44. ناگاتا، ی. برایسی، او. Dullaert، W. الگوریتم ممتیک مونتاژ لبه بر اساس جریمه برای مسئله مسیریابی وسیله نقلیه با پنجره های زمانی. محاسبه کنید. اپراتور Res. 2010 ، 37 ، 724-737. [ Google Scholar ] [ CrossRef ]
  45. دوندو، آر. Cerdá, J. یک رویکرد بهینه‌سازی مبتنی بر خوشه برای مشکل مسیریابی ناوگان ناوگان چند انباره ناهمگن با پنجره‌های زمانی. یورو جی. اوپر. Res. 2007 ، 176 ، 1478-1507. [ Google Scholar ] [ CrossRef ]
  46. Milthers، NPM حل VRP با استفاده از نمودارهای Voronoi و جستجوی همسایگی بزرگ تطبیقی. پایان نامه کارشناسی ارشد، دانشگاه کپنهاگ، کپنهاگ، دانمارک، 2009. [ Google Scholar ]
  47. سانتوس، ال. کوتینیو-رودریگز، جی. Antunes، CH یک سیستم پشتیبانی تصمیم فضایی وب برای مسیریابی وسایل نقلیه با استفاده از نقشه های گوگل. تصمیم گیری حمایت کردن. سیستم 2011 ، 51 ، 1-9. [ Google Scholar ] [ CrossRef ]
  48. تو، دبلیو. لی، کیو. چانگ، ایکس. یو، ی. ژو، جی. چارچوب پشتیبانی تصمیم مکانی-زمانی برای توزیع لجستیک در مقیاس بزرگ در منطقه شهری. در پیشرفت در مدیریت و تجزیه و تحلیل داده های مکانی ؛ Harvey, F., Leung, Y., Eds. Springer: برلین، آلمان، 2015; صص 193-206. [ Google Scholar ]
  49. تو، دبلیو. نیش، ز. لی، کیو. شاو، اس.-ال. Chen، BY یک نمودار اکتشافی دو سطحی Voronoi برای مشکل مسیریابی وسایل نقلیه چند انباری در مقیاس بزرگ با پنجره زمانی. ترانسپ Res. E-Log 2014 ، 61 ، 84-97. [ Google Scholar ] [ CrossRef ]
  50. باربر، CB; دوبکین، DP. Huhdanpaa، HT الگوریتم سریع هال برای بدنه های محدب. ACM. تی. ریاضی. نرم افزار 1996 ، 22 ، 469-483. [ Google Scholar ] [ CrossRef ]
  51. Zachariadis, EE; کیرانودیس، CT یک استراتژی برای کاهش پیچیدگی محاسباتی روش‌های مبتنی بر جستجوی محلی برای مشکل مسیریابی خودرو. محاسبه کنید. اپراتور Res. 2010 ، 37 ، 2089-2105. [ Google Scholar ] [ CrossRef ]
  52. Dongarra, J. عملکرد کامپیوترهای مختلف با استفاده از نرم افزار معادلات خطی استاندارد. در دسترس آنلاین: http://www.netlib.org/benchmark/performance.ps (در 30 اوت 2015 قابل دسترسی است).
  53. گرینگ، اچ. Homberger, J. یک فراابتکاری تکاملی ترکیبی موازی برای مشکل مسیریابی وسیله نقلیه با پنجره های زمانی. در مجموعه مقالات EUROGEN99، Jyväskylä، فنلاند، 30 مه تا 3 ژوئن 1999. صص 57-64.
  54. معیارهای VRPTW GEHRING و HOMBERGER. در دسترس آنلاین: http://www.bernabe.dorronsoro.es/vrp/ (دسترسی در 10 اکتبر 2015).
  55. مجموعه داده های مشکل VRPTW و MDVRPTW در مقیاس بزرگ در شانگهای، چین. در دسترس آنلاین: https://github.com/spatialsmart/VRPTW/tree/master/Shanghai/Problem (دسترسی در 10 اکتبر 2015).
  56. کوی، اس. گلدن، بی. رانگر، جی. Wasil، E. استفاده از طراحی تجربی برای یافتن تنظیمات پارامتر موثر برای اکتشاف. J. اکتشافی. 2001 ، 7 ، 77-97. [ Google Scholar ] [ CrossRef ]
  57. گرویر، سی. گلدن، بی. Wasil، E. کتابخانه ای از اکتشافات جستجوی محلی برای مشکل مسیریابی خودرو. ریاضی. برنامه. محاسبه کنید. 2011 ، 2 ، 79-101. [ Google Scholar ] [ CrossRef ]

;کاربردهای GISمقالات

آموزش کاربردی ArcGISالهام ابراهیم زادهکاربرد جی ای اسکاربرد جی ای اس در زمین شناسی

بدون نظر

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

همواره حمایت دانشجویان عزیزمان همراه ما بوده و این سببب شده که گامی محکم به‌سوی ایجاد یک مرجع برای آموزش GIS برداریم. با این امید که بتوانیم قدردان حمایت شما بزرگواران باشیم.

  • خانه
  • آموزش
  • فیلم آموزشی
  • تماس با ما
  • درباره ما
  • وبلاگ
  • سمنان /خیابان کاشانی/ساختمان فناوری اطلاعات/پ 8
  • 09120049370