مدل مسیریابی خدمات تغذیه‌کننده‌های شبه همگانی با استفاده از خودروهای خودران در معابر شهری

نوع مقاله : مقاله پژوهشی

نویسندگان

1 استاد، گروه حمل‌ونقل، دانشکده مهندسی عمران، دانشگاه علم و صنعت ایران، تهران، ایران

2 دانشجوی کارشناسی ارشد، دانشکده مهندسی عمران، دانشگاه علم و صنعت ایران، تهران، ایران

3 دانشجوی دکتری، دانشکده مهندسی عمران، دانشگاه علم و صنعت ایران، تهران، ایران

چکیده

اگر از خودروهای خودران در طرح خدمات تماس - سفر استفاده شود، محدودیت‌های مربوط به وجود راننده، مانند محدودیت زمانی رانندگی، از بین می‌روند. مسئله مسیریابی تماس – سفر مطالعه حاضر به دنبال ارائه برنامه‌ریزی مسیریابی ناوگانی از وسایل نقلیه خودران الکتریکی است، که به گروهی از درخواست‌های سفر خدمت‌رسانی می‌کنند. هدف از مسئله تعریف شده، بهینه‌سازی تعداد ناوگان برای خدمت‌رسانی، کمینه کردن هزینه‌های مسیرهای خودروها و ناراحتی مسافران است. مسئله حاضر علاوه بر محدودیت‌های راحتی سفر کاربران، با چالش‌هایی از جمله مدیریت باتری و انحراف مسیر خودرو‌ها به ایستگاه‌های شارژ نیز مواجه است. در پژوهش حاضر ابتدا یک مدل ریاضی چند هدفه مقید متناسب با مسئله مسیریابی مورد نظر بررسی می‌گردد، سپس یک روش حل دو مرحله‌ای مبتنی بر الگوریتم فرا ابتکاری ژنتیک ارائه می‌گردد. ساختار الگوریتم ژنتیک به گونه‌ای معرفی می‌گردد که تعیین تعداد ناوگان و تخصیص مسافران به خودروها را شامل شود. برای حل مسئله و تحلیل نتایج بدست آمده با روش حل پیشنهادی، نمونه داده‌های جدیدی، از طریق پردازش داده‌های خام شرکت اوبر در شهر سانفرانسیسکو آمریکا، ایجاد گردید. نتایج نشان می‌دهند که روش حل پیشنهادی قادر به بدست آوردن جواب‌های با کیفیت در زمانی قابل مقایسه با روش حل دقیق شاخه و برشِ مطالعه پیشین می‌باشد. همچنین نتایج حل مسئله برای نمونه داده‌های جدید نشان می‌دهد که همواره استفاده از حداقل تعداد ناوگان منجر به جواب‌های برتر و بهینه نمی‌شود. به علاوه نتایج حاکی از آن است که مقصد یکسانِ برخی مسافران در هنگام فعالیت خدمات تغذیه‌کننده، باعث افزایش میزان همسواری می‌گردد.

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

Optimal Routing for Shared Autonomous Vehicles Feeder Services in Urban Networks

نویسندگان [English]

  • Shahriar Afandizadeh 1
  • Dorsa Aziz Jalali 2
  • Hamid Bigdeli Rad 3
1 Professor, School of Civil Engineering, Iran University of Science and Technology, Tehran, Iran.
2 M.Sc. Student., School of Civil Engineering, Iran University of Science and Technology, Tehran, Iran.
3 Ph. D. Student, School of Civil Engineering, Iran University of Science and Technology, Tehran, Iran.
چکیده [English]

The Complexities of Operating DAR Services Mean That Computerized Planning and Scheduling Is Necessary for Systems of Realistic Size. This Research Studies an Electric Autonomous Fleet Size with Mix Dial-A-Ride Problem. The Goal of The Problem Is to Minimize a Weighted Objective Function Consisting of The Total Travelling Costs of All Vehicles, Users' Excess Ride Time Costs and Vehicles' Acquisition Costs While Satisfying Customer Service Level Constraints Along with Battery Level Management and Recharge Times Management Constraints. In This Variant of The Dial-A-Ride Problem, Recharging at Any of The Available Charging Stations Is Allowed. A Cluster-First, Route-Second Genetic Algorithm Is Proposed to Solve the Problem, Where the Clustering Is Performed by Choosing the Fleet Size and Assigning the Customers to The Fleet Using a Genetic Algorithm (GA), Then the Primary Routes Are Developed by A Routing Heuristic, Finally the Charging Stations Will Be Inserted to The Algorithm Using an Insertion Technique. The Performance of The Proposed Method Is Tested by Using Benchmark Instances of a Related Problem from The Recent Literature. The Proposed Method Has Achieved Solutions Comparable with The Current State-Of-Art Methods. The Computational Results Show That the Proposed Method Is Effective in Finding Comparable Solutions with The Current State-Of-Art Method. New Instances, Some of Which Include First-Mile Feeder Services, Are Generated Based on The Data from Uber Technologies Inc. Tests Performed on New Instances Demonstrate That the Minimum Possible Fleet Size Does Not Always Result in Minimum Costs. Moreover, The Tests Show That Integration of The Feeder Services into Dial-A-Ride Services Increases Ride-Sharing Ridership.
.

