Teoria De Los Grafos

Introducción

El impacto ambiental de las operaciones llevadas a cabo por las empresas se ha convertido en tiempos recientes en un tema de gran interés, tanto por parte de académicos y profesionales como del personal de dirección de las empresas, debido a su relevancia social y económica; tanto es así que en muchos mercados puede llegar a convertirse en una fuente de ventaja competitiva sostenible, en la medida que los consumidores preferirían adquirir bienes o servicios provenientes de empresas ambientalmente responsables, incluso, si ello implica un mayor costo de adquisición.

Esta tendencia emergente y las regulaciones ambientales cada día más exigentes han impulsado la adición de un componente ambiental a la gestión de los sistemas de distribución comercial y, en general, a la gestión de las cadenas de suministro, dado que sus operaciones tienen un alto impacto ambiental debido a las emisiones provenientes del consumo del combustible (principalmente diésel) por parte de los vehículos utilizados. Es por ello que se hace necesario ahondar en la investigación y aplicación de herramientas de modelamiento que permitan optimizar las rutas de transporte, minimizando las distancias y/o el número de vehículos utilizados, lo cual se asocia directamente con una disminución en el consumo de combustible brindando una enorme oportunidad para reducir el impacto ambiental.

El estudio de los problemas de ruteo surge a mediados del siglo pasado con la proposición del modelo matemático del problema del agente viajero (Traveling Salesman Problem, TSP), a partir del cual muchas investigaciones se han dedicado de lleno a estos problemas en todos los casos particulares y con aplicaciones en el mundo real. En las últimas décadas ha aumentado el desarrollo de herramientas informáticas para la resolución de problemas reales de diseño de rutas de transporte, basados en modelos conceptuales inspirados en sistemas biológicos, inteligencia artificial, teorías matemáticas, entre otros, a los cuales se les programan e incorporan algoritmos y funciones, dependiendo del problema a solucionar.

Teoría de grafos

Muchos problemas de planificación de rutas de distribución han encontrado alternativas de solución en la teoría de grafos, dado que se facilita su modelamiento por la similaridad conceptual de las estructuras. Al igual que las rutas de distribución, los grafos son estructuras discretas que constan de vértices conectados mediante arcos. Un grafo dirigido (figura 1) se denota por G = (V, A), donde V es un conjunto no vacío de elementos denominados vértices y AC V x V es un conjunto de arcos. Cada a ∈ A tiene asociados dos vértices de V, i y j, i ≠ j; a i se le denomina origen del arco y a j, destino del arco. El arco a también se denota por (i, j), de esta forma se hace referencia al vértice origen y al vértice destino del arco

Problema de ruteo de vehículos con restricciones de capacidad

El problema de ruteo de vehículos con restricciones de capacidad (CVRP) es un problema fundamental de optimización combinatoria con aplicaciones en la práctica logística. En las últimas dos décadas se han logrado grandes avances en su solución debido, principalmente, a mejores algoritmos y al aumento creciente de las capacidades de los equipos de cómputo2. En el CVRP se da un conjunto finito de ciudades y los costos de viajes entre ellas; una ciudad específica es identificada como el depósito de los vehículos y el resto como los clientes. Cada cliente corresponde con una localización donde se entrega una cantidad de un único producto. Las cantidades demandadas por los clientes están determinadas previamente y no se pueden dividir, es decir, que tienen que ser entregadas a un vehículo de una sola vez. En la versión más simple se supone que los vehículos son homogéneos y, por lo tanto, tienen la misma capacidad máxima.

Proyecto Grafos

Grafos es una herramienta informática (software) libre para la construcción, edición y análisis de grafos de utilidad para la docencia, aprendizaje y práctica de la teoría de grafos y otras disciplinas relacionadas como investigación operativa, diseño de redes, ingeniería de organización industrial, logística y transporte, etc. Incorpora algoritmos y funciones que permiten modelar, diseñar y analizar problemas reales8. El proceso del software tiene como pilares el desarrollo de una interfaz para la construcción y edición de grafos y el desarrollo de una estructura de clases y librerías con algoritmos de resolución y análisis de problemas de teoría de grafos.

El usuario puede dibujar libremente el grafo sin preocuparse del análisis o algoritmo que utilizará posteriormente. El programa le avisa en caso de no factibilidad o de cualquier otro requerimiento para un análisis en particular. Esta libertad de cara al usuario implica una mayor complejidad en el desarrollo del código fuente, ya que no sólo hay que contemplar los supuestos aplicables al tipo de análisis o problema a resolver, sino cualquier escenario que pueda generar la interacción con el usuario (incluyendo los de no factibilidad)9.

Grafos permite la construcción tanto de grafos dirigidos como no dirigidos. Los arcos pueden tener valores asociados de costo o distancia, flujo mínimo y flujo máximo. Asimismo, los nodos, además de tener una etiqueta de identificación, pueden tener un valor asociado (peso del nodo, demanda o capacidad de

...