pablorosasdatlas

Alguna vez se han puesto a pensar ¿Qué porcentaje del parque vehicular no son autos particulares sino que ofrecen algún servicio de transporte?. Para poner un ejemplo de la importancia de esta clase de servicios, según datos del INEGI (2020) solamente el servicio de mensajería y paquetería esta presente en 743 de las 822 actividades económicas del país, poco más del 90%, lo que significa que apoya a casi todos los sectores de la economía.

De igual manera como podemos ver en la imagen, existen otra clase de servicios de transporte más importantes como el autotransporte de carga. El autotransporte de carga es la actividad dedicada a transportar productos o mercancías de cualquier tipo, pudiendo requerir para su transportación equipo especializado o no. Este tipo de transporte suele ser utilizado en la cadena de suministro, la cual se puede definir como el conjunto de pasos y elementos que le permiten a las empresas adquirir los recursos para producir o manufacturar un producto. De igual manera el autotransporte se usa en lo que se conoce dentro del área de logística como distribución de última milla, que es la etapa de entrega de un producto desde un centro de distribución (CEDIS) a el cliente final.

** Te podría interesar: «Categorizando las zonas con choques y siniestro en Nuevo León»

Estos dos tipos de transporte tienen varias cosas en común, pero una de ellas es la necesidad de generar rutas de viaje que les permitan optimizar uno o más atributos, por ejemplo: maximizar el número de clientes atendidos durante un turno o minimizar las emisiones de carbono de toda la ruta. Este tipo de problemas en investigación de operaciones se conoce como problema de ruteo de vehículos (VRP – vehicule routing problem).

El VRP es un problema de optimización combinatoria descrito por primera vez en 1959 por el matemático Dantzing. El objetivo del problema es encontrar las rutas optimas de vehículos que parten de un depósito, atienden a cada cliente y después regresan al depósito.

A pesar de ser un problema común en la mayoría de las empresas, resolver un VRP es computacionalmente costoso y se categoriza como NP-Hard porque en la vida real puede involucrar restricciones que introducen una complejidad significativa al problema, algunas de estas características se enlistan a continuación:

Ventanas de tiempo: Los clientes tienen restricciones de tiempo para satisfacer su demanda
Tiempos de viaje dependientes del horario: Consideran factores que cambian con respecto al horario como el tráfico.
Múltiples depósitos: En los VRPs clásicos hay un solo depósito, en este caso se consideran varios.
Flotas heterogéneas: Los vehículos no tienen las mismas características.
Rutas con recolección y entrega: Para algunos clientes se deja algún producto y en otros se recolecta o ambos.
Los vehículos no regresan al depósito de origen: No regresan al mismo depósito del que partieron forzosamente. Aplica en casos como en la renta de vehículos.
Algunas variables son aleatorias y se pueden encontrar dentro de un rango de probabilidad.
Multiobjetivo: Se pueden considerar varios objetivo a maximizar o minimizar

Formas de resolverlo

Un VRP puede ser resuelto de varias formas. Mediante un método exacto como un modelo de optimización, un modelo de programación dinámica o programación por restricciones. De igual manera se puede resolver mediante un algoritmo de aproximación de soluciones como una metaheurística.

Modelo de optimización

A continuación se describe un modelo de optimización para el VRP clásico, para el que se hacen varias asunciones:

El depósito tiene demanda cero
Cada ubicación o cliente es atendido solamente por un vehículo
La demanda de cada cliente es indivisible
El vehículo no excede su capacidad de carga
El vehículo inicia y termina en un depósito
La demanda, distancias y costos de entrega de los clientes son conocidos

El modelo matemático se muestra en la siguiente imagen

En este modelo c_ij representa el costo de ir del nodo i al nodo j. La variable binaria x_ij tomara el valor de 1 si se usa el arco para ir del nodo i al nodo j, 0 en otro caso. K es el número de vehículos disponibles y r(S) representa el número mínimo de vehículos necesarios para atender a todos los clientes.

La restricción 1 y 2 establecen que solo un arco entra y solo un arco sale de cada vértice. Las restricciones 3 y 4 establecen que el número de vehículos que salen del depósito es el mismo que regresa. La restricción 5 son las restricciones de corte la cual establece que todas las rutas deben de estar conectadas y que la ruta no debe de exceder la capacidad del vehículo. La restricción 6 es es una restricción de integralidad de las variables.

** Te puede interesar nuestra participación en HACK MTY con un reto de choques y siniestros con alumnos y alumnas del TEC de MTY

Este tipo de modelos pueden ser programados en distintos lenguajes de programación como Python, C++, Java, etc., y suelen usar software especializados como GUROBI, CPLEX.

Métodos de aproximación

