Optimal Routing for Shared Autonomous Vehicles Feeder Services in Urban Networks

Document Type : Original Article

Authors

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.

Abstract

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.
.

Keywords

Main Subjects

References

-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.

Files

Share

How to cite

Statistics