Premium
Solution of the Dial‐a‐Ride Problem with multi‐dimensional capacity constraints
Author(s) -
Wong K. I.,
Bell Michael G. H.
Publication year - 2006
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2006.00544.x
Subject(s) - computer science , scheduling (production processes) , route planning , heuristic , mathematical optimization , operations research , duration (music) , lift (data mining) , job shop scheduling , capacity planning , simulation , engineering , mathematics , routing (electronic design automation) , computer network , artificial intelligence , art , literature , data mining , operating system
The Dial‐a‐Ride Problem (DARP) consists of planning routes and schedules for picking up and delivering users within user‐specified time windows. Vehicles of a given fleet with limited capacity depart from and end at a common depot. The travel time of passengers cannot exceed a given multiple of the minimum ride time. Other constraints include vehicle capacity and vehicle route duration. In practice, scheduling is made more complicated by special user requirements and an inhomogeneous vehicle fleet. The transportation of elderly and handicapped people is an important example, as space for wheelchairs is limited and a lift is required. In this study, we present a modified insertion heuristic to solve the DARP with multi‐dimensional capacity constraints, and the performance of the proposed algorithm is tested in simulation. We show that the proposed methodology is effective when compared with the classic algorithms.