back

VEHICLE ROUTING PROBLEM

Intelligent Software Systems

The Vehicle Routing Problem (VRP) is one of the most challenging combinatorial optimization task (speaking in terms of computational cost). The VRP is a well-known integer programming problem which falls into the category of NP-hard problems, meaning that the computational effort required to solve the problem increases exponentially with the problem size (well, at least if P not equal NP).

The goal is to find a set of optimal routes for a fleet of vehicles that deliver a set of customers with minimum cost. The demands are known beforehand and the route should, as far as possible, originate and terminate at a depot.

The following figures depict a typical input for a VRP problem (Figure 1) and one possible solution (Figure 2):

Figure 1. Typical input for a Vehicle Routing Problem
Figure 1. Typical input for a Vehicle Routing Problem

Figure 2. An output for the instance above
Figure 2. An output for the instance above

Nowadays, VRP research is motivated by both its great practical relevance on logistics and also by its difficulty to find optimum solutions because of its extremely large solution space.


Financed Projects


Publications


People Involved


Student Work


Press Articles



Partners

More about Grupo de Sistemas Informáticos de Nueva Generación (SING)
Grupo de Sistemas Informáticos de Nueva Generación (SING)
More about Laboratorio de Informática Aplicada
Laboratorio de Informática Aplicada