An ACS-based memetic algorithm for the heterogeneous vehicle routing problem with time windows. (1st November 2020)

• Record Type: Journal Article
• Authors: Molina, Jose C.; Salmeron, Jose L.; Eguia, Ignacio
• Is Part Of: Expert systems with applications. Volume 157(2020)
• Publication Date: 2020-11-01
• Subjects: Heterogeneous VRPTW -- Ant colony system -- Memetic algorithms -- VNTS; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2020.113379
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: This problem appears when a limited fleet with different capacities. The objective is to perform the route design minimizing the costs. The problem is solved using an ACS algorithm with local search. The results show that the proposal has a good performance on the HVRPTW. Abstract: This paper presents a solution methodology to solve the heterogeneous vehicle routing problem with time windows (HVRPTW). This problem appears when a limited fleet of vehicles, characterized by different capacities, fixed costs and variable costs, is available for serving a set of customers which have to be visited within a predefined time window. The objective is to perform the route design minimizing the total fixed vehicle costs and distribution costs and satisfying all problem constraints. The problem is solved using an Ant Colony System (ACS) algorithm which has been successfully applied to combinatorial optimization problems. Moreover, to improve the performance of the ACS on the HVRPTW, a hybridized ACS with local search, called memetic ACS algorithm is proposed where the local search is performed by a variable neighborhood Tabu Search algorithm. Experiments are conducted on sets of benchmark instances from the scientific literature to evaluate the performance of the proposed algorithm. The results show that the algorithm has a good performance on the HVRPTW. In particular, out of the 80 instances, it obtained 65 new best solutions and matched 6 within reasonable computational times.