An integrated optimisation framework for locating depots in shared autonomous vehicle systems

Abstract

This study presents an integrated optimisation framework for locating depots in a Shared autonomous vehicle (SAV) system under demand uncertainty. A two-stage stochastic mixed integer programming (MIP) model is formulated to optimise the number and locations of depots in a SAV system, where demand uncertainty is represented by multiple scenarios with occurrence probability. The dynamics of vehicle movements are further considered by forming a trip chain for each AV. An enhanced Benders decomposition-based algorithm with multiple Pareto-optimal cuts via multiple solutions is developed to solve the proposed model. The proposed modelling framework and the solution algorithm are tested using two different sizes of transportation networks. Computational analysis demonstrates that the proposed algorithm can handle large instances within acceptable computational cost, and be more efficient than the MIP solver. Meanwhile, insights regarding the optimal deployment of depots in SAV systems are also delivered under different parametric and demand pattern settings.

Keywords:

• Shared autonomous vehicles (SAV)
• depot location
• demand uncertainty
• mixed integer stochastic programming
• benders decomposition

Acknowledgments

The authors are grateful to Metropolitan Council for sharing the data.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 In this paper, we will use depot and parking lot interchangeably.

2 https://www.marketwatch.com/story/demand-for-driverless-cars-could-boost-uber-to-2016-09-19.

3 https://wginc.com/parking-outlook/.

Additional information

Funding

This study is partially supported by the Natural Science Foundation of Jiangsu Province in China [grant number BK20210250], National Natural Science Foundation of China [grant numbers 72201056, 7190105], National Science Foundation of United States [grant numbers CMMI-1637548, CMMI-1831140], and Minnesota Department of Transportation [grant numbers 1003325 WO 111, 1003325 WO 44].