3/25/2022: Selecting the best algorithm to solve the vehicle routing problem in the plane with unit demands, Olivier Goldschmidt and Isaías Huerta Vargas

The input data for a problem instance consists of the locations of the customers in the plane, the location of the depot, and the capacity of the trucks. The objective is to assign customers to trucks and to find, for each truck, a route to visit its customers, starting from and returning to the depot such that the total Euclidean distance traveled by all trucks is minimized.

We present two sweep algorithms. The first partitions the customers into two groups, the first within a circle centered at the depot, the rest of customers forming the second group. Then customers in each group are swept clockwise and assigned to trucks. Finally, using a nearest neighbor followed by a 2-opt exchange heuristic, we find a short route for each truck. The second sweep algorithm varies from the first in the way the customers are assigned to groups. For a given percentage of customers, assign the ones further from the depot to the first group such that their number is an integer multiple of the truck capacity and assign the rest of customers to the second group.

With different customer numbers and truck capacities, we generate real-world instances of the problem by randomly selecting address locations in Los Angeles and in New-York. For every instance, the depot is located in the center.

We show that statistically, the best circle radius for the first algorithm or the best percentage for the second heavily depends on the number of customers and the truck capacity. We also show that the second algorithm dominates the first in almost all instances. This is probably due to the fact that the second algorithm always guarantees to use a minimum number of trucks.

Finally, we use two machine learning approaches to select the best circle radius or the best percentage of customers. The first approach uses a Random Forest classification model and the second a Convolutional Neural Network regression model. The CNN model input is an image representing the position of the customers and some additional features, and the output is the cost obtained for each parameter of the algorithm. We show that, even with a modest number of instances to train the models, we obtain good accuracies when evaluating the test instances.