An adaptive large neighborhood search heuristic for the share-a-ride problem. (February 2016)

• Record Type: Journal Article
• Authors: Li, Baoxiang; Krushinsky, Dmitry; Van Woensel, Tom; Reijers, Hajo A.
• Is Part Of: Computers & operations research. Volume 66(2016)
• Page Start: 170
• Page End: 180
• Publication Date: 2016-02
• Subjects: Transportation -- The Share-a-Ride Problem (SARP) -- Adaptive large neighborhood search -- Slack time; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2015.08.008
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: The Share-a-Ride Problem (SARP) aims at maximizing the profit of serving a set of passengers and parcels using a set of homogeneous vehicles. We propose an adaptive large neighborhood search (ALNS) heuristic to address the SARP. Furthermore, we study the problem of determining the time slack in a SARP schedule. Our proposed solution approach is tested on three sets of realistic instances. The performance of our heuristic is benchmarked against a mixed integer programming (MIP) solver and the Dial-a-Ride Problem (DARP) test instances. Compared to the MIP solver, our heuristic is superior in both the solution times and the quality of the obtained solutions if the CPU time is limited. We also report new best results for two out of twenty benchmark DARP instances. Abstract : Highlights: We propose an adaptive large neighborhood search (ALNS) heuristic. The performance of our heuristic is benchmarked against an MIP solver and Dial-a-Ride (DARP) test instances. The ALNS-based heuristic can solve medium size instances of the Share-a-Ride Problem.