الگوریتم شاخه و برش برای مساله مسیریابی با بارگیری و تحویل همزمان

قیمت: 40,000 تومان

دانلود رایگان مقاله

خرید ترجمه مقاله

عنوان فارسی

الگوریتم شاخه و برش برای مساله مسیریابی با بارگیری و تحویل همزمان

عنوان لاتین

A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery

این مقاله، به مساله مسیریابی با بارگیری و تحویل همزمان(LRPSPD) می پردازد که حالتی کلی از مساله مسیریابی می باشد.LRPSPD به عنوان مسیریابی انبارها و طراحی مسیرهای خودرو به صورتی که تقاضای هر مشتری برای بارگیری و تحویل با یک خودرو انجام شود و هزینه های کلی به حداقل برسد، تعریف شده است. ما یک الگوریتم شاخه و برش موثر را برای حل LRPSPD پیشنهاد کردیم. الگوریتم پیشنهادی، چند نامعادله معتبر گرفته شده از مقالات را برای مساله اجرا می کند و جستجوی محلی را بر اساس الگوریتم تبرید شبیه‌ سازی شده انجام می دهد تا کران های بالا را به دست آورد. نتایج محاسباتی، برای تعداد زیادی از مثال های گرفته شده از مقالات، نشان می دهد که برخی از موارد با 88 مشتری و 8 انبار بالقوه را می توان در یک زمان محاسبه منطقی حل کرد.

This paper addresses a location-routing problem with simultaneous pickup and delivery (LRPSPD) which is a general case of the location-routing problem. The LRPSPD is defined as finding locations of the depots and designing vehicle routes in such a way that pickup and delivery demands of each customer must be performed with same vehicle and the overall cost is minimized. We propose an effective branch-and-cut algorithm for solving the LRPSPD. The proposed algorithm implements several valid inequalities adapted from the literature for the problem and a local search based on simulated annealing algorithm to obtain upper bounds. Computational results, for a large number of instances derived from the literature, show that some instances with up to 88 customers and 8 potential depots can be solved in a reasonable computation time