Internship Subject
2891 - Machine-learning-based method to solve dynamic dial-a-ride problem
Recently, the integration between machine learning and operations research has been a novel trend to tackle problems with stochasticity. For example, Baty et al., (2024) tackle the dynamic vehicle routing problem (VRP) with real-time customer requests. The task involved a rapid delivery service using capacitated vehicles to serve customer requests originating from a depot. Each request had to be served within a specified time window. Requests arrived dynamically, and vehicles were dispatched in waves to serve them. At each wave's decision time $t$, the system state $X_t$ consists of the set of requests that have not yet been served. The decision $Y_t$ involves selecting the subset of requests to be served by the vehicles dispatched at time $t$, as well as the corresponding routing plan. The objective is to find a policy $h$ that minimizes the expected total routing cost. The authors proposed hybrid machine learning pipelines to tackle the problem, which includes two layers: a graph neuro network (GNN) to predict the ``prize" of serving each request in the graph and a combinatorial optimization layer to solve a price-collection capacitated vehicle routing problem at each decision epoch $t$ to produce the routing solution with the predicted prizes. Another important stream is to integrate Large Language models (LLMs) into optimization, where the optimization task is described in natural language. In each optimization step, the LLM generates new solutions from the prompt that
contains previously generated solutions with their values, then the new solutions are
evaluated and added to the prompt for the next optimization step. This idea has been demonstrated efficient in solving traveling salesman problems (TSP) (Yang et al.,(2023)).
The objective of the internship is to implement combinatorial optimization augmented machine learning (COAML) method and LLM to solve dynamic electric autonomous dial-a-ride problem (E-ADARP). The static version of the E-ADARP with determined requests has been fully analyzed in Su et al., (2023, 2024) and Bongiovanni et al., (2019). The first step is to leverage the existing resource of Baty et al., (2024) and Yang et al., (2023) to solve the dynamic DARP - a simplified version of dynamic E-ADARP by deactivating charging options. It would be a good example to start, as the dynamic DARP is extended from VRP and TSP. The obtained results will be benchmarked with literature.
These are approximative dates. Please contact the training supervisor to know the precise period.