INSTITUTO TECNOLÓGICO Y DE ESTUDIOS SUPERIORES DE MONTERREY

CAMPUS MONTERREY

DIVISIÓN DE INGENIERÍA Y ARQUITECUTRA

PROGRAMA DE GRADUADOS EN INGENIERÍA

MÉTODO HEURÍSTICO PARA LA FORMACIÓN DE SECTORES DE

REPARTO CON CARGA DE TRABAJO EQUILIBRADA

TESIS
PRESENTADA COMO REQUISITO PARCIAL PARA OBTENER EL GRADO ACADÉMICO DE:

MAESTRA EN CIENCIAS
CON ESPECIALIDAD EN SISTEMAS DE MANUFACTURA

POR:
ING. MARCELA MACIEL NAVA

MONTERREY, N. L. DICIEMBRE DEL 2007

 Resumen

El presente trabajo aborda el problema de generar zonas de reparto para apoyar la labor
diaria de rutear vehículos para una empresa que realiza entregas a domicilio.

El problema completo es llamado “Ruteo de Vehículos” y el enfoque de solución que el

trabajo aborda es el de las dos fases “Sectorizar primero –Rutear después”. El alcance
del trabajo se limita a la primera parte del enfoque “La Sectorización” y su solución.

La pregunta que resuelve el problema completo se define como ¿qué clientes debe
atender cada vehículo y en que orden debe de visitarlos?. Y la que resuelve el problema
del trabajo es ¿Qué clientes debe atender cada vehículo?

El trabajo propone un método de solución heurístico para la solución de la Sectorización.

El método de solución se basa en dos metodologías básicas, el árbol de costo mínimo
total (MST) y el método de barrido.

El trabajo esta dividido en 4 capítulos, el primer capítulo aborda la propuesta de

investigación que define el problema, la justificación, el alcance, los objetivos, los
métodos de investigación usados y las limitantes del trabajo. El segundo capítulo es un
desarrollo teórico que ubica el problema dentro del contexto de la empresa, empezando
de lo más general, la función de Logística; a lo más particular, Sectorización. Así como
las dos metodologías básicas que se unen para formar el método de solución, el MST y el
método de barrido. El tercer capítulo desarrolla el método de solución y sus
consideraciones. El cuarto y último capítulo presenta la aplicación del método a un
conjunto de datos reales y las soluciones obtenidas de este caso particular. Se concluye el
trabajo con comentarios y recomendaciones para trabajos posteriores.

3
 Indice

Resumen 3

Indice General 4

Indice de Figuras 6

Indice de Tablas 7

Capítulo 1 Propuesta de Investigación

1.1 Introducción 8

1.2 Definición del Problema 10

1.3 Justificación 11

1.4 Objetivos 11

1.5 Alcance de la Investigación 12

1.6 Limitantes de la Investigación 12

1.7 Metodología y Métodos 12

Capítulo 2 Trabajos y literatura relacionada

2.1 Marco del problema dentro de la empresa 13
2.2 Logística 15
2.2.1 Historia 15
2.2.2 Procesos de Logística 18
2.2.3 Niveles de Planeación 19
2.2.4 Estrategias Principales 20
2.2.5 Clasificación en base al tipo de negocio 23
2.2.6 Costos y Empresas de Servicio 24
2.3 Diseño y Programación de Rutas 26
2.3.1 Generalidades del Problema 26
2.3.2 Clases de VRP 29
2.3.3 Métodos de solución 33
2.4 Sectorización 37
2.4.1 Fundamentos 37

4
 2.4.2 Comparación de trabajos publicados sobre el tema 43
2.4.3 Método de solución vs trabajos publicados 46
2.5 Método de Barrido 49
2.6 Árbol de Costo Mínimo Total 52
2.6.1 Algoritmo Boruvka 54
2.6.2 Algoritmo Kruskal 56
2.6.3 Algoritmo Prim/Dijkstra 58

Capítulo 3 Método de solución

3.1 Consideraciones del Método de Solución 61

3.2 Descripción gráfica del Método de Solución 65
3.2.1 Problema de número de vehículos impar 65
3.2.2 Problema de número de vehículos par 69
3.3 Diagrama de Flujo del Método de Solución 71
3.4 Pseudos Código del Método de Solución 76

3.5 Automatización del Método de Solución 80

3.5.1 Ventana de interacción del Programa 81

3.5.2 Pasos para correr el programa de manera semiautomática 82
3.5.3 Pasos para correr el programa de manera automática 83

Capítulo 4 Caso de Aplicación

4.1 Descripción del Caso 84

4.2 Situación Actual 86
4.3 Definición de Parámetros para el Programa del Usuario Final 89
4.4 Solución del Problema con 26 vehículos 91
4.5 Solución del problema con 25 vehículos 94
4.6 Observaciones de la Solución 97

Conclusiones 98

Recomendaciones 99

Bibliografía 100

Anexo 1: Código del Programa 105

5
 Indice de Figuras

Figura 1. Sectorización dentro de la Empresa 14

Figura 2. Procesos de Logística 18
Figura 3. Niveles de Planeación 19
Figura 4. Estrategias Principales de Logística 20
Figura 5. Método de Barrido: Paso 1 50
Figura 6. Método de Barrido: Paso 2 50
Figura 7. Método de Barrido: Paso 3 50
Figura 8. Método de Barrido: Paso 4 51
Figura 9. Método de Barrido: Paso 5 51
Figura 10. Minimum Spanning Tree 52
Figura 11. Algoritmo Boruvka 55
Figura 12. Algoritmo Kruskal 57
Figura 13. Algoritmo Prim Parte 1 59
Figura 14. Algoritmo Prim Parte 2 60
Figura 15. Tipo de Sectores en el Método de Solución 61
Figura 16. Capas de Sectores en Problema Impar 62
Figura 17. Capas de Sectores en Problema Par 62
Figura 18. Método Solución para Vehículos Impar Parte 1 65
Figura 19. Método Solución para Vehículos Impar Parte 2 66
Figura 20. Método Solución para Vehículos Impar Parte 3 67
Figura 21. Método Solución para Vehículos Impar Parte 4 68
Figura 22. Método Solución para Vehículos Par Parte 1 69
Figura 23. Método Solución para Vehículos Par Parte 2 70
Figura 24. Diagrama de Flujo Método Solución Parte 1 72
Figura 25. Diagrama de Flujo Método Solución Parte 2 73
Figura 26. Cuadro de Diálogo del Método de Solución Automatizado en C++ 81
Figura 27. Configuración Actual de Sectores 87
Figura 28. Configuración Actual de Sectores sobre Mapa de Monterrey 88
Figura 29. Cuadro de Diálogo del Programa para el Usuario Final 90
Figura 30. Configuración Propuesta para Sectores Par 92
Figura 31. Configuración Propuesta para Sectores Par sobre mapa de Monterrey 93
Figura 32. Configuración Propuesta para Sectores Impar 95
Figura 33. Configuración Propuesta para Sectores Impar sobre mapa de Monterrey 96

6
 Índice de Tablas

Tabla 1. Estrategia Logística vs Nivel Decisión 22

Tabla 2. Sectorización y su relación Estrategia-Nivel Decisión 22
Tabla 3. Tabla Comparativa de Trabajos Publicados 43
Tabla 4. Peso de los sectores de la Configuración Actual 86
Tabla 5. Evaluación de parámetros para el caso de aplicación 89
Tabla 6. Peso de los sectores de la Configuración Propuesta para vehículos Par 91
Tabla 7. Peso de los sectores de la Configuración Propuesta para vehículos Impar 94
Tabla 8. Tabla Comparativa de Soluciones 97

7
CAPÍTULO 1 PROPUESTA DE INVESTIGACIÓN

1.1 Introducción

Hoy en día el entorno competitivo es muy exigente, día con día los consumidores exigen
más para estar satisfechos, solicitan mejores servicios a menores costos, con rápidos
tiempos de respuesta y también esperan productos de gran variedad o hechos a la medida
“customized”. Esto nos demuestra que hoy, quien dicta las reglas del mercado es el
consumidor. Sumamos a estas circunstancias la globalización de los mercados que trae
consigo el aumento de competencia y por tanto la repartición del mercado entre estos
productores. Por tales razones las empresas siempre deben buscar la manera de mejorar y
tener una ventaja sobre sus competidores para poder acaparar una parte de ese mercado.

Todo esto confronta el entorno competitivo que se teñía no hace más de 10 años, donde el
productor era quien fijaba el movimiento del mercado, fijaba los precios, los tiempos de
respuesta, las condiciones de venta e incluso podía darse el lujo de no vender si así lo
determinaba ya que era el único que ofrecía ese producto, la competencia era poca o nula.

Un aspecto muy importante de las exigencias actuales del consumidor es el tiempo de

respuesta y en un futuro no muy lejano, el lugar donde se entrega este producto. Se
observa que conforme el tiempo avanza son más las empresas que ofrecen el servicio a
domicilio como un plus en sus servicios, que muchas de las veces es la ventaja sobre sus
competidores. Por el momento es una ventaja, más se predice que en un futuro no será
ventaja sino un requerimiento básico para que esta empresa sea considerada por el
consumidor. Todo esto no se veía en el pasado ya que el que tenía que viajar por el
producto era el consumidor y ahora los papeles se invierten, el que viaja es el productor
al sitio del consumidor para entregar el producto o servicio.

Esta necesidad de entrega a domicilio es desencadenada por el ritmo tan acelerado de

vida que hoy en día se tiene, las personas valoran su tiempo casi o más que el dinero.
Todas las personas desean que su tiempo sea productivo y cualquier literatura afirma que

8
los tiempos de traslado no generan valor pero son necesarios e inevitables, por esto las
personas ya no quieren cargar con esta actividad. El crecimiento de vehículos transitando
las calles aumenta los tiempos de traslado e incluso los torna enfadosos por el tráfico y el
estrés que generan. De esta manera las personas están dispuestos a pagar un costo
razonable para evitarse esta actividad y dedicar su tiempo en otra que le produzca un
mayor beneficio.

Retomando la idea de mejora continua de las empresas para mantenerse competitivo en el

mercado, primeramente debe enfocarse a reducir costos en las áreas que aportan los
mayores costos a la empresa, siendo compras y logística las más importantes. En el área
de compras el mayor aporte de costo es la materia prima y como el productor no influye
en ese factor, se tornan entonces los ojos a logística. Dentro de la logística el transporte es
uno de los costos más altos que como se comento antes es un mal necesario por lo que su
optimización siempre será importante y deseable. Si se logra optimizar este proceso el
beneficio es mutuo, tanto para la empresa por generarle menores costos y aumentar sus
utilidades, como para los consumidores por recibir menores precios y mayor rapidez de
respuesta.

9
 1.2 Definición del Problema

Hablando de transporte y considerando el servicio a domicilio nos referimos

principalmente al problema de ruteo de vehículos. Problema que conforme aumenta el
número de puntos a repartir complica el proceso, la exactitud y el tiempo de solución. Por
esta razón se propone la modelación del ruteo de vehículos bajo el enfoque de las dos
fases: Sectorizar primero-Rutear después. Siguiendo este enfoque, a partir de un
problema muy grande, difícil y tardado de resolver obtendremos varios pequeños, fáciles
y rápidos de solucionar. Al hacer esto se mejora la productividad de nuestro equipo de
logística y se mejora el tiempo de respuesta a la demanda del cliente.

El problema abordado por este trabajo implica lo siguiente: una empresa de reparto a
domicilio (comida rápida, lavandería, mensajería, mueblería, etc.) consta de una flota
de “m” vehículos disponibles para realizar el reparto a “n” puntos o clientes
diariamente. Los clientes a quien deben realizarse las entregas son variables, no siempre
son la misma dirección, ni el mismo número de clientes.

Tenemos que el problema de ruteo es un problema de nivel operativo, que se realiza día
con día, mientras la sectorización se considera un problema de estrategia, es decir no se
realiza frecuentemente, se supone una frecuencia de 6 meses a un año. Tiempo razonable
para reajustar los límites de los sectores o la modificación de los mismos.

La propuesta del trabajo es dividir la zona total de reparto (donde están contenidos todos
los puntos a repartir en un día) en pequeñas zonas que corresponderán a la zona de
reparto de cada vehículo. Al tener sectores formados, tenemos un mejor punto de partida
para el ruteo de los vehículos, ya que se tendrán límites geográficos para cada sector. Por
ejemplo, cuando tengamos una orden de reparto a un cliente, sabiendo su ubicación,
directamente sabremos a que zona asignarlo y que vehículo lo deberá de atender. Los
sectores permanecen fijos hasta que una nueva prueba se haga. Es decir las rutas cambian
diariamente pero los sectores no.

10
 1.3 Justificación

El trabajo surge de la inquietud de una empresa de reparto a domicilio de reducir el

número de vehículos a utilizar. La empresa apoya la teoría de que para poder realizar esta
minimización primero se debe partir de una sectorización equilibrada en cuanto a carga
de trabajo para asignar a cada vehículo. Esta equidad de sectores también favorecerá la
satisfacción de los empleados ya que no producirá envidias o recelos entre ellos porque
unos trabajen más que otros. Se desea facilitar el trabajo de sectorización, ya que al día de
hoy el proceso es muy rudimentario, impreciso y tardado. Nunca se hace una nueva
sectorización por lo tardado del proceso sino solo se mejora la configuración de los
sectores actuales.

1.4 Objetivos

• Objetivo general
Solucionar “la sectorización”, del problema de reparto modelado bajo el criterio
de las dos fases. Generando un método de solución para fraccionar una zona en
pequeños sectores equilibrados.

• Objetivos Particulares

1. Generar un método de solución que genere sectores con carga de trabajo

equilibrada.

2. Automatizar el método de solución para que su uso sea más fácil y apoye la toma
de decisiones de la empresa.

3. Probar que el método genera buenas soluciones y mejora los intentos ya hechos
en este tema para esta empresa.

11
 1.5 Alcance de la Investigación

La formación de sectores de reparto (Sectorización) para el problema VRP en la

modalidad de las dos fases. La aplicación y prueba de este método a un conjunto de datos
proporcionado por una empresa de paquetería.

1.6 Limitantes de la Investigación

La confidencialidad del nombre de la empresa de la cual se obtuvieron los datos para una
aplicación real. La falta de datos de otra empresa para probar el alcance, comportamiento
y resultados del método de solución.

1.7 Metodología y Métodos

Se utilizan métodos cuantitativos para la creación del método de solución, siendo dos las
metodologías básicas: el método de barrido y el método de MST. La metodología usada
para el marco teórico es la investigación en fuentes bibliográficas y la revisión de trabajos
publicados que abordan este tipo de problema. El método de prueba y error, para ir
creando la heurística que solucionará el problema. También el método de prueba y error
para determinar los parámetros que requiere el programa y que generan la mejor solución
para el caso de aplicación.

12
CAPITULO 2 TRABAJOS Y LITERATURA RELACIONADOS

2.1 Marco del problema dentro de la empresa

Para entender mejor el método de solución propuesto, se presenta una introducción

conceptual desde lo más general hasta lo más particular, terminando en las dos
metodologías básicas a partir de las cuáles se forma el método de solución.

También se ubica el problema abordado por el trabajo dentro del contexto global de la
empresa, siendo la Logística la función principal de la empresa de la cuál se deriva el
concepto de Sectorización.

Partiendo de la función de Logística, una de las estrategias de esta es la de Transporte, y

dentro de esta estrategia se incluye ¿como distribuir el producto o servicio a los clientes
finales?, llamado “problema de reparto”. Este problema puede ser resuelto con dos
enfoques: generar directamente las rutas de reparto o primero generar sectores de reparto
y después generar las rutas para cada sector. En un apartado posterior se mencionan los
métodos usados para ambos enfoques.

Con estos antecedentes se comprende mejor la aportación del método y su importancia

dentro de la empresa. Se enfatiza que el trabajo aporta solo la primera fase para
solucionar el problema de reparto, la “Sectorización”, para la segunda fase se puede usar
cualquiera de los métodos o paquetes comerciales que se encuentran en el mercado.

13
 EMPRESA

Servicios de Planeación Logística Marketing Finanzas

Información Estratégica

Distribución Gerencia de Materiales

Física

Estrategia de Estrategia de Información Estrategia de Estrategia de Ubicación

Inventarios Transporte

Diseño de rutas Capacidad Número de Selección Programación de

(VRP) vehículo vehículos de Modo vehículos

Ruteo Sectorizar primero

Directo rutear después

Sectorizar Rutear

Figura 1. Sectorización dentro de la Empresa

14
 2.2 Logística

2.2.1 Historia

Tan remotamente como lo registra la historia, los bienes que las personas deseaban no se
producían en el lugar donde querían que se consumieran, o no eran accesibles cuando la
gente los quería consumir. Por esta razón el mercado y el consumo de productos se veía
limitado, el consumidor solo podía adquirir los productos que se cosechaban o producían
cerca del lugar donde habitaba, y el productor solo podía vender a aquellas personas en
las cercanías de su zona de producción.

Estos factores limitaban el potencial de venta de los productos, pero conforme el paso de
la historia, los avances tecnológicos han permitido expandir el alcance de venta de los
productos. Algunos de los avances tecnológicos que han aumentado el alcance de venta
son: conservadores, nuevas técnicas de conservación (la refrigeración, envasado al
vacío), los transportes (empezando por la rueda hasta terminar en el avión), los empaques
que permiten proteger los productos durante su traslado y lleguen con sus características
y cualidades intactas, por mencionar algunos.

Así con el paso del tiempo el concepto de Logística también se ha desarrollado y es la

Logística la que ha permitido llevar desde el lugar de producción hasta el lugar de
consumo nuevos productos con más eficiencia en tiempo y costo. Cabe señalar que
conforme ha evolucionado la Logística también los factores que la afectan han
aumentado y por tanto el proceso se complica. Entonces para resolver los nuevos
problemas que día a día aparecen, hay que estudiar el problema y generar soluciones
adecuadas para él.

“La logística añade valor a los productos o servicios esenciales para la

satisfacción del cliente y para las ventas” (Ballou 2004)

15
Se tiene registro que el varón Antoine Henri Jomini, General de Napoleón manifestaba
por los años 1835 que la logística era definida como "el arte de alimentar a los ejércitos"
(Logística 2007). Pero varios investigadores concuerdan que no es sino durante la
Primera Guerra Mundial cuando al término se le da una importancia considerable, al
igual que la Investigación de Operaciones, y es definido como: “Parte de la ciencia
militar que calcula, prepara y realiza todo lo referente a movimientos y necesidades de las
tropas en campaña a fin de conseguir la máxima eficacia de una operación”. Dejando
atrás la historia y enfocando más el término de Logística en los negocios encontramos
varias definiciones:

1. "una función operativa importante que comprende todas las actividades necesarias
para la obtención y administración de materias primas y componentes, así como el
manejo de los productos terminados, su empaque y su distribución a los clientes"
(Ferrel 2004)

2. "el proceso de administrar estratégicamente el flujo y almacenamiento eficiente

de las materias primas, de las existencias en proceso y de los bienes terminados
del punto de origen al de consumo" (Lam 2002)

3. "el movimiento de los bienes correctos en la cantidad adecuada hacia el lugar

correcto en el momento apropiado" (Franklin 2004)

Integrando las definiciones anteriores tenemos que Logística se compone de un conjunto

de técnicas y medios destinados a gestionar: el flujo de materiales y el flujo de
información (notar que en la actualidad la logística se extiende hasta la información y no
solo a los productos tangibles); con el objetivo de satisfacer las necesidades (bienes o
servicios) de un cliente (minorista, mayorista, consumidor final, etc.) en calidad,
cantidad, lugar y momento que el cliente determine, todo esto al menor costo posible. Es
solo bajo estas circunstancias cuando el producto adquiere su valor.

16
OBJETIVOS DE LOGÍSTICA

La Logística como cualquier función de negocio tiene objetivos particulares que serán sus
reglas para actuar dentro de la empresa y son:

1. Responder a la demanda, obteniendo un óptimo nivel de servicio al menor costo

posible.

2. Suministrar los productos necesarios en el momento oportuno, en las cantidades

requeridas, con la calidad demandada y al mínimo costo, y, en todos los casos:
a. Haciendo prioritarias las necesidades del cliente.
b. Flexibilidad necesaria para cubrir las necesidades del mercado cambiante
c. Reaccionando rápidamente ante los pedidos del cliente
d. Eliminar stocks innecesarios hacer que los pedidos del cliente jalen el
proceso productivo.

Cabe mencionar que Logística no es la única función de negocio ni la más importante,

