A mixed integer programming model and a hybrid VNS/TS algorithm for GVRP with the heterogeneous fleet, time windows, and vehicle selection

The green vehicle routing problem (GVRP) is a logistical problem considering environmental effects. Existing GVRP studies considered important constraints such as time windows (TW) or heterogeneous fleets (HF), but mostly, they assumed that there is an available fleet where all vehicles can be used. However, some companies build their fleets using rented cars by selecting the vehicle numbers and types. Therefore, we focus on GVRP with the HF, TW, and vehicle selection to minimise travel, rental, and emission costs. A MIP model, and a hybrid algorithm combining variable neighbourhood search with the tabu search algorithm are proposed. The performance of the algorithm is demonstrated by using the modified Solomon test instances. The proposed algorithm could produce high-quality solutions within a short computation time. In addition, an average improvement of 45.49% and 16.69% are achieved respectively compared to the first scenario and the second scenario where the vehicles are held constant. [Submitted: 6 February 2023; Accepted: 9 January 2024]