Solving a dial-a-ride problem with a hybrid evolutionary multi-objective approach: Application to demand responsive transport

Demand responsive transport allows customers to be carried to their destination as with a taxi service, provided that the customers are grouped in the same vehicles in order to reduce operational costs. This kind of service is related to the dial-a-ride problem. However, in order to improve the quality of service, demand responsive transport needs more flexibility. This paper tries to address this issue by proposing an original evolutionary approach. In order to propose a set of compromise solutions to the decision-maker, this approach optimizes three objectives concurrently. Moreover, in order to intensify the search process, this multi-objective evolutionary approach is hybridized with a local search. Results obtained on random and realistic problems are detailed to compare three state-of-the-art algorithms and discussed from an operational point of view.

Figure optionsDownload as PowerPoint slideHighlights
► Demand responsive transport problem, related to the DARP, is tackled with an evolutionary approach.
► Original variation operators are provided.
► An iterative local search (ILS) introduced in the mutation intensifies the search process.
► Three state-of-the-art evolutionary algorithms (NSGA-II, SPEA2, IBEA) are compared through two performance indicators.
► The analysis of the quality of solutions along time shows that IBEA outperforms SPEA2 and NSGA-II, whatever the indicator or the kind of instance.
► The comparison of the algorithms, hybridized or not, shows the relevance of the ILS in the mutation step: all hybrid algorithms are better than their respective standard counterparts.
► The approach proposed is capable of solving large-size problems (two sets of 10 instances with 100 customers and one set of 10 instances with 1000 customers).