کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1131619 1488955 2016 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations
ترجمه فارسی عنوان
پیدا کردن راه حل بهینه برای مسئله مسیریابی وسایل نقلیه با خدمات وانت و تحویل با پنجره زمانی: یک روش برنامه ریزی پویا بر اساس بازنمایی شبکه حالت ـ فضا ـ زمان
کلمات کلیدی
مسیریابی وسایل نقلیه با وانت و تحویل با پنجره های زمان؛ آرامش لاگرانژی؛ مشکل راه کمترین هزینه وابسته به زمان. برنامه نویسی پویا پیشرو؛
موضوعات مرتبط
علوم انسانی و اجتماعی علوم تصمیم گیری علوم مدیریت و مطالعات اجرایی
چکیده انگلیسی


• Model vehicle routing with real-world transportation networks and time-dependent link travel time.
• Develop an efficient dynamic programming algorithm based on state–space–time networks.
• Model pickup and delivery time window constraints using multi-dimensional network flow program.
• Synchronize vehicle routing and determine request pricing within Lagrangian relaxation framework.

Optimization of on-demand transportation systems and ride-sharing services involves solving a class of complex vehicle routing problems with pickup and delivery with time windows (VRPPDTW). This paper first proposes a new time-discretized multi-commodity network flow model for the VRPPDTW based on the integration of vehicles’ carrying states within space–time transportation networks, so as to allow a joint optimization of passenger-to-vehicle assignment and turn-by-turn routing in congested transportation networks. Our three-dimensional state–space–time network construct is able to comprehensively enumerate possible transportation states at any given time along vehicle space–time paths, and further allows a forward dynamic programming solution algorithm to solve the single vehicle VRPPDTW problem. By utilizing a Lagrangian relaxation approach, the primal multi-vehicle routing problem is decomposed to a sequence of single vehicle routing sub-problems, with Lagrangian multipliers for individual passengers’ requests being updated by sub-gradient-based algorithms. We further discuss a number of search space reduction strategies and test our algorithms, implemented through a specialized program in C++, on medium-scale and large-scale transportation networks, namely the Chicago sketch and Phoenix regional networks.

Figure optionsDownload as PowerPoint slide

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Transportation Research Part B: Methodological - Volume 89, July 2016, Pages 19–42
نویسندگان
, ,