Population-Based Iterated Local Search Approach for Dynamic Vehicle Routing Problems

Abstract

This article addresses the dynamic vehicle routing problem (DVRP). DVRP is a challenging variation of the classic vehicle routing problem in which some customers are not known in advance. The objective is to incorporate new customers into the schedule as they become known while still attempting to minimize the cost of serving all customers without violating the problem constraints. This work proposes an effective population-based approach that integrates various algorithmic components to address DVRP. The approach combines a local search algorithm with various evolutionary operators (crossover and mutation) in an adaptive manner. To promote diversity, the proposed approach utilizes a population of solutions and uses a quality-and-diversity strategy to retain only promising solutions. The well-known 21 DVRP benchmark instances are utilized to test the performance of the proposed approach. An experimental comparison is carried out to assess the contribution of the integrated components. Results demonstrate that the integrated components significantly improve search performance. It is also shown that the proposed approach produces new best results for several instances when compared with the best methods reported in the literature. Note to Practitioners—This work deals with dynamic vehicle routing problems (DVRPs). In DVRP, only limited information is available at the start, and new information is revealed over time. It proposes an effective hybrid approach to tackle this problem. The proposed approach combines evolutionary operators and a local search approach in an adaptive manner to exploit the benefits of each algorithmic component. The proposed approach produces several new best-known solutions. The experimental results demonstrate that the proposed approach is very effective in dealing with DVRP and can help decision-makers in designing best-routing solutions.

Topics & Concepts