Hybrid column generation and large neighborhood search for the dial-a-ride problem |
| |
Authors: | Sophie N Parragh Verena Schmid |
| |
Affiliation: | 1. Department of Business Administration, University of Vienna, Vienna, Austria;2. Centro para la Optimizacióny Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Cr 1E No. 19A-10, ML315, Bogotá, Colombia |
| |
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. |
| |
Keywords: | Large neighborhood search Column generation Hybrid algorithm Variable neighborhood search Dial-a-ride problem |
本文献已被 ScienceDirect 等数据库收录! |
|