Dial-a-Ride is an emerging transport system, in which a fleet of vehicles, without fixed routes and schedules, carries people from the desired pickup point to the desired delivery point, during a pre-specified time interval. It can be modeled as an NP-hard routing and scheduling problem, with a suitable mixed integer programming formulation. Exact approaches to this problem are too limited to tackle real-life instances (hundred of trips), therefore heuristics are needed. The heuristic method proposed in this paper builds an auxiliary graph and then solves an assignment problem on this graph. The auxiliary graph is obtained by replacing pairs of nodes with a single one and associating an ad hoc cost function to the new set of arcs. Two different simple methods are employed to transform the infeasible solution given by the assignment problem into a feasible one. The proposed algorithms have been tested on instances created using the Milan network and shown to be fast and effective.

### An effective and fast heuristic for the Dial-a-Ride problem

#### Abstract

Dial-a-Ride is an emerging transport system, in which a fleet of vehicles, without fixed routes and schedules, carries people from the desired pickup point to the desired delivery point, during a pre-specified time interval. It can be modeled as an NP-hard routing and scheduling problem, with a suitable mixed integer programming formulation. Exact approaches to this problem are too limited to tackle real-life instances (hundred of trips), therefore heuristics are needed. The heuristic method proposed in this paper builds an auxiliary graph and then solves an assignment problem on this graph. The auxiliary graph is obtained by replacing pairs of nodes with a single one and associating an ad hoc cost function to the new set of arcs. Two different simple methods are employed to transform the infeasible solution given by the assignment problem into a feasible one. The proposed algorithms have been tested on instances created using the Milan network and shown to be fast and effective.
##### Scheda breve Scheda completa Scheda completa (DC)
2007
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11584/253601`
##### Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

• ND
• 57
• 44