existe también el Marketing, Ventas, Compras, Producción, Sistemas de información,
Finanzas y otros. Esto significa que todas ellas son importantes aunque algunas aporten
mayor costo al producto o servicio debe atenderse cada una de ellas. Y todas en conjunto
deben de trabajar para lograr el mayor beneficio de la empresa y no beneficios
particulares. Debe existir coordinación y colaboración entre todas las funciones para
lograr una mejora continua y llegar a ser líderes en el mercado y mantenerse en esa
posición.

La logística no es una función que se realice una sola vez, sino es una función recurrente
en varias actividades de la empresa, esto se explica porque las fuentes de materia prima o
los puntos de venta muchas de las veces no están en la misma ubicación que las fábricas.
En muchos de los casos y más hoy en día, se realiza nuevamente la función de logística
para llevar de los puntos de venta a los consumidores finales los productos o servicios
deseados.

17
 2.2.2 Procesos de Logística

Considerando el enfoque de Logística de Negocios, los procesos principales de Logística

de la empresa son: DISTRIBUCIÓN FÍSICA y GERENCIA DE MATERIALES, debido
a su directa interrelación, la primera provee a los clientes un nivel de servicio requerido
por ellos, optimizando los costos de transporte y almacenamiento desde los sitios de
producción a los sitios de consumo, la segunda optimizará los costos de flujo de
materiales desde los proveedores hasta la el productor con el criterio JIT. (Ballou 2007)

Logística de la Empresa

Gerencia de Materiales Distribución Física

(Materia Prima) (Producto Terminado)

Fuente de Fábrica/ Clientes

Suministro Empresa

Figura 2. Procesos de Logística

Para lograr la eficiencia de estos dos procesos deben de tomarse decisiones en los tres
niveles de planeación sobre las tres estrategias principales: Inventarios, Ubicación y
Transporte. Si una falla es posible que el proceso sea cual fuere distribución o gerencia de
materiales no pueda realizarse asegurando el menor costo.

18
 2.2.3 Niveles de Planeación

Para lograr los objetivos de Logística de cada empresa es necesario tomar decisiones en
tres niveles de planeación para la empresa (fig ) para responder a las preguntas ¿que?
¿cuándo? y ¿como?. La diferencia entre estos tres niveles es el horizonte de tiempo
considerado. (Ballou 2004)

Estratégica

Táctica

Operativa

Figura 3. Niveles de Planeación

Nivel Estratégico: De largo alcance con horizonte de tiempo mayor a un año, trabaja con
información que por lo general esta incompleta o es imprecisa, los datos usados pueden
ser promedios o estimaciones. Los resultados se consideran adecuados si se encuentran
bastante cercanos a lo óptimo.

Nivel Táctico: Un horizonte de tiempo menor a un año, usa información más precisa y
los resultados deben ser más exactos que los de nivel estratégico.

Nivel Operativo: Toma de decisiones de corto alcance, las decisiones pueden ser día a
día u hora a hora. Utiliza información exacta y los métodos de planeación utilizados en
este nivel deben ser capaces de manejar esta gran cantidad de información y obtener
resultados óptimos.

19
 2.2.4 Estrategias Principales

Las decisiones que deben tomarse en los tres niveles de planeación se refieren a las
cuatro estrategias de logística que permitirán brindar un servicio al cliente adecuado para
el mercado. (Ballou 2004)

Facilidades

Transporte Estrategias Inventarios

Sistemas de
Información

Figura 4. Estrategias Principales de Logística

Estrategia de Inventarios: Son decisiones o políticas que define cada empresa acerca de
cuanto stock en producto en proceso, producto terminado y materia prima quiere
mantener en sus facilidades. Las estrategias de reabastecimiento para los stocks, así como
las políticas para fijar los niveles y controlarlos.

20
Estrategia de Ubicación: Decisiones acerca de donde localizar geográficamente las
facilidades de una empresa, ya sean fábricas, almacenes, Centros de Distribución, puntos
de abastecimiento, etc.., el tamaño o capacidad de las mismas y el número de ellas. Todas
estas decisiones deben de considerar con mucho cuidado el transporte y el costo que este
incurre en llevar desde la materia prima hasta el consumidor final el flujo del material,
esto al menor costo posible.

Estrategia de Transporte: Decisiones acerca del modo de transporte, tamaño de los

envíos, establecimiento y programación de rutas, subcontratación del servicio, etc.. Estas
decisiones son influidas por la proximidad entre facilidades y los inventarios o demandas
que afectan el tamaño de envío.

Estrategia de Sistemas de Información: Esta estrategia es la integradora de las otras

tres, permite la comunicación entre estrategias, explota los beneficios de cada una e
integra los mismos para lograr un impacto mayor. Debe ser considerada como una
estrategia que facilite el proceso de las demás. Debe ser elegida con sumo cuidado para
no desperdiciar el potencial del sistema ni quedarnos cortos en el alcance del mismo.

Para entender mejor la relación entre nivel de planeación y las estrategias principales de
logística se presenta el siguiente cuadro que pone una actividad muestra para cada
interrelación.

21
 Área de Nivel de Decisión
Decisión
Estratégica Táctica Operativa
(Estrategias)

Número, tamaño,
Ubicación de ubicación de
Facilidades almacenes, plantas y
terminales
Ubicación de Niveles de Cantidades y
Inventarios inventarios y inventario de tiempos de
políticas de control seguridad reabastecimiento
Tipos de reportes o Tipos de reportes o
Sistemas de Tipo de sistema a
comunicaciones comunicaciones
Información usar
mensuales diarias

Transporte Arrendamiento de
Diseño de ruta,
equipo, asignación
Selección del Modo asignación de rutas
de zonas de reparto
a vehículos
a vehículos
Tabla 1. Estrategia Logística vs Nivel Decisión

Nivel de Decisión
Estrategias
Estratégica Táctica Operativa

Facilidades
Sist. Inf.
Inventarios
Transporte Formación de Zonas de Reparto
Tabla 2. Sectorización y su relación Estrategia-Nivel Decisión

22
 2.2.5 Clasificación en base al tipo de negocio

Ahora bien, dentro del ámbito de los negocios existen niveles o tipos de negocio por ello
las decisiones acerca de las estrategias no serán las mismas para uno y otro. Se presenta
una clasificación en base al tipo de negocio, sugiriendo que todas aquellas empresas que
pertenezcan a cada uno de estos niveles deben realizar decisiones similares en relación a
las estrategias de logística. Se definen tres niveles y sus actividades: nivel fábrica, nivel
distribuidor mayorista, nivel distribuidor detallista. (MAR 2007)

1. Logística de Producción o del producto (Nivel Fábrica): los productores cuentan

con una serie de medios: fábricas, almacenes, etc., para realizar sus actividades
que incluyen:

a. Compra de materias primas a los proveedores

b. Almacenamiento de materias primas
c. Transformación de la materia prima en productos terminados
d. Almacenamiento de productos terminados

2. Logística de Distribución (Nivel Mayorista): engloba todas aquellas actividades

que realizan los distribuidores y no los fabricantes. Para realizar sus actividades
cuentan con los siguientes medios: almacenes, herramientas de transporte y de
mantenimiento. Las actividades que realizan son:

a. Aprovisionamiento de los almacenes, ya sea un almacén central o centros

de distribución (comprende el transporte del producto terminado al
almacén y el almacenamiento y gestión de stocks en sí)
b. Transporte hacia los puntos de venta

23
 3. Logística de Distribución Comercial (Nivel Distribuidor Detallista o Minorista):
está relacionada con las actividades logísticas que realizan los puntos de venta y
minoristas. Los medios con los que cuentan son: superficie de venta y almacenes.
Las actividades que realizan son:
a. Compra de los productos
b. Almacenamiento de los productos
c. Venta de los productos al consumidor final.

Se observa que sea cual sea el nivel de negocio o el tipo de proceso (distribución física o
gerencia de materiales) una serie de decisiones debe ser tomada para lograr los objetivos
de logística de la empresa. Primero cada empresa define su objetivo primario: lo que
quiere hacer, ofrecer al cliente o lograr en el mercado y en base a esto se desarrolla su
plan logístico. Todas las decisiones logísticas en cualquiera de lo niveles de planeación
deberán de ir alineados a los objetivos primarios de la empresa. Ese objetivo determinará
el enfoque para actuar y decidir sobre las estrategias a implementar.

2.2.6 Costos y Empresas de Servicio

COSTOS
La razón por la cuál a la logística se le ha dado tanta importancia en los últimos años
radica en el costo que esta aporta a los productos o servicios de una empresa y al impacto
que tiene para el servicio y satisfacción del cliente. En un mundo tan cambiante como el
de hoy, donde la competencia es global y las exigencias del cliente son cada vez mayores
en cuestión de rapidez de servicio y menores costos, el menor objetivo de cualquier
empresa es subsistir a la competencia y lograr posicionarse en el mercado haciendo
cautivos a sus clientes y su máximo es ser el líder del mercado. Estamos viviendo un
mercado en el cual la guerra de precios es muy agresiva, día con día debemos de buscar
nuevas oportunidades de mejora para reducir nuestros costos. Una de la áreas a las que
más se han tornado los ojos de las empresas es la logística por incurrir en costos desde un
4% hasta un 30% del total de las ventas (Davis 2002), solo la función de compras le gana
con el 50% a 60%. Es por esto que optimizar la logística, buscar el conjunto de

24
decisiones que nos permita reducir este porcentaje, es y seguirá siendo un área de
oportunidad para cualquier empresa. Todos los esfuerzos que puedan ser realizados para
mejorar esta área serán bien apreciados tanto por la empresa como por el consumidor.

EMPRESAS DE SERVICIO

Todo lo mencionado anteriormente refiere básicamente al sector manufacturero y nos

preguntamos si los conceptos logísticos pueden ser utilizados para empresas de servicio y
la respuesta es sí. Aunque para algunas empresas de servicio no se tenga tan clara la
distribución física o la gerencia de materiales en todas ellas se realizan decisiones sobre
las estrategias logísticas. Por mencionar algunos ejemplos: Federal Express, empresa de
paquetería, debe decidir sobre sus facilidades (que son sus terminales), su transporte
(camionetas, vans, motos) y su distribución física (sus rutas de recolección y entrega).
Otro ejemplo, una iglesia católica, debe decidir sobre el número de iglesias en una región,
su ubicación, su capacidad, el inventario de sus padres y personal de mantenimiento para
la misma (acólitos, sacristanes, monjas voluntarias, etc..), abastecimiento de materiales
(ostias, vino de consagrar) por mencionar algo. (Ballou 2004)

Ubicando la tesis dentro de todo este marco Logístico se dice que el presente trabajo
propone un método de solución para el nivel de planeación Táctico/Estratégico en
cuestión de estrategia de transporte. La estrategia de transporte se limita solo a la parte
de Distribución Física que es la encargada de llevar el producto o servicio al cliente final.
Si consideramos la clasificación en base a la unidad de negocio el problema a resolver se
ubica en el tercer nivel o tipo de negocio, Distribución Comercial.

La importancia de este problema se refleja en el costo en que incurre la empresa para

llevar acabo este proceso entre el 7% y 9% de las ventas totales de la empresa (Davis
2002). Si optimizamos esta área costos considerables se reducen e impactan tanto en el
costo del producto o servicio, utilidades para la empresa y mejora del servicio al cliente,
es decir todos ganan.

25
 2.3 Diseño y Programación de Rutas

2.3.1 Generalidades del Problema

El problema de ruteo de vehículos (VRP) es, aquellos problemas referentes a la

distribución de productos o servicios entre uno o más depósitos y un conjunto de clientes
por un conjunto de vehículos.

Este tipo de problema fue primeramente abordado por Dantzig y Ramser (Dantzig 1959)
y seguido por Clarke and Wright (Clarke 1964). A partir de estos dos trabajos un gran
número de algoritmos, tanto exactos como heurísticos, han sido propuestos como
solución de este tipo de problema. La razón del esfuerzo que se ha hecho por solucionar
este problema es por su importancia práctica, es decir, la aplicación de este modelo a
problemas reales y su impacto en el desempeño de la empresa. Este tipo de problema
tiene un alto grado de dificultad para encontrar la solución óptima en problemas grandes,
es por eso que tantos métodos han sido desarrollados y siguen desarrollándose.

La distribución de productos es el servicio a un conjunto de clientes, en un período de

tiempo determinado, por un número dado de vehículos, localizados en uno o varios
depósitos, operados por un conjunto de chóferes y que realizan sus movimientos en un
conjunto de vías o calles (llamada red vial).

La solución del problema VRP se resume a encontrar el conjunto de rutas, cada una
realizada por un vehículo que sale del depósito al empezar la ruta y regresa al depósito al
terminar la ruta, tal que satisfagan los requerimientos del cliente y no violen ninguna
restricción de operación determinadas con anterioridad y el costo total de transporte sea
minimizado.

Normalmente una red vial es representada como un grafo formado por un conjunto de
arcos que representan una fracción de calle y por nodos o vértices que unen un arco con

26
otro y representan a los clientes y al depósito. Los arcos del grafo pueden ser
unidireccionales si el sentido de la calle es uno y bidireccional si el sentido de la calle es
doble. Cada arco tiene asociado un costo, que generalmente representa el tiempo de
traslado entre nodos o la distancia recorrida entre ellos. Estos arcos pueden ser
asimétricos o simétricos, el primero si no es lo mismo ir de A-B, que ir de B-A, el
segundo si el arco cuesta lo mismo A-B = B-A. Se presentan las características de cada
una de las entidades que intervienen y las restricciones del problema. (Toth 2002)

CARACTERÍSTICAS DE LOS CLIENTES

• Demanda: cantidad y tipo de producto a recolectar o entregar al cliente.

• Tiempo de entrega (Time Windows): tiempo en el que el cliente está dispuesto a
entregar o recibir el producto.
• Tiempo de carga y descarga: tiempo que tarda el operador en cargar o descargar
los bienes del vehículo y entregarlo al cliente en su ubicación.
• Vehículos que pueden servir al cliente: es posible que por el tipo de producto que
el cliente maneja no todos los vehículos (si son diferentes) sean capaces de dar
servicio a ese determinado cliente.

CARACTERÍSTICAS DE LOS VEHÍCULOS

• Depósito asignado: depósito al cuál reporta ese vehículo y la posibilidad de

regresar a otro depósito si es necesario.
• Capacidad del vehículo: peso, volumen o número de pallets máximos que el
vehículo puede manejar.
• Tipos de compartimientos del vehículo: cada compartimiento puede llevar solo
cierto tipo de productos.
• Accesorios disponibles para la carga y descarga de productos.
• Subconjunto de vías o calles del grafo que el vehículo puede recorrer: si es un
vehículo grande no podrá transitar calles angostas.
• Costo asociado con la utilización del vehículo

27
RESTRICCIONES DEL PROBLEMA

Las rutas que forman parte de la solución del problema deben de respetar las restricciones
de operación que dependen de varios factores como: naturaleza del producto, calidad del
servicio, características de los clientes y de los vehículos. Las más comunes son:

• No sobrepasar la capacidad de carga de los vehículos.

• Las rutas no deben de exceder el tiempo del turno de trabajo para los operadores.
• Las rutas visitan el depósito por lo menos una vez.
• Los clientes son atendidos solo por una ruta.

OBJETIVOS DEL PROBLEMA VRP

• Minimización del costo total de transporte.

• Minimización del número de vehículos a utilizar.
• Balanceo de rutas (en tiempo o distancia del recorrido o carga del vehículo).
• Minimización de penalidades asociadas con el servicio parcial a los clientes.

Cuando un problema VRP incluye varios depósitos, puede dividirse el problema en

varios subproblemas de menor tamaño e independientes unos de otros, cada problema
integrando un depósito y un conjunto de clientes a atender. De esta manera se simplifica
la solución de cada uno de ellos y del problema original.

28
 2.3.2 Clases de VRP

™ CVRP: VRP con restricción de Capacidad

Esta clase de VRP es aquella donde todos los clientes corresponden a una entrega y las
demandas son determinísticas, conocidas y que no pueden separarse. Los vehículos
utilizados son idénticos, existe un solo depósito y solo hay restricción de capacidad de los
vehículos (puede ser peso o volumen). El objetivo es minimizar el costo total de servir a
todos los clientes.

Si los arcos son asimétricos el problema es ACVRP y si son simétricos es SCVRP. Si el

problema ubica los clientes en un mapa y su ubicación corresponde a coordenadas en el
mismo, el costo del arco será la distancia euclidiana entre puntos y los arcos serán
simétricos, por lo que el problema es llamado SCVRP euclidiano.

Para asegurar la factibilidad del problema se tienen un número “k” de vehículos, dado
que “k” sea mayor o igual al número mínimo de vehículos necesarios para atender a
todos los clientes, este número mínimo puede obtenerse resolviendo el problema con
anterioridad bajo el concepto del problema de la mochila, teniendo una capacidad
supuesta y un número “n” de clientes a asignar.

El CVRP consiste en encontrar un número “k” de rutas, cada una asignada a un vehículo,
cuya suma sea el mínimo costo y que cumpla que la suma de las demandas de los clientes
de cada ruta no excede la capacidad del vehículo que los atiende.

Algunas variantes de este problema son: aquellas donde las capacidades de los vehículos
son variables; cuando las rutas que visitan a un solo cliente no son aceptadas; cuando el
número de vehículos disponibles es mayor al número mínimo de vehículos requeridos y
se dejan vehículos sin utilizar, en este caso se tienen que crear el número de rutas igual al

29
número de vehículos disponibles. Esta clase de problema se asemeja mucho al problema
del agente viajero (TSP).

Otra variante de esta clase es el llamado VRP con restricción de distancia (DVRP), este
tipo de problema tiene restricción de capacidad traducida en la distancia máxima (o el
tiempo máximo) que el vehículo puede recorrer para realizar su ruta. En este caso el costo
del arco es la distancia entre nodos o el tiempo que se tarda el vehículo en trasladarse de
un nodo a otro. Así también si se tienen los tiempos que tarda el vehículo en servir a un
cliente (tiempo en descargar su mercancía, tiempo en estacionarse u otros), el costo total
del arco será el tiempo que tarda en moverse de A-B más el tiempo que tarda en surtir B.
Y el objetivo de este problema es minimizar la longitud de las rutas o la duración de las
mismas. Si el problema considera capacidad de vehículo y restricción en distancia o
tiempo de recorrido el problema es llamado CDVRP.

™ VRPTW: VRP con ventanas de tiempo

Es el tipo de problema donde se le agrega un período determinado de tiempo (ventana de

tiempo) en el cuál se puede atender a cada cliente. Su aplicación más común es para
aquellos establecimientos que tienen horario de recepción de mercancía, digamos los
lunes y martes de 10:00 a 13:00 hrs., la ventana de tiempo será (10-13 hrs los lunes y
martes).

Entonces el problema se define como un problema de generación de rutas con

restricciones de capacidad y período de entrega para cada cliente. Se especifican los
tiempos en que cada vehículo sale del depósito, el tiempo de viaje entre nodos para cada
arco y el tiempo de servicio o de atención para cada cliente (si). El problema restringe al
vehículo a servir a cada cliente durante su ventana de tiempo y a durar en la ubicación del
cliente el tiempo de servicio definido para él (si). Si un vehículo llega antes de empezar la
ventana de tiempo de algún cliente, ese vehículo deberá de esperar en el lugar sin hacer
nada a que la ventana de tiempo empiece y pueda servir al cliente que visita.

30
El problema tiene una matriz de costo y tiempo normalmente simétrica, pero las ventanas
de tiempo inducen cierta orientación a las rutas por lo que el problema se modela como
un problema asimétrico. Se supone que los vehículos parten del depósito en el tiempo 0.

La solución del problema es encontrar rutas de mínimo costo que cumpla que la suma
de demandas de los clientes que visita una ruta no excede la capacidad del vehículo y que
cada cliente sea atendido durante su ventana de tiempo y el vehículo se queda en ese
lugar el tiempo (si).

™ VRPB: VRP donde primero se realizan las entregas y luego las recolecciones

Este problema supone dos conjuntos de clientes, aquellos a los que se les entrega
producto (A) y aquellos de los cuáles se recolecta producto (B). El problema tiene
restricción de precedencia, es decir primero tiene que visitar a todos los clientes del
conjunto A antes de atender a cualquier cliente del conjunto B. La solución del problema
es encontrar el conjunto de rutas de mínimo costo donde la suma de las demandas de los
clientes visitados (de entrega y recolección, separados) no excede la capacidad del
vehículo y en todas las rutas las entregas preceden a las recolecciones

