An effective and fast heuristic for the Dial-a-Ride problem |
| |
Authors: | Roberto Wolfler Calvo Alberto Colorni |
| |
Institution: | (1) Institut Charles Delaunay (ICD), FRE CNRS 2848, University of Technology of Troyes, BP 2060, 10010 Troyes, France;(2) Departement of Industrial Design, Arts and Comunications (INDACO), Politecnico di Milano, Piazza Leonardo da Vinci, 32, 20133 Milano, Italy |
| |
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
-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.
|
| |
Keywords: | Dial-a-Ride Routing Scheduling Heuristic |
本文献已被 SpringerLink 等数据库收录! |
|