Panorama Divino

Revisión y programación de modelos de optimización como una plataforma en GAMS-CPLEX para problemas de ruteo de vehículos.

C. E. Torres Pérez, E. Olivares-Benítez, J. L. Martínez FloresUniversidad Popular Autónoma del Estado de Puebla

Puebla, Puebla, México

Resumen: Este documento presenta la revisión de modelos de optimización para problemas de ruteo de vehículos: VRP (Ruteo Simple), FSMVRP (VRP con determinación de composición y tamaño de la flota) y HFVRPTW (VRP con Ventanas de Tiempo y Flota Heterogénea). Los modelos se revisaron y se corrigieron o complementaron para programarlos en GAMS. En este trabajo se muestran las modificaciones realizadas a los modelos. Se resolvieron instancias de 7 a 100 clientes. De esta manera se desarrolló una plataforma computacional para resolver instancias reales con este alcance en tamaño, con el propósito de usarla como herramienta en proyectos de investigación y consultoría.

Palabras clave: Problema de Ruteo de Vehículos, Flota heterogénea, Ventanas de tiempo

Abstract: This paper presents a review of optimization models for vehicle routing problems: VRP (Simple Vehicle Routing Problem), FSMVRP (Fleet Size and Mix Vehicle Routing Problem), and HFVRPTW (Heterogeneous Fleet Vehicle Routing Problem with Time Windows). The models were reviewed and corrected or complemented, to be programmed in GAMS. This work shows the modifications done to the models. Instances of 7 to 100 customers were solved. In this way, a computational platform was developed to solve real instances within this scope in size, with the goal of use it as a tool in research and consulting projects.

Key words: Vehicle Routing Problem, Heterogeneous fleet, Time windows

Introducción

El problema de ruteo de vehículos (Vehicle Routing Problem o VRP, por sus siglas en inglés), es un problema de optimización combinatoria bien conocido en Investigación de Operaciones. Consiste en determinar un conjunto de rutas para una flota de vehículos que parten de uno o más depósitos o almacenes para satisfacer la demanda de varios clientes dispersos geográficamente en una región [1].

El objetivo principal es entregar la demanda a todos los clientes minimizando el costo total involucrado que generan las rutas, disponiendo de una flota de vehículos con una cierta capacidad de transportación. Cada ruta es realizada por un solo vehículo que inicia y termina en el depósito, de tal forma que se satisfagan los requerimientos de los clientes y las restricciones operacionales.

Existe un gran número de variantes del problema de ruteo de vehículos. Entre las más conocidas destacan:

Capacitated VRP (CVRP)

Capacitated VRP with time windows (CVRPTW)

Periodic VRP (PVRP)

Periodic VRP with Time Windows (PVRPTW)

Heterogeneous Fleet Vehicle Routing Problem (HF-VRP)

Vehicle Routing Problem with Time Windows (VRPTW)

Vehicle Routing Problem with Pick-up and Deliveries (VRPPD)

Capacitated VRP with Pick-up and Deliveries and Time Windows (CVRPPDTW)

Multiple Depot VRP (MDVRP)

Multiple Depot VRP with Time Windows (MDVRPTW)

Modelo matemático

Básicamente, el VRP es una extensión del TSP (Traveling Salesman Problem), y lo podemos expresar en su forma simple como lo describe [2] de la siguiente manera. La red de transporte por la que circulan los vehículos se modela mediante [3] un grafo ponderado G = (V,E,C). Los nodos del grafo representan a los clientes y depósitos. Para el caso de un solo depósito, éste se representa por el nodo {0}. Los nodos {1,..., n} V representan a los clientes, y el conjunto K representa a los vehículos de la flota. En algunos casos se agrega una copia del depósito etiquetada con {n+1} para simplificar la formulación. Cada arco (i,j) E representa el mejor camino para ir desde el nodo i hacia el nodo j en la red de transporte y tiene asociado un costo cij y un tiempo de viaje tij. Denotaremos por y al conjunto de nodos adyacentes e incidentes al nodo i, es decir, y . Cada cliente tiene asociada una demanda di, y cada vehículo tiene una capacidad (cuando la flota es Homogénea), una formulación básica puede verse en [2].

En este problema la cantidad de rutas no es fijada de antemano. Utilizando como base los modelos de [2], podemos formular de la siguiente manera:

Sujeto a:

Las variables xij indican si el arco (i, j) es recorrido por un vehículo tomando el valor de 1, y de cero en otro caso. La función objetivo (1) es el costo total de las rutas. Las restricciones (2) y (3) indican que m es la cantidad de vehículos utilizados en la solución y que todos los vehículos que parten del depósito deben regresar. Las restricciones (4) y (5) aseguran que todos los clientes deben ser visitados. La restricción (6) actúa como restricción de eliminación de sub-tours y a la vez impone que la demanda total de los clientes visitados por un vehículo no exceda su capacidad C; La restricción (7) asegura que el número de vehículos a utilizar sea positivo y al menos uno. Por último la restricción (8) hace a xij una variable binaria tal como se indica al principio.

Para implementar el modelo anterior hay que determinar el valor de r(S), donde K es un conjunto con suficientes vehículos para satisfacer la demanda. Esta demanda total se puede expresar como , para un conjunto de clientes S. La variable actúa como una variable de decisión si el vehículo es utilizado.

Entonces, determinar el valor de r(S), requiere resolver el siguiente problema

Sujeto a:

La solución de este problema genera una cota inferior para atender la demanda completa de un conjunto de clientes que pertenecerán a una ruta, con el mínimo de transportes .

Su función objetivo es minimizar el número de rutas, y no existe un límite superior. La restricción (8) no permite que la demanda exceda la capacidad del vehículo y en (9) se requiere que cada cliente sea asignado solo a un vehículo. Las variables de decisión son y .

Discusión

Utilizamos los modelos base que propone [2] Olivera, en su trabajo de “Heurísticas para Problemas de Ruteo de Vehículos” , para las versiones del VRP (Problema de Ruteo de Vehículos), FSMVRP (Problema de Ruteo de Vehículos con una Flota Heterogénea) y HF-VRPTW (Problema de Ruteo de Vehículos con ventanas de Tiempo y Flota Heterogénea). Se estudiaron tales modelos y se reformularon parcialmente para corregir algunos errores y para mejorar la implementalidad en el lenguaje del software de optimización. A continuación las propuestas por modelo:

VRP (Problema de Ruteo Simple)

Para

...