Para saber el número de vehículos que se deben de tener se resuelve el problema con la
asignación de la mochila, uno para las recolecciones y otro para las entregas, entonces mi
número k de vehículos debe ser mayor o igual que el máximo de la k de recolecciones y
de la k de entregas. Y lo mismo se hace para determinar la capacidad del vehículo,
resolver el problema de la mochila referido en capacidad para recolecciones y luego para
entregas, se toma la mayor capacidad de ambas y esa será la capacidad a usar para el
problema VRP.

31
 ™ VRPPD: VRP con entregas y recolecciones mezcladas

Este problema aborda la situación donde las entregas pueden ser entre clientes, es decir
un vehículo recoge producto de un cliente para entregárselo a otro cliente en la ruta. En
los problemas anteriores esta situación no existe, lo que se recolecta de los clientes se
lleva al depósito y de ahí partirá una nueva ruta. O lo que se entrega a los clientes
siempre viene del depósito.

En este problema los clientes pueden tener dos demandas, d1 es la cantidad de producto
que se entrega al cliente y d2 la cantidad que se recolecta de ese cliente.A veces se
simplifica en una, siendo D= d1- d2 para cada cliente. También para cada cliente se
denota un Oi y un Pi, siendo Oi el nodo del cuál viene el producto a entregar al cliente i y
Pi el nodo al cual se le entrega lo recolectado del cliente i. La carga del vehículo en un
determinado punto es la carga inicial del vehículo más las recolecciones menos las
entregas. La solución es encontrar el conjunto de rutas de mínimo costo donde la carga
del vehículo debe ser positiva y no debe exceder en ningún punto la capacidad; para cada
cliente i, el cliente Oi, si es diferente del depósito, debe ser servido por la misma ruta de i
y antes del cliente i; para cada cliente i, el cliente Pi, si es diferente del depósito, debe ser
servido por la misma ruta de i y después del cliente i. (VRP 2007)

32
 2.3.3 Métodos de Solución
1. Ramificación y acotamiento (Nemhauser 1988)
a. Relajaciones combinatorias básicas
i. Problema de Asignación (El-Farzi 1992)
ii. Árbol de costo mínimo
iii. Relajación de espacio y estado
b. Relajaciones Lagrangianas
c. Enfoque Aditivo
2. Ramificación y corte
3. Cubrimiento de conjuntos
4. Heurísticas
a. Métodos Constructivos
i. Criterio de ahorros (Clarke 1964)
ii. Criterio inserción
Los incisos a y b pueden utilizar el criterio que mejor se adapte al
problema, de menor costo, más cercano, más lejano o
aleatoriamente.
a. Secuencial (Mole 1976)
b. Paralelo (Potvin 1963) (Christofides 1979)
b. Métodos de dos fases
i. Sectorizar Primero-rutear después (González 2007)
ii. Rutear primero-sectorizar después (Goleen 1984) (Beasley 1983)
c. Métodos de mejora (Búsqueda Local) (Lin 1965) (Renaud 1996)
5. Metaheurísticas
a. Recocido simulado (Bergey 2003)
b. Búsqueda Tabú (Glover 1986) (Taillard 1993) (Vigo 2003)
c. Algoritmos genéticos (Holland 1975)
d. Colonia de hormigas (Gambardella 1996)
e. Redes neuronales

33
Heurísticas: Desarrolladas entre los 60´s y 90´s, realizan una exploración limitada del
espacio de solución, normalmente producen buenos resultados con tiempos de
procesamiento computacional pequeños.

Métodos Constructivos: Gradualmente van creando una solución factible sin dejar de
considerar siempre el costo de la solución, no contienen fase de mejora o refinamiento.

Métodos de dos fases: El problema es descompuesto en sus dos componentes naturales, la

primera sectorizar los vértices en rutas factibles y la segunda construir las rutas finales,
con posible retroalimentación entre ambas.

™ Sectorizar primero – Rutear después

En este caso los clientes son agrupados en sectores factibles y después se
construye una ruta para cada sector.
™ Rutear primero – Sectorizar después
En este caso primero se genera una ruta con todos los clientes y después se va
partiendo la ruta en rutas más pequeñas factibles, cada ruta final sería un sector.

Métodos de mejora (Búsqueda Local): Su finalidad es mejorar las soluciones obtenidas

anteriormente, realizando un intercambio de nodos o arcos entre rutas vecinas o en la
misma ruta.

Metaheurísticas: Desarrolladas de los 90´s a la fecha, se enfatizan en explorar más a

detalle los espacios de solución más prometedores, normalmente combinan reglas de
búsqueda de vecindad, estructuras de memoria y recombinación de soluciones, generan
mejores resultados que las heurísticas pero su tiempo de procesamiento es mayor.

Revisar los trabajos de Laporte (Laporte 1987) y (Laporte 1992) para tener una idea
general de los métodos exactos usados para la solución de este problema.

34
Con lo mencionado en esta sección podemos mencionar una serie de similitudes que hay
entre el problema VRP y el planteamiento de sectorización para este trabajo. Se inicia
desde el punto de vista que la sectorización y el ruteo no son la misma cosa, más si usan
términos, situaciones y métodos similares.

Para el problema de sectorización tenemos el mismo tipo de entidades que para el

problema de ruteo: clientes, depósitos y vehículos, así como los recursos de tiempo,
distancia y capacidad. De esta misma manera también tenemos una red formada por todos
los clientes y los caminos que se forman entre ellos.

En base a todo esto y a la teoría presentada se observa que entre el VRP y el problema de
sectorización, el tipo de problema que mejor se ajusta a la sectorización es el CVRP. Solo
debe hacerse ciertas consideraciones, la restricción de capacidad es considerada como
distancia y el límite de capacidad lo dicta el mismo peso del árbol de todos los puntos o
clientes. El enfoque del trabajo utiliza la distancia euclidiana entre puntos cuyos arcos
son simétricos y bidireccionales. Lo que debe diferenciarse es que la sectorización no
generará una ruta para los vehículos, aún cuando se estima el recorrido gracias a un árbol
de costo mínimo, y que los arcos no representan una red vial solo las uniones entre
clientes y su distancia euclidiana. La red vial en nuestro caso no es un factor crítico ya
que no es el objetivo primordial el generar rutas.

La distancia que se estima para el problema de sectorización no considera un retorno al

depósito, ni el regreso de los vehículos cuando llega a un punto cualquiera, por ser la
metodología del árbol de costo mínimo, por todo esto no se puede lograr una ruta. Para el
problema de sectorización esta distancia es suficiente ya que se considera el mismo
criterio para todos los sectores además de que el objetivo del método de solución es
equilibrar sectores en base a trabajo traducido en distancia recorrida. Esta es otra
similitud con los problemas VRP que consideran como una de las funciones objetivo el
equilibrio, pero en su caso de rutas.

35
Una similitud más del CVRP con el problema de sectorización abordado es considerar
vehículos del mismo tipo y con igual tamaño de capacidad, además de solo admitir tener
un solo depósito para atender a todos los clientes.

Además de lo mencionado, el método de solución también considera el peso de paradas o

tiempo de servicio de cada punto, aunque se limita a que todos los puntos deben tener el
mismo peso. El tiempo de servicio se traduce a distancia para uniformar las unidades y
trabajar solo en el equilibrio de sectores basándose en la distancia recorrida en cada
sector.

Ya definida la concepción del problema, se hace referencia en similitudes de los métodos

de solución que utiliza el VRP y el método de solución del método propuesto. En general
el trabajo presentado puede considerarse como parte de un problema más grande, el de
rutear vehículos. Como el alcance del presente trabajo es solo la solución de la
sectorización, puede considerarse el problema completo como un VRP con enfoque de
dos fases: Sectorizar primero y Rutear después.

El método de solución que aporta el trabajo es una heurística creada en base a dos
metodologías básicas: barrido y MST. La metodología de barrido es un tipo de heurística
que considera la inserción de puntos siguiendo el criterio del más cercano que en este
caso será también el de mínimo costo, por ser el costo una traducción de distancia. Este
trabajo se limita a ser una heurística sin métodos de mejora, por lo que aquí tenemos una
de las oportunidades para trabajos posteriores.

36
 2.4 Sectorización

Como ya se menciono en la sección anterior el concepto de Sectorización puede existir

dentro del contexto de un VRP o como un problema de sectorización independiente
donde solo se busca generar clusters o sectores para un fin diferente al de generar rutas de
reparto.

2.4.1 Fundamentos

La formación de distritos o sectorización es un concepto que aplicado nos ayuda a

atender la demanda de una manera más eficiente, ya sea que los sectores se creen con el
objetivo de ser atendidos por facilidades o por medios de transporte (si se ve en el
contexto de VRP). Si es con el objetivo de ser atendidos por facilidades algunos ejemplos
serían: casillas electorales, escuelas, hospitales, oficinas de pago de luz, agua, etc…

La sectorización se define entonces como “la división de una región en zonas más
pequeñas siguiendo ciertos criterios y con un fin específico”. Las características básicas
que cualquier sector debe tener son (Mehrotra 1998):

• vecindad o contigüidad
• compacidad
• equilibrio (poblaciones heterogéneas o cargas equilibradas)

Estas características dictan los criterios para formar los sectores, aunque dependiendo del
problema a resolver pueden generarse criterios particulares o limitantes que ajusten mejor
el modelo del problema. Las zonas formadas son llamadas “distritos o sectores” y cada
uno es independiente y responsable de las actividades generadas dentro de sus límites
establecidos.

37
Los conceptos de sectorización y ruteo aunque parecidos no son lo mismo, bajo la
perspectiva de planeación existe una diferencia fundamental. Mientras la sectorización se
da a un nivel táctico o estratégico, el ruteo se da a nivel operacional (Muyldermans
2003). Si se realiza una buena sectorización y se habla en el contexto de VRP, la
formación de rutas de estos sectores dará muy bueno resultados y se simplificará el
proceso de formación de las mismas. Normalmente la sectorización se realiza después de
que han sido ubicados los centros de distribución, depósitos o almacenes y el problema
entonces se convierte en ¿que clientes debe atender cada depósito, o que conjunto de
puntos debe visitar cada vehículo de reparto?, con esto no estamos indicando la ruta del
vehículo sino un espacio físico con límites o fronteras llamado “sector”.

La aplicación más típica del concepto de sectorización es el problema de “Formación de

Distritos Electorales”. Dentro de la literatura se puede encontrar diversos trabajos que
abordan esta problemática con casos reales y sugieren métodos de solución que brindan
buenos resultados. Otras aplicaciones aunque no tan comunes pero no por eso menos
importantes son: asignación de alumnos a las escuelas, formación de territorios de venta,
sectorización de la población para brindar servicio médico, de bomberos, de policía y
servicios similares, sectorización de la población para atender emergencias o desastres

La sectorización es, en conclusión, “la división de una unidad mayor en entidades más
pequeñas considerando los criterios específicos del problema a resolver, en general lo que
se pretende es: formar nuevas entidades de características similares y lo más compactas
posibles”.

La formación de distritos electorales como se menciono antes es el problema más

estudiado en la literatura y se detalla a continuación. Parte de tener una población muy
grande y con el objetivo principal de formar sectores pequeños que sean heterogéneos en
población para evitar el “gerrymandering” (termino acuñado en 1812 por la legislatura de
Massachussets, EUA). La población puede estar dividida previamente en unidades

38
menores como los distritos políticos y en algunos casos estas divisiones se convierten en
una nueva restricción, cuando se requiera respetar los límites de estos o ajustar los límites
de los sectores a crear con los de los distritos políticos. Esta sería una restricción
particular del problema. La restricción de heterogenización de la población de cada
sector, se logra equilibrando en base a raza, ideologías y preferencias políticas, para
lograr esto se ponen límites o estándares que hay que cumplir. Por ejemplo, no exceder
un porcentaje de demócratas ni de conservadores, no crear distritos únicos de población
afroamericana, blanca o latina, no formar distritos de cristianos, protestantes, católicos,
mormones, etc…El fin es formar sectores que combinen todas estas posibilidades y que
la mezcla de población lograda evite el “gerrymandering”, que significa que algún sector
tenga preferencia por algún candidato o partido político. De esta manera los candidatos
en todos los distritos tienen la misma probabilidad de ganar ya que ningún grupo político,
de raza o de otras preferencias domina un distrito, es decir la población del distrito
formado permanece heterogénea. Hay que considerar que para lograr esto es probable
que los distritos no cumplan con la restricción de contigüidad o de compacidad, por esto
hay que tener criterios de negociación y ceder en ambos sentidos, ponderar para nuestro
problema que criterio es más importante que el otro y negociar los resultados.

Otra aplicación de la sectorización es para la problemática de la asignación de alumnos a

las escuelas (Caro 2004), la restricción de población heterogénea se fundamenta en el fin
de integrar a la población y fomentar la convivencia entre razas, por esto debe generarse
un equilibrio de la población que acude a cada escuela considerando los factores de raza,
religión y costumbres. Este tipo de aplicación puede incluir restricciones particulares
donde una de ellas se refiere a la distancia máxima a recorrer por los alumnos de su casa
a la escuela. Esta restricción se impone para evitar que por equilibrar la población un
alumno tenga que recorrer una distancia inhumana poder llegar a su escuela. Otra
restricción que se genera como protección a los alumnos es: evitar que los alumnos
crucen avenidas de mucho tránsito, ríos, lagos u otro obstáculo que los ponga en riesgo.
Hay que considerar también los escenarios futuros, ya que no todas las escuelas ofrecen
los mismos grados, por ello hay que asignar a los alumnos considerando los años que
estos pasaran en cada escuela, considerando la demanda y oferta de los cursos.

39
La aplicación de sectorización para la formación de territorios de venta fue abordada en
un principio por (Hess 1971) (Zoltners 1980) (Heschel 1977), esta aplicación es la que
más se asemeja al problema estudiado, se tienen las siguientes restricciones:

1. Igualar la carga de trabajo por agente (Easingwood 1973), esto medido en

kilómetros viajados para visitar a los clientes, número de llamadas realizadas para
lograr la venta
2. Equilibrar las zonas de acuerdo al potencial de venta que cada cliente tiene
(Lodish 1974), medido en base al poder adquisitivo de cada cliente.
3. Considerar múltiples objetivos que en la actualidad es la tendencia de los
problemas a resolver, este enfoque fue primeramente abordado por Zoltners en
(Zoltners 1979). Se integra aquí la distancia, el potencial, los gastos de venta,
etc…

Para este tipo de problema se considera que el encargado de ventas debe tener especial
cuidado en la sectorización de las regiones para evitar la baja moral de los empleados, el
bajo desempeño y la baja productividad de la fuerza de ventas. Una sectorización
balanceada arroja datos más consistentes y efectivos para evaluar individualmente
(Shanker 1975). Si la sectorización no esta bien realizada los resultados individuales no
son confiables y puede tomarse decisiones equivocadas en cuanto al desempeño de la
gente. Por esto la sectorización debe hacerse con sumo cuidado y a nivel estratégico o
táctico para evitar problemas operacionales e insatisfacción en el personal.

Para esta aplicación el criterio de contigüidad y de compacidad se aborda con la solución

de ir agregando a cada zona de ventas colonias vecinas a las que ya se tiene dentro del
sector o usar el criterio de códigos postales y de ahí sacar una solución preliminar (Hess
1971), esto es todas aquellas colonias, zonas o regiones con el mismo código postal
formarán una zona. Esta restricción se asemeja al caso de los distritos electorales donde
se tiene la restricción de los límites de los distritos políticos. Así mismo la
heterogeneidad de los sectores debe cumplirse para evitar insatisfacción de los

40
vendedores, por ejemplo, si se realiza una sectorización y en uno de los sectores
formados resultará que están todos los clientes de mayor demanda, los agentes de ventas
de los otros sectores y con justa razón estarían molestos porque su mercado es inferior al
de este sector, es por eso que se debe de lograr el equilibrio en base a este tipo de factores
y heterogenizar la población de clientes en cada sector formado evitando así problemas
operacionales y de insatisfacción del personal.

A través del tiempo la sectorización se ha logrado utilizando diversos métodos (Coth

2002):

A. Métodos de Asignación
B. Métodos elementales de sectorización
Algoritmo de Barrido (Wren 1972) (Gillet 1974)
Algoritmo de Fisher and Jaikumar (Fisher 1981)
Algoritmo Bramel y Simchi-Levi (Bramel 1995)
C. Método de pétalos o de las margaritas (Balinski 1964)
D. Como problema de diseño de rutas utilizando todos los métodos mencionados
en el apartado anterior

El problema de sectorización es de tipo NP-duro (Galvao 2006), lo que significa que la

solución óptima solo puede encontrarse evaluando todas las posibilidades, lo que genera
una complicación computacional, conforme la información aumenta. Por esta razón se
proponen metodologías y heurísticas que si bien no conducen al óptimo si generan
buenos resultados. Además como se menciono en la sección de Niveles de Decisión en la
función Logística, para el nivel estratégico una buena solución es aceptable y bien
recibida.

Como se menciono el problema abordado por el trabajo tiene similitud con la formación
de zonas de venta, primeramente porque ambos se refieren en el contexto empresarial,
segundo porque se enfocan en equilibrar sectores en base a carga de trabajo y tercero
porque buscan la solución que ayude a reducir tensiones laborales.

41
Todo lo que se comento sobre insatisfacción acerca de sectores desequilibrados también
aplica para el problema del trabajo, si no se tiene este equilibrio es posible que la segunda
parte del problema el ruteo, se generen rutas dentro de cada sector que excedan el tiempo
de trabajo de un turno y puede existir también el caso donde una ruta este demasiado
sobrada en tiempo. Esto nos implica que empiecen a existir recelos entre los mismos
empleados, que se empiecen a formar malas mañas para aquellos cuyo tiempo les sobra,
se tomen descansos que no deben, usen los vehículos para pasear y otras situaciones. Y
para aquellos que tienen muy cargada la ruta que manejen a velocidades no adecuadas,
que sean descuidados y causen accidentes, que traten mal al cliente, lo apresuren o lo
atiendan de mala gana, incluso que no le den el servicio porque ya se acabo el turno.

Se dice “en teoría una óptima segmentación es aquella en la que se crean unidades
funcionales con igual oportunidad de ser rentables” (Bergey 2003), adecuándolo al
problema, “formar sectores que tengan cargas de trabajo similares y la capacidad de dar
el mismo nivel de servicio al cliente”.

42
 2.4.2 Comparación de trabajos publicados sobre el tema

Referencia Aplicación del problema (diseño de rutas,

Tipo de Problema Método usado Tipo Método
Bibliográfica zonas o ambos)

Localización de una Algoritmo genético vs Clusterizar y rutear para minimizar la distancia

(Gonzalez
facilidad (Empresa heurísticas de barrido y Heurísticas total que los vehículos deben recorrer para
2007)
Manufacturera) búsqueda local distribuir el producto de la empresa
Formación de zonas de distribución que sean
Formación de distritos para SAGA (Algoritmo Genético de
económicamente viables para nuevas empresas,
(Bergey 2003) la distribución eléctrica de Recocido Simulado) vs PSA Heurísticas
para romper el monopolio de distribución
Ghana (Recocido Simulado Paralelo)
eléctrica en la República de Ghana

Formación de zonas electorales que respeten

Metodología de ramas y costos,
límites políticos y subunidades anteriores,
(Mehrotra para la optimización. Heurísticas y
logrando equidad de población y zonas
1998) Rediseñar distritos políticos. Programación entera y métodos
compactas. Modela el problema como una
generación de columnas para la exactos
división de grafo, siendo los nodos las
primera fase de solución.
subunidades anteriores.

Programación lineal (Matriz de Formación de zonas de venta para asignar a

Formación de regiones de Métodos
(Hess 1971) costos de transporte, calculo de cada agente, basándose en subunidades de
venta exactos
centroides) código postal para formar la zona de venta

Formulado como una red de Ubicar prisiones, determinar capacidades y

Planeación de: localización
(Marianov transporte y resuelto con Métodos asignar provincias de chile a las prisiones
de prisiones, su capacidad y
2005) programación lineal (Cmplex exactos (formación de zonas), para minimizar el costo
su sectorización
7) del sistema, considerando el futuro.
Modela el problema como un grafo y se forman
Formación de Territorios Old Bachelor Acceptance zonas en base a la distancia recorrida entre
(Ricca 2004) Heurísticas
Heuristic (Similar al SA) nodos, respetando criterios de contigüidad,
zonas compactas y equilibradas

Tabla 3. Tabla Comparativa de Trabajos Publicados

43
 Referencia Aplicación del problema (diseño de rutas,
Tipo de Problema Método usado Tipo Método
Bibliográfica zonas o ambos)
Técnica multivariada del
(Cano- Formación de distritos Enfoque Forma distritos en base a las características de
análisis de componentes
Guervos 2003) (cualquiera) subjetivo las viviendas de la población
principales
Forma zonas de reparto, uniendo ubicaciones
(Haugland Formación de zonas de Heurística Multiinicio vs Tabu de clientes y evaluando el costo de transporte
Heurísticas
2007) reparto search entre ellos, la técnica más favorable fue Tabú
Search
Método fisico estadistico (q-
Forma zonas de elección considerando el
Formación de distritos state Potes Model) para Simulación y
(Chou 2006) equilibrio de la población y la contigüidad de
electorales resolver y para optimizar el Heurísticas
sus subunidades en la ciudad de Taipei.
método MonteCarlo o SA.
Forma zonas de reparto, relajando los límites
Formación de zonas de Diagramas Voronoi MW de las subunidades iterativamente hasta lograr
(Galvao 2006) Heurísticas
reparto (multiplicatively-weighted) una mejor utilización de tiempo y capacidad de
los vehículos.
Forma zonas y compara los resultados con un
Formación de distritos software de la Universidad de Leeds (ZDES)
(Bacao 2005) Algoritmos Genéticos Heurísticas
electorales que usa recocido simulado, los GA generan
mejores resultados.
Programación Lineal y Forma zonas en base a criterios particulares, se
Reajuste de distritos para Métodos
(Caro 2004) Sistemas Geográficos de apoya en un software que agrega los factores
asignación a las escuelas exactos
Información (GIS) geográficos al problema.
Programación lineal y métodos Forma zonas de distribución considerando el
(Muyldermans Formación de distritos para de asignación de nodos (uno se recorrido que hará el vehículo saliendo y
actividades de reparto o Heurísticas
2003) basa en un Emin ratio y el otro regresando a un depósito y recorriendo todos
servicio en Cmin ratio) los puntos dentro de la zona.

Tabla 3. Tabla Comparativa de Trabajos Publicados… Continuación

44
 Referencia Aplicación del problema (diseño de rutas,
Tipo de Problema Método usado Tipo Método
Bibliográfica zonas o ambos)

Aplicación a la ciudad de Pensilvania,

Formación de distritos para
(Yang 2004) Simulación y herramientas GIS Simulación formación de zonas para mejorar el servicio
bomberos
brindado, el método produce buenos resultados

Aplicación para el Hospital Cote des Beiges,

Montreal, formación de 6 zonas de atención
Formación de distritos para médica a domicilio. Con 5 criterios a respetar:
(Blais 2003) Tabu search Heurísticas
atención médica respetar unidades básicas, respetar límites
municipales, conectividad, transporte del
personal, y equilibrar cargas de trabajo

Formación de distritos Formar zonas electorales, aplicación a los

(Forman 2003) Algoritmos Genéticos Heurísticas
electorales estados de Carolina del Norte y sur y Iowa.

Formación de zonas electorales, formula el

(Bozkaya Formación de distritos
Tabu Search Heurística problema con una función multicriteria,
2003) electorales
presenta resultados para la ciudad de Edmonton

Forma zonas de servicio, modela el problema

(D´Amico Rediseñar los límites para la como un problema de división de grafo,
Recocido simulado Heurística
2002) policía considera también criterios de calidad de
servicio

(Chabrier Método
Ruteo de Vehículos Generación de columnas Encuentra la ruta mínima para los vehículos
2006) exacto

(Rousseau Generación de columnas y Método Forma rutas, busca el camino más corto con
2004) Ruteo de Vehículos programación restringida Exacto programación restringida.

Tabla 3. Tabla Comparativa de Trabajos Publicados… Continuación

45
 2.4.3 Método de solución vs trabajos publicados

Al comparar los diferentes trabajos sobre el tema se encontró que la mayoría de la

literatura propone métodos heurísticos para la solución de este problema. Esto derivado
de que el problema es NP-duro, muy difícil de encontrar la solución óptima cuando la
cantidad de información crece, por lo que una heurística que genere buenas soluciones es
aceptable, solo con la condición que el tiempo de procesamiento sea corto.

A continuación se compara la forma de solucionar los tres criterios básicos de

sectorización de los trabajos citados y del método de solución:

Equilibrio
La mayoría de los trabajos se enfoca a los problemas de distritos electorales y estos
difieren del trabajo en el énfasis que le dan a la igualdad de población, equilibrar las razas
y las preferencias políticas. El problema del trabajo no incurre en estos objetivos, si bien
quiere equilibrar algo no es la población de clientes sino la carga de trabajo en los
sectores. Los artículos que abordan este problema son: (Mehrotra 1998) (Chou 2006)
(Bacao 2005) (Forman 2003) (Bozkaya 2003). De estos el que usa una teoría de grafos es
(Mehrotra 1998) pero la utiliza inversamente al problema del trabajo, el peso lo coloca en
los nodos mientras que el método de solución ubica el peso en los arcos del grafo.

(Hess 1971) equilibra sectores en base al potencial de ventas para cada sector, (Marianov
2005) (Ricca 2004) en base al tiempo de recorrido dentro de los sectores, (Haugland
2007) en base al costo de transporte entre puntos, (Galvao 2006) en base a la utilización
en capacidad y tiempo del vehículo, (Muyldermans 2003) en base al recorrido entre
puntos y su salida y regreso al deposito, (Blais 2003) en base a carga de trabajo
(pacientes atendidos, distancia recorrida para llegar a ellos, disponibilidad de transporte
publico, etc), (D´Amico 2002) en base al tiempo de respuesta dentro de los sectores.

46
De todos estos los más similares al método de solución son (Marianov 2005) (Ricca
2004) y (Muyldermans 2003), aunque a diferencia de este último el método solo
considera la salida del vehículo desde el depósito más no su regreso.

Compacidad y contigüidad
En cuanto a los criterios de compacidad y contigüidad la mayoría de los trabajos
considera como buena opción ir insertado aquellos puntos que se encuentren más
cercanos al que ya se ha seleccionado y en este caso es el mismo proceso para el método
de solución. Para el método de solución el punto más cercano es aquel que le sigue
tomando como referencia el ángulo de su coordenada polar y la compacidad del sector se
estima con el peso del sector usando la metodología de MST que asegura la ruta mínima
entre puntos. En el caso de (Hess 1971) no se usa distancia sino la ubicación física de
las colonias, si esta al lado de la colonia ya seleccionada se puede elegir, sino no, este
criterio se conoce también como de vecindad. También es utilizado por otros trabajos en
los que se define el problema usando un grafo, aquí la vecindad se restringe cuando un
nodo no tiene un arco que lo una a otro, la unión no se puede hacer porque esos dos
nodos no son vecinos. La otra opción es la de asignar penalizaciones para la uniones
entre nodos no vecinos. (González 2007) utiliza al igual que el método de solución el
algoritmo de barrido para la inserción de puntos, (Ricca 2004) y (Muyldermans 2003)
consideran el punto más cercano como el punto al que se recorre la mínima distancia para
llegar a él. (Mehrotra 1998) considera la distancia del centro del sector a sus fronteras, y
así asegurar su criterio de compacidad.

Si la metodología abordada por (Bergey 2003) se adaptará al problema del trabajo, las
pequeñas unidades serían las colonias y estás se combinarían para formar un sector de
reparto que posteriormente sería asignado a un vehículo. El problema es que no se podría
partir una colonia para poder equilibrar los sectores y por tanto la carga de trabajo no
sería equitativa. Algo importante es que no debe de considerarse el equilibrio en base al
número de clientes atendidos sino en la distancia y tiempo de servicio a cada cliente.

47
De la literatura revisada podemos observar que utilizar la teoría de grafos es una práctica
común, así como la distancia euclidiana para los arcos del grafo. La distancia euclidiana
nos ayuda a convertir fácilmente los tiempos en distancia y así equilibrar en base a un
solo parámetro, tiempo o distancia. Se aprecia también que se prefiere la configuración
de distritos circulares (Galvao 2006) o tendiendo a circular y se rechazan aquellos
sectores alargados y delgados (Mehrotra 1998) (Bacao 2005). Configuración que el
método de solución también considera, ya que si un sector es alargado se parte por la
mitad para hacerlo mas equitativo en sus dos longitudes, el ancho y el largo.

Otros factores y diferencias

Algunos trabajos como (Mehrotra 1998) consideran subunidades y a partir de ellas

formar un sector mayor, el método de solución al contrario empieza de algo grande y crea
pequeños. Otros autores consideran restricción de obstáculos físicos para generar
soluciones más adecuadas a la geografía de la zona, (Caro 2004) sugiere la utilización de
las herramientas GIS para incorporar este tipo de factor, el geográfico. Otros factores que
considera son: el factor de utilización de los vehículos, la distribución de las vías rápidas
dentro de la zona y los factores de tráfico que hacen que los chóferes usen rutas alternas y
alteren la distancia calculada. El presente trabajo se apoya en GIS pero solo para la
obtención de las coordenadas de los clientes.

Otra diferencia importante es el uso de semillas de aleatorización para generar soluciones

iniciales, para seleccionar un punto de partida, en el trabajo por default siempre se
empieza en el eje x positivo para el barrido.

(Marianov 2005) aporta la penalización de uniones de nodos con distancias muy grandes,
esta penalización puede adoptarse si se quiere evitar que un mismo vehículo entregue a
dos clientes, por ejemplo una entrega de productos frágiles y otro de muy pesados, que
pongan en riesgo la integridad del producto.

48
 2.5 Método de Barrido

Es un método sencillo y directo para la planificación y asignación de puntos de reparto a

vehículos. Su funcionamiento se guía por el objetivo de minimizar la distancia total
recorrida por la flota de vehículos. En general, el método funciona bien si hay muchos
puntos, si el volumen asociado a cada uno representa una pequeña fracción de la
capacidad total del vehículo y si los puntos están razonablemente próximos uno de otros.

En los casos en que no se den estas condiciones, probablemente se obtendrá una mala
distribución de cargas de trabajo y un bajo aprovechamiento de la capacidad de los
vehículos. No obstante gran parte de los resultados se pueden ajustar de forma manual.

Esta técnica propone establecer un punto de origen en el depósito y desde allí realizar un
barrido para abarcar toda el área geográfica del problema, determinando así cada uno de
los clusters, sectores o zonas.

Los puntos se representan con coordenadas polares (r, θ) y se ordenan de menor a mayor
considerando el parámetro θ. Los puntos van agregándose a un sector en el orden en que
quedan en la lista. Un sector esta completo cuando su capacidad es excedida. En ese
momento se inicia un nuevo sector, considerando solo los puntos que no han sido
integrados anteriormente a un sector. Así sucesivamente hasta que todos los puntos de la
gráfica han sido asignados. Este proceso sigue los siguientes pasos gráficamente
(González 2007):

49
1. Localizar el depósito y todos los clientes en una gráfica.

Figura 5. Método de Barrido: Paso 1

2. Centrar el punto de origen del barrido en el depósito y trazar una línea recta del
centro hacia la derecha y tendiendo al infinito.

Figura 6. Método de Barrido: Paso 2

3. Realizar el barrido rotando la línea en sentido contrario a las manecillas del reloj.

Figura 7. Método de Barrido: Paso 3

50
4. Detener la inserción de un cliente en el sector cuando el vehículo haya excedido
su capacidad.

Figura 8. Método de Barrido: Paso 4

5. Reiniciar el barrido hasta asignar todos los clientes a un sector.

Figura 9. Método de Barrido: Paso 5

51
2.6 Árbol de Costo Mínimo Total (Minimum Spanning Tree MST)

En un conjunto de puntos localizados en un plano, un grafo es aquél formado por todos

los arcos que unen los puntos entre ellos. El árbol de costo mínimo total es aquel sub-

grafo formado por los arcos de menor peso que unen todos los puntos del conjunto y que

la suma total de estos pesos es la posibilidad mínima de recorrido entre ellos con la

condición de tocar una sola vez cada punto y no formar un ciclo, generando un sub-grafo

que asemeja las ramas de un árbol.

Figura 10. Minimum Spanning Tree

Un grafo puede contener más de un árbol de costo mínimo lo que genera un bosque de

árboles. El peso de cada arco representa la distancia entre puntos, el costo de la ruta, la

preferencia de este arco sobre otros tomando en cuenta criterios particulares designados

por los evaluadores, etc…El problema del árbol de costo mínimo es uno de los problemas

más conocidos de la optimización combinatoria, los métodos de solución para este

problema han generado ideas importantes y jugado un rol especial en el diseño

52
computacional de algoritmos. El problema genera soluciones eficientes y prácticas para

grafos muy grandes.

Algunas de las aplicaciones más importantes del problema son: diseño de redes

computacionales y de telecomunicaciones, conexiones alámbricas, redes de transporte,

redes hidráulicas y eléctricas, y otras relacionadas con minimizar distancias y recorridos,

así como la formación de clusters.

Es común que el problema de árbol de costo mínimo surja como un subproblema en la

solución de un problema mayor. Las soluciones de este problema son considerados como

algoritmos voraces y se tiene como primer registro al científico Otakar Boruvka en 1926,

cuyo propósito era desarrollar una buena cobertura de la red eléctrica de Bohemia. Los

otros dos métodos más usados y que siguieron y citaron a Boruvka son: Algoritmo Prim y

Algoritmo Kruskal, los tres algoritmos corren en tiempo polinomial y el tipo de problema

es P. Hasta la fecha el algoritmo más veloz es el desarrollado por Bernard Chazelle,

basado en el algoritmo Boruvka. Su tiempo de procesamiento es O(e α(e,v)), donde v se

refiere al número de vértices y α es la clásica función inversa de la función Ackermann.

Se explican con más detalle los tres algoritmos más usados: Boruvka, Prim y Kruskal.

(MST2 2007)

53
 2.6.1 Algoritmo Boruvka

Consta evidencia escrita en dos trabajos del año 1926 escritos por Otakar Boruvka de ser

el pionero en generar un algoritmo efectivo para resolver el problema del árbol de costo

total mínimo. Boruvka fue criticado en su primer trabajo por no describir nítidamente su

algoritmo, más en un trabajo posterior demuestra que su idea es clara, concreta y factible.

Un tiempo de procesamiento de O(m log n). (GRAHAM 1985)

• Paso 1: unir cada uno de los puntos del conjunto con su punto más cercano

formando así subárboles.

• Paso 2: Se une cada uno de estos subárboles con otro subárbol, tomando el arco

menor que una a este par, los dos subárboles forman un nuevo subárbol,

reduciendo así el tamaño del bosque, este paso se repite hasta formar un solo

subárbol que será el árbol de costo mínimo.

Este algoritmo fue redescubierto por otros autores en tiempos y países distintos: Gustave

Choquet en 1938, George Sollin en Apris 1961, un grupo de investigadores Wroclaw

Polonia en 1950, Czekanowski en 1909 y otros más dedicados al análisis de clusters.

Todos estos autores tienen ideas similares al algoritmo Boruvka, pero el algoritmo en si

es atribuido al científico Otakar Boruvka.

54
1

Se parte de un grafo cuyos pesos

de los arcos son conocidos

Cada nodo elige su arco de menor

peso, al final todos los nodos
tienen por lo menos un arco
resaltado. Se formaron varios
subárboles, en este caso 2, cada
uno diferenciado por el color de
los arcos.

Se identifica el arco de menor

peso y los nodos del mismo para
cada subárbol que lo une con otro
subárbol.

De los arcos identificados en el

paso anterior se seleccionan los
4 de peso menor que permitan que
el grafo quede completamente
unido. En este caso solo hay una
opción el arco AF, al resaltarlo se
tiene el grafo completamente
unido.

Si se tienen “n” subárboles habrá

que escoger “n-1” arcos para que
el grafo se complete.

Figura 11. Algoritmo Boruvka

55
 2.6.2 Algoritmo Kruskal

Todos los arcos del grafo son ordenados de menor a mayor considerando su peso, se

examinan los arcos en orden creciente, si el arco no genera un ciclo con los subarboles

pertenecientes al bosque final, el arco es insertado en el bosque, de otra manera el arco se

descarta. Tiempo de procesamiento de O(m log n) (GRAHAM 1985). Para formar el

bosque final deben cumplirse las siguientes condiciones de inserción.

• Condición 1: Ninguno de los dos nodos del arco evaluado pertenece al bosque final

de subárboles, por lo tanto la rama es insertada, los dos nodos generan un nuevo

subárbol perteneciente al bosque final.

• Condición 2: Solo uno de los nodos del arco evaluado esta presente en uno de los

subárboles del bosque final, por lo tanto el arco es insertado en el bosque final.

• Condición 3: Cada uno de los nodos del arco evaluado están presentes en diferentes

subárboles del bosque, por lo tanto el arco es insertado en el bosque y los

subárboles se unen en uno solo.

• Condición 4: Los dos nodos del arco evaluado están presentes en el mismo subárbol

del bosque, por tanto el arco no es seleccionado y se desecha.

Este algoritmo fue desarrollado por Loberman y Weinberger simultáneamente en otra

parte del mundo, pero el algoritmo se le reconoce a Kruskal por haberlo publicado con

primicia.

56
1 2

Se inicia con un grafo cuyos pesos de los Se busca el arco de menor peso y que no
arcos son conocidos. Ningún arco ha sido cierre un ciclo y se selecciona. Mismo
seleccionado todavía. criterio para cada paso.

3 4

Se busca el siguiente arco. Si hay dos arcos Se busca el siguiente arco, en este caso es
con el mismo peso se selecciona uno el arco de igual peso que el paso anterior.
arbitrariamente.

5 6

Se busca el siguiente arco y se selecciona. Se busca el siguiente arco, en este caso hay
dos de mismo peso (7), el arco AF y el DE,
se selecciona el AF ya que el DE forma un
7 ciclo (DFE).

Igual que el paso anterior, se selecciona el

arco CD en lugar del AG y el grafo esta
totalmente conectado, por lo tanto el
algoritmo termino.

Figura 12. Algoritmo Kruskal

57
 2.6.3 Algoritmo Prim/Dijkstra
En este algoritmo los arcos son divididos en 3 grupos:

I. Los arcos pertenecientes al subárbol final

II. Los arcos de donde se selecciona el siguiente arco para el subárbol final

III. Los arcos restantes (los ya descartados o los que no se consideran todavía).

Los nodos son divididos en dos grupos:

A. Los nodos conectados por los arcos del conjunto I

B. Los nodos restantes (uno y solo uno de los arcos del grupo II llegará a cada uno

de estos nodos).

El algoritmo comienza seleccionando un nodo del conjunto arbitrariamente, el nodo se

inserta en el grupo A y los arcos que contienen este nodo en el grupo II. Al comenzar, el

grupo I esta vacío. En seguida se realizan los siguientes dos pasos iterativamente:

• Paso 1: El arco de peso menor del grupo II es retirado del grupo e insertado en el

grupo I, el otro extremo de este arco es transferido del grupo B al A.

• Paso 2: Considerar los arcos que unen el nodo recién transferido al grupo A y los

nodos restantes en el grupo B. Si el arco bajo consideración es más grande que el

arco del grupo II, es rechazado; si es menor, reemplaza al arco correspondiente en

el grupo II, y este último es rechazado. Se regresa al paso 1 y se termina cuando el

grupo II y el B estén vacíos. Los arcos contenidos en el grupo 1 forman el

subárbol final.

Este algoritmo tiene un tiempo de procesamiento de O(n2) (GRAHAM 1985).

58
1 2

Se parte de un grafo cuyos arcos son Se elige un nodo al azar, y se puntean

conocidos. Los nodos rojos son parte los arcos que unen este nodo (rojo) a
del árbol, los azules son aquellos que otros nodos (azules).
son candidatos a elegir.

3 4

De los arcos punteados se selecciona El nodo (azul), extremo del arco

aquel cuyo peso sea menor y no forme seleccionado ahora es parte del árbol
un ciclo en el grafo. El arco (se pasa a rojo), y se puntean los arcos
seleccionado se resalta con aqua. que unen el nuevo nodo con otros
nodos.

5 6

Se escoge el siguiente arco del grupo de Se agregan arcos punteados al conjunto

arcos punteados, el de menor peso y de selección.
que no forme un ciclo.

Figura 13. Algoritmo Prim Parte 1

59
7 8

Se selecciona un nuevo arco y nodo. Se agregan arcos punteados.

9 10

Se selecciona un nuevo arco y nodo. Se agregan arcos punteados.

11 12

Se selecciona un nuevo arco y nodo. Se agregan arcos punteados.

13

El algoritmo termina ya que todos los

nodos están unidos. El valor del árbol
es la suma de los arcos seleccionados
en aqua.

