The capacitated vehicle routing problem with stochastic demands and time windows

ABSTRACT

The capacitated vehicle routing problem with stochastic demands and time windows is an extension of the capacitated vehicle routing problem with stochastic demands, in which demands are stochastic and a time window is imposed on each vertex. A vertex failure occurring when the realized demand exceeds the vehicle capacity may trigger a chain reaction of failures on the remaining vertices in the same route, as a result of time windows. This paper models this problem as a stochastic program with recourse, and proposes an adaptive large neighborhood search heuristic for its solution. Modified Solomon benchmark instances are  used in the experiments. Computational results clearly show the superiority of the proposed heuristic over an alternative solution approach.

INTRODUCTION

The problem discussed in this paper is the capacitated vehicle routing problem with stochastic demands and time windows (CVRPSDTW), an extension of capacitated vehicle routing problem with stochastic demands (CVRPSD). The CVRPSDTW is defined on an undirected graph G¼(V,E), where V¼{v0, v1,y,vn} is the vertex set and E ¼ fðvi,vjÞ : vi,vj AV,iojg is the edge set. Vertex v0 is a depot at which are based m identical vehicles of capacity Q, while the remaining vertices represent customers. A symmetric travel cost matrix C¼(c(vi, vj)) is defined on E. We assume that all vehicles travel at unit speed and that travel costs are equal to distances. A service time is incurred when visiting a vertex. Each vertex vi is associated with a nonnegative and stochastic demand xi to be collected. The stochastic demands are splittable and unknown until vehicles arrive at the vertices. As a result, failure may occur along a route if the total collected demand exceeds the vehicle capacity. The CVRPSD can be cast as a stochastic mathematical program. There exist two main solution concepts in stochastic programming: chance constrained programming (CCP) and stochastic programming with recourse (SPR). In CCP, the problem is solved by imposing a constraint ensuring that the probability of route failure is bounded by some parameter.

چکیده

مشکل رانندگی کامیون با خواسته های تصادفي و پنجره های زمان، فرمت مشکل رانندگی کامپيوتر با خواسته های تصادفي است که در آن تقاضاها به صورت تصادفی و یک پنجره زمان بر هر رأس تحمیل می شود. خرابی ریشه زمانی که تقاضای متوجه شده از ظرفیت وسیله نقلیه بیش از ظرفیت خودرو می تواند یک واکنش زنجیره ای از شکست در رأی های باقی مانده در همان مسیر، به عنوان یک نتیجه از ویندوز زمان. این مقاله این مسئله را به عنوان یک برنامه تصادفی با استفاده از آن پیشنهاد می کند و پیشنهاد می کند که راه حل سازگار با جستجوی محله بزرگ برای حل آن. نمونه های اصلاح شده سلیمان در آزمایشات استفاده می شود. نتایج محاسباتی به وضوح نشان دهنده برتر بودن اکتشافی پیشنهادی نسبت به یک راه حل جایگزین است.

مقدمه

مشکل مطرح شده در این مقاله، مساله مسیریابی مسکن با خواسته های تصادفی و پنجره های زمانی (CVRPSDTW)، گسترش یک مساله مسیریابی مسکن با خواسته های تصادفی (CVRPSD) است. CVRPSDTW بر روی یک گراف غیرقابل هدایت G¼ (V، E) تعریف شده است، جایی که V¼ {v0، v1، y، vn} مجموعه ی رأس است و E ¼ fðvi، vjÞ: vi، vj AV، iojg مجموعه ی لبه است. Vertex v0 یک انبار است که در آن وسایل نقلیه یکسان ظرفیت Q را در نظر گرفته اند، در حالی که رأی های باقی مانده نشان دهنده مشتریان است. ماتریس هزینه متقارن C¼ (c (vi، vj)) در E تعریف شده است. فرض کنیم که تمام وسایل نقلیه با سرعت واحد و هزینه های سفر برابر با فاصله هستند. هنگام بازدید از یک رأس زمان خدمت است. هر رأس vi با یک تقاضای غیرمستقیم و تصادفی xi همراه است. خواسته های تصادفی تقسیم و ناشناخته است تا زمانی که وسایل نقلیه به رأس ها برسد. در نتیجه، اگر کل تقاضای جمع آوری شده از ظرفیت وسیله نقلیه بیش از ظرفیت وسیله نقلیه باشد، در طول مسیر ممکن است رخ دهد. CVRPSD را می توان به صورت یک برنامه ریاضی تصادفی اجرا کرد. دو راه حل اصلی در برنامه نویسی تصادفی وجود دارد: برنامه ریزی محدودیت شانس (CCP) و برنامه ریزی تصادفی با استفاده از SPR. در CCP، این مسئله با تحمیل یک محدودیت حل می شود تا اطمینان حاصل شود که احتمال شکست مسیر توسط بعضی پارامتر محدود شده است.

Year: 2011

Publisher : ELSEVIER

By : Hongtao Lei , Gilbert Laporte ,c,, Bo Guo

File Information: English Language/ 9 Page / size: 782 KB

Download

سال : 1390

ناشر : ELSEVIER

کاری از : Hongtao Lei، Gilbert Laporte، c ،، Bo Guo

اطلاعات فایل : زبان انگلیسی / 9 صفحه / حجم : KB 782

لینک دانلود