Multiple Vehicle Routing Problem with Fuel Constraints

Abstract

In this paper, a Multiple Vehicle Routing Problem with Fuel Constraints (MVRPFC) is considered. This problem consists of a field of targets to be visited, and a collection of vehicles with fuel tanks that may visit the targets. Consideration of this problem is mainly in the improvement of feasible solutions, but the following steps are discussed: Cost Matrix Transformation, Field Partitioning, Tour Generation and Rerouting, and Tour Improvement.

Four neighborhoods were investigated (2-opt, 3-opt, Target Vehicle Exchange, Depot Exchange), using the Variable Neighborhood Descent and Variable Neighborhood Search schemes, with APD and Voronoi partition methods. These neighborhoods were compared to investigate their performance for various instances using the above schemes and partition methods. In general, 2-opt performed as well as 3-opt in less time than 3-opt; in fact, 3-opt was the slowest of the four neighborhoods. Additionally, the Variable Neighborhood Descent scheme was found to produce better results than the Variable Neighborhood Search.