Otra forma de resolver un VRP es mediante la implementación de metaheurísticas. Una metaheurística es un algoritmo capaz de generar soluciones de buena calidad para un problema en especifico pero sin asegurar optimalidad. Generalmente son usadas como alternativas a los métodos exactos debido a que tienen la capacidad de resolver problemas complejos como un VRP con instancias grandes, ofreciendo soluciones de buena calidad en un tiempo computacional usualmente menor a un método exacto. Algunos ejemplos de dichos algoritmos son:

Tabu search
Algoritmos genéticos
GRASP
VNS
Simulated Anealing
entre otros…

Al igual que con los modelos de optimización, estos algoritmos pueden programarse con distintos lenguajes de programación como Python, C++, Java, etc.

Video de las iteraciones de la metaheurística Tabu Search para el VRP. Se puede observar en la parte superior como el valor disminuye conforme avanzan las iteraciones, lo que implica que el objetivo es minimizar alguna característica.

– Equipo Datlas –

Keep it weird

Ligas de interés:

Imagina que quisieras saber que calificación obtendrás en una materia al final del semestre o si es recomendable realizar una fiesta en el exterior la siguiente semana, para esto otras cosas, podrías utilizar un árbol de decisión.

¿Qué es un árbol de decisión?

Los árboles de decisión son uno de los modelos más fáciles de entender en tareas de clasificación y son la base para usar algoritmos un poco más complejos como lo son “bosques aleatorios (Random forest)”. Un árbol de decisiones se define como un algoritmo de aprendizaje supervisado, el cual suele ser utilizado para tareas de clasificación y regresiones. Se compone de una estructura jerárquica con forma de árbol el cual tiene un nodo raíz, ramas, nodos internos y nodos hoja.

Los algoritmos de aprendizaje supervisado son aquellos en los que sus datos necesitan estar etiquetados previamente para ser entrenados, Revisa: “Algoritmos Supervisados: Clasificación vs. Regresión”.

La estructura de los árboles de decisión tiene una representación que facilita el entender porque se obtiene un resultado u otro de acuerdo con las decisiones tomadas en nodos con una profundidad menor. El aprendizaje dentro de los árboles de decisión emplea una búsqueda codiciosa (Búsqueda Greedy) para identificar los puntos de división óptimos. El proceso se repite de forma recursiva hasta que todos o la mayoría de los registros sean clasificados con una etiqueta.

Dicho de otra manera, el proceso de clasificación inicia con un nodo raíz el cual considera un atributo y una condición aplicada al valor de dicho atributo. El proceso se desplaza a una rama si se cumple o no la condición, llegando a un nuevo nodo con posiblemente un nuevo atributo y una condición diferente. Este proceso de división, evaluación y ramificación continúa hasta llegar a un nodo hoja.

Pero no es tan sencillo como parece, cada paso tiene un conjunto de posibles variantes que vuelven un árbol más eficiente o menos eficiente.

Imagen tomada de Cheat-Sheet: Decision Trees Terminology.

Veamos un ejemplo practico con Python, estas por comprar un vuelo y te gustaría saber si ese vuelo se va a retrasar de acuerdo a cierta información con la que cuentas:

La Aerolínea
Número de vuelo
Aeropuerto de salida
Aeropuerto de llegada
día de la semana
Duración del vuelo
Distancia

id	Aerolínea	Vuelo	Aeropuerto Salida	Aeropuerto Llegada	Día de la semana	Duración	Distancia	Retrasó
1	CO	269	SFO	IAH	3	15	205	1
2	US	1558	PHX	CLT	3	15	222	1
3	AA	2400	LAX	DFW	3	20	165	1
4	AA	2466	SFO	DFW	3	20	195	1
5	AS	108	ANC	SEA	3	30	202	0
…	…	…	…	…	…	…	…	…
539379	CO	178	OGG	SNA	5	1439	326	0
539380	FL	398	SEA	ATL	5	1439	305	0
539381	FL	609	SFO	MKE	5	1439	255	0
539382	UA	78	HNL	SFO	5	1439	313	1
539383	US	1442	LAX	PHL	5	1439	301	1

Vista parcial de los datos de vuelos.

Para poder usar un árbol de decisiones importamos algunas librerías

import pandas as pd
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn import metrics
from sklearn.tree import export_graphviz
from sklearn import tree
import six
import sys
sys.modules['sklearn.externals.six'] = six
from IPython.display import Image  
import pydotplus
import graphviz 
import matplotlib.pyplot as plt

Es necesario tener solo valores numéricos en los atributos, por lo que es necesario cambiar los valores de la Aerolínea, aeropuerto de llegada y de salida por Ids.

d = {}
names = list(airlines.AirportFrom.unique())
id = 0
for n in names:
   d[n] = id
   id = id + 1

 airlines['Airline'] = pd.factorize(airlines['Airline'])[0]
 airlines['AirportFrom'] = airlines['AirportFrom'].map(d)
 airlines['AirportTo'] = airlines['AirportTo'].map(d)

