An Economic Efficiency Analysis of a capacitated vehicule routing problem

International audienceThe Vehicle Routing Problem (VRP) is a well-known and extensively studied problem in the Operations Research literature. Many variants exist, such as VRP with time windows, multi-period VRP, VRP with stochastic clients, etc). In this presentation, we are concerned with the classical Capacitated VRP (CVRP). For this problem, we are given n clients, a hub, costs cij for traveling from a client/hub I to a client/hub j, and a capacity for the vehicle. The CVRP aims at assigning each client to a vehicle and then at finding the visiting order of the clients, so that the total distance traveled by all vehicle is minimized. Exact linear programming models are known for this problem [2]. From an economical point of view, we deal with a transportation system and we want to find its allocative efficiency, that is the minimum cost required to insure a precribe output (the output being delivering the demand to each client). More precisely, given the number of vehicles, their capacity, the traveling costs (as function of exogenous parameters such as cost of time, cost of gasoline), an efficient solution must be found, that is one that minimizes the cost for the expected output. The allocative efficiency is a well-known economical concept, and several functions are known to be apt to model the allocative efficiency of a system (e.g., Cobb-Douglas, translog, quadratic, Leontief) [1]. The purpose of this work is to study the CVRP problem from an economical point of view, that is to consider that the optimal solution of the CVRP is on the efficiency frontier, and then to try to guess, through several types of regression, the functional form of this frontier. This functional form should be defined as a function of the natural economical parameters (e.g., the cost for gasoline, and not directly the aggregated cij). The issues are to find an appropriate function, to compute its parameters, and to study its variations with regards to each parameters (typically resulting in the shadows or marginal costs of each resource, such as the cost of the gasoline, or the capacity of a vehicle). Ultimately, we would like to determine hypotheses under which one can accurately guess the optimal value of CVRP without having to actually compute it. The model and the preliminary experiments and results shall be presented. Bibliography [1] Pels, E., Piet, R., "Chapter 19: Cost functions in transport", C. In Handbook of Transport Modelling, D.A. Hensher and K.J. Button (Eds.), 2000, Pag. 321-333. [2] Toth, P.,Vigo, D. "Models, relaxations and exact approaches for the capacitated vehicle routing problem", Discrete Applied Mathematics 123, 2002, Pag. 487 - 512