A case-based reasoning approach to solve the vehicle routing problem with time windows and drivers' experience. (July 2021)

• Record Type: Journal Article
• Authors: Quirion-Blais, Olivier; Chen, Lu
• Is Part Of: Omega. Volume 102(2021)
• Publication Date: 2021-07
• Subjects: Case base reasonning (CBR) -- Drivers' experience -- Artificial intelligence -- Routing -- Optimization; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2020.102340
• Languages: English
• ISSNs: 0305-0483

Abstract

Highlights: We address a last-mile delivery problem faced by an online retailer. Drivers' experience obtained from real data are used in the decision process. A methodology based on artificial intelligence generates routes based on historical routes. Extensive experiments demonstrate the effectiveness of the methodology. Abstract: In last-mile delivery, on-line retailers deliver goods from local distribution centers to endpoint customers using a fleet of vehicles. This problem is often related to vehicle routing problems with time windows (VRPTWs) in the literature. For an on-line retailer in China, it was found that experienced drivers could often find better routes rather than relying on computerized tools using state-of-the-art algorithms. Therefore, the focus of this paper is to generate routes based on experience. To do so, we propose a methodology based on case base reasoning (CBR). The methodology designs new routes to fulfill orders by retrieving and adapting routes previously performed from a repository named case base. A mechanism is also developed to maintain good quality routes in the case base. The methodology is first tested on problem instances generated using a construction heuristic. Other tests are also performed using real data from an on-line retailer in China. Results show that the CBR methodology designed can effectively generate routes to solve new problems similar to routes previously performed. A comparison to the BoneRoute algorithm show that the solutions obtained with CBR are in average 18.4% longer. However, this result does not take into consideration the time required by the drivers to adapt to a very different route.