Figura 14. Algoritmo Prim Parte 2

60
CAPITULO 3
MÉTODO DE SOLUCIÓN

3.1 Consideraciones del Método de Solución

El método de solución genera sectores lo más equilibrados posibles utilizando como

criterio de equilibrio la carga de trabajo. Esta carga de trabajo se define en unidades de
distancia y es la suma de las distancias euclidianas entre puntos. El método se construye
en base a dos metodologías básicas: el árbol de costo mínimo, utilizando el algoritmo
Kruskal, y la metodología de barrido.

El método de solución usa el MST para calcular la distancia mínima necesaria para unir
todos los puntos pertenecientes a un sector, esta distancia en lo sucesivo será el peso del
sector. Y utiliza la metodología de barrido para dictar el orden en que los puntos son
agregados a los sectores. El criterio de inserción se basa en los parámetros de las
coordenadas polares de los puntos.

Gracias a estas dos metodologías se logra cumplir con los tres criterios básicos de la
sectorización: equilibrio gracias a la metodología MST, contigüidad gracias a la
metodología de barrido y compacidad gracias a la combinación de ambas metodologías.
Dentro del método de solución existen dos tipos de sectores: finales y temporales.

Sector
impar

Sector
temporal

Sector
final

Figura 15. Tipo de Sectores en el Método de Solución

61
Los sectores finales forman la configuración de la solución del problema y representan un
área de trabajo que será asignada posteriormente a un vehículo de reparto. Los sectores
temporales son aquellos sectores que sirven como paso intermedio para llegar a la
configuración final, son solamente para ayuda del método y no representan la solución.

El sector impar no es más que un sector final, se le denomina de esta manera para mayor
claridad en la explicación del método. Solo se forma cuando el número de vehículos es
impar.

Otra diferencia importante entre sectores temporales y finales es su peso. El peso de los
sectores se calcula generando el árbol de costo mínimo de todos los puntos del problema
y la solución de este árbol se divide entre el número de vehículos disponibles para
repartir. Este peso será asignado a los sectores finales, a los temporales se les asigna el
doble del peso de los finales.

Los sectores temporales son formados en la segunda etapa del método de solución para el
problema de vehículos impar y en la primera etapa para el problema de vehículos par. En
las demás etapas los sectores formados serán finales.

Otro término a definir para el método son las capas de la configuración final de los
sectores.

3 2
2
1
1

2 1

Figura 16. Capas de Sectores en Figura 17. Capas de Sectores en

Problema Impar Problema Par

62
En la figura 16 se muestran las configuraciones posibles para el problema de vehículos
impar, donde se numeran las capas existentes para cada configuración. Se observa que el
máximo de capas para este tipo de problema es 3.

En la figura 17 se muestran las capas para el problema de vehículos par, el máximo de

capas en este caso son 2.

Debido a la configuración de capas es necesario considerar la distancia necesaria para

llegar a la frontera de cada uno de los sectores. Es de mayor importancia para aquellos
sectores más alejados ya que su carga de trabajo sería el peso de su sector más la
distancia requerida para llegar al límite del sector saliendo desde el depósito. Por su
lejanía al depósito este último parámetro los haría quedar en desventaja en comparación
con aquellos sectores más cercanos al depósito.

En orden de lograr sectores lo más equilibrados posibles y eliminar esta desventaja se

decide agregar a los sectores formados a partir de los sectores temporales un punto extra,
que será la coordenada del depósito.
.
El método de solución para un número par de vehículos se realiza en dos etapas, la
primera etapa divide la región en j sectores (sectores temporales), donde j es la mitad del
número de camionetas, y de cada uno de ellos se generan dos sectores más pequeños que
serán sectores finales, de esta manera completando el número i de sectores finales que el
problema necesita.

El algoritmo para un número impar de vehículos es de tres etapas, la primera etapa genera
el sector impar, y las siguientes dos etapas son las mismas que el problema de vehículos
par, solo considerando que los puntos contenidos en el sector impar ya no pueden ser
incluidos en ningún otro sector.

63
Puntos asumidos:

• Solo debe existir un almacén, depósito o centro de distribución que abastece a

todos los puntos de entrega o clientes.
• La ubicación del cliente debe proporcionarse en coordenadas cartesianas.
• El barrido de los puntos siempre empieza en el grado 0 y en sentido contrario a las
manecillas del reloj, tomando como eje de giro el depósito.
• Para el barrido de sectores temporales, si existen dos puntos con el mismo ángulo,
se ingresa primero el de menor radio y después el de mayor.
• Para el barrido del sector impar, si existen dos puntos con mismo radio, es
indiferente cual entra primero.
• El método de solución genera un número “k” de sectores igual al número “m” de
vehículos
• Trabaja para ambos casos: el de vehículos par y el de vehículos impar.
• Si las coordenadas de los puntos son reales, es decir, equivalen en coordenadas de
longitud y latitud, cada unidad del peso del árbol equivale a un metro de distancia

64
3.2 Descripción gráfica del Método de Solución
3.2.1 Problema de Número de Vehículos Impar

Se tiene un conjunto “n” de puntos

distribuidos sobre una zona y un
depósito del cuál serán atendidos
todos los puntos. Se forman “m”
número de sectores, equivalente al
número de vehículos disponibles.

Se establece un ángulo criterio “A”

para partir el sector en capa o en
tira.

Se calcula el árbol de costo mínimo

para todos los puntos el valor o
peso del mismo será llamado Peso
Total (PT).

Se calcula el límite del peso del

sector final (PF) y el límite del
peso del sector temporal (PE).

Se forma el sector impar,

realizando un barrido concéntrico
al depósito. Se van agregando los
puntos del conjunto que tengan el
menor radio. (El parámetro r de la
coordenada polar)

Figura 18. Método Solución para Vehículos Impar Parte 1

65
 Según se van agregando puntos al
sector impar se calcula el peso del
árbol de estos puntos. Mientras no
se sobrepase el límite PF se siguen
agregando puntos, de otra manera
parar.

Se forman los sectores temporales

haciendo un barrido circular con eje
de giro en el depósito y recta de
inicio en el eje x positivo. El criterio
de inserción es el ángulo de la
coordenada polar, siempre el menor.

Los puntos miembros del sector

impar, ya no pueden ser
seleccionados.

Cada que se inserta un punto al

sector temporal, se calcula el peso
de su árbol y se compara con el PE,
si se sobrepasa se empieza un nuevo
sector, de otra manera se continúa
agregando puntos al actual.

Este paso termina cuando se barren

los 360° del problema.

Figura 19. Método Solución para Vehículos Impar Parte 2

66
 Se calcula el ancho del sector
temporal. Para cada sector, restando
al ángulo del último punto insertado
el ángulo del primer punto
insertado.

C1 Si el ancho del sector es menor al

ángulo límite “A”, el sector
temporal se parte en capa.
C2
Se crean dos conjuntos, uno con
todos los puntos del sector más el
depósito y el otro solo con el
depósito. Se transfiere un punto a la
vez, del conjunto lleno al vacío, en
este caso el punto de mayor radio.
Se calculan los pesos de los sectores
(C1 y C2).

C2 C1
Se calcula la diferencia absoluta
entre los pesos de los sectores, se
transfiere otro punto y se vuelve a
calcular la diferencia, si la
diferencia nueva es menor a la
anterior se continúa transfiriendo
puntos, sino, se para y se evalúa un
nuevo sector temporal.

Figura 20. Método Solución para Vehículos Impar Parte 3

67
C1 C2
Si el ancho del sector es mayor al
ángulo límite “A”, el sector
temporal se parte en tira.

Se crean dos conjuntos, uno con

todos los puntos del sector más el
depósito y el otro solo con el
depósito. Se transfiere un punto a la
vez, del conjunto lleno al vacío, en
este caso el punto de mayor ángulo.
Se calculan los pesos de los sectores
(C1 y C2).

C1 C2

Se calcula la diferencia absoluta

entre los pesos de los sectores, se
transfiere otro punto y se vuelve a
calcular la diferencia, si la
diferencia nueva es menor a la
anterior se continúa transfiriendo
puntos, sino, se para y se evalúa un
nuevo sector temporal.

Cuando se han evaluado todos los

sectores temporales, el método
termina y la configuración esta
completa. En este caso 3 sectores se
parten en capas y dos en tiras.

Las líneas aqua muestran la frontera

de cada uno de los sectores.

Figura 21. Método Solución para Vehículos Impar Parte 4

68
3.2.2 Problema de Número de Vehículos Par

Se tiene un conjunto “n” de puntos

distribuidos sobre una zona y un depósito
del cuál serán atendidos todos los puntos.
Se deben formar “m” número de sectores,
equivalente al número de vehículos de
reparto disponibles, en este caso par.

Formar los sectores temporales, realizando

un barrido circular en base al ángulo de los
puntos, la línea de partida es el eje x
positivo, y el eje de giro es el depósito en
sentido contrario a las manecillas del reloj.

Al terminar de barrer los 360° de la zona,

queda esta configuración. Los sectores
formados por las líneas moradas son los
sectores temporales.

Figura 22. Método Solución para Vehículos Par Parte 1

69
 Se calcula el ancho de los sectores
temporales y se decide como se va a
partir cada sector temporal.

Al terminar de partir todos los sectores

temporales, la configuración de la zona
queda como el de la figura, siendo las
líneas turquesa los límites de cada sector.

Cada sector será asignado a un vehículo y

este debe servir a todos los puntos dentro
de sus límites

Figura 23. Método Solución para Vehículos Par Parte 2

Nota: Para el caso de sectores pares se sigue el mismo procedimiento que el método para
vehículos impares, solo se omite el paso de crear el sector impar (el barrido concéntrico
al depósito).

Tanto el método de solución como el código del programa es propiedad de la autora de

este trabajo, se autoriza su uso solo para fines de investigación, para cualquier otra
aplicación acercarse a la autora.

70
3.3 Diagrama de Flujo del Método de Solución

NOTACIÓN

k = Contador de sectores finales

PT = Peso del árbol de todos los puntos
m = Número de vehículos
I = peso teórico del árbol del sector impar
I´ = peso real del árbol del sector impar creado
T = peso teórico del árbol del sector temporal
T´ = peso real del árbol del sector temporal creado
DV = Diferencia vieja
DN = Diferencia nueva
PK = Peso del árbol del sector k
PK+1 = Peso del árbol del sector k+1

71
 k=0

Calcular PT (1)

No Sí
“m” es par?

k +1

Calcular I (2)

Crear sector impar (3)

Agregar 2 puntos al sector (4)

Calcular I´ (5)

Sí No
I´ <= I k +1

Marcar punto (6)

Agregar otro punto Calcular T (7)

Calcular I´

Sí No
k <= m

Crea sector temporal (8)

Agregar dos puntos al sector (9)

Calcular T´ (10)

Sí No
T´ <= T

Marcar punto (11)

k +2
Agregar otro punto

Calcular T´

Figura 24. Diagrama de Flujo Método Solución Parte 1

72
 No Sí
“m” es par?

k=2 k=1

Sí No
k <= m

DV = 1,000,000

Sectorización Completa
Crear 2 sectores finales (12)

Agregar depósito (13)

Fin
Calcular Ancho (14)

Sí No
Ancho k<Ángulo
(15)

Agregar punto a k+1 (16) Agregar punto a k+1 (17)

Marcar punto (18)

Calcular PK (19)

Calcular PK+1 (20)

Calcular DN (21)

Sí No
DN<DV

DV=DN (22) Marcar punto de k (23)

Agregar otro punto a k+1 (24)

k+2

Figura 25. Diagrama de Flujo Método Solución Parte 2

73
EXPLICACIÓN CUADRO POR CUADRO

1) Se genera el árbol de costo mínimo (MST) para todos los puntos y el resultado es
el peso del árbol generado más el peso de las paradas de los puntos visitados
2) Se calcula de la siguiente manera: (PT/m) + la tolerancia permitida
3) Crea una lista de puntos auxiliar que crece conforme se insertan puntos, este
sector solo se crea cuando el número de camionetas es impar y generara un sector
circular concéntrico al depósito, este sector será un sector final
4) Agrega dos puntos a la lista auxiliar, el criterio para agregar puntos al sector
impar es: aquellos de menor radio que no estén asignados a ningún sector.
5) Se calcula el MST de los dos puntos introducidos al sector, incluyendo el peso de
las paradas en los puntos
6) Se marcan los puntos recién introducidos al sector como miembros del sector “k”
formado
7) Se calcula de la siguiente manera: [(PT*2)/m] + la tolerancia permitida
8) Crea una lista de puntos auxiliar que crece conforme se insertan puntos, forma
sectores temporales que en un paso posterior se parten en 2 para generar sectores
finales
9) Agrega dos puntos a la lista auxiliar, el criterio para agregar puntos a los sectores
temporales es: aquellos de menor ángulo no asignados a ningún sector
10) Se calcula el MST de los puntos introducidos al sector temporal más el peso de
las paradas de los puntos introducidos
11) Mismo procedimiento que el paso (6)
12) Crea dos listas de puntos auxiliares, una para cada sector final, crecen según se le
agreguen los puntos. Una lista es para el sector k y otra para el sector k+1.
13) A las dos listas creadas se le agrega las coordenadas del depósito, considerándolo
como un punto más, esto con el fin de considerar la distancia saliendo desde el
depósito y que el equilibrio de los sectores sea más exacto
14) Se buscan los puntos del sector que tengan el ángulo máximo y el mínimo, se saca
la diferencia (MAX-MIN) y ese será el ancho del sector

74
15) El ángulo es el ángulo límite introducido para ser la referencia si partir el sector
temporal en capa o en tiras delgadas
16) El criterio para agregar el punto es tomar aquel punto con mayor radio y que sea
miembro del sector k
17) El criterio para agregar el punto es tomar aquel punto con mayor ángulo y que sea
miembro del sector k
18) Se marca el punto recién introducido como miembro del sector k+1
19) PK es el peso del árbol resultado de generar el MST de los puntos que son
miembros del sector k y el peso de las paradas de visitar estos puntos
20) PK+1 es el peso del árbol resultado de generar el MST de los puntos que son
miembros del sector k+1 y el peso de las paradas de visitar estos puntos
21) El DN es el valor absoluto de la diferencia de PK y PK+1
22) La variable DV ahora toma el valor de DN
23) Se marca el punto recién transferido a k+1 como miembro de k, ya que
adicionarlo al sector k+1 no favorece el equilibrio de los árboles
24) Agrega un nuevo punto siguiendo el criterio seleccionado en el punto 16 o 17.

75
3.4 Pseudo código del método de solución

Inicializar contadores
Introducir número de vehículos
Introducir ángulo límite
Limpiar listas

Mientras haya coordenadas de puntos que introducir

Calcular coordenadas polares del punto
Insertar punto en la lista ordenada
Calcular lista de distancias de la lista de puntos*
Calcular peso del árbol de la lista de puntos*
Calcular peso del sector impar*
Calcular peso del sector temporal*
Si el número de vehículos es impar
Agregar 1 a contador_sectores
Crear sector impar*
Mientras el contador_sectores sea menor al número de vehículos
Crear sector temporal*
Agregar 2 a contador_sectores
Para cada sector temporal
Calcular ancho del sector*
Si el ancho es mayor al ángulo límite
Partir sector por el ángulo*
De lo contrario
Partir sector por el radio*

*Funciones

76
FUNCIONES

Calcular lista de distancias de la lista de puntos

Se calcula la distancia de todas las combinaciones posibles de los puntos
contenidos en la lista

Calcular peso del árbol de la lista de puntos

Mientras haya puntos de la lista de puntos que no estén en el árbol
Se selecciona el arco de menor distancia de la lista de distancias generada
El arco forma un ciclo
Quitar arco de la lista de distancias
De otra manera
Agregar arco al árbol
Quitar arco de la lista de distancias
Calcular el peso del árbol que será la suma de los arcos que son parte del árbol

Calcular peso límite del sector impar

Dividir el peso del árbol de la lista de puntos entre el número de vehículos

Calcular peso límite del sector temporal

Multiplicar por 2 el peso del sector impar por 2

Crear sector impar

Agregar los dos puntos de menor radio de la lista de puntos
Calcular peso del árbol de estos puntos
Mientras el peso del árbol sea menor al peso límite del sector impar
Marcar punto como miembro del sector
Agregar punto de menor radio no marcado como miembro de algún sector
Calcular peso del árbol de los puntos marcados más el último seleccionado

77
Crear sector temporal
Agregar los dos puntos de menor ángulo no miembros de otro sector
Calcular peso del árbol de estos puntos
Mientras el peso del árbol sea menor al peso límite del sector temporal
Marcar punto como miembro del sector
Agregar punto de menor ángulo no miembro de algún sector
Calcular peso del árbol de los puntos seleccionados como miembros del
sector más este último seleccionado

Calcular ancho del sector

Buscar punto miembro del sector con el ángulo mínimo
Buscar punto miembro del sector con el ángulo máximo
Calcular ancho restando al ángulo máximo el ángulo mínimo

Partir sector por el ángulo

Inicializar DF a 1,000,000
Inicializar DN a 0
Crear lista1 con los puntos miembros del sector temporal n
Crear una lista2 vacía

Agregar coordenadas del depósito a ambas listas

Pasar el punto de mayor ángulo de la lista1 a la lista2
Calcular peso del árbol de la lista 1
Calcular peso del árbol de la lista 2
Calcular DN como la diferencia absoluta del peso del árbol de la lista 1 y de la 2
Mientras DN sea menor a la DV
DV toma el valor de DN
Se marca el punto transferido a la lista 2 como miembro del sector n+1
Se actualiza lista1
Transferir otro punto de la lista1 a la lista2 , siempre el de mayor ángulo

78
 Calcular peso del árbol de la lista 1
Calcular peso del árbol de la lista 2
Calcular DN como la diferencia absoluta del peso del árbol de la lista 1 y
de la 2

Partir sector por el radio

Inicializar DF a 1,000,000
Inicializar DN a 0
Crear lista1 con los puntos miembros del sector temporal n
Crear una lista2 vacía

Agregar coordenadas del depósito a ambas listas

Pasar el punto de mayor radio de la lista1 a la lista2
Calcular peso del árbol de la lista 1
Calcular peso del árbol de la lista 2
Calcular DN como la diferencia absoluta del peso del árbol de la lista 1 y de la 2
Mientras DN sea menor a DV
DV toma el valor de DN
Se marca el punto transferido a la lista 2 como miembro del sector n+1
Se actualiza lista1
Transferir otro punto de la lista1 a la lista2 , siempre el de mayor radio
Calcular peso del árbol de la lista 1
Calcular peso del árbol de la lista 2
Calcular DN como la diferencia absoluta del peso del árbol de la lista 1 y
de la 2

79
3.5 Automatización del método de solución

Para facilitar el uso del método de solución se creo un programa para automatizar el
proceso y así permitir que el método pueda ser usado como una herramienta para la
planeación logística de una empresa. Se utilizó C++ para crear el código del programa y
este tiene ciertas consideraciones para su funcionamiento:

• La ubicación del cliente debe proporcionarse en coordenadas cartesianas y

siempre referenciada al depósito, las coordenadas del depósito siempre serán (0,0)
• Se considera un tiempo de servicio para cada punto en minutos, este peso se
traduce a distancia y se agrega al peso del árbol del sector
• Puede considerarse un porcentaje de tolerancia para los límites de peso de los
sectores impares y temporales
• Cuando el número de puntos excede 500, el peso del árbol de todos los puntos
será un estimado. Se divide el conjunto total de datos en conjuntos no mayores de
500 datos, se calcula el peso del árbol de cada nuevo conjunto. La suma de estos
pesos será el estimado del peso del árbol de todos los datos.
• Se tiene un recuadro donde se pone el límite para partir cada sector temporal en
capa o en tira.
• Los archivos de datos deben ser .CSV, y contener solo dos columnas. La primera
para la coordenada X y la segunda para la coordenada Y. No debe de contener
encabezados ni renglones vacíos al final del archivo.

La figura 24 presenta el cuadro de diálogo del programa que permite realizar pruebas
para casos particulares y variar los parámetros de decisión como: ángulo límite, tiempo
de parada, velocidad promedio de los vehículos, tolerancias para los sectores temporal y
el impar. Esta aplicación nos permite determinar los valores que mejor se ajustan para el
caso.

80
3.5.1 Ventana de interacción del Programa

Tiempo de 7
1 12 Servicio (min)
3

*
8

9
*

10
5

Velocidad *
Promedio
13
km/hr
11

* Campos Obligatorios

Figura 26. Cuadro de Diálogo del Método de Solución Automatizado en C++

