Vehicle Routing for Shared Autonomous Electric Vehicles Considering Passengers’ Uncertain Waiting Time Tolerance and Acceptable Stopover

Xu Ouyang, Min Xu, Ting Wu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


The ridesharing system effectively allocates limited vehicle resources by organizingpassengers with similar itineraries to share seats of the same vehicle, thereby reducingvehicle miles traveled and the number of required vehicles. Shared autonomouselectric vehicles (SAEVs), which apply autonomous electric vehicles to ridesharingsystems, have attracted rising attention from both academia and industry, thanks totheir high fleet efficiency, flexible mobility, and low energy consumption. This studyinvestigates the vehicle routing problem of SAEVs considering passengers’ uncertainwaiting time tolerance (WTT) and acceptable stopovers. Specifically, a passenger isassumed to have an uncertain WTT for vehicle pick-up delays and a pre-specifiednumber of acceptable stopovers during the entire trip. The vehicle routes of SAEVs areoptimized to serve a set of pre-known passengers so that the profit of SAEV operatorsare maximized. To solve this problem, we first develop a robust mixed-integer program(RMIP) that explicitly formulates the number of stopovers during passenger trips and allpossible realizations of passengers’ uncertain WTT. The intractable constraintsassociated with the uncertain WTT in RMIP are then addressed using robustoptimization techniques. Since the resultant model cannot be easily solved by availablesolvers, we thus further develop a formulation-based two-layer heuristic algorithm byexploiting decomposable model structures to efficiently find good-quality solutions. Acase study using real-life ridesharing data of Chengdu, China demonstrates theefficacy of the proposed model and the heuristic algorithm. We also analyze the impactof stopovers and fleet size on profits and the optimal solution and report practicalmanagerial insights.
Original languageEnglish
Title of host publicationProceedings of the 100th Annual Meeting of Transportation Research Board
Number of pages24
Publication statusPublished - Jan 2021
EventThe 100th Transportation Research Board Annual Meeting - Online, United States
Duration: 5 Jan 202129 Jan 2021


ConferenceThe 100th Transportation Research Board Annual Meeting
Country/TerritoryUnited States


  • shared autonomous electric vehicle
  • stopover
  • uncertain waiting time tolerance
  • formulation-based heuristic

Cite this