| Sumario: | En este trabajo consideramos un problema de creación de territorios y ruteo, que consiste en dividir un conjunto de clientes en un número fijo de territorios tomando como objetivo principal la minimización de las distancias entre los clientes (dispersión). Después de tener la configuración de clientes asignados a territorios, los cuales son asociados a repartidores, se busca minimizar el tiempo de espera de cada cliente en cada uno de los territorios creados.
El problema es formulado como un modelo de programación binivel con múltiples seguidores, donde en el nivel superior (líder) se forman los territorios garantizando que todos los clientes estén asignados a uno solo y a que no haya territorios vacíos. Algunas otras restricciones, tales como el balanceo de la carga de trabajo se consideran en el nivel superio. Por otro lado, en el nivel inferior (seguidor) se conoce el conjunto de clientes asociado a cada territorio y en base a esto, cada repartidor realiza libremente su ruta. Para diseñar las rutas, lo hará enfocado en la satisfacción del cliente, es decir, busca minimizar los tiempos de espera de cada uno de ellos.
Después de tener las rutas diseñadas en base al tiempo de espera de los clientes, se debe verificar el cumplimiento de una restricción de presupuesto dada por la empresa. Es decir, existe una restricción de acoplamiento en el nivel superior que involucra las variables del seguidor.
En éste trabajo, además de proponer el modelo matemático para formular este problema, proponemos un algoritmo heurístico capaz de resolver de manera eficiente el problema.
El algoritmo propuesto consiste en un método constructivo multi-arranque que explora soluciones del líder y para cada una de ellas resuelve de manera óptima el nivel inferior. El algoritmo propuesto explota las características del problema al aplicar búsqueda local en las soluciones del líder sin necesidad de resolver el nivel inferior durante cada exploración. Dicho algoritmo fue aplicado para resolver un caso de estudio de una empresa local de la ciudad. Además, se probaron con instancias de prueba para validar su robustez y buena aplicabilidad.
Los resultados muestran que el algoritmo tiene un buen desempeño en todas las instancias de prueba. Por otro lado, los resultados muestran que el hecho de considerar la satisfacción de los clientes durante el proceso de decisión se va a afectar la dispersión pero las cargas de trabajo se van a balancear satisfactoriamente.
|
|---|