81
3.5.2 Pasos para correr el programa de manera semiautomática

1. Ingresar puntos del problema (puede hacerse de 2 maneras):

a. Manualmente uno por uno usando los recuadros (1) y (2), después de
haber ingresado los datos en ambos recuadros pulsar el botón AGREGAR.
Así para cada dato.
b. Se inserta la ruta del archivo .CSV que contiene las coordenadas de los
puntos del problema en el recuadro (9) y se pulsa el botón ABRIR
ARCHIVO, después de esto se pueden agregar más puntos al conjunto
utilizando la forma del inciso “a”.
2. Marcar el origen solo pulsando el botón de MARCAR ORIGEN *
3. Ingresar el tiempo de servicio en el recuadro (3)
4. Ingresar el ángulo (solo el valor y en grados) en el recuadro (4), que será límite
para saber si se parte el sector temporal en capas o tiras *
5. Ingresar el número de vehículos a utilizar o el número de sectores que se quiere
formar, en el recuadro (5) *
6. En el recuadro (13) ingresar la velocidad promedio para realizar la conversión de
tiempo a distancia.
7. Ingresar la tolerancia del sector temporal en el recuadro (8) y del sector impar en
el recuadro (7)
8. Pulsar el botón DISTANCIAS *
9. Pulsar el botón ÁRBOL *
10. Seleccionar la opción de salida de los sectores formados (Puede ser ambos) *
a. Imprimir en archivo: Marcar recuadro de IMPRIMIR ARCHIVO y
colocar en el recuadro (10) la ruta del archivo en el cuál se quiere guardar
la información. El nombre del archivo debe ser nuevo y de tipo CSV.
b. Imprimir en pantalla: Marcar IMPRIMIR EN PANTALLA, la
información aparecerá en el recuadro (12)
11. Si se quiere obtener un archivo con el peso de los sectores, insertar la ruta del
archivo en el recuadro (11). El nombre del archivo debe ser nuevo y de tipo CSV.
12. Pulsar el botón CALCULAR SECTORES *

82
3.5.3 Pasos para correr el programa de manera automática

1. Se inserta la ruta del archivo .CSV que contiene las coordenadas de los puntos del
problema en el recuadro (9)
2. Marcar el origen, solo pulsando el botón de MARCAR ORIGEN *
3. Ingresar el tiempo de servicio en el recuadro (3)
4. Ingresar el ángulo (solo el valor y en grados) en el recuadro (4), que será límite
para saber si se parte el sector temporal en capas o tiras *
5. Ingresar el número de vehículos a utilizar o el número de sectores que se quiere
formar , en el recuadro (5) *
6. En el recuadro (13) ingresar la velocidad promedio para realizar la conversión de
tiempo a distancia.
7. Ingresar la tolerancia del sector temporal en el recuadro (8) y del sector impar en
el recuadro (7)
8. Seleccionar la opción de salida de los sectores formados (Puede ser ambos) *
a. Imprimir en archivo: Marcar recuadro de IMPRIMIR ARCHIVO y
colocar en el recuadro (10) la ruta del archivo en el cuál se quiere guardar
la información. El nombre del archivo debe ser nuevo y de tipo CSV.
b. Imprimir en pantalla: Marcar IMPRIMIR EN PANTALLA, la
información aparecerá en el recuadro (12)
9. Si se quiere obtener un archivo con el peso de los sectores, insertar la ruta del
archivo en el recuadro (11). El nombre del archivo debe ser nuevo y de tipo CSV.
10. Pulsar el botón ABRIR CON CALCULO

NOTA: Todos los incisos marcados con (*) para ambos casos, de la forma
semiautomática y automática, son obligatorios, si alguno no se ingresa el programa o no
corre o arrojará resultados erróneos.

83
CAPITULO 4
CASO DE APLICACIÓN

A raíz de la globalización y el cambio del mercado donde la competencia ha crecido en

sobremedida, se ve afectada o modificada la manera de intercambiar información y
productos entre empresas. Ya sea que es una relación cliente-proveedor o entre empresas
del mismo grupo o compañeras. Se tiene como hecho que el servicio postal Mexicano
esta muy por debajo de los índices de rapidez en referencia con el Sistema Postal de
Estados Unidos. Por esta razón nacen las empresas de paquetería Express que brindan un
servicio aunque más costoso, más eficiente en cuanto a tiempo de entrega. Uno o dos días
es el tiempo de entrega dentro de la República por esta circunstancia el ruteo de vehículos
para este tipo de empresas es un proceso muy frecuente y de gran importancia. Se puede
preguntar si ya existe el internet porque no mandar por medio de esta vía todos los
documentos o información, sencillo, no todas las empresas actualmente están listas para
esta tecnología ya que requiere inversión y mucho trabajo. Además que los productos
tangible no pueden enviarse por esta vía. Por lo que la necesidad de este tipo de empresas
se mantendrá y en la actualidad se observa que va en aumento. Años atrás eran una o dos
las empresas de paquetería en México, hoy en día podemos nombrar más de 10.

4.1 Descripción del Caso

Una empresa de paquetería quiere utilizar una flota de 26 vehículos para dar servicio a
toda la zona metropolitana de Monterrey. Para este problema se considera que todos los
clientes tienen una demanda parecida (entregas de sobres o pequeños paquetes) por lo
que la capacidad física de volumen no se considera para la aplicación. La empresa divide
la carga total de trabajo diario entre sus 26 vehículos generando rutas para cada uno de
ellos. Como ya se sabe entre mayor sea el número de clientes más complicado se torna la
solución del problema de ruteo.

84
Por esta razón la empresa ha elegido modelar el problema de ruteo con el método de las
dos fases: primero sectorizar y después rutear, para simplificar el mismo y generar
soluciones más fácilmente. Como el problema de sectorización se considera un problema
de estrategia o táctica, el proceso no se realiza continuamente sino con una periodicidad
de 6 meses hasta un año.

Para realizar este primer intento se toma como muestra representativa un día de actividad
normal de la empresa, siendo el dato a considerar la dirección del cliente. En este intento
la sectorización se realizaba de la manera más rudimentaria, en un mapa pegado a una
pared, los clientes eran señalados con una tachuela de color. Ya ubicados todos los
clientes del día se agrupaban en 26 sectores según la intuición del planeador y cada grupo
era asignado a un vehículo. Este método además de impreciso es inexacto ya que los
sectores que generan no son equilibrados en cuanto a trabajo porque no consideran la
distancia de recorrido, solo consideran el factor visual.

Un segundo intento realiza lo mismo pero de un manera automatizada, el mapa es

electrónico usando la tecnología CAD y la ubicación de los clientes son exportados de los
aparatos GPS (en coordenadas de latitud y longitud) que cada uno de los vehículos
transporta. Pero al igual que el primer intento la sectorización se realiza solo
considerando el factor visual por lo tanto, se tienen las mismas desventajas que el primer
intento.

El presente trabajo presenta un tercer intento de sectorización, utilizando el método de

solución y la automatización del mismo. Se pretende comprobar que el método genera
mejores resultados que los usados actualmente y que es de gran ayuda para mejorar el
proceso diario de ruteo, haciéndolo más rápido y eficiente. Así como permitir realizar la
sectorización completa en poco tiempo y con esto poder realizar nuevas sectorizaciones
con mayor frecuencia para responder mejor al cambio del mercado de clientes. Se
presentará la situación actual y los resultados de la aplicación del método para ambos
casos, con número de vehículos par e impar.

85
 4.2 Situación Actual

Utilizando el conjunto de datos proporcionado por la empresa que contiene 26 rutas

actuales. El peso del sector corresponde al conjunto de datos de la ruta. En la siguiente
página se muestra la configuración gráfica.

Actual Sectorización
Sector Peso Puntos
1 71264.83 59
2 54514.50 62
3 47202.20 64
4 37582.35 56
5 32550.50 58
6 58388.69 69
7 46576.45 64
8 29602.58 51
9 31438.56 58
10 47382.35 64
11 27365.00 57
12 52477.50 70
13 36210.08 52
14 37023.75 64
15 45438.48 68
16 19942.27 47
17 30301.59 61
18 38833.85 63
19 27776.36 51
20 26452.79 60
21 27724.54 56
22 30837.27 64
23 20643.07 48
24 30310.66 52
25 22656.07 56
26 75877.61 63
Media 36346.10 58.78
Desv. Std 14365.04 6.19

Tabla 4. Peso de los sectores de la Configuración Actual

86
Figura 27. Configuración Actual de Sectores

87
 Depósito

ACTUAL

Figura 28. Configuración Actual de Sectores sobre Mapa de Monterrey

88
 4.3 Definición de Parámetros para el Programa del Usuario Final

Se evaluaron varios parámetros en cuanto a tolerancia y ángulo referencia:

Prueba Tolerancia Impar % Tolerancia Temporal % Angulo (°)

1 - - <18
2 20 10 <18
3 20 8 <18
4 20 9 <15
5 20 9 >15
6 20 9 >20
7 20 9 >30
Tabla 5. Evaluación de parámetros para el caso de aplicación

Datos del Caso:

• Una lista de 1537 puntos, muestra de un día normal de trabajo

• Una flota de 26 vehículos
• Las coordenadas de los puntos esta referenciada a la coordenada del depósito
• La lista de puntos se parte en 4 para estimar el peso del árbol de todos los puntos

Los parámetros seleccionados para correr las soluciones (por ser aquellos que mejor
equilibrio arrojaron) son:

• Tolerancia del 20 % para los sectores temporales

• Tolerancia del 9 % para el sector impar
• Un peso de parada de 250 unidades equivalentes a 0.25 minutos, que se considera
el tiempo de entrega del paquete, si los vehículos fuesen a una velocidad
promedio de 60 km/hr.
• Un ángulo referencia de 30°, si los sectores tiene mayor ángulo se parten en tiras,
si son menores se parten en capas

89
Se muestra el ejecutable del programa ya cargado con los valores escogidos para cada
uno de los parámetros antes mencionados. Este ejecutable será el programa para el
usuario final para el caso particular de estudio. De esta manera el usuario solo tiene que
introducir la ruta del archivo de puntos y la ruta del archivo de salida. Además del
número de vehículos que se desea utilizar.

Figura 29. Cuadro de Diálogo del Programa para el Usuario Final

90
4.4 Solución del Problema con 26 vehículos

Sectorización Propuesta
Sector Peso Puntos
1 39899.72 48
2 40429.74 67
3 37977.74 46
4 41929.05 58
5 42663.03 77
6 42311.93 75
7 38229.83 93
8 38693.28 93
9 38172.10 94
10 33940.26 75
11 38790.61 57
12 50069.96 47
13 54196.70 75
14 41089.58 69
15 42158.80 42
16 40532.06 50
17 42368.79 40
18 44121.44 34
19 43232.68 57
20 40065.88 64
21 39895.79 75
22 39191.76 97
23 34970.33 53
24 47703.20 15
25 51162.84 27
26 55375.47 9
Media 41969.76 53.00
Desv. Std 5264.49 23.40

Tabla 6. Peso de los sectores de la Configuración

Propuesta para vehículos Par

91
Figura 30. Configuración Propuesta para Sectores Par

92
 Depósito

26 Vehículos

Figura 31. Configuración Propuesta para Sectores Par sobre mapa de Monterrey

93
 4.5 Solución del problema con 25 vehículos

Utiliza los mismos datos y parámetros de la solución de 26 vehículos, el único dato que
varía es el de vehículos, pasa de 26 a 25.

Sectorización Propuesta
Sector Peso Puntos
1 41208.94 106
2 42489.02 50
3 42820.64 55
4 40319.43 47
5 41102.60 78
6 45103.22 76
7 43102.47 91
8 40009.48 81
9 40217.62 112
10 36484.81 79
11 43900.25 67
12 55527.39 55
13 41755.42 52
14 43495.33 69
15 43584.31 47
16 41837.39 40
17 43603.38 21
18 46144.31 47
19 44106.40 65
20 41223.04 87
21 40730.78 81
22 39256.48 75
23 48044.16 15
24 56163.65 21
25 42521.87 20
Media 43193.87 54.70
Desv. Std 4326.81 25.65

Tabla 7. Peso de los sectores de la Configuración

Propuesta para vehículos Impar

94
Figura 32. Configuración Propuesta para Sectores Impar

95
 Depósito

25 Vehículos

Figura 33. Configuración Propuesta para Sectores Impar sobre mapa de Monterrey

96
 4.6 Observaciones de la Solución

Peso Sector
Sectorización (en distancia mts)
Media Desviación
Actual 36346.10 14365.04
Impar 43193.87 4326.81
Par 41969.76 5264.49

Tabla 8. Tabla Comparativa de Soluciones

Se observa que para ambos casos, el de vehículos par y el de vehículos impar, la

desviación de los sectores arrojada por el método de solución es tres veces menor que la
configuración actual de la sectorización de la empresa.

El tiempo necesario para generar cada solución no excede los 15 minutos. Gracias al
programa se pueden realizar más iteraciones fácil y rápidamente, variando los parámetros
e investigar si existen otros que generen una mejor solución que las encontradas en este
trabajo. Gracias al método se logra un mejor equilibrio y por tanto reparto equitativo de
trabajo, así como la consideración de un peso de parada.

De las dos soluciones propuestas y de la configuración actual se pude comentar que hay
similitudes en cuanto a división visual, existen capas de sectores, aunque en la
sectorización actual se observan hasta cuatro capas para el caso de vehículos par, en el
método de solución se tiene como restricción el máximo de 2 capas.

En ambos casos los propuestos y la sectorización actual se observan los sectores

delgados. Se tiene que la configuración actual le ha funcionado a la empresa; por las
similitudes mencionadas entre configuraciones se puede asumir que la propuesta del
trabajo será aceptada por el equipo de logística de la empresa.
CONCLUSIONES

Se comprueba que el método desarrollado por este trabajo es efectivo para la solución del
problema de sectorización. Los resultados generados para el caso de aplicación son
razonables y mejoran la solución actual del problema para esta empresa.

El tiempo necesario para la solución del problema es corto y aceptable, el grado de

dificultad para usar el programa desarrollado es bajo, por lo que su uso para apoyo a la
toma de decisiones se considera adecuado y factible. La flexibilidad del programa
permite la variación de parámetros del método de solución para buscar la solución más
adecuada para la sectorización de un caso de aplicación de cualquier tipo de empresa con
servicio a domicilio. Siempre y cuando se cumpla la restricción de un solo depósito
disponible. La sectorización puede realizarse para asignar vehículos, agentes de venta,
facilidades u otro tipo de asignación, no solo vehículos.

La principal aportación de este trabajo es la posibilidad de tener una referencia

matemática para posteriores trabajos. Todo lo que se puede medir se puede mejorar.
Anteriormente no se tenia manera de saber que tan equilibrados estaban los sectores, con
este método se tienen mediciones de la sectorización actual y las configuraciones
propuestas. A partir de aquí, se pueden desarrollar nuevos métodos y compararlos con
los resultados y evaluar si el método sigue siendo un buen criterio o se puede hacer algo
mejor para solucionar el problema de sectorización.

El mayor beneficio del método es que los sectores formados bajo este criterio son más
equilibrados en cuanto a peso de trabajo basados en distancia que los sectores con los que
actualmente se trabaja. Otro beneficio de importancia es la posibilidad de generar
sectorización totalmente nueva en un tiempo muy corto lo que permite aumentar la
frecuencia de la sectorización en la empresa y con esto reflejar con mayor rapidez el
cambio de la demanda y con esto realizar los ajustes necesarios para lograr una mayor
eficiencia.
.

98
RECOMENDACIONES

• Incluir un método de mejora para la formación de sectores, intercambiar puntos

entre sectores que se encuentren en los límites de los mismos o cercanos a ellos
para ver si mejora el equilibrio entre ellos.
• Considerar el volumen de las entregas para diferenciar entre tipos de clientes y
asignar mejor los sectores y vehículos. Generar sectores para cada tipo de cliente.
• Probar el enfoque de aglomerar pequeñas unidades para formar una mayor, por
ejemplo por colonias, para que una colonia no sea parte de 2 sectores
• Considerar factores de tráfico y velocidades de traslado. No es lo mismo utilizar
una calle secundaria que una vía rápida.
• Realizar mediciones de tiempo y sustituir el parámetro de distancia por el de
tiempo
• Modificar la automatización del método para poder empezar el barrido en otra
ubicación que no sea sobre el eje x positivo. Para poder tener más opciones de
juego y encontrar mejores soluciones de sectorización.
• Insertar penalización a la unión de nodos que no queramos que vayan juntos
(comida y químicos, etc..)
• Insertar penalización para aquellas uniones que rebasen un límite máximo de
distancia

99
BIBLIOGRAFÍA

BACAO F, LOBO V, PAINHO M. Applying genetic algorithms to zone design. Soft

Computing 9 (5): 341-348 MAY 2005

BALINSKI, M., QUANDT, R. On an integer program for a delivery problem. Operations

Research 12 (1964) 300–304

BALLOU RONALD H.. Logística y Administración de la Cadena de Suministro, Quinta

Edición, Pearson-Prentice Hall, 2004.

BEASLEY, J. Route first – cluster second methods for vehicle routing. Omega 11 (1983)
403–408

BERGEY PAUL K., CLIFF T. RAGSDALE, MANGESH HOSKOTE. A Simulated

Annealing Genetic Algorithm for the Electrical Power Districting Problem. Annals of
Operations Research 121, 33-55, Jul 2003.

BLAIS M, LAPIERRE SD, LAPORTE G. Solving a home-care districting problem in an

urban setting. Journal of the Operational Research Society 54 (11): 1141-1147 NOV
2003

BOZKAYA B, ERKUT E, LAPORTE G. A tabu search heuristic and adaptive memory

procedure for political districting. European Journal of Operational Research 144 (1): 12-
26 JAN 1 2003

BRAMEL, J., SIMCHI-LEVI, D. A location based heuristic for general routing

problems. Operations Research 43 (1995) 649–660

CANO-GUERVOS RAFAEL, JORGE CHICA-OLMO, JOSE A. HERMOSO-

GUTIERRÉZ. A Geo-Statistical Method to Define Districts within a City. Journal of
Real Estate Finance and Economics Vol. 27 No.1 61-85 Jul 2003

CARO F, SHIRABE T, GUIGNARD M, [Link]. School redistricting:

embedding GIS tools with integer programming. Journal of the Operational Research
Society 55 (8): 836-849 AUG 2004

CHABRIER ALAIN. Vehicle routing Problem with elementary shortest path based
column generation Computers & Operations Research. New York: Oct 2006. Vol. 33, Iss.
10; p. 2972

CHOU CI, LI SP. Taming the Gerrymander - Statistical physics approach to Political
Districting Problem. Physica A-Statistical Mechanics and its Applications 369 (2): 799-
808 SEP 2006

100
CHRISTOFIDES, N., MINGOZZI, A., TOTH, P. The Vehicle Routing Problem. In:
Combinatorial Optimization. Wiley, Chichester (1979) 315–338

CLARKE, G., WRIGHT, W.: Scheduling of vehicles from a central depot to a number of
delivery points. Operations Research 12 (1964) 568–581

D'AMICO SJ, WANG SJ, BATTA R, RUMP C.M. A simulated annealing approach to
police district design. Computers & Operations Research volume 29 issue(6): 667-684
MAY 2002

DANTZIG, G., RAMSER, J.: The truck dispatching problem. Management Science 6
(1959) 80–91

DAVIS HERBERT W., DRUMM WILLIAM H. Logistics Costs and Service Database-
2002. Annual Conference Proceedings. San Francisco, CA: Council of Logistics
Management, 2002.

EASINGWOOD C. Heuristic approach to selecting sales regions and territories. Oper.

Res. Quart. 24 (4) (1973) 527-534

EL-FARZI E. AND [Link]. Solution of set-covering and set partitioning problems

using assignment relaxations. J. [Link]. Soc. 43 (1992) 483

FAULIN J., ÚBEDA S. Y MONJE D. Construcción de rutas de distribución de

mercancías usando criterios medioambientales. Navactiva: El portal para las empresas de
Navarra. (Universidad Pública de Navarra) 30/01/2006

FERREL O.C., HIRT GEOFREY, RAMOS LETICIA, ADRIAENSÉNS MARIANELA

Y FLORES MIGUEL ANGEL. Introducción a los Negocios en un Mundo Cambiante,
Cuarta Edición, Mc Graw Hill, 2004, Pág. 282.

FISHER, M., JAIKUMAR, R. A generalized assignment heuristic for the vehicle routing
problem. Networks 11 (1981) 109–124