Separamos el conjunto de datos en un conjunto de atributos y la etiqueta

#  SEPARAMOS LOS ATRIBUTOS DE LA ETIQUETA
atributos = ['id', 'Airline', 'Flight', 'AirportFrom', 'AirportTo', 'DayOfWeek','Time', 'Length']
X = airlines[atributos]
y = airlines.Delay

Creamos un conjunto de entrenamiento y uno de prueba, en este caso nos quedamos con un 70% de los datos como entrenamiento y un 30% como conjunto de prueba:

#  SEPARAMOS EN CONJUNTO DE ENTRENAMIENTO Y CONJUNTO DE PRUEBA
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=1)

Creamos nuestro árbol y lo entrenamos. Podemos variar el nivel de profundidad del árbol, pero para este ejercicio, con una profundidad de tres es suficiente, de igual manera podemos cambiar la función de calidad de los nodos.

#  CREAMOS UN ARBOL DE DECISION
clf = DecisionTreeClassifier(max_depth=3)

#  ENTRENAMOS NUESTRO ARBOL
clf = clf.fit(X_train,y_train)

Si quisiéramos ver el árbol lo podemos hacer de la siguiente manera

fig = plt.figure(figsize=(25,20))
tree.plot_tree(clf, feature_names= atributos, rounded=True, filled=True, proportion=True, max_depth=3)
plt.show()

Podemos cambiar la función para medir la calidad de una ramificación, por defecto se usa la función ‘gini’ que hace referencia a la impureza de los nodos Gini, pero podemos usar la función ‘entropy’ o ‘log_loss’ , si quieres más información puedes revisar la documentación de la librería Scikit learn, DecisionTreeClasiffier y el siguiente enlace con la formulación matemática: Formulación, para más información acerca de esta función puedes revisar la siguiente liga: Gini impurity .

Para poder ver que tan bien predice nuestro árbol con los parámetros por defecto lo podemos hacer de la siguiente manera:

#  PREDECIMOS SOBRE EL CONJUNTO DE PRUEBA
y_pred = clf.predict(X_test)
print("Accuracy:",metrics.accuracy_score(y_test, y_pred))

Durante el proceso de expansión del árbol, no es necesario que todos los atributos se utilicen, en el ejemplo anterior con una profundidad de seis el atributo “Aeropuerto Salida” no se utilizó. Se puede decir que los atributos en niveles menos profundos del árbol tienen mayor influencia en el valor de la variable objetivo que los que aparecen en una mayor profundidad.

Ventajas

Algunas de las ventajas de los árboles de decisión son:

Son fáciles de interpretar: La representación visual de los árboles es muy fácil de entender. La naturaleza jerárquica hace fácil ver cuales atributos son mas importantes lo cual no siempre pasa con otros algoritmos (ej. Redes neuronales).
Poca o ningún preprocesamiento de los datos: Los árboles de decisión tienen una serie de características que los hacen más flexibles que otros clasificadores. Puede manejar varios tipos de datos, es decir, valores discretos o continuos, y los valores continuos pueden convertirse en categóricos mediante el uso de umbrales. Además, también puede manejar valores nulos, lo que puede ser problemático para otros clasificadores.
Muy flexible: Los árboles de decisión pueden utilizarse tanto para tareas de clasificación como de regresión, lo que los hace más flexibles que otros algoritmos. También es insensible a las relaciones subyacentes entre atributos; esto significa que, si dos variables están muy correlacionadas, el algoritmo solo elegirá una de las características para dividir.

Desventajas

Propensos al sobreajuste: Los árboles de decisión tienden a sobreajustarse y no generalizan bien a nuevos datos. Esta situación puede evitarse mediante los procesos de prepoda o postpoda. La prepoda detiene el crecimiento del árbol cuando los datos son insuficientes, mientras que la postpoda elimina los subárboles con datos inadecuados tras la construcción del árbol.
Estimadores de alta varianza: Pequeñas variaciones en los datos pueden producir un árbol de decisión muy diferente. El ensacado, o promediado de estimaciones, puede ser un método para reducir la varianza de los árboles de decisión. Sin embargo, este enfoque es limitado, ya que puede dar lugar a predictores muy correlacionados.
Sub-optimalidad: Se sabe que el problema de aprender un árbol de decisión óptimo es NP-completo bajo varios aspectos de optimalidad e incluso para conceptos simples. En consecuencia, los algoritmos de aprendizaje de árboles de decisión se basan en algoritmos de búsqueda heurísticos como el algoritmo Greedy, en el que se toman decisiones localmente óptimas en cada nodo. Estos algoritmos no garantizan la obtención de un árbol de decisión globalmente óptimo. Esto se puede mitigar entrenando múltiples árboles en un aprendiz conjunto, en el que las características y las muestras se muestrean aleatoriamente con reemplazo.