Send to

Choose Destination
See comment in PubMed Commons below
Comput Oper Res. 2013 Jan;40(1):490-497.

Hybrid column generation and large neighborhood search for the dial-a-ride problem.

Author information

Department of Business Administration, University of Vienna, Vienna, Austria.


Demographic change towards an ever aging population entails an increasing demand for specialized transportation systems to complement the traditional public means of transportation. Typically, users place transportation requests, specifying a pickup and a drop off location and a fleet of minibuses or taxis is used to serve these requests. The underlying optimization problem can be modeled as a dial-a-ride problem. In the dial-a-ride problem considered in this paper, total routing costs are minimized while respecting time window, maximum user ride time, maximum route duration, and vehicle capacity restrictions. We propose a hybrid column generation and large neighborhood search algorithm and compare different hybridization strategies on a set of benchmark instances from the literature.


Column generation; Dial-a-ride problem; Hybrid algorithm; Large neighborhood search; Variable neighborhood search

PubMed Commons home

PubMed Commons

How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for PubMed Central
    Loading ...
    Support Center