FORMAN SL, YUE YD. Congressional districting using a TSP-based genetic algorithm.
Lecture Notes in Computer Science 2724: 2072-2083 2003

FRANKLIN B. ENRIQUE. Organización de Empresas, Segunda Edición, Mc Graw Hill,

2004, Pág. 362.

GALVAO LC, NOVAES AGN, DE CURSI JES, ET AL.A multiplicatively-weighted

Voronoi diagram approach to logistics districting. Computers & Operations Research 33
(1): 93-114 Ene 2006

101
GAMBARDELLA, L.M., DORIGO, M. Solving symmetric and asymmetric TSPs by ant
colonies. In: IEEE Conference on Evolutionary Computation, IEEE Press(1996) 622–627

GILLETT, B., MILLER, L. A heuristic algorithm for the vehicle-dispatch problem.

Operations Research 22 (1974) 340–349

GLOVER, F. Future paths for integer programming and links to artificial intelligence.
Computers & Operations Research 13 (1986) 533–549

GOLDEN, B., ASSAD, A., LEVY, L., GHEYSENS, F. The fleet size and mix vehicle
routing problem. Computers & Operations Research 11 (1984) 49–66

GONZÁLEZ VARGAS, GUILLERMO Y GONZÁLEZ ARISTIZABAL, FELIPE.

Metaheurísticas aplicadas al ruteo de vehículos. Un caso de estudio: Parte 2: algoritmo
genético, comparación con una solución heurística. Ingeniería Investigación, ene./abr.
2007, vol.27, no.1, p.149-157. ISSN 0120-5609.

GRAHAM R. L. AND PAVOL HELL. On the History of the Minimum Spanning Tree
Problem. Annals of the History of Computing, Volume 7, Number 1, January 1985

HAUGLAND D, HO SC, LAPORTE G. Designing delivery districts for the vehicle

routing problem with stochastic demands. European Journal of Operational Research 180
(3): 997-1010 AUG 1 2007

HESCHEL M.S. Effective sales territory development. [Link] 41(2) (1977) 39-43

HESS S.W. AND [Link]. Experiences with sales districting model: criteria and
implementation. Management Science 18(4) (1971) 41-54

HOLLAND, J. Adaptation in Natural and artificial systems. The University of Michigan

Press (1975)

LAMB CHARLES, HAIR JOSEPH Y MCDANIEL CARL. Marketing, Sexta Edición,

International Thomson Editores S.A., 2002, Pág. 383.

LAPORTE, G. The vehicle routing problem: an overview of exact and approximate

algorithms. European Journal of Operational Research 59 (1992) 345–358

LAPORTE, G., NOBERT, Y. Exact algorithms for the vehicle routing problem. Annals
of Discrete Mathematics 31 (1987) 147–184

LIN, S. Computer solutions of the traveling salesman problem. Bell System Technical
Journal 44 (1965) 2245–2269

LODISH L.M., Vaguely right approach to sales force allocations, Harvard Business Rev.
(January-February, 1974) 119-124

102
MARIANOV V., F. FRESARD. A procedure for the strategic planning of locations,
capacities and districting of jails: application to Chile. Journal of the Operational
Research Society, (2005) 56, 244-251

MEHROTRA ANUJ, ELLIS L JONSON, GEORGE L NEMHAUSER. An Optimization

Based Heuristic for Political Districting. Management Science Vol.44, No.8, Ago 1998.

MOLE, R.H., JAMESON, S.R. A sequential route-building algorithm employing a

generalised savings criterion. Operational Research Quarterly 27 (1976) 503–511

MUYLDERMANS L, CATTRYSSE D, VAN OUDHEUSDEN D. District design for

arc-routing applications. Journal of the Operational Research Society 54 (11): 1209-1221
NOV 2003

NEMHAUSER, G., WOLSEY, L. Integer and Combinatorial Optimization. John Wiley

& Sons (1988)

POTVIN, J.Y., ROUSSEAU, J.M. A parallel route building algorithm for the vehicle
routing and scheduling problem with time windows. European Journal of Operational
Research 66 (1993) 331–340

RENAUD, J., BOCTOR, F., LAPORTE, G. A fast composite heuristic for the symmetric
travelling salesman problem. INFORMS Journal on Computing 8 (1996) 134–143

RICCA FEDERICA. A Multicriteria Districting Heuristic for the Aggregation of Zones

and its Use in Computing Origin-Destination Matrices. Infor. Vol. 42 No.1 Feb. 2004

ROUSSEAU LOUIS-MARTIN , MICHEL GENDREAU, GILLES PESANT AND

FILIPPO FOCACCI. Solving VRPTWs with Constraint Programming Based Column
Generation. Annals of Operations Research. Volume 130, Numbers 1-4 / August, 2004.

SHANKER R.J., R.E. TURNER AND A.A. ZOLTNERS. Sales territory design: An
integrated approach, Management Science 22(3) (1975) 309-320

SOLOMON MARIUS. Algorithms for the vehicle Routing and scheduling Problems with
time Windows Constraints. Operation Research 1987, pg 35, 254-265.

TAILLARD, E.D. Parallel iterative search methods for vehicle routing problems.
Networks 23 (1993) 661–673

TOTH PAOLO, VIGO DANIELE. The vehicle routing Problem. SIAM monographs on
discrete mathematics and applications. Society for Industrial and Applied Mathematics,
2002,Philadelphia

103
TOTH, P., VIGO, D. The granular tabu search and its application to the vehicle-routing
problem. INFORMS Journal on Computing 15 (2003) 333–346

VERA C. ALONSO. El problema de ruteo de vehículos solucionado con Heurísticas.

Tesis de Magíster PUC, 1996

WREN, A., HOLLIDAY, A. Computer scheduling of vehicles form one or more depots
to a number of delivery points. Operational Research Quarterly 23 (1972) 333–344

YANG BY, VISWANATHAN K, LERTWORAWANICH P, ET AL. Fire station

districting using simulation: Case study in Centre Region, Pennsylvania. Journal of
Urban Planning and Development-ASCE 130 (3): 117-124 SEP 2004

ZOLTNERS A.A. AND [Link]. Integer programming models for sales resource
allocation. Management Science 26(3) (1980) 242-260

ZOLTNERS A.A. A unified approach to sales territory alignment. Sales Management:

New Developments Behavioral and Decision Model Research (Marketing Science
Institute, Cambridge, MA, 1979) pp. 360-376

REFERENCIAS ELECTRÓNICAS

VRP
[Link]
Última consulta el 20 de Noviembre 2007

MAR Logística. Organización y Administración de Empresas. El rincón del vago.

[Link]
Última consulta el 20 de Noviembre 2007

MST
[Link]
Ultima consulta el 10 de Octubre 2007

Logística
[Link]
Última consulta el 10 de Septiembre 2007

MST2
[Link]
Última consulta el 20 de Septiembre 2007

104
ANEXO 1: Código del Programa

// Tarea 11Dlg.h : header file

// CTarea11Dlg dialog

class CTarea11Dlg : public CDialog

