An ELS-based approach with dynamic probabilities management in local search for the Dial-A-Ride Problem. (February 2016)

• Record Type: Journal Article
• Authors: Chassaing, M.; Duhamel, C.; Lacomme, P.
• Is Part Of: Engineering applications of artificial intelligence. Volume 48(2015:Dec.)
• Page Start: 119
• Page End: 133
• Publication Date: 2016-02
• Subjects: DARP -- ELS -- Metaheuristic -- Heuristic dynamic probabilities; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2015.10.002
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: This paper addresses the Dial-A-Ride Problem (DARP) which is used to model on-demand transportation services. This kind of transportation is quickly becoming an essential service for modern public mobility or logistics providers. In the DARP, a set of transportation requests has to be handled by a fleet of vehicles. Each request corresponds to a client to be transported from a pickup point to a delivery point. The routing costs have to be minimized, while respecting a set of constraints including time windows on nodes, maximum riding time per client and a maximal total duration of trips. An Evolutionary Local Search (ELS) based approach is proposed to solve this problem. A new greedy randomized heuristic to compute initial solutions is developed. A dynamic probabilities management mechanism is used in the local search to improve the convergence. The method is benchmarked on a classic set of instances from the literature and it is compared against state of the art methods. The numerical results show the effectiveness of this approach.