title: Hybrid column generation and large neighborhood search for the dial-a-ride problem.
abstract: 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.
authors.affiliation: Department of Business Administration, University of Vienna, Vienna, Austria.
authors.forename: Sophie N
authors.initials: SN
authors.lastname: Parragh
authors.forename: Verena
authors.initials: V
authors.lastname: Schmid
keywords: Column generation; Dial-a-ride problem; Hybrid algorithm; Large neighborhood search; Variable neighborhood search