جستجوی همسایگی وسیع با برنامه‌ریزی محدود برای یک مساله مسیریابی وسایل نقلیه با محدودیت‌های همزمانی ​

این مقاله بسط مساله مسیریابی وسایل نقلیه را با پنجره‌های زمانی در نظر می‌گیرد که در آن ورود دو خودرو در مکان‌های مختلف مشتری باید همزمان شود.یعنی این که یک وسیله نقلیه باید مقداری محصول را به یک مشتری منتقل کند، مانند یک سیستم تئاتر خانگی، در حالی که خدمه بر روی یک وسیله نقلیه دیگر باید آن را نصب کنند.این نوع مشکل اغلب در عمل دیده می‌شود و به خاطر وابستگی متقابل میان مسیرهای خودرو، بسیار چالش برانگیز است، اما در ادبیات توجه کمی را به خود جلب کرده‌است.یک جستجوی محدود مبتنی بر برنامه‌نویسی برای حل این مشکل پیشنهاد شده‌است.قابلیت‌های جستجو در جستجوی همسایگی زیاد و توانایی انتشار محدود برنامه‌نویسی محدودیت برای تعیین امکان هر گونه تغییر پیشنهادی در راه‌حل فعلی ترکیب می‌شوند.نتایج عددی بر روی نمونه‌های بدست‌آمده از نمونه‌های معیار برای مساله مسیریابی وسایل نقلیه با پنجره‌های زمانی با بیش از ۲۰۰ مشتری گزارش شده‌است. ​

This paper considers an extension of the vehicle routing problem with time windows, where the arrival of two vehicles at different customer locations must be synchronized. That is, one vehicle has to deliver some product to a customer, like a home theater system, while the crew on another vehicle must install it. This type of problem is often encountered in practice and is very challenging due to the interdependency among the vehicle routes, but has received little attention in the literature. A constraint programming-based adaptive large neighborhood search is proposed to solve this problem. The search abilities of the large neighborhood search and the constraint propagation abilities of constraint programming are combined to determine the feasibility of any proposed modification to the current solution. Numerical results are reported on instances derived from benchmark instances for the vehicle routing problem with time windows with up to 200 customers.