Explicación de códigos Python
PARTE I:
Importación de librerías:
Para el comienzo del código, se debe de hacer la importación de los módulos desde la librería de
gurobi para los modelos (Model), las constantes o especificaciones necesarias para la
configuración del modelo o la lectura del resultado de la optimización (GRB) y la variable
quicksum que se utiliza para las sumatorias de las restricciones que necesita el modelo.
Datos del problema:
Después de la importación de las librerías, se debe
realizar el ingreso de los datos correspondientes, en este
caso se contó con una cantidad de 11 nodos (desde el 0
hasta el 10), el registro de los arcos desde donde salen
hasta donde entran con sus respectivos costos A = (salida,
entrada, costo) y el origen que se tomará para la
inicialización del flujo (s = 0) y la finalización de éste
mismo (t = 10).
Construcción del modelo:
Se realiza la definición de una variable que contenga al modelo para el problema a solucionar.
Variables de decisión:
Se define la variable x como una variable binaria que tomará los valores de los arcos definidos
anteriormente, con la única diferencia de que si el arco es utilizado la variable tendrá valor igual
a 1 y 0 si es que no se utiliza para la ruta más corta.
Función objetivo:
Se establece la función objetivo (con la función .setObjetive) para minimizar los costos
utilizados, es decir, la función objetivo tratará de minimizar la suma de todos los arcos
multiplicados con sus costos correspondientes para poder lograr la ruta óptima.
Restricciones:
restricciones del flujo de ruta:
Se realizan las restricciones para las salidas y entradas de los nodos (con la función para crear
restricciones .addConstr) para que solamente salga y entre 1 flujo de los nodos, para que quede
más claro, del nodo origen el flujo solamente puede salir una vez y entrar una sola vez al nodo de
destino.
Restricción de conservación de flujo de nodos intermedios:
Se realiza un ciclo for para recorrer todos los nodos registrados del grafo, al siguiente se realiza
una filtración de nodos que no sean el de origen ni el de destino logren formar una cadena entre
todos los nodos necesarios para poder formar la ruta óptima.
Resolución del modelo:
Se resuelve el modelo con la función .optimize() y ejecutar todo lo antes
construido.
Visualización del modelo:
Para la visualización del modelo, se hace un chequeo de optimalidad donde se creara una lista
vacía (en este caso ruta = []) donde para cada arco en el conjunto de arcos es mayor a 0 (se toma
este valor ya que la variable al ser binaria tiene que ser 1 si se activa) el arco se guardará en la
lista vacía creada anteriormente con el costo del arco correspondiente la cuál formará parte de la
solución óptima factible, en el caso de que ningún arco cumpla con las condiciones se utiliza un
else para destacar que no se encontró una solución óptima.
Importación de librerías:
Para la realización del modelo de programación lineal para la ruta más corta solamente fue
utilizada la librería heap, el cual es una librería que realiza la implementación de elementos o la
extracción de elementos con valor mínimos, como por ejemplo la realización de listas de costos
mínimos.
Datos del problema:
Para este problema se utilizaron los mismos datos que el inciso anterior, por lo que no es
necesario volver a ingresarlos.
Construcción del grafo dirigido:
Inicialmente se realiza un diccionario (en este caso se le llamo grafo) donde se creó una lista
vacía para cada nodo dentro del conjunto de los nodos. Seguido a esto se realiza un recorrido
para los arcos dentro del conjunto de los arcos, donde:
u: nodo de origen.
v: nodo de destino.
w: costo respectivo del arco.
Entonces con la última línea de código de esta sección, para cada nodo con una lista vacía
agregada se le agrega a esta lista la conexión con el nodo de destino con su respectivo costo.
Ej: 0: [10, 5], 10 es el nodo de destino y 5 es el costo del arco.
Utilización del algoritmo Dijkstra:
Se inicia el algoritmo definiendo para la función Dijkstra
los parámetros de grafo, comienzo y final, donde grafo es
el diccionario antes creado, el parámetro comienzo
representa el nodo de origen del flujo y el parámetro final
que representa el nodo de destino del flujo.
Además, se añadieron las variables dist, prev y queue,
donde:
Dist: es un diccionario (del mismo tipo que la variable grafo) que guarda la distancia mínima
desde el nodo de inicio a cada nodo. Este diccionario se inicializa como infinito con el código
float(‘inf’) recorriendo todos los nodos anteriormente guardados en el diccionario grafo, ya que
inicialmente no se conoce ninguna ruta optima.
Prev: un diccionario que guarda el nodo anterior en la ruta mas corta hacia cada nodo (esto
servirá para reconstruir la ruta para generar la más corta).
Luego de esto se asigna con el diccionario dist que la distancia entre el nodo de origen hasta si
mismo es 0, también se añade una cola de prioridad (queue) que guarda tuplas donde 0 es el
costo acumulado y comienzo en la posición de los nodos, es decir, el costo acumulado en el costo
de origen es 0.
Después de la definición de parámetros se comienza un bucle while para la cola de prioridad,
donde se quita el nodo con menor costo acumulado hasta el momento, luego se define que si el
nodo es igual al nodo final se termina el ciclo.
Con un ciclo for se dice que para cada vecino (nodo adyacente) y peso (costo para llegar al nodo
vecino) para cada nodo en el grafo se recorrerán todos los vecinos del nodo actual donde se
actualizará el costo nuevo añadiendo el peso al costo actual.
Si el costo nuevo es menor que el que se tenía registrado, se actualizará la distancia mínima con
dist(vecino), se actualizará el nodo previo para la reconstrucción de la ruta con prev(vecino) =
nodo y finalmente se agrega el vecino a la cola donde se procesa la ruta nuevamente desde este
mismo.
Reconstrucción de la ruta:
Se inicia la reconstrucción de la ruta creando una
variable ruta y asignándole una lista vacía, luego se
asigna el nodo final a la variable nodo porque se
comenzará a construir la ruta desde el final hasta el
origen, donde para esta misma variable se inicia un ciclo
while donde mientras el nodo no sea ninguno se
reconstruirá la ruta.
Se usa el .insert() para ir cada nodo seleccionado al
inicio de la lista, de modo que la ruta final en el orden correcto, desde origen hasta el destino, la
función prev que se fue construyendo desde el comienzo donde se registro desde qué nodo se
llego a otro nodo de la forma más económica
Finalmente se realiza el retorno con la ruta lista con el costo total para llegar al nodo final desde
el nodo de comienzo.
Ejecución y visualización de resultados:
se escoge el nodo de inicio (0) y el de destino
(10), seguido a esto se asignan las variables
para la ruta optima y el costo total
igualándolas con la función Dijkstra.
Importación de librerías:
Las librerías utilizadas para este modelo de programación lineal es el mismo que el del inciso c),
por lo que no es necesario realizar la descripción de este mismo.
Datos del problema:
Para este problema son los mismos datos que los incisos anteriores por lo que no es necesario
describirlos.
Construcción del grafo no dirigido:
Para la construcción del grafo no dirigido se sigue la misma
estructura que para uno dirigido, solamente que con la
diferencia de que también se anota la dirección contraria a
la de ida, es decir, desde u se puede ir a v con costo w y
desde v se puede ir a u con costo w (obviamente existe este
tipo de relación entre los dos nodos).
¿Por qué se realiza la construcción de un grafo no dirigido?
Esto se realiza debido al objetivo que tiene el ejercicio, en este caso como queremos resolver un
problema para el árbol de expansión mínima y aplicaremos el algoritmo Prim se realiza la
transformación computarizada necesaria para que el algoritmo trabaje de manera correcta.
Utilización del algoritmo Prim:
de manera similar al algoritmo Dijkstra se inicia la
utilización del algoritmo definiendo los parámetros grafo e
inicio, donde el parámetro grafo es el diccionario antes
creado que guarda el peso y el vecino correspondiente al
nodo analizado y el parámetro de inicio corresponde en
donde iniciará el árbol de expansión mínima.
Luego tenemos la variable visitado que será el conjunto de
nodos ya visitados en el árbol de expansión mínima,
también tenemos la variable aem que será una lista vacía
donde se alojarán los arcos que formaran parte del árbol de expansión mínima y el costo total
que será la suma total de todos los costos los arcos registrados en el árbol final.
Seguido de la definición de las variables antes mencionadas, se realiza una cola de prioridad,
donde cada elemento representa lo siguiente:
0: costo de arco desde el nodo de origen hasta el nodo de destino.
Nodo origen: Nodo desde iniciará el arco.
Nodo de destino: Nodo donde terminará el arco.
Viéndolo, así como heap = [(0, nodo_origen, nodo_destino)]
En este caso se inicia con heap = [(0, inicio, inicio)] ya que no existe una conexión real inicial,
por lo que actúa de manera ficticia para después construir el árbol ya con todos los nodos
respectivos.
Después se inicia un ciclo while para la cola de prioridad, donde se quitará el arco con menor
costo de la cola de prioridad donde solo se procederá si el nodo de destino (v) aun no ha sido
visitado, si se procede el nodo de destino será marcado como visitado y si el nodo de destino no
es el primer nodo, se agregará el arco y se acumulará el costo del árbol.
Luego para cada vecino del nodo (v), si este no ha sido visitado se agrega el arco (v, vecino) a la
cola de prioridad con su costo (peso) correspondiente.
Y finalmente se devuelve con la función return la lista de arcos formados para el árbol de
expansión mínima y la suma total de los costos de los arcos enlistados.
Visualización de resultados:
Se llama a la función Prim con grafo (el grafo
no dirigido ya construido gracias a los códigos
anteriores) y inicio = 0 que indica el punto de
partida del AEM, el cual devolverá una lista de
tuplas con los arcos del AEM en el formato (u,
v, w) (la cual será bordes_aem) y la suma total
del costo de los arcos (la cual será total).
La cual después se iniciará un ciclo for ordenando los datos anteriormente devueltos para ordenar
de forma estructurada el árbol y finalmente el costo total óptimo.
PARTE II:
Importación de librerías:
Para este ejercicio se utilizan las librerías de gurobi, pandas, numpy, [Link], las
cuales sus funciones son:
Gurobi: Esta librería sirve para la construcción del modelo (modulo Model) ya que ayuda a la
definición de tipos de variable y las variables en si (GRB) y a la construcción de las restricciones
respectivas (quicksum).
Pandas: Esta librería ayuda a la lectura de datos o archivos para analizarlos y manipularlos de la
manera mas eficiente posible.
Numpy: Esta librería ayuda a la realización de los cálculos numéricos y también para las
operaciones de matrices y vectores de forma computarizada de una manera eficiente.
[Link]: Esta librería es utilizada para calcular distancia entre vectores analizando
los conjuntos de puntos en el espacio el cual para este ejercicio es muy útil (modulo cdist
puntualmente).
Lectura de datos:
Se realiza la lectura de datos del archivo Excel “VRP_Backhaul6 Grupo [Link]” ya que se
trabajará el código en base a este archivo, después se realiza la carga de datos del archivo usando
la librería pandas.
Extracción de datos:
Se realiza la extracción del dataframe “data” de la columna de “CUSTOMER CUST NO.”, luego
se transforma la columna en una lista con la función .tolist() ya que de esta forma los clientes
actuarán como conjunto de nodos para este problema.
De forma similar se realiza la extracción de las coordenadas x e y convirtiéndolas en un array
(matriz) con él .to_numpy() del dataframe el cual sirve para hacer más eficiente los cálculos de
las distancias, las cuales son necesarias mas adelante en el código.
Y de ultima se asignan la cantidad de nodos extraídos aplicando la función len() para manejar
estos nodos de una manera mas eficiente.
Matriz de distancias:
Como se mencionó anteriormente, se realiza el cálculo de las distancias utilizando las
coordenadas antes realizadas de forma matricial con la métrica euclidiana para finalmente
construir la matriz necesaria para la resolución del problema TSP.
Creación del modelo:
Con la función Model() se crea el modelo con el nombre “TSP”
asignándole la variable m para la simplificación del código.
Variables de decisión:
Se inscribe la variable de decisión x[n, n] el cual [n, n] representa el nodo de salida, ósea i, y [n,
n] representa el nodo de entrada, ósea j, de esta forma se puede crear la variable binaria de si el
tour pasa directamente del nodo i al nodo j o no.
La variable u se considera una variable continua debido a que puede tomar cualquier número (no
es necesario que sea un entero) ya que es una variable auxiliar que nos ayudará a eliminar los
subtours que se pueden generar y asegurar la ruta TSP (se aplicó formulación MTZ).
¿Por qué se utiliza n y no i, j?
Esto se hace debido a que n esta leyendo la lista de nodos anteriormente creada el cual como se
mencionó, simplifica el código y la creación de las restricciones.
Función objetivo:
Para este problema se busca minimizar la distancia total recorrida el cual es la sumatoria del
punto (i, j) en la matriz de distancia multiplicadas por la variable de si el nodo i pasa
directamente al nodo j o no.
Restricciones:
Cada nodo tiene exactamente una entrada:
Para cada nodo de entrada (j) en el conjunto de nodos N la sumatoria desde i distinto a j hasta N
de si el nodo i pasa al nodo j de forma directa tiene que ser igual 1, es decir, que cada nodo tiene
una entrada.
Cada nodo tiene exactamente una salida:
Para cada nodo de salida (i) en el conjunto de nodos N la sumatoria desde i distinto a j hasta N de
si el nodo i pasa al nodo j de forma directa tiene que ser igual 1, es decir, que cada nodo tiene una
entrada.
Eliminación de subtours:
Para cada nodo de salida (i) en el conjunto de nodos N desde 1 hasta N y Para cada nodo de
entrada (j) en el conjunto de nodos N desde 1 hasta N, si el nodo i es distinto al nodo j, la resta
entre el orden de visita del nodo i y el orden de visita al nodo j más la cantidad total de nodos*la
variable binaria que indica si el nodo i pasa al nodo j directamente tiene que ser menor o igual a
la cantidad total de nodos menos 1, con esto aseguramos que no existan subtours, es decir que se
realiza una única secuencia que pasa por todos los nodos sin repetir ningún ciclo.
Resolución del modelo:
Se hace la resolución del modelo con la función .optimize() el cual busca el
óptimo del modelo.
Visualización del modelo:
De forma similar al código del problema de la
ruta mas corta, se utiliza el [Link] ya
que esta devuelve la solución óptima del modelo
y se añade una variable con una lista vacía donde
se alojará la ruta TSP óptima.
¿Qué pasa si tenemos una capacidad lo suficientemente pequeña y grande?
Primeramente, se añadiría la variable de demanda para poder utilizarlas en las restricciones de
capacidad mas adelante, de la forma:
De forma seguida, se realiza la definición de la capacidad pequeña y grande:
Estas definiciones de capacidad nos ayudarán con sus respectivas restricciones. Aunque antes de
pasar se debe de fijar la carga del nodo inicial ya que el medio de transporte comienza vacío y
comienza a cargar demanda a medida que este visite los nodos:
Después de realizar todo lo anterior se escribe las siguientes restricciones:
Esta restricción corresponde a la de capacidad, donde el orden de visita del nodo i debe superar o
igualar las demandas del nodo i y ser menor o igual que la capacidad máxima (Q)
Esta restricción actúa de forma similar a la eliminación de subtours original, solo que, en vez de
utilizar la cantidad de nodos del problema, utiliza la capacidad designada anteriormente.
Resultados:
Para el problema con una capacidad lo suficientemente pequeña, no existe una solución factible
ya que la capacidad máxima no ayuda a satisfacer la demanda del nodo i.
Para el problema con una capacidad lo suficientemente grande, este trabajará de forma normal ya
que la demanda será satisfecha gracias a que la capacidad es muy grande.
PARTE III: