Routing optimization of shared autonomous electric vehicles under uncertain travel time and uncertain service time

Li Zhang, Zhongshan Liu, Lan Yu, Ke Fang, Baozhen Yao and Bin Yu

Transportation Research Part E: Logistics and Transportation Review, 2022, vol. 157, issue C

Abstract: The emerging autonomous electric vehicles have facilitated the implementation of the shared autonomous electric vehicle (SAEV) service. In real-life applications, the operations of SAEVs may be affected by various uncertain factors, such as uncertain travel time caused by traffic congestion and uncertain service time caused by unpredictable customer delay. It is essential to consider uncertain factors to design conservative and robust routes for SAEVs. In this paper, we study a routing optimization problem of SAEVs, where the charging schedules, uncertain travel time, and uncertain service time are considered. The objective of the problem is to minimize the total operational cost that consists of fixed cost and travel cost of SAEVs. A branch-and-price algorithm is developed to solve the problem. Specifically, a tailored label setting algorithm is introduced to identify the robust feasible routes with accessible charging schedules for the pricing subproblem. The proposed algorithm is tested on a set of generated instances. The computational results indicate that the proposed algorithm outperforms the commercial solver CPLEX in terms of both solution quality and computational time. Besides, based on the sensitivity analyses, we show the impact of the budgets of uncertainty, maximum deviations of uncertain parameters, battery capacity, fixed cost, and charging speed on the SAEV service. This work can also provide inspirations of both models and algorithms for many other application areas, such as urban logistics.

Keywords: Shared autonomous electric vehicles; Routing optimization; Charging schedules; Travel time uncertainty; Service time uncertainty; Branch-and-price algorithm (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554521003069
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:157:y:2022:i:c:s1366554521003069

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2021.102548

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().