کلیدواژه‌ها [English]

  • Dial-A-Ride Problem
  • Electric Autonomous Vehicles
  • Feeder Services
  • Genetic Algorithm

مراجع

-Afandizadeh, S., & Rad, H. B. (2021). Developing a model to determine the number of vehicles lane changing on freeways by Brownian motion method. Nonlinear Engineering, 10(1), 450-460.
-Afandizadeh Zargari, S., Bigdeli Rad, H., & Shaker, H. (2019). Using optimization and metaheuristic method to reduce the bus headway (Case study: Qazvin Bus Routes). Quarterly Journal of Transportation Engineering, 10(4), 833-849.
-Bongiovanni, C., Kaspi, M., & Geroliminis, N. (2019). The electric autonomous dial-a-ride problem. Transportation Research Part B: Methodological, 122, 436-456.
-Braekers, K., Caris, A., & Janssens, G. K. (2014). Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots. Transportation Research Part B: Methodological, 67, 166-186.
-Cordeau, J. F. (2006). A branch-and-cut algorithm for the dial-a-ride problem. Operations Research, 54(3), 573-586.
-Cordeau, J. F., & Laporte, G. (2003). A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B. Methodological, 37(6), 579-594.
-Cordeau, J. F., & Laporte, G. (2007). The dial-a-ride problem: models and algorithms. Annals of Operations Research, 153(1), 29-46.
-Fagnant, D. J., & Kockelman, K. (2015). Preparing a nation for autonomous vehicles: opportunities, barriers and policy recommendations. Transportation Research Part A: Policy and Practice, 77, 167-181.
-Gökay, S., Heuvels, A., & Krempels, K. H. (2019). A High-level Category Survey of Dial-a-Ride Problems. In VEHITS, 594-600.
-https://afdc.energy.gov/stations/#/find/nearest, visited in November 2021.
-https://python-visualization.github.io/folium/, visited in June 2022.
-Jorgensen, R. M., Larsen, J., & Bergvinsdottir, K. B. (2007). Solving the dial-a-ride problem using genetic algorithms. Journal of the Operational Research Society, 58(10), 1321-1331.
-Keskin, M., & Çatay, B. (2016). Partial recharge strategies for the electric vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies, 65, 111-127.
-Lin, J., Zhou, W., & Wolfson, O. (2016). Electric vehicle routing problem. Transportation research procedia, 12, 508-521.
-Masmoudi, M. A., Braekers, K., Masmoudi, M., & Dammak, A. (2017). A hybrid genetic algorithm for the heterogeneous dial-a-ride problem. Computers & operations research, 81, 1-13.
-Masmoudi, M. A., Hosny, M., Demir, E., & Pesch, E. (2020). Hybrid adaptive large neighborhood search algorithm for the mixed fleet heterogeneous dial-a-ride problem. Journal of Heuristics, 26(1), 83-118.
-Masmoudi, M. A., Hosny, M., Demir, E., Genikomsakis, K. N., & Cheikhrouhou, N. (2018). The dial-a-ride problem with electric vehicles and battery swapping stations. Transportation research part E: logistics and transportation review, 118,
392-420.
-Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2008). A survey on pickup and delivery problems. Journal für Betriebswirtschaft, 58(1), 21-51.
-Pfeiffer, C., & Schulz, A. (2022). An ALNS algorithm for the static dial-a-ride problem with ride and waiting time minimization. OR Spectrum, 44(1), 87-119.
-Ropke, S., Cordeau, J. F., & Laporte, G. (2007). Models and branch‐and‐cut algorithms for pickup and delivery problems with time windows. Networks: An International Journal, 49(4), 258-272.
-S. N. Parragh. (2011). Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem, Transp. Res. Part C Emerg. Technol., Vol. 19, No. 5, 912–930.
-Schneider, M., Stenger, A., & Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation science, 48(4), 500-520.
-Semet, F., Toth, P., & Vigo, D. (2014). Chapter 2: Classical exact algorithms for the capacitated vehicle routing problem. In Vehicle Routing: Problems, Methods, and Applications, Second Edition, 37-57. Society for Industrial and Applied Mathematics.
-Su, Y., Puchinger, J., & Dupin, N. (2021). A Deterministic Annealing Local Search for the Electric Autonomous Dial-a-Ride Problem.
-Taxicab 0.0.3 description https://pypi.org/project/Taxicab/#description, visited in November 2021.
-Tellez, O., Vercraene, S., Lehuédé, F., Péton, O., & Monteiro, T. (2018). The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity. Transportation Research Part C: Emerging Technologies, 91, 99-123.
-Uber gps data, uber-gps-analysis/gpsdata at master dima42/uber-gps-analysis· GitHub, visited in February 2021.

فایل ها

هم رسانی

ارجاع به این مقاله

آمار