Online clustering reduction based on parametric and non-parametric correlation for a many-objective vehicle routing problem with demand responsive transport

In this paper, we address an online dimensionality reduction approach to deal with a many-objective formulation of a Vehicle Routing Problem with a Demand Responsive Transport (VRPDRT). The problem relates to a mode of transport similar to available carpooling services in which passengers are transported from their origin to their destination sharing the same vehicle. The goal is to reduce the operating/riding costs while meeting passenger needs and providing high-quality service. Due to the complexity and conflicting characteristics of the problem, an evolutionary approach based on a dimensionality reduction technique is applied to solve the VRPDRT in which eight different objective functions are used. The performance of the proposed approaches – OnCL_τ-MOEA/D and OnCL_ρ-MOEA/D – are compared to an a priori cluster dimensionality reduction with Pearson's and τ of Kendall correlation coefficients using a realistic data set containing distances and travel time for Belo Horizonte, Brazil. The online and offline versions of the algorithms are also compared with a baseline approach, a classic version of MOEA/D. Results show that the online cluster-based approach achieves a better spread of solutions, when compared to its a priori versions. Moreover, there is no difference between the results obtained from the online Cluster-based approach and the original MOEA/D. It shows that the proposed dimensionality reduction is an effective technique presenting a positive effect on the search efficiency, computational cost, and in the application of usual visualization techniques.