Publication

A Two Phase Heuristic Approach For The Dynamic Electric Autonomous Dial-a-Ride Problem

Abstract

In the Dial-a-Ride-Problem (DARP) a fleet of vehicles provide shared-ride services to users specifying their origin, destination, and preferred arrival time. In the dynamic version of the DARP, some trips are booked in advance while others come in real-time. In this work, a two-phase heuristic algorithm is designed for the dynamic DARP with the use of electric autonomous vehicles (the electric Autonomous Dial-a-Ride Problem, e-ADARP). In addition to classic constraints from the DARP (i.e. time-windows, origin-destination precedence, users’ maximum ride-times, vehicles’ maximum route durations), the e-ADARP includes online battery management, decisions regarding detours to charging stations, partial vehicles’ recharging, and selection of destination depots. The two-phase heuristic approach includes an insertion stage, in which online requests are introduced in existing routes, and an improvement stage, in which local search heuristics are applied in order to re-optimize the vehicles’ plans after a number of successful insertions. An event-based simulation environment is designed to perform computational experiments on adapted benchmark instances from DARP literature and instances based on real data from Uber Technologies Inc.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.