Publication

A predictive large neighborhood search for the dynamic electric autonomous dial-a-ride problem

Abstract

The dynamic electric autonomous Dial-a-Ride Problem (e-ADARP) is a generalization ofthe dial-a-ride problem which employs electric Autonomous Vehicles (e-AVs) to provide sharedrides to on-line requests. The goal of the dynamic e-ADARP is to maximize the number of servedrequests while minimizing operational cost and user excess ride time. To reach this goal, meta-heuristics are designed to modify vehicle-trip assignments as information reveals over time. Dif-ferently from human-driven vehicles, e-AVs can be re-routed as often as desired in the courseof operations. Given the on-line nature of the problem, plan modifications need to be efficientlyperformed to timely notify users and provide new instructions to the vehicles.In this work, we present a new extension to the family of Large Neighborhood Search(LNS) metaheuristics, which employs a machine learning component to select destroy/repair cou-ples from a pool of competing algorithms. At each iteration, the machine learning componentpredicts the objective function improvement that is expected to be obtained after the employmentof each of the competing algorithms. The destroy/repair couple is consequently drawn accord-ing to the expected improvement proportions. Worsening solutions are also considered and drawnwith the same likelihood of descent solutions. The proposed metaheuristic is denoted by Predic-tive Large Neighborhood Search (PLNS) and is employed to efficiently solve dynamic e-ADARPinstances. Computational results are performed on 244 100-request dynamic instances from UberTechnologies Inc. Results show that PLNS outperforms the state-of-the art in the context of on-line operations.

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.
Related concepts (18)
Human-powered transport
Human-powered transport is the transport of person(s) and/or goods using human muscle power. Unlike animal-powered transport, human-powered transport has existed since time immemorial in the form of walking, running and swimming. Modern technology has allowed machines to enhance human-power. Although motorization has increased speed and load capacity, many forms of human-powered transport remain popular for reasons of cost, convenience, leisure, physical exercise, and environmentalism.
Hybrid vehicle
A hybrid vehicle is one that uses two or more distinct types of power, such as submarines that use diesel when surfaced and batteries when submerged. Other means to store energy include pressurized fluid in hydraulic hybrids. Hybrid powertrains are designed to switch from one power source to another to maximize both fuel efficiency and energy efficiency. In hybrid electric vehicles, for instance, the electric motor is more efficient at producing torque, or turning power, while the combustion engine is better for maintaining high speed.
Vehicular automation
Vehicular automation involves the use of mechatronics, artificial intelligence, and multi-agent systems to assist the operator of a vehicle (car, aircraft, watercraft, or otherwise). These features and the vehicles employing them may be labeled as intelligent or smart. A vehicle using automation for difficult tasks, especially navigation, to ease but not entirely replace human input, may be referred to as semi-autonomous, whereas a vehicle relying solely on automation is called robotic or autonomous.
Show more
Related publications (32)

Haptics based collaborative steering control in automated driving environments

Tomohiro Nakade

A vehicle's steering is a particular system in that it is exposed to individual subjective reviews based on criteria that are hard to assess quantitatively. Haptic design of such systems is a prime concern that has been at the center of industrial developm ...
EPFL2023

Resource aware pricing for electric vehicle charging

Nils Gustav Nilsson

Electric vehicle charging facilities offer their capacity constrained electric charge and parking to users for a fee. As electric vehicle adoption grows, so too does the potential for excessive resource utilization. In this paper, we study how prices set b ...
PERGAMON-ELSEVIER SCIENCE LTD2023

Potential of electric mobility as service to the grid in renewable energy hubs

François Maréchal, Cédric Terrier, Luise Middelhauve

The electrification of private mobility is becoming a popular solution to reduce the reliance on fossil fuels. However, uncontrollable charging of a large electric vehicle fleet challenges the distribution grid due to transmission bottlenecks, voltage limi ...
2022
Show more
Related MOOCs (6)
Optimization: principles and algorithms - Linear optimization
Introduction to linear optimization, duality and the simplex algorithm.
Optimization: principles and algorithms - Linear optimization
Introduction to linear optimization, duality and the simplex algorithm.
Optimization: principles and algorithms - Network and discrete optimization
Introduction to network optimization and discrete optimization
Show more

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.