Checking the Feasibility of Dial‐a‐Ride Instances Using Constraint Programming

Checking the Feasibility of Dial‐a‐Ride Instances Using Constraint Programming

0.00 Avg rating0 Votes
Article ID: iaor20118529
Volume: 45
Issue: 3
Start Page Number: 399
End Page Number: 412
Publication Date: Aug 2011
Journal: Transportation Science
Authors: , ,
Keywords: programming: mathematical
Abstract:

In the dial‐a‐ride problem (DARP), a fleet of vehicles must serve transportation requests made by users that need to be transported from an origin to a destination. In this paper we develop the first exact algorithm which is able to either efficiently prove the infeasibility or to provide a feasible solution. Such an algorithm could be used in a dynamic setting for determining whether it is possible or not to accept an incoming request. The algorithm includes solution space reduction procedures, and filtering algorithms for some DARP relaxations. Computational results show that the filtering algorithms are effective and that the resulting algorithm is advantageous on the more constrained instances.

Reviews

Required fields are marked *. Your email address will not be published.