{
// Construction
public:
CTarea11Dlg(CWnd* pParent = NULL); // standard constructor

// Dialog Data
//{{AFX_DATA(CTarea11Dlg)
enum { IDD = IDD_TAREA11_DIALOG };
CListBox L_Arbol2;
CListBox L_CPolares;
CListBox L_Tree;
CListBox L_Dist;
CListBox L_Puntos;
CListBox L_SectorPuntos;
CButton C_File;
CButton C_List;
int E_Px;
int E_Py;
CString E_Peso;
int E_PuntoSale;
CString E_CadenaSale;
int E_Camion;
CString E_CadenaOrigen;
double E_TolSectorImpar;
double E_TolSectorTemp;
CString E_InFilePath;
CString E_OutFilePath;
int E_Parada;
int E_AnguloLimite;
int E_ArbolTotal;

// Implementation
double GetLowerRatio(CListaPuntos&,int&);
void FillDistancesList(CListaPuntos&,CListaDistancias&);
void CopyList(CListaPuntos&,CListaPuntos&);
double GetDistanceToSectorDivision(double,double);
int CalculateSectorWideAndWidth(CListaPuntos&,CListaPuntos&,int,int&,int&,int&);
int GetHigherRatioNodeNumber(CListaPuntos&,int&,int&);

private:
int xo,yo;

// ListaDistancias.h: interface for the CListaDistancias class.

//
//////////////////////////////////////////////////////////////////////
typedef struct NodoDistancia
{
int a; // punto origen
int b; // punto destino
double d; // distancia
bool tree; // identificador ¿pertenece al árbol?
struct NodoDistancia *sig; // apuntador al siguiente nodo
}ND;

class CListaDistancias // Lista Ordenada por Distancias Simplemente Ligada

{
public:
CListaDistancias();
virtual ~CListaDistancias();
void Push(int,int,double); // Inserta un nodo

105
 CString GetNodo(int); // Devuelve un nodo
void Clear(); // Elimina todo los nodos de la lista
void SetTreeNodes(int); // Devuelve la info del nodo si pertenece al tree
int GetSize(); // Obtiene el tamaño de la lista
CString GetNodoTree(int); // Devuelve un nodo si forma parte del árbol final
double GetPesoTree(); // Devuelve el peso total del árbol
double GetTreeWeightForIncreasingPoints(); // Devuelve el peso total del árbol sin validar que la lista de puntos se
destruya

private:
CListaPA LPA;
ND *head;
int size;
};

// ListaPA.h: interface for the CListaPA class.

//
//////////////////////////////////////////////////////////////////////

typedef struct NodoPuntoArbol

{
int punto;
int tree;
struct NodoPuntoArbol *sig;
}NPA;

class CListaPA
{
public:
CListaPA();
virtual ~CListaPA();
bool Create(int);
int GetTree(int);
void SetTree(int,int);
void Clear();
private:
NPA *head;
};

// ListaPuntos.h: interface for the CListaPuntos class.

//
//////////////////////////////////////////////////////////////////////

typedef struct NodoPunto ///Nodo lista

{
int x;
int y;
double r;
double ang;
int num;
int sector;
int isOrigin;

struct NodoPunto *sig;

}NP;

class CListaPuntos
{
public:
CListaPuntos();
virtual ~CListaPuntos();
bool Push(int,int,int=0,int=0);
CString GetLastItem();
double GetDistancia(int,int);
int GetSize();
CString GetData(int);
double GetDataForNode(int,int);
bool IsEmpty();

106
 CString Pop(int);
double CalcRadio(int,int);
double CalcAngulo(int,int);
void SetDataForNode(NodoPunto*,double,int);
void PopByNum(int);
void SetCurrentNode(int n);
double GetCurrentRatio();
double GetCurrentAngle();
int GetCurrentNumber();
int GetCurrentX();
int GetCurrentY();
int GetCurrentSector();
void SetCurrentSector(int);
void Clear();
void SetCurrentNodeByNum(int);
CString GetDataWithSector(int,CString&);

private:

int nodex;
int nodey;
double noder;
double nodeang;
int nodesector;
int nodenum;

NP *currentnode;

int size;
NP *head;
};

// [Link]: implementation of the CListaPuntos class.

//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Tarea 11.h"
#include "ListaPuntos.h"
#include "Math.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CListaPuntos::CListaPuntos() // Constructor -> Inicializa variables

{
head = new NP;
head->x = 0;
head->y = 0;
head->r = 0;
head->ang = 0;
head->sector =0;
head->isOrigin =0;
head->sig = NULL;
size = 0;
nodex=0;
nodey=0;
noder=0;
nodeang=0;
nodenum=0;
currentnode=head;

107
}

CListaPuntos::~CListaPuntos()
{
Clear();
delete head;
}

bool CListaPuntos::Push(int x, int y,int mynumber,int isOrigin)

{
int nodenumber=0;
if(IsEmpty())
{
NP *nuevo = new NP;
nuevo->x = x;
nuevo->y = y;
if(isOrigin)
{
nuevo->r = 0;
nuevo->ang = 0;
}
else
{
nuevo->r = CalcRadio(x,y);
nuevo->ang = CalcAngulo(x,y);
}
nuevo->sector = 0;
nuevo->isOrigin=isOrigin;

nuevo->sig = head->sig;
head->sig = nuevo;
size++;
if(mynumber==0)
nuevo->num = GetSize();
else
nuevo->num = mynumber;
currentnode=nuevo;
return TRUE;
}
else
{
NP *temp;
temp = head;

//Valida que no se meta un nodo que ya existe

while(temp->sig != NULL)
{
temp = temp->sig;
if(temp->x == x && temp->y == y)
return FALSE;
}

NP *nuevo = new NP;

nuevo->x = x;
nuevo->y = y;
nuevo->r = CalcRadio(x,y);
nuevo->ang = CalcAngulo(x,y);
nuevo->sector = 0;
nuevo->isOrigin=isOrigin;
NP *temp2;
temp2=head;

if(isOrigin)
{
nuevo->r = 0;
nuevo->ang = 0;
nuevo->sig = temp2->sig;
temp2->sig = nuevo;
size++;

108
 return TRUE;
}

while(temp2->sig != NULL)
{
nodenumber++;

if((nuevo->ang < temp2->sig->ang)||(nuevo->ang == temp2->sig->ang && nuevo->r < temp2->sig-

>r))
{
nuevo->sig = temp2->sig;
temp2->sig = nuevo;
size++;

if(mynumber==0)
{
temp2=temp2->sig;

while(temp2!=NULL)
{
temp2->num=nodenumber;
temp2=temp2->sig;
nodenumber++;
}
}
else
nuevo->num=mynumber;

return TRUE;
}
else
temp2 = temp2->sig;
}
nuevo->sig = NULL;
temp->sig = nuevo;
nuevo->isOrigin=isOrigin;
size++;
if(mynumber==0)
nuevo->num = GetSize();
else
nuevo->num = mynumber;
currentnode=nuevo;
return TRUE;
}
}

bool CListaPuntos::IsEmpty()
{
if(head->sig == NULL)
return TRUE;
else
return FALSE;
}

void CListaPuntos::Clear()
{
NP *temp;
while(head->sig != NULL)
{
temp = head->sig;
head->sig = temp->sig;
delete temp;
}
size=0;
}

CString CListaPuntos::GetLastItem()
{
NP *temp;

109
 CString str;

temp = head;

while(temp->sig != NULL)
temp = temp->sig;

[Link]("%-2d - (%-2d, %-2d) - (%-1f, %-1f)",size,temp->x,temp->y, temp->ang, temp->r);

return str;
}

double CListaPuntos::GetDistancia(int a, int b)

{
NP *ta = head;
NP *tb = head;
int c1, c2;

for(int aux = 0; aux < a; aux++)

ta = ta->sig;
for(aux = 0; aux < b; aux++)
tb = tb->sig;

if(ta->x >= tb->x)

c1 = ta->x - tb->x;
else c1 = tb->x - ta->x;

if(ta->y >= tb->y)

c2 = ta->y - tb->y;
else c2 = tb->y - ta->y;

return sqrt(pow(c1,2) + pow(c2,2));

}

int CListaPuntos::GetSize()
{
return size;
}

CString CListaPuntos::GetData(int n)
{
CString str;
NP *temp = head;
for (int i=0; i<n; i++)
{
temp = temp->sig;
}
[Link]("%-2d - (%-2d, %-2d) - (%-1f, %-1f)",i,temp->x,temp->y, temp->ang, temp->r);
return str;

CString CListaPuntos::GetDataWithSector(int n,CString& s_dForFile)

{
CString str;
NP *temp = head;
for (int i=0; i<n; i++)
{
temp = temp->sig;
}
[Link](" %d. (%d,%d) -> %d",temp->num,temp->x,temp->y, temp->sector);
s_dForFile.Format("%d,%d,%d\n",temp->x,temp->y,temp->sector);
return str;
}

double CListaPuntos::GetDataForNode(int n,int data)

110
{
NP *temp = head;
for (int i=0; i<n; i++)
temp = temp->sig;

switch(data)
{
case 1:
return temp->x;
case 2:
return temp->y;
case 3:
return temp->r;
case 4:
return temp->ang;
case 5:
return temp->sector;
default:
return 0;
}
}

void CListaPuntos::SetDataForNode(NodoPunto* NodeToChange,double data,int datatype)

{

switch(datatype)
{
case 1:
NodeToChange->x=int(data);
case 2:
NodeToChange->y=int(data);
case 3:
NodeToChange->r=data;
case 4:
NodeToChange->ang=data;
case 5:
NodeToChange->sector=int(data);
}
}

CString CListaPuntos::Pop(int n)
{

double CListaPuntos::CalcRadio(int x,int y)

{
return sqrt(pow(x,2)+pow(y,2));
}

double CListaPuntos::CalcAngulo(int x, int y)

{
double z;
if(atan2(y,x)>0)
z = (atan2(y,x))*57.29578;
else
z = 360 + ((atan2(y,x))*57.29578);

if(z==360)
z=0;

return z;
}

void CListaPuntos::SetCurrentNode(int n)
{
NP *temp = head;

111
 for (int i=0; i<n; i++)
temp = temp->sig;

if(temp!=NULL)
{
nodex=temp->x;
nodey=temp->y;
noder=temp->r;
nodeang=temp->ang;
nodesector=temp->sector;
nodenum=temp->num;
currentnode=temp;
}
}

void CListaPuntos::SetCurrentNodeByNum(int mynumber)

{
NP *temp = head;
int b_found=0;

for (int i=1; i<=size; i++)

{
if(!b_found)
{
if(temp->num==mynumber)
{
nodex=temp->x;
nodey=temp->y;
noder=temp->r;
nodeang=temp->ang;
nodesector=temp->sector;
nodenum=temp->num;
currentnode=temp;
b_found=1;
}
else
temp = temp->sig;
}
}
}

double CListaPuntos::GetCurrentRatio()
{
return noder;
}

double CListaPuntos::GetCurrentAngle()
{
return nodeang;
}

int CListaPuntos::GetCurrentNumber()
{
return nodenum;
}

int CListaPuntos::GetCurrentX()
{
return nodex;
}

int CListaPuntos::GetCurrentY()
{
return nodey;
}

int CListaPuntos::GetCurrentSector()
{
return nodesector;

112
}

void CListaPuntos::SetCurrentSector(int sector)

{
currentnode->sector=sector;
}

void CListaPuntos::PopByNum(int n)
{
NP *temp = head;
NP *temp2;
int popped=0;

do
{
if(temp->sig->num==n)
{
temp2 = temp->sig;
temp->sig = temp->sig->sig;
delete temp2;
size--;
popped=1;
}

if(temp->sig!=NULL)
temp = temp->sig;
else
popped=1;

}while(popped==0);

// [Link]: implementation of the CListaPA class.

CListaPA::CListaPA()
{
head = new NPA;
head->punto = 0;
head->sig = NULL;
head->tree = 0;
}
CListaPA::~CListaPA()
{
Clear();
delete head;
}
bool CListaPA::Create(int p) // Crea una lista de correspondencia
{
NPA *temp = head;
if(p<2)
return FALSE;
for(int c=1; c<= p; c++)
{
NPA *nuevo = new NPA;
nuevo->punto = c;
nuevo->tree = c;
temp->sig = nuevo;
temp = temp->sig;
}
temp->sig = NULL;
return TRUE;
}
void CListaPA::Clear()
{
NPA *temp;
while(head->sig != NULL)

113
 {
temp = head->sig;
head->sig = temp->sig;
delete temp;
}
}
int CListaPA::GetTree(int p)
{
NPA *temp=head;
while(temp->sig != NULL)
{
temp = temp->sig;
if(temp->punto == p)
return temp->tree;
}
return 0;
}
void CListaPA::SetTree(int ot, int nt)
{
NPA *temp=head;
while(temp->sig != NULL)
{
temp = temp->sig;
if(temp->tree == ot)
temp->tree = nt;
}
}

// [Link]: implementation of the CListaDistancias class.

CListaDistancias::CListaDistancias() // Constructor -> Inicializa variables

{
head = new ND;
head->a = 0;
head->b = 0;
head->d = 0;
head->tree = FALSE;
head->sig = NULL;
}

CListaDistancias::~CListaDistancias() // Destructor -> Libera memoria

{
Clear();
delete head;
}

void CListaDistancias::Push(int a, int b, double d) // Inserta un nodo

{
ND *nuevo = new ND;
nuevo->a = a;
nuevo->b = b;
nuevo->d = d;
nuevo->tree = FALSE;
size++;

if(head->sig == NULL)
{
nuevo->sig = head->sig;
head->sig = nuevo;
return;
}
else
{
ND *temp;
temp = head;

while(temp->sig->d < d)
{
temp = temp->sig;

114
 if(temp->sig == NULL)
{
temp->sig = nuevo;
nuevo->sig = NULL;
return;
}
}

nuevo->sig = temp->sig;
temp->sig = nuevo;
}
}

int CListaDistancias::GetSize()
{
return size;
}

void CListaDistancias::Clear() // Elimina todos los nodos

{
ND *temp;
while(head->sig != NULL)
{
temp = head->sig;
head->sig = temp->sig;
delete temp;
}
size=0;
}

CString CListaDistancias::GetNodo(int n) // Devuelve un nodo en una cadena

{
ND *temp;
temp = head;
CString str;
for(int x=0; x<n; x++)
{
temp = temp->sig;

}
[Link]("%d --> %d -- %.2f",temp->a,temp->b,temp->d);
return str;
}

CString CListaDistancias::GetNodoTree(int n) // Devuelve un nodo en una cadena

{
ND *temp;
temp = head;
CString str = "";
for(int x=0; x<n; x++)
{
temp = temp->sig;

}
if(temp->tree)
{
[Link]("%d --> %d -- %.2f",temp->a,temp->b,temp->d);
}
return str;
}

double CListaDistancias::GetPesoTree()
{
double total = 0;
ND *temp;
temp = head;

while(temp->sig != NULL)
{

115
 temp = temp->sig;
if(temp->tree)
total += temp->d;

}
return total;
}

void CListaDistancias::SetTreeNodes(int p) // Determina las distancias que componen el árbol final

{
[Link](p);

ND *aux = head;

int t1, t2;

while(aux->sig != NULL)
{
aux = aux->sig;
t1 = [Link](aux->a);
t2 = [Link](aux->b);
if(t1 != t2)
{
[Link](t1,t2);
aux->tree = TRUE;
}
}
[Link]();
}

double CListaDistancias::GetTreeWeightForIncreasingPoints()
{
double total = 0;
ND *temp;
temp = head;

while(temp->sig != NULL)
{
temp = temp->sig;
if(temp->tree)
total += temp->d;

}
return total;
}

// Tarea [Link] : implementation file

//

#include "stdafx.h"
#include "Tarea 11.h"
#include "Tarea 11Dlg.h"
#include "dialog2.h"
#include "Math.h"

#include "FileDialog_ReadOnly.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

CListaPuntos LP,LPWork,LPA;
CListaDistancias LD,LDA,LDW;

double f_totTreeW;

116
/////////////////////////////////////////////////////////////////////////////
// CTarea11Dlg dialog

CTarea11Dlg::CTarea11Dlg(CWnd* pParent /*=NULL*/)

: CDialog(CTarea11Dlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CTarea11Dlg)
E_Px = 0;
E_Py = 0;
E_Peso = _T("");
E_PuntoSale = 0;
E_CadenaSale = _T("");
E_Camion = 0;
E_TolSectorImpar=0;
E_TolSectorTemp=0;
E_InFilePath=_T("");
E_OutFilePath=_T("");
E_OutTempFilePath=_T("");
E_Parada = 0;
E_AnguloLimite = 0;
E_ArbolTotal = 0;
E_TotalDivisiones=0;
//}}AFX_DATA_INIT
// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CTarea11Dlg::DoDataExchange(CDataExchange* pDX)

{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CTarea11Dlg)
DDX_Control(pDX, IDC_LIST4, L_CPolares);
DDX_Control(pDX, IDC_LIST3, L_Tree);
DDX_Control(pDX, IDC_LIST2, L_Dist);
DDX_Control(pDX, IDC_SECTORLIST, L_SectorPuntos);
DDX_Control(pDX, IDC_CHECK1, C_File);
DDX_Control(pDX, IDC_CHECK2, C_List);
DDX_Text(pDX, IDC_EDIT1, E_Px);
DDX_Text(pDX, IDC_EDIT2, E_Py);
DDX_Text(pDX, IDC_EDIT3, E_Peso);
DDX_Text(pDX, IDC_EDIT6, E_Camion);
DDX_Text(pDX, IDC_SORIGEN, E_CadenaOrigen);
DDX_Text(pDX, IDC_TSIMPAR, E_TolSectorImpar);
DDX_Text(pDX, IDC_TSTEMP, E_TolSectorTemp);
DDX_Text(pDX, IDC_TXTFILE, E_InFilePath);
DDX_Text(pDX, IDC_TXTOFILE, E_OutFilePath);
DDX_Text(pDX, IDC_TXTTEMPFILE, E_OutTempFilePath);
DDX_Text(pDX, IDC_EDIT7, E_Parada);
DDX_Text(pDX, IDC_EDIT8, E_AnguloLimite);
DDX_Text(pDX, IDC_EDIT9, E_ArbolTotal);
DDX_Text(pDX, IDC_TXTDIVTREE, E_TotalDivisiones);
//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CTarea11Dlg, CDialog)
//{{AFX_MSG_MAP(CTarea11Dlg)
ON_WM_PAINT()
ON_WM_QUERYDRAGICON()
ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
ON_BN_CLICKED(IDC_BUTTON2, OnButton2)
ON_BN_CLICKED(IDC_BUTTON3, OnButton3)
ON_BN_CLICKED(IDC_CALCSECT, OnCalcsect)
ON_BN_CLICKED(IDC_BMARCAO, OnBmarcao)
ON_BN_CLICKED(IDC_OFILE, OnOfile)
ON_BN_CLICKED(IDC_BOCALCULO, OnBocalculo)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////

117
// CTarea11Dlg message handlers

void CTarea11Dlg::OnButton1()
{
UpdateData(TRUE);

if([Link](E_Px,E_Py) == FALSE)
MessageBox("El punto ya existe","Error", MB_ICONEXCLAMATION);
else
{
L_CPolares.ResetContent();
int n;
n = [Link]();
for(int i=1; i<= n; i++)
L_CPolares.AddString([Link](i));
}
E_Px = E_Py = 0;
// TODO: Add your control notification handler code here
UpdateData(FALSE);
}

void CTarea11Dlg::OnButton2()
{
int pos =0;
int ne = [Link]();
double dis;
L_Dist.ResetContent();
[Link]();

for(int a = 1; a < ne ; a++)

for(int b = a+1; b <= ne; b++)
{
dis = [Link](a,b);
[Link](a,b,dis);
}
ne = [Link]();
L_Dist.AddString("Distancias Procesadas");

// TODO: Add your control notification handler code here

}

void CTarea11Dlg::OnButton3()
{

L_Tree.ResetContent();
[Link]([Link]());
CString str;
int mar = 0;

UpdateData(TRUE);
f_totTreeW = [Link]() + ([Link]()*E_Parada);
[Link]("%.4f",f_totTreeW);
E_Peso = str;
L_Tree.AddString("Arbol procesado");

UpdateData(FALSE);
// TODO: Add your control notification handler code here
}

void CTarea11Dlg::OnCalcsect()
{
// TODO: Add your control notification handler code here
double f_impairW,f_noderatio,f_thistreeweight,f_atreeweight,f_lastdifference,f_thisdifference,f_tolisector,f_toltempsector;
int b_numimparCamion,i_node,i,i_Sector=0,i_totSector=0,i_newSector=0,b_divideByAngle,i_ns=0;
int
i_nodenumber,i_x,i_y,b_isMaxOptimization,b_isLastSector,i_LastNode,i_pendX,i_pendY,b_IsPointPending,totSectores;

118
CString s_nodoanalizado;
CString SForTempSecFile,s_thisTempW;
int cont_puntos;
int cont_puntos2;
[Link]();
CopyList(LP,LPWork);

SForTempSecFile="Sector,Peso\n";

UpdateData(TRUE);
b_numimparCamion=E_Camion%2;

i_ns=ceil(double(E_Camion)/2);

if(b_numimparCamion)
{
totSectores=(E_Camion-1)/2+1;
}
else
{
totSectores=E_Camion/2;
}

f_impairW=f_totTreeW/E_Camion;
f_tolisector=f_impairW*(1+E_TolSectorImpar/100);
f_toltempsector=f_impairW*2*(1+E_TolSectorTemp/100);

if(b_numimparCamion)
{
//Se marca el primer nodo con el sector 1
i_Sector++;
f_noderatio=GetLowerRatio(LP,i_node);
[Link](i_node);
[Link](i_Sector);
[Link]([Link](),[Link]());
[Link](i_node);
cont_puntos=1;

//Se marcan los nodos dentro del sector 1

do
{
f_noderatio=GetLowerRatio(LPWork,i_node);
[Link](i_node);
[Link](i_Sector);
i_LastNode=i_Sector;
[Link]([Link](),[Link]());
[Link](i_node);
FillDistancesList(LPA,LDA);
[Link]([Link]());
cont_puntos++;
f_thistreeweight= (cont_puntos*E_Parada)+[Link]();
}
while(f_thistreeweight<f_tolisector);

s_thisTempW.Format("%d,%f\n",i_Sector,f_thistreeweight);
SForTempSecFile+=s_thisTempW;

[Link](i_LastNode);
[Link](i_Sector+1);

//Se forman los sectores siguientes en base al angulo

b_isLastSector=0;
b_IsPointPending=0;

while([Link]()>0)

119
{
[Link]();
[Link]();
i_Sector++;
if(b_IsPointPending)
{
[Link](i_pendX,i_pendY);
}
if(totSectores == i_Sector)
b_isLastSector=1;

i=1;
f_thistreeweight=0;
cont_puntos=1;
do
{
[Link](1);
[Link]();
i_LastNode=[Link]();
[Link](i_LastNode);
[Link](i_Sector);
i_pendX=[Link]();
i_pendY=[Link]();
[Link](i_pendX,i_pendY);
[Link]([Link]());
if(i>1)
{
FillDistancesList(LPA,LDA);
[Link]([Link]());
f_thistreeweight=(cont_puntos*E_Parada) + [Link]();
}
i++;
cont_puntos++;

}while(f_thistreeweight<f_toltempsector && [Link]()>0|| b_isLastSector && [Link]()>0);

if(b_isLastSector==0)
{
[Link](i_LastNode);
[Link](i_Sector+1);
b_IsPointPending=1;
}

i_totSector=i_Sector;
i_newSector=i_Sector+1;

//Se calculan el largo y el ancho de cada sector

if(b_numimparCamion)
i_Sector=2;
else
i_Sector=1;

for(i_Sector;i_Sector<=i_totSector;i_Sector++)
{
[Link]();
[Link]();
[Link]();
[Link]();
b_isMaxOptimization=0;
b_divideByAngle=CalculateSectorWideAndWidth(LP,LPWork,i_Sector,i_x,i_y,i_node);

if([Link]()<3)
{
for(int i=1;i<=[Link]();i++)
{
[Link](i);
[Link]([Link]());

120
 if(i%2==1)
[Link](i_Sector);
else
[Link](i_newSector);
}
}
else
{
[Link](xo,yo,0,1);
[Link](i_x,i_y);
[Link](xo,yo,0,1);
[Link](i_node);
[Link](i_newSector);
[Link](i_node);
cont_puntos2=1;
cont_puntos= [Link]();
FillDistancesList(LPA,LDA);
FillDistancesList(LPWork,LDW);
[Link]([Link]());
[Link]([Link]());
f_thistreeweight=(cont_puntos2*E_Parada) + [Link]();
f_atreeweight=(cont_puntos*E_Parada) + [Link]();
f_lastdifference=fabs(f_thistreeweight-f_atreeweight);
if(b_divideByAngle)
{
//Se divide el sector por el angulo
while(b_isMaxOptimization==0&&[Link]()>1)
{
[Link]();
[Link]();
[Link]([Link]());
[Link]([Link](),[Link]());
i_nodenumber=[Link]();
[Link]([Link]());
cont_puntos = [Link]();
cont_puntos2++;
FillDistancesList(LPA,LDA);
FillDistancesList(LPWork,LDW);
[Link]([Link]());
[Link]([Link]());
f_thistreeweight= (cont_puntos2*E_Parada) +
[Link]();
f_atreeweight= (cont_puntos*E_Parada) +
[Link]();
f_thisdifference=fabs(f_thistreeweight-f_atreeweight);
if(f_thisdifference<f_lastdifference)
{
[Link](i_nodenumber);
[Link](i_newSector);
f_lastdifference=f_thisdifference;
}
else
{
b_isMaxOptimization=1;
s_thisTempW.Format("%d,%f\n",i_Sector,f_atreeweight);
SForTempSecFile+=s_thisTempW;
s_thisTempW.Format("%d,%f\n",i_newSector,f_thistreeweight);
SForTempSecFile+=s_thisTempW;
}
}

}
else
{
//Se divide el sector por el radio
while(b_isMaxOptimization==0&&[Link]()>1)
{
[Link]();
[Link]();

121
 i_nodenumber=GetHigherRatioNodeNumber(LPWork,i_x,i_y);
[Link](i_nodenumber);
[Link](i_x,i_y);
[Link](i_nodenumber);
cont_puntos = [Link]();
cont_puntos2++;
FillDistancesList(LPA,LDA);
FillDistancesList(LPWork,LDW);
[Link]([Link]());
[Link]([Link]());
f_thistreeweight=(cont_puntos2*E_Parada) +
[Link]();
f_atreeweight= (cont_puntos*E_Parada) +
[Link]();
f_thisdifference=fabs(f_thistreeweight-f_atreeweight);
if(f_thisdifference<f_lastdifference)
{
[Link](i_nodenumber);
[Link](i_newSector);
f_lastdifference=f_thisdifference;
}
else
{
b_isMaxOptimization=1;
s_thisTempW.Format("%d,%f\n",i_Sector,f_atreeweight);
SForTempSecFile+=s_thisTempW;
s_thisTempW.Format("%d,%f\n",i_newSector,f_thistreeweight);
SForTempSecFile+=s_thisTempW;
}
}
}
}
i_newSector++;
}

CString SForFile,SThisRegister,SForPrintList;
SForFile="X,Y,Sector\n";

L_SectorPuntos.ResetContent();
for(i=1;i<=[Link]();i++)
{
SForPrintList=[Link](i,SThisRegister);
if(C_List.GetCheck())
L_SectorPuntos.AddString(SForPrintList);
if(C_File.GetCheck())
SForFile+=SThisRegister;
}

if(C_File.GetCheck())
{

const char *filename = E_OutFilePath;

FILE *Archi;
Archi = fopen(filename,"a");
fprintf(Archi,SForFile);
fclose(Archi);
const char *tempfilename = E_OutTempFilePath;
FILE *TempArchi;
TempArchi = fopen(tempfilename,"a");
fprintf(TempArchi,SForTempSecFile);
fclose(TempArchi);
}

UpdateData(FALSE);

double CTarea11Dlg::GetLowerRatio(CListaPuntos& PointList,int &i_node)

122
{
int i_pointlistsize,i=1;
double f_lowratio=0,f_noderatio;

i_pointlistsize=[Link]();

if(i_pointlistsize>0)
{
[Link](i);
f_lowratio=[Link]();
i_node=[Link]();
i++;
for(i;i<=i_pointlistsize;i++)
{
[Link](i);
f_noderatio=[Link]();
if(f_noderatio<f_lowratio)
{
f_lowratio=f_noderatio;
i_node=[Link]();
}
}

return f_lowratio;
}

void CTarea11Dlg::FillDistancesList(CListaPuntos& PointList,CListaDistancias &DistanceList)

{
int pos =0;
int ne = [Link]();
[Link]();

for(int a = 1; a < ne ; a++)

for(int b = a+1; b <= ne; b++)
[Link](a,b,[Link](a,b));
}

void CTarea11Dlg::CopyList(CListaPuntos& ListToCopy,CListaPuntos& NewList)

{

for(int i = 1; i <= [Link]() ; i++)

{
[Link](i);
[Link]([Link](),[Link]());

}
}

int CTarea11Dlg::CalculateSectorWideAndWidth(CListaPuntos& ListToCheck,CListaPuntos& SectorPointList,int sector, int& x,

int& y, int& mynumber)
{
double f_maxangle,f_minangle,f_sectorangle,f_divisionangle,f_triangleangle;
double f_maxabovedistance=0,f_maxbelowdistance=0,f_currentdistance=0,f_currentratio;
double wide,width;
int i_xwidth,i_ywidth,b_isWide;

//Crear la lista con los puntos correspondientes al sector

for(int i = 1; i <= [Link]() ; i++)
{
[Link](i);
if([Link]()==sector)

[Link]([Link](),[Link](),[Link]());

123
 }

[Link](1);
f_minangle=[Link]();
[Link]([Link]());
f_maxangle=[Link]();
f_sectorangle=f_maxangle-f_minangle;
f_divisionangle=f_minangle+f_sectorangle/2;
width=0;
wide=f_sectorangle;

for(i = 1; i <= [Link]() ; i++)

{
[Link](i);
f_currentratio=[Link]();
if(f_currentratio>width)
{
width=f_currentratio;
i_xwidth=[Link]();
i_ywidth=[Link]();
mynumber=[Link]();
}

if(wide>E_AnguloLimite)
{
x=[Link]();
y=[Link]();
b_isWide=1;
mynumber=[Link]();
}
else
{
x=i_xwidth;
y=i_ywidth;
b_isWide=0;
}

return b_isWide;

double CTarea11Dlg::GetDistanceToSectorDivision(double myangle,double myratio)

{
double distancetoret;

distancetoret=fabs(sin(myangle)*myratio);

return distancetoret;
}

void CTarea11Dlg::OnBmarcao()
{
UpdateData(TRUE);
xo=E_Px;
yo=E_Py;
E_CadenaOrigen.Format("Deposito: (%d,%d)",xo,yo);
UpdateData(FALSE);

int CTarea11Dlg::GetHigherRatioNodeNumber(CListaPuntos& PointList,int& x, int& y)

124
{
double f_maxratio=0,f_noderatio;
int nodenumber=0;
x=y=0;

for(int i = 1; i <= [Link]() ; i++)

{
[Link](i);

f_noderatio=[Link]();
if(f_noderatio>f_maxratio)
{
f_maxratio=f_noderatio;
nodenumber=[Link]();
x=[Link]();
y=[Link]();
}
}
return nodenumber;
}

void CTarea11Dlg::OnOfile()
{
UpdateData(TRUE);
int prueba;
const char *filename = E_InFilePath;

UpdateData(FALSE);

int i_newx,i_newy,n;
CString myString;
char linea[100], cadena[100];
FILE *Archi;
Archi = fopen(filename,"r");
if (Archi==0)
fprintf(stderr,"Fallo al abrir %s \n",filename);

for(int j=0;;j++)
{
if (feof(Archi)) break;

for (int i=0;i<100;i++)

{
linea[i]=fgetc(Archi);
if (linea[i]=='\n') break;
if (feof(Archi)) break;
}
linea[i] = '*'; //fin d datos de las celdas

//Procesamiento de cada linea

UpdateData(TRUE);

myString= linea; //ultima cadena

i_newx=atoi([Link]([Link](',')));
i_newy=atoi([Link]([Link](',')+1,[Link]('*')-[Link](',')-1));
UpdateData(TRUE);

[Link](i_newx,i_newy);

L_CPolares.ResetContent();
n = [Link]();

UpdateData(FALSE);
}

fclose(Archi);
L_CPolares.AddString("Archivo Procesado");

125
 if(E_TotalDivisiones>0)
f_totTreeW=CalculateTreeWeightbyParts() + ([Link]()*E_Parada);
else
{
OnButton2();
OnButton3();
}

void CTarea11Dlg::OnBocalculo()
{
OnOfile ();
OnCalcsect();
}

double CTarea11Dlg::CalculateTreeWeightbyParts()
{

CListaPuntos LPAUX,LPCurrent;
CListaDistancias LDAUX;
int i_ListSize;
double f_treeweight;
CString str;

i_ListSize=[Link]();
i_ListSize=i_ListSize/E_TotalDivisiones;
f_treeweight=0;
[Link]();
[Link]();
[Link]();

CopyList(LP,LPAUX);

while([Link]()>0)
{
[Link]();
[Link]();
GetLastElements(LPAUX,LPCurrent,i_ListSize);
FillDistancesList(LPCurrent,LDAUX);
[Link]([Link]());
f_treeweight=f_treeweight+ [Link]();
}

L_Tree.ResetContent();
UpdateData(TRUE);
[Link]("%.4f",f_treeweight);
E_Peso = str;
L_Tree.AddString("Arbol procesado");

UpdateData(FALSE);
return f_treeweight;
}

void CTarea11Dlg::GetLastElements(CListaPuntos& ListToGet,CListaPuntos& ResultsList,int myElementsnum)

{

for(int i = 1; i <= myElementsnum; i++)

{
if ([Link]() > 0)
{
[Link](1);
[Link]([Link](),[Link]());
[Link](1);
}
}
}

126