Sophie Parragh, Verena Schmid,
"Hybrid column generation and large neighborhood search for the dial-a-ride problem"
, in Computers and Operations Research, Vol. 40, Nummer 1, Elsevier Ltd., Seite(n) 490-497, 1-2013, ISSN: 0305-0548
Hybrid column generation and large neighborhood search for the dial-a-ride problem
Sprache des Titels:
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.