A Maximum Cluster Algorithm for Checking the Feasibility of Dial-A-Ride Instances

The dial-a-ride problem (DARP) involves the dispatching of a fleet of vehicles to transport customers requesting service and is one of the most challenging tasks of combinatorial optimization. We study the DARP as a constraint satisfaction problem, where the goal is to find a feasible solution with...

Full description

Saved in:
Bibliographic Details
Published in:Transportation science 2015-05, Vol.49 (2), p.295-310
Main Authors: Häme, Lauri, Hakula, Harri
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Clusters
Combinatorial analysis
Combinatorial optimization
Customer satisfaction
Customers
dial-a-ride problem
dynamic programming
Evaluation
Feasibility
Logistics
Motor vehicle fleets
Optimization
Optimization algorithms
Planning
Precedence constraints
Routes
Transportation services
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The dial-a-ride problem (DARP) involves the dispatching of a fleet of vehicles to transport customers requesting service and is one of the most challenging tasks of combinatorial optimization. We study the DARP as a constraint satisfaction problem, where the goal is to find a feasible solution with respect to the time, capacity, and precedence constraints, or to prove infeasibility. The main contribution of our work is a new robust method for this problem formulation. The algorithm is based on a dynamic subroutine that finds for any set of customers a maximum cluster, that is, a maximal set of customers that can be served by a single vehicle. The performance of the algorithm is analyzed and evaluated by means of computational experiments, justifying the efficiency of the solution method.
ISSN:0041-1655
1526-5447
DOI:10.1287/trsc.2013.0495