The electric autonomous dial-a-ride problem

Claudia Bongiovanni, Mor Kaspi and Nikolas Geroliminis

Transportation Research Part B: Methodological, 2019, vol. 122, issue C, 436-456

Abstract: In the Dial-a-Ride-Problem (DARP) a fleet of vehicles provides shared-ride services to users specifying their origin, destination, and preferred arrival time. Typically, the problem consists of finding minimum cost routes, satisfying operational constraints such as time-windows, origin-destination precedences, user maximum ride-times, and vehicle maximum route-durations. This paper presents a problem variant for the DARP which considers the use of electric autonomous vehicles (e-ADARP). The problem covers battery management, detours to charging stations, recharge times, and selection of destination depots, along with classic DARP features. The goal of the problem is to minimize a weighted objective function consisting of the total travel time of all vehicles and excess ride-time of the users. We formulate the problem as a 3-index and a 2-index mixed-integer-linear program and devise a branch-and-cut algorithm with new valid inequalities derived from e-ADARP properties. Computational experiments are performed on adapted benchmark instances from DARP literature and on instances based on real data from Uber Technologies Inc. Instances with up to 5 vehicles and 40 requests are solved to optimality.

Keywords: Dial-a-Ride problem; Branch-and-cut; Electric autonomous vehicles (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (24)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261517309669
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:transb:v:122:y:2019:i:c:p:436-456

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2019.03.004

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().