An improved variable neighbourhood search algorithm for selective dial-a-ride problems

Abstract

Various alternative means of transportation are emerging aiming to combat traffic congestion. Among these solutions, car sharing and pooling schemes are currently gaining in popularity. Such schemes require computationally tractable algorithms for the efficient allocation of resources. Towards such an aim, the Variable Neighbourhood Search has emerged as the leading algorithmic solution. Aiming to speed up its convergence, this paper introduces two novelties to this algorithm. Results based on a realistic simulation scenario in a densely populated area demonstrate the added accuracy obtained using these novelties in a time-sensitive application.