Experimental evaluation of a linear programming model for solving the vehicle routing problem (VRP)

Abstract

This article aims to propose a quantitative criterion to evaluate the feasibility of implementing solutions based on linear programming for solving the vehicle routing problem (VRP). An experimental design was used to measure the relative solution time with a proposed linear programming model. The sample was randomized employing three dispersion scenarios of the delivery points: poorly scattered, scattered and very scattered. A linear programming solver was used to determine the time and iterations necessary for solving the model. As a result, the solution time was found in terms of the number of delivery points and the number of iterations for the proposed scenarios, and the time required to solve the problem was predicted using the proposed model. The research concludes with a proposal of the number of viable points to be solved by linear programming.

Keywords

• programación lineal
• complejidad
• ruteo, vehículos
• puntos de entrega