The heterogeneous vehicle routing problem with time windows and a limited number of resources. (September 2020)

• Record Type: Journal Article
• Authors: Molina, Jose C.; Salmeron, Jose L.; Eguia, Ignacio; Racero, Jesus
• Is Part Of: Engineering applications of artificial intelligence. Volume 94(2020)
• Publication Date: 2020-09
• Subjects: Vehicle routing problem -- VRP with time windows -- Fixed heterogeneous fleet -- Variable neighborhood descent -- Analytical and numerical modeling -- Performance analysis; 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.2020.103745
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: This paper introduces the heterogeneous vehicle routing problem with time windows and a limited number of resources (HVRPTW-LR), a practical extension of the classical vehicle routing problem in which routes to be designed share common scarce resources. The HVRPTW-LR arises when a limited number of resources, such as vehicles, drivers, instruments, and so on, are available but are insufficient to serve all customers in a route planning. Therefore, the route design involves the selection of customers to be visited at each route and resources to be used. Applications to this problem are found in real services companies with high seasonal demand which attend to different types of works and have to decide on how to effectively manage their resources. For designing optimal routes, a hierarchical objective function is considered, maximizing the total number of served customers as the primary objective, and minimizing the travel costs as secondary. A mathematical model of linear programming is introduced to describe and understand all constraints clearly. The problem is first heuristically solved by a semi-parallel insertion heuristic. Then, solutions are improved by a hybrid variable neighborhood descent metaheuristic based on a Tabu Search algorithm for the exploration of the neighborhood and a holding list. Experiments are conducted on numerous sets of benchmark instances from the literature to evaluate the performance of the proposed algorithm. Results show that the algorithm proposed in this paper has a good performance and can be easily applied for solving numerous vehicle routing problem variants from the literature. A new set of benchmark cases for the HVRPTW-LR are also presented and solved.