VEHICLE ROUTING PROBLEM
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 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
-
Title: FIREPOCTEP Fortalecimiento de los sistemas transfronterizos de prevención y extinción de incendios forestales y mejora de los recursos para la generación de empleo rural posCovid-19
Start Date: 01/05/2021
End Date: 31/12/2022
Budget: 33850 €
Leaders: Alma Gómez Rodríguez, Juan Carlos González Moreno, Francisco Javier Rodríguez Martínez
Funding Bodies: Interreg V A - Unión Europea - POCTEP - Cooperación Transfronteriza España Portugal [0756_FIREPOCTEP_6_E] -
Title: Conecun: Desenvolvemento dun sistema de control integral de patoloxías dixestivas en cunicultura mediante combinación de distintas tecnoloxías
Start Date: 01/01/2015
End Date: 30/06/2015
Budget: 18000 €
Leaders: Juan Francisco Gálvez Gálvez
Funding Bodies: Xunta de Galicia [CO-0008-15] -
Title: Servidor de cálculo científico de altas prestaciones
Start Date: 01/01/2013
End Date: 31/12/2015
Budget: 278239 €
Leaders: Xosé Antón Vila Sobrino
Funding Bodies: Ministerio de Economía y Competividad [UNVI13-1E-2283], European Union (FEDER Funds) -
Title: Sistema intelixente de planificación de vendas para axentes comerciais e optimización de rutas para o control de flotas de distribución
Start Date: 01/11/2009
End Date: 31/10/2012
Budget: 90670 €
Leaders: Juan Francisco Gálvez Gálvez
Funding Bodies: Xunta de Galicia [PGIDIT09TIC001E], Ignacio de las Cuevas S.L. -
Title: Sistema inteligente para la planificación y distribución de pienso
Start Date: 15/05/2007
End Date: 31/10/2008
Budget: 94875 €
Leaders: Juan Francisco Gálvez Gálvez
Funding Bodies: Xunta de Galicia [PGIDIT07SIN047E], EDISA Tecnologías de Informática Industrial S.A.
Publications
-
Title: Quasi-linear time heuristic to solve the Euclidean traveling salesman problem with low gap
Year: 2024
Journal: Journal of Computational Science
Editorial: Elsevier [doi.org/10.1016/j.jocs.2024.102424]
Issn: 1877-7503
Volumen: 82
Pages: 1 - 12
Type: Journal Articles
Authors: Arno Formella
-
Title: Adaptación y optimización del algoritmo Clarke&Wright a un problema de distribución multirrestrictivo
Year: 2009
Isbn: 84-613-6906-5
Pages: 109 - 113
City: Ourense
Country: Spain
Conference Name: IX Congreso Gallego de Estadística e Investigación de Operacións
Type: Conference Contributions
Authors: Pilar Carrión Pardo, Arno Formella, Jacobo Campos Casal, Juan Francisco Gálvez Gálvez, José Jaime Novella Feijoó
People Involved
- Calvo Domínguez, Diego
- Campos Casal, Jacobo
- Formella, Arno
- Gálvez Gálvez, Juan Francisco
- Novella Feijoó, José Jaime
Student Work
-
Title: Sistema de gestión y optimización de visitas a clientes y distribución de pedidos
Year: 2013
Volumen: ENI-412
Type: Master's Thesis
Authors: Diego Calvo Domínguez
-
Title: Optimización y adaptación del algoritmo Clarke&Wright clásico a un problema de distribución multirestrictivo
Year: 2009
Type: Diploma De Estudios Avanzados
Authors: José Jaime Novella Feijoó
Press Articles
- (05/12/2016)De la bioinformática a la simulación aeroespacial
- (30/11/2012)A 'ruta perfecta' dos comerciais e distribuidores do Grupo Cuevas leva selo universitario
