PONTIFICIA UNIVERSIDAD CATÓLICA DEL PERÚ FACULTAD DE CIENCIAS E INGENIERÍA Sistema de entrega a domicilio con ruta de despacho de productos para una cadena de boticas o farmacias Tesis para optar por el Título de Ingeniero Informático, que presenta el bachiller: Ricardo Miguel Vente Montes Asesor: Mag. César Augusto Aguilera Serpa Lima, septiembre de 2019 I Resumen Uno de los canales de consumo con mayor crecimiento y oportunidades en estos últimos años es el mercado farmacéutico; ante este crecimiento, la preferencia cada vez mayor de las personas en comprar productos con entrega a domicilio y que el comercio electrónico se está volviendo cada vez más rentable en el país, conocidas empresas dedicadas a la venta de medicamentos han optado por abrir nuevos canales de venta como el de venta a domicilio, también conocido como delivery, para mejorar aún más sus ingresos. De esta manera, el servicio de delivery se está volviendo un punto importante para las boticas y farmacias que operan en Lima, por desgracia este servicio presenta varios problemas que de no ser resueltos perjudicarían directamente al negocio. Los principales problemas identificados son: Lidiar con el tráfico de la ciudad, que de no ser tomado en cuenta podría generar retrasos en las entregas y con ello descontento en los clientes. No conocer el stock global de sus productos y de esta manera dejar de atender pedidos que se crean no disponibles. Y no conocer el estado de disponibilidad de sus repartidores, lo que generarían tiempos muertos que pueden ser usados para la entrega de más productos. Por estas razones se propone implementar un sistema de entrega a domicilio que considere el stock de los locales dentro de un área determinada al momento de realizar la venta y un algoritmo de enrutamiento que seleccione la farmacia, o grupo de farmacias que cumplirán con el pedido y genere un óptimo recorrido indicando el orden de las farmacias a recorrer para completar la orden y llegar a entregar el producto en el punto acordado. II Dedicatoria A Dios por estar siempre presente en mi vida. A mis padres Elsa y Ricardo por su apoyo incondicional. A mis familiares y amigos que me ayudaron a lo largo de mi carrera. A mi asesor, el Mag. César Aguilera, por su tiempo y dedicación en este proyecto. III Tema FCI IV V Tabla de Contenidos ÍNDICE DE FIGURAS .............................................................................................. VII ÍNDICE DE TABLAS ............................................................................................... VIII CAPÍTULO 1. GENERALIDADES .............................................................................. 1 1.1 PROBLEMÁTICA .................................................................................................. 1 1.2 OBJETIVOS .......................................................................................................... 5 1.2.1 Objetivos específicos .......................................................................................... 5 1.2.2 Resultados esperados ......................................................................................... 5 1.3 HERRAMIENTAS Y MÉTODOS .............................................................................. 7 1.3.1 Herramientas ....................................................................................................... 8 1.3.2 Metodologías ..................................................................................................... 11 1.3.3 Métodos .............................................................................................................. 12 1.3.4 Modelos .............................................................................................................. 13 1.4 ALCANCE, LIMITACIONES Y RIESGOS ................................................................. 13 1.4.1 Alcance ............................................................................................................... 13 1.4.2 Limitaciones ...................................................................................................... 14 1.4.3 Riesgos ............................................................................................................... 14 1.5 JUSTIFICACIÓN Y VIABILIDAD DEL PROYECTO ................................................... 15 1.5.1 Justificación ....................................................................................................... 15 1.5.2 Viabilidad .......................................................................................................... 15 CAPÍTULO 2. MARCO LEGAL/REGULATORIO/CONCEPTUAL/OTROS .... 17 2.1 MARCO CONCEPTUAL ....................................................................................... 17 2.1.1 Despacho ........................................................................................................... 17 2.1.2 Repartidor .......................................................................................................... 17 2.1.3 Unidad de transporte ....................................................................................... 17 2.1.4 Producto ............................................................................................................. 17 2.1.5 Heurística .......................................................................................................... 17 2.1.6 Experimentación Numérica (Diseño de Experimentos) .............................. 18 2.1.7 Ruta de despacho .............................................................................................. 18 2.1.8 Inventario ........................................................................................................... 18 2.1.9 Transacción de salida ...................................................................................... 18 2.1.10 Transacción de entrada ................................................................................... 18 2.1.11 Control de Inventarios ..................................................................................... 19 2.2 MARCO LEGAL ................................................................................................. 19 CAPÍTULO 3. ESTADO DEL ARTE ......................................................................... 20 3.1 REVISIÓN Y DISCUSIÓN ..................................................................................... 20 3.1.1 Artículos ............................................................................................................. 20 3.1.2 Productos Comerciales .................................................................................... 20 3.1.3 Tesis .................................................................................................................... 22 3.2 CONCLUSIONES ................................................................................................. 22 CAPÍTULO 4. PRESENTACIÓN DE LOS RESULTADOS ESPERADOS .......... 23 VI 4.1 OE1 MODELAR EL PROCESO DE RECEPCIÓN, PROCESAMIENTO Y ENTREGA DE UN PEDIDO ......................................................................................................................... 23 4.1.1 Recepción ........................................................................................................... 23 4.1.2 Procesamiento de la información ................................................................... 23 4.1.3 Despacho ........................................................................................................... 24 4.1.4 Diagrama de procesos ..................................................................................... 24 4.2 OE2 DISEÑO DE UN ALGORITMO PARA LA UBICACIÓN DE LOS LOCALES FARMACÉUTICOS A RECORRER. .................................................................................... 26 4.2.1 Función Objetivo .............................................................................................. 27 4.2.2 Pseudocódigo .................................................................................................... 28 4.2.3 Ejemplo .............................................................................................................. 28 4.2.4 Validación .......................................................................................................... 29 4.3 OE3 DISEÑAR UN ALGORITMO GRASP CONSTRUCCIÓN Y GENÉTICO QUE ASIGNE EL RECORRIDO QUE HARÁ EL REPARTIDOR. ...................................................... 30 4.3.1 GRASP Construcción ....................................................................................... 30 4.3.2 Algoritmo Genético .......................................................................................... 32 4.4 OE4: REALIZAR UNA EXPERIMENTACIÓN NUMÉRICA ENTRE LOS RESULTADOS OBTENIDOS DEL ALGORITMO GENÉTICO Y GENÉTICO + GRASP ................................... 35 4.4.1 Resultados de ambos algoritmos .................................................................... 35 4.4.2 Experimentación numérica .............................................................................. 36 4.5 OE5 DISEÑAR E IMPLEMENTAR UN MÓDULO QUE USE EL ALGORITMO DE SELECCIÓN DE FARMACIAS ........................................................................................... 39 4.5.1 Estructura de datos .......................................................................................... 39 4.5.2 Especificación de requisitos ............................................................................ 44 4.5.3 Arquitectura del sistema .................................................................................. 45 4.5.4 Diagrama de flujo del algoritmo .................................................................... 45 4.5.5 Implementación del algoritmo ........................................................................ 46 4.5.6 Validación .......................................................................................................... 52 4.6 OE6: IMPLEMENTAR UNA VISTA QUE, USANDO EL ALGORITMO IMPLEMENTADO ANTERIORMENTE MUESTRE EL RECORRIDO EN UN MAPA .............................................. 53 4.6.1 Mapa que muestra la ruta de despacho. ........................................................ 53 4.6.2 Casos de prueba del sistema planteado frente a Google Maps. ................ 53 CAPÍTULO 5. CONCLUSIONES Y TRABAJOS FUTUROS. ............................... 57 EN ESTA SECCIÓN SE PRESENTARÁN LAS CONCLUSIONES DEL SISTEMA, ADEMÁS SE PRESENTARÁN LOS POSIBLES TRABAJOS FUTUROS CON LO QUE SE PUEDE OPTIMIZAR EL RESULTADO O MEJORAR SU DESEMPEÑO. ..................................................................... 57 5.1 CONCLUSIONES Y TRABAJOS FUTUROS .............................................................. 57 5.2 TRABAJOS FUTUROS .......................................................................................... 58 BIBLIOGRAFÍA .......................................................................................................... 59 ANEXOS ....................................................................................................................... 62 VII Índice de Figuras Ilustración 1 Encuesta a farmacias que cuentan con el servicio a domicilio .................... 2 Ilustración 2 Encuesta a farmacias, atención de pedidos de entrega a domicilio ............. 2 Ilustración 3 Encuesta a farmacias, conocimiento de productos en otros locales ............ 3 Ilustración 4 Encuesta a motorizados, medio de ubicación del destino ........................... 4 Ilustración 5 Modelamiento del proceso de recepción de un pedido. ............................ 25 Ilustración 6 Modelamiento del proceso de edición de un producto .............................. 25 Ilustración 8 Implementación de la funcion Harvesine en Javascript (Movable Type Scripts, s.f.) ..................................................................................................................... 27 Ilustración 9 Ejemplo de funcionamiento del algoritmo de selección de farmacias ...... 29 Ilustración 10 Ejemplo del funcionamiento del algoritmo de enrutamiento (Grasp Construcción) ................................................................................................................. 32 Ilustración 11 Ejemplo del funcionamiento del algoritmo de enrutamiento (Genético) 35 Ilustración 12 Datos de entrada y salida de la ejecución de ambos algoritmos............. 36 Ilustración 13 Gráfico de la distribución normal de los resultados usando el algoritmo genético. .......................................................................................................................... 37 Ilustración 14 Gráfico de la distribución normal de los resultados usando el algoritmo genético + GRASP. ........................................................................................................ 37 Ilustración 15 Datos cargados en RStudio. ..................................................................... 38 Ilustración 16 Ejecución de la funcion T-Student en RStudio. ...................................... 38 Ilustración 17 Imagen de la zona de Pueblo Libre ......................................................... 39 Ilustración 18 Imagen de la zona delimitada para el proyecto ....................................... 40 Ilustración 19 Imagen de los puntos que forman la zona del proyecto .......................... 41 Ilustración 21 Diagrama de base de datos ...................................................................... 43 Ilustración 22 Vista de despliegue del sistema. .............................................................. 45 Ilustración 23 Diagrama de flujo del algoritmo de selección de farmacias.................... 46 Ilustración 24 Creación del pedido. ................................................................................ 47 Ilustración 25 Salida del algoritmo de selección de farmacias. ...................................... 47 Ilustración 26 Salida del algoritmo GRASP para hallar el recorrido. ............................ 48 Ilustración 28 Pantalla principal del sistema. ................................................................. 50 Ilustración 29 Pantalla de lista de farmacias del sistema................................................ 50 Ilustración 30 Pantalla que lista los productos en una farmacia. .................................... 51 Ilustración 32 Pantalla de edición de productos. ............................................................ 52 Ilustración 33 Pantalla de edición de motorizados. ........................................................ 52 Ilustración 34 Ventana que muestra la ruta a seguir. ...................................................... 53 Ilustración 35 Salida del algoritmo genético usando 3 generaciones. ............................ 54 Ilustración 36 Salida del algoritmo genético usando 10 generaciones. .......................... 54 Ilustración 37 Recorrido usando Google Maps. ............................................................. 55 VIII Índice de Tablas Tabla 1 Tabla de Verificación de objetivos. ..................................................................... 6 Tabla 2 Tabla de Verificación de objetivos. ..................................................................... 7 Tabla 3 Lista de riesgos .................................................................................................. 14 Tabla 4 Cronograma para la implementación del algoritmo. ......................................... 16 Tabla 5 Cronograma para la implementación del sistema. ............................................. 16 Tabla 6 Pruebas del algoritmo de selección ................................................................... 29 Tabla 7 Lista de establecimientos MiFarma en el distrito de Pueblo Libre ................... 40 Tabla 8 Tipos de datos. ................................................................................................... 44 Tabla 9 Especificación de requisitos. ............................................................................. 44 Tabla 10 Casos de prueba. .............................................................................................. 55 1 Capítulo 1. Generalidades 1.1 Problemática Uno de los canales de consumo con mayor crecimiento y oportunidades en estos últimos años es el mercado farmacéutico. Según la consultora de investigación del consumidor Kantar Worldpanel, entre los años 2015 y 2016, las farmacias y boticas han tenido un crecimiento en ventas del 14% y 13% respectivamente, a diferencia de otros canales como los mercados, que solo se han incrementado en un 4%. (Kantar Worldpanel, 2017) Ante este crecimiento, y la preferencia, cada vez mayor, de las personas en comprar productos desde la comodidad de su hogar (Capital, 2017), las farmacias han optado por nuevos canales de ventas como el servicio de entrega a domicilio que, revisando portales web de reconocidos locales de venta de productos farmacéuticos, muchas de ellas ya han adoptado. Pues el servicio de comercio electrónico se está volviendo cada vez más rentable en el país. (La República, 2014) De esta manera el servicio de entrega a domicilio se está volviendo un punto clave para las boticas o farmacias que operan en Lima, por desgracia este servicio presenta varios problemas; uno de ellos es el tráfico debido a la gran cantidad de autos que transitan actualmente por las calles (La República, 2015) y porque algunos conductores no respetan las normas de tránsito y terminan conduciendo como mejor les parece (RPP, 2017). Esto afecta directamente al servicio pues prolonga el tiempo estimado de las entregas. Varias farmacias ya cuentan con este servicio en la actualidad, por lo que se realizó una encuesta entre diez de estas farmacias con el fin de tener una referencia del alcance que el servicio debería cumplir, ésta arrojó los siguientes resultados: • Todas las farmacias consultadas que tienen sistema de entrega a domicilio cuentan con una central de llamadas para este servicio y no cuentan con teléfono particular para realizar pedidos por este medio. Estas centrales tienen acceso al stock de los locales y usan un criterio de selección para poder elegir la que despachará el producto. (ver Ilustración 1) 2 Boticas o farmacias que cuentan con entrega a domicilio 9 8 7 6 5 4 3 2 1 0 central telefonica telefono en el local no cuenta con el servicio Ilustración 1 Encuesta a farmacias que cuentan con el servicio a domicilio • Los repartidores se encuentran ubicados en un local de la cadena, pero ellos no atienden solo a este establecimiento, si no que están a la espera de los pedidos que le pueda asignar la central (ver Ilustración 2). Con esto disminuye el posible tiempo muerto que podría presentarse de solo atender los pedidos de un local. Atención de pedidos 9 8 7 6 5 4 3 2 1 0 Solo del propio local Los que diga la central Ilustración 2 Encuesta a farmacias, atención de pedidos de entrega a domicilio 3 • Las farmacias cuentan con un sistema de inventario para poder realizar consultas sobre la ubicación de determinados productos, tal como muestra la Ilustración 3. Conocimiento de otros locales donde el producto se encuentra disponible 9 8 7 6 5 4 3 2 1 0 Conoce los locales que cuentan con el No conoce los locales que cuentan con el producto producto Ilustración 3 Encuesta a farmacias, conocimiento de productos en otros locales Con los resultados de la encuesta previamente mencionados se puede deducir que los principales problemas al momento de implementar un sistema de despacho son: la posible ineficiencia que este servicio pueda presentar al no conocer el stock disponible en todas sus farmacias al momento de ofrecer un producto, de esta manera podría dejar de atender pedidos que se crean no disponibles; no tener conocimiento de los repartidores en el área para que puedan atender otros pedidos y no contar con un sistema de enrutamiento que facilite el recorrido a seguir por el repartidor. También se realizó una encuesta a repartidores, ver Ilustración 4, en su centro de trabajo, y el problema más importante que se identificó es que la empresa no les brinda un sistema de rutas para determinar el camino a seguir para despachar el producto, y si bien pueden usar aplicaciones de mapas como Google Maps o Waze, terminan empleando otros medios como un mapa ubicado en alguna zona del local o sus propios conocimientos de calles, que en la mayoría de casos no llegan a ser tan buenos como el mencionado al inicio, lo que genera posibles retrasos en las entregas. 4 Medio de ubicación del domicilio 7 6 5 4 3 2 1 0 Mapa Conocimientos propios Ilustración 4 Encuesta a motorizados, medio de ubicación del destino Considerando lo antes mencionado, el mercado farmacéutico presenta una oportunidad de ventas en el canal de entrega a domicilio, pero a su vez se puede afirmar que, al momento de implementar un sistema de entrega a domicilio para este tipo de negocio (cadena de tiendas), se debe tomar en consideración el stock disponible en todas las farmacias al momento de ofrecer un producto para así poder atender la mayor cantidad de pedidos, tener conocimiento de los repartidores en el área para que puedan atender otros pedidos y contar con un sistema de enrutamiento que facilite el recorrido a seguir por el repartidor. Habiendo definido la problemática, este proyecto pretende como alternativa de solución, implementar un sistema de entrega a domicilio que considere el stock de los locales dentro de un área determinada al momento de realizar la venta. Además, para el sistema de entrega se propone implementar un algoritmo heurístico para seleccionar las farmacias y motorizados que atenderán el pedido y emitir una posible ruta de despacho que puedan seguir los motorizados para realizar las entregas de una manera óptima. 5 1.2 Objetivos Objetivo General Implementar un sistema de entrega a domicilio con ruta de despacho, de productos para una cadena de boticas o farmacias. 1.2.1 Objetivos específicos 1. OE1: Modelar el proceso de recepción, procesamiento y entrega de un pedido. 2. OE2: Diseñar un algoritmo que ubique los locales farmacéuticos dentro de un área determinada y el repartidor disponible para realizar la entrega. 3. OE3: Diseñar un algoritmo GRASP Construcción y un algoritmo genético que asigne el recorrido que hará el repartidor para realizar los productos solicitados. 4. OE4: Realizar una experimentación numérica con los resultados obtenidos con el algoritmo genético y el genético + GRASP para determinar cuál es el mejor algoritmo para usar. 5. OE5: Diseñar e implementar un módulo que, usando el algoritmo implementado en OE2, muestre los locales farmacéuticos dentro de un área determinada y el repartidor seleccionado que se encuentre disponible. 6. OE6: Diseñar e implementar una vista que, usando el mejor algoritmo en base a la experimentación numérica, muestre el recorrido que hará el repartidor para realizar su tarea pasando por las farmacias seleccionadas de la manera óptima. 1.2.2 Resultados esperados 1. Resultados del Objetivo Específico 1 1. RE1: Documento de análisis explicando los procesos del sistema. 2. Resultados del Objetivo Específico 2 1. RE2: Pseudocódigo e implementación del algoritmo que selecciona las farmacias y motorizados que cumplirán con los pedidos. 3. Resultados del Objetivo Específico 3 1. RE3: Pseudocódigo e implementación del algoritmo GRASP Construcción que servirá para hallar la población inicial del algoritmo genético. 2. RE4: Pseudocódigo e implementación del algoritmo genético. 6 4. Resultados del Objetivo Específico 4 1. RE5: Resultados de la ejecución del algoritmo genético y genético + GRASP 2. RE6: Experimentación numérica en base a los resultados obtenidos en el punto anterior. 5. Resultados del Objetivo Específico 5 1. RE7: Estructura de datos para el sistema. 2. RE8: : Módulo que identifique las farmacias a ser elegidas para atender el pedido ubicando las que, solas o en conjunto, cumplan con la totalidad del pedido y se encuentren dentro de un área definida por un radio determinado desde el local donde se hizo la llamada y evaluando, para esta selección, el costo beneficio de las rutas versus el pedido. Y el repartidor que no cuente con despachos pendientes y tenga espacio para realizar la entrega. 6. Resultados del Objetivo Específico 6 1. RE9: Ruta de despacho que valide el correcto funcionamiento módulo. 2. RE10: Casos de prueba del sistema planteado frente a Google Maps. En la Tabla 1 se muestra la relación entre cada objetivo y cómo podrá ser verificado, además de los resultados que estos van a arrojar. Tabla 1 Tabla de Verificación de objetivos. Objetivos Resultados Intermedios Medios de Verificación Específicos 1 OE1 Documento de análisis que Comparación con los datos explica el procedimiento. obtenidos en las encuestas. 2 OE2 Pseudocódigo e implementación Pruebas unitarias sobre el del algoritmo para la selección de algoritmo. farmacias. 3 OE3 Pseudocódigo e implementación Pruebas unitarias sobre los del algoritmo GRASP algoritmos. Construcción. Pruebas integrales con el Pseudocódigo e implementación algoritmo de OE2. del algoritmo genético. 4 OE4 Resultados de ambos algoritmos. Resultado de la experimentación numérica usando un método estadístico conocido. 7 Objetivos Resultados Intermedios Medios de Verificación Específicos 5 OE5 Estructura de datos. Pruebas unitarias sobre la Módulo que identifique las funcionalidad del módulo que farmacias que pueden ser validen la correcta selección de elegidas para atender un pedido los locales y motorizados. Pruebas de integración con el algoritmo seleccionado. 6 OE6 Mapa con la ruta de despacho Pruebas unitarias de señalizada enrutamiento de despachos que sirvan para validad el correcto funcionamiento del módulo. Pruebas de integración con el módulo anterior. Pruebas funcionales de todo el sistema. Casos de prueba del sistema planteado frente a Google Maps. 1.3 Herramientas y Métodos En la Tabla 2 se describen las herramientas, metodologías, métodos y modelos a utilizar para el logro de los resultados establecidos. Tabla 2 Tabla de Verificación de objetivos. Resultados esperados Herramientas RE1: Documento de análisis de • Draw.io estructuras RE2: Pseudocódigo e implementación del • Netbeans algoritmo que selecciona las farmacias y • Sublime Text 3 motorizados • MySQL • PhpMyAdmin • Apache • Extreme Programming (XP) RE3: Pseudocódigo del algoritmo • Netbeans GRASP construcción • Sublime Text 3 • MySQL • PhpMyAdmin • Apache • Extreme Programming (XP) RE4: Pseudocódigo del algoritmo • Netbeans Genético • Sublime Text 3 RE5: Resultados del algoritmo Genético • Netbeans y Genético + GRASP • Sublime Text 3 RE6: Experimentación numérica de los • RStudio algoritmos. • Google Docs 8 Resultados esperados Herramientas RE5: Estructura de datos • Netbeans • MySQL RE6: Módulo de identificación de • Netbeans farmacias y repartidores • Sublime Text 3 • Apache • MySQL • PhpMyAdmin • Modelo incremental RE7: Ruta de entrega a domicilio • Netbeans • Google Maps RE8: Casos de prueba del sistema • Plantilla de casos de prueba planteado frente a Google Maps. brindada en los cursos de la universidad. 1.3.1 Herramientas Draw.io Plataforma online que permite el uso de distintos diagramas de flujo, se diferencia de otras conocidas como Visio porque ésta es gratuita aun cuando posee casi la misma cantidad de herramientas disponibles que su competencia y que son las suficientes para poder llevar a cabo satisfactoriamente las tareas necesarias en el proyecto, otra característica es su integración con Google Drive, así lo cambios hechos se pueden guardar directamente en la cuenta de Google a su vez cuenta con todos los beneficios de esta cuenta, como colaboración en tiempo real e historial de modificaciones. (draw.io, s.f.). Se usará draw.io para realizar el pseudocódigo, y los distintos diagramas de la solución. Netbeans 8.1 Entorno de desarrollo integrado (IDE) que permite crear proyectos para distintas plataformas como Windows o Android, se caracteriza por ser un entorno ligero, de código abierto y con una interfaz simple, además posibilita el uso de lenguajes de programación como C, C++, Java, PHP, entre otros. (Netbeans, s.f.) Se desarrollarán los módulos de identificación de farmacias y repartidores y enrutamiento usando Netbeans en el lenguaje de programación Java, además se usará esta IDE para el desarrollo de los algoritmos. 9 Además, se usarán las librerías jxl para el manejo de documentos en MS Excel (Source Forge, s.f.) y mysql-connector-java para realizar las conexiones con la base de datos MySQL. (MySQL, s.f.). También se usará la librería gráfica de Netbeans para poder dibujar el recorrido del motorizado. Sublime Text 3 Editor de texto dedicado a lenguajes de programación que ayuda la fácil comprensión del código usando distintos formatos de texto para diferenciar variables, funciones, etc. Además, permite agregar y organizar distintos proyectos directamente desde el editor. (Sublime Text, s.f.). Sublime servirá para ayudar al desarrollo de los módulos al igual que Netbeans, pero su uso se enfocará más a la rápida visualización y modificación del código desarrollado. MySQL Motor de base de datos de código abierto que, a lo largo de los años, se ha posicionado como una de las mejores opciones para el manejo de base de datos debido a su sólida arquitectura, integración de datos y fiabilidad. Además, provee distintas opciones útiles para los desarrolladores, como escalabilidad, respaldo, entre otros. (MySQL, s.f.) Se usará MySQL como base para almacenar los datos de los puntos que forman el mapa, las conexiones entre estos puntos y las distintas farmacias, estos pueden ser nombre de medicamentos, cantidad, ubicación, etc., también se usarán para el correcto funcionamiento de los módulos. PhpMyAdmin Es una herramienta que ayuda a la administración del motor de base de datos usando el servicio web, permite el fácil acceso y modificación de la base mediante un entorno amigable usando algún navegador web como Internet Explorer o Google Chrome. (PhpMyAdmin, s.f.) Se usará PhpMyAdmin para acceder a visualizar los datos de la base de datos del proyecto. 10 Apache Es un servidor HTTP (Protocolo de transferencia de hipertexto) o servidor web, que se encarga de procesar información realizando conexiones eficientes y seguras con el cliente para, de este modo, poder brindar o generar respuesta a las peticiones que este realice. Lanzado en 1995 es el servidor web más popular en la actualidad. (Apache, s.f.) Se usará Apache para establecer la conexión de la base de datos MySql que contiene los datos para el funcionamiento del proyecto. BitBucket Es un controlador de repositorios en la nube que permite tener el código de proyectos y software alojados en un servidor haciendo que sean fácilmente accesibles desde cualquier parte del mundo sin tener que llevar el código fuente de los proyectos siempre en algún dispositivo. Además, cuenta con la opción de poder revisar versiones anteriores, hacer inserciones y crear distintas imágenes del mismo proyecto usando la terminal Git en cualquier PC donde se encuentre desarrollando el proyecto. (Bitbucket, s.f.) Se usará BitBucket para alojar el proyecto en un servidor web y poder acceder a él desde cualquier lugar, además se utilizará para realizar distintas versiones de la solución separándolas por avance y también por seguridad. Al ser un proyecto académico se optó por esta opción sobre GitHub porque BitBucket ofrece repositorios privados sin la necesidad de una cuenta de pago. RStudio Entorno de desarrollo integrado para R, software para análisis de datos de código abierto, que presenta una interfaz amigable, soporta la ejecución de código directamente desde el entorno y presenta la opción de mostrar los datos en distintas tablas y gráficos estadísticos. (RStudio, s.f.) Se usará RStudio para ejecutar la experimentación numérica entre los algoritmos genético y genético + GRASP. 11 Google Maps Google Maps permite visualizar porciones específicas distintas localidades, además de contar con la opción de guardar posiciones de distintos puntos para luego exportarlos en formato XML. (Google, s.f.) Se usará Google Maps para usar una imagen de referencia del mapa donde luego se trazarán las líneas que conforman la ruta de entrega, extraer cada uno de los puntos que forman el mapa y realizar los casos de prueba de la solución. (RStudio, s.f.) Google Sheets Google Sheets es un programa de hojas de cálculo de Google que permite generar reportes usando fórmulas incorporadas, tablas dinámicas y opciones de formato. Algunas de sus ventajas son su accesibilidad desde cualquier navegador sin necesidad de usar un programa externo y la capacidad de sincronizar todos los documentos con una cuenta de Google y así poder acceder a ellos desde cualquier locación. (Google, s.f.) Se usará Google Sheets para presentar los datos y calcular los valores que sean necesarios al momento de realizar la experimentación numérica entre los algoritmos. 1.3.2 Metodologías Extreme Programming (XP) Es una metodología ágil que permite adaptarse a equipos de desarrollo reducidos sin comprometer la calidad de software a desarrollarse, además presenta una flexibilidad en el desarrollo de los entregables en cada iteración pues está enfocado a trabajar con requisitos que pueden cambiar a lo largo del desarrollo sin afectar el rendimiento del proyecto. (Beck & Andres, 2005) Se usarán las fases I: Exploración, III: Iteraciones y IV: Producción de Extreme Programming para la gestión del proyecto y para el desarrollo de los algoritmos porque además de proponer un desarrollo incremental cuenta con pruebas unitarias e integrales para la detección de errores. 12 1.3.3 Métodos Algoritmo Genético El algoritmo genético hace referencia a la evolución de vida en el planeta mediante las ideas de adaptación y aprendizaje que los Homo Sapiens lograron mediante la observación continua de ellos mismo y el entorno en donde vivían, de esta manera se podría deducir que el aprendizaje y adaptación son los pilares para el desarrollo de robustos procedimientos y estructuras. (Goldberg & Holland, 1988) Así este algoritmo tiene como objetivo ir optimizando la solución mientras transcurren “generaciones” de resultados hasta lograr una que sea óptima para el problema. Algoritmo GRASP El algoritmo GRASP combina heurística ávida, que buscan la solución óptima evaluando cada elemento solo una vez, aleatoriedad y búsqueda local, de esta manera se logra realizar una búsqueda robusta en un espacio complejo de datos. El procesamiento es efectuado en dos pasos: Grasp Construcción, donde se busca la mejor solución posible que está cercana a un óptimo local y Grasp Búsqueda donde se realizan n iteraciones buscando en distintos “vecindarios”, que son conjuntos de datos donde es probable que se encuentre un óptimo local. (Kontoravdis & Bard, 1995) Problema de enrutamiento de vehículos El problema de enrutamiento de vehículos consiste en diseñar la ruta o conjunto de rutas de menor costo para que se pueda realizar la entrega optimizando distintos factores. Como consideración del problema cada cliente es servido solo una vez y todos deben ser atendidos sin exceder las capacidades de los vehículos. (Solomon, 1987) Una variante de este problema agrega el tiempo máximo de entrega como una variable a considerar y se denomina problema de enrutamiento de vehículos con ventanas de tiempo. (Solomon, 1987) Como en el caso de la entrega a domicilio de productos farmacéuticos necesita una solución donde se entreguen estos en el tiempo establecido se tratará de resolver este tipo de problema. 13 1.3.4 Modelos Modelo Incremental – Para la gestión del producto El modelo incremental combina los elementos lineales de la metodología tradicional, como el modelo en cascada, con proceso en paralelo. De esta manera cada secuencia produce “incrementos” del software. Este modelo permite entregar, con cada incremento, módulos o funcionalidades ya integradas al producto final, así se pueden ya hacer pruebas sobre estos módulos y no esperar a que todo el software esté completo para que funcione. Al usar un modelo incremental el primer incremento usualmente es el proceso principal y luego este se va adaptando o modificando para que pueda integrar los demás módulos o funcionalidades de cada uno de los incrementos de la solución. (Pressman, 2005). Se seguirá este modelo para el desarrollo de la solución. 1.4 Alcance, limitaciones y riesgos 1.4.1 Alcance El proyecto se relaciona con las empresas del sector ventas que cuentan con una cadena de locales, específicamente las dedicadas a venta de medicamentos. Éste fue el sector elegido debido a que es uno de los canales con mayor crecimiento y oportunidades en los últimos años. (Kantar Worldpanel, 2017) El proyecto trata de optimizar el proceso de ventas a domicilio, presente o no, en cadena de farmacias, tomando como base las características que actualmente se ofrecen para este servicio, que son, el inventario actual de los productos que presenta cada uno de los locales de la cadena, para lograr identificar cuáles, solos o en conjunto, logran cubrir la totalidad del pedido, y la distribución de motorizados (repartidores) por áreas de atención y no por local, optimizando el trabajo de estos pues podrán cubrir mayor cantidad de pedidos. A estas características se le agregará un enrutamiento para la entrega de pedidos, opción que muchas de ellas no presentan actualmente, de esta manera se buscará optimizar el servicio mejorando los tiempos de entrega de los productos farmacéuticos. El sistema de despacho a domicilio sólo se enfocará a este proceso ya que otros, como sistema de ventas o compras, están ya establecidos en el negocio, de esta manera se elaborarán dos módulos, uno para recepcionar el pedido e indicar las farmacias y repartidores que realizaran el servicio y otro módulo que, por medio de una imagen que 14 puede ser impresa y adjunta al pedido, presentará el recorrido que el repartidor debe hacer para recoger los productos y entregarlos al destino establecido. 1.4.2 Limitaciones • El presente proyecto debe seguir lo citado en la Ley № 29733 de Protección de Datos Personales por lo que debe adecuarse para cumplir con esta ley. • El tiempo de ejecución de los algoritmos está sujeto a las especificaciones de hardware y software del equipo donde se ejecuten. • El desarrollo del proyecto se realizará empleando software libre o versiones académicas. • El hardware utilizado para el desarrollo y despliegue del producto será únicamente la proporcionada por el tesista. 1.4.3 Riesgos En la Tabla 3 se describen los riesgos identificados. El score se calcula de la siguiente manera: Score = Índice de impacto x índice de probabilidad Es decir, multiplicando el índice de probabilidad por el índice de impacto, donde el índice de probabilidad tiene los valores de: Baja = 1, Media = 2, Alta = 3 y los índices de impacto son Bajo = 1, Medio = 2, Alto = 3. Tabla 3 Lista de riesgos # Riesgo Prob. Impacto Score Consecuencia Medidas para identificado mitigar 1 Mala Baja Alto Bajo El documento Comunicar comunicación no puede ser oportunamente con el asesor. corregido. al asesor para Rechazo del conocer su documento. horario disponible. 2 Obtención de Media Alto Medio El sistema no Según fecha la puede ser límite generar información probado. datos aleatorios inicial de para las datos para la pruebas. solución. 15 1.5 Justificación y viabilidad del proyecto 1.5.1 Justificación En la actualidad el mercado farmacéutico es uno de los canales de consumo con mayor crecimiento (Kantar Worldpanel, 2017) y muchas empresas de este rubro han optado por aumentar sus canales de ventas para aprovechar esta demanda (La República, 2014). Uno de los canales más importantes es el de reparto a domicilio pues cada vez más personas prefieren que los productos que adquieran sean llevados a casa en lugar de salir a comprarlos (Capital, 2017). De este modo implementar un sistema de despacho para este tipo de negocios (cadenas de farmacias) ayudaría a las empresas que pretendan optar por dicho canal de ventas. Y mejoraría el desempeño de las empresas que ya cuentan con este servicio, pero no tienen ninguna técnica para el ruteo de sus pedidos. La solución busca beneficiar a los dueños del negocio mejorando la oferta de stock de la cadena de farmacias, de esta manera permite la gestión de sus productos y la posibilidad de atender a una mayor cantidad de clientes por el servicio de despacho a domicilio. Adicionalmente, los repartidores se benefician del sistema al contar con una ruta establecida que delimita su recorrido y de esta manera ya no tienen que consumir tiempo en determinar una ruta por donde tendrán que ir para llegar a su destino. 1.5.2 Viabilidad Viabilidad Técnica Las herramientas que se necesitarán en el proyecto, mencionados anteriormente, pueden ser utilizadas sin la necesidad de licencias ya que son libres. Los métodos y herramientas por usar han sido aprendidos a lo largo de carrera universitaria. Finalmente, tanto Netbeans como las librerías antes mencionadas proporcionan las funciones necesarias para el desarrollo del proyecto, además no implica gran cantidad de horas dedicadas en su aprendizaje pues es un software conocido que ya ha sido utilizado anteriormente. Por lo antes mencionado el proyecto es viable técnicamente. 16 Viabilidad Temporal El proyecto estará dividido en dos partes: implementación del algoritmo e implementación del sistema, estas se describen en la Tablas 4 y Tabla 5 respectivamente. Tabla 4 Cronograma para la implementación del algoritmo. Implementación del algoritmo Documento de análisis donde se describe el proceso de 1 semana entrega a domicilio. Análisis de la estructura de datos a usar e implementar de 3 semanas ambos algoritmos Experimentación numérica de los resultados 1 semana Tabla 5 Cronograma para la implementación del sistema. Implementación del sistema Implementación del módulo de asignación de farmacias y 3 semanas repartidores. Pruebas unitarias y de integración. Implementación del módulo de enrutamiento. 3 semanas Pruebas unitarias y de integración. 17 Capítulo 2. Marco Legal/Regulatorio/Conceptual/otros 2.1 Marco Conceptual Es necesario definir algunos conceptos relacionados a empresas comerciales además de conceptos de heurísticas, algoritmos, entre otros. 2.1.1 Despacho El despacho o reparto es una actividad de logística consolidada que tiene como objetivo cargar y enviar pedidos a los clientes de una compañía. Para que esta actividad se realice de manera satisfactoria para el cliente, las distintas áreas como compras, producción, manufactura, entre otras deben satisfacer las necesidades prometidas ya que el no lograr esto significa pérdidas para la empresa. (García, 2010) 2.1.2 Repartidor Es la persona que repartirá mensajes, documentos, paquetes y otros productos a establecimientos o domicilios establecidos, estas personas pueden realizar dicho trabajo ya sea a pie o movilizándose usando algún medio de transporte como un auto moto o transporte público, para este caso los repartidores se movilizarán usando motos. (Carrer Planner) 2.1.3 Unidad de transporte Es un vehículo usado por el repartidor que lo ayudará a movilizarse para poder despachar los productos, son bienes de la empresa por lo que los gastos de combustible, mantenimiento y otros influyen en la eficiencia del servicio. (García, 2010) 2.1.4 Producto Es un bien material, servicio o idea formado por diferentes atributos, que pueden ser tangibles o intangibles, que lo caracterizan y lo hacen diferenciarse de los demás. Estos serán ofrecidos por la empresa con el fin de recibir alguna remuneración monetaria. (Pérez & Perez, 2006) Algunos de los atributos específicos para este proyecto son la marca, ya que para cada medicamento puede o no existir una versión derivada o genérica, el precio y el tamaño o volumen que este ocupa, necesario para la buena administración del reparto. 2.1.5 Heurística Son métodos para decidir cuál opción a escoger entre una gran variedad de alternativas buscando la que presente una mayor eficiencia para lograr alcanzar un objetivo. Se puede 18 decir que las heurísticas representan el compromiso entre dos requerimientos: la necesidad de hacer algo de la manera más simple posible y el deseo de poder identificar entre lo bueno y lo malo al tratar de lograrlo. (Pearl, 1984) 2.1.6 Experimentación Numérica (Diseño de Experimentos) Es el conjunto de pruebas o métodos que se realizan con la intención de resolver un problema o comprobar una hipótesis y así proponer mejoras al proceso que se está observando. El objetico de estos métodos estadísticos es lograr que el proceso de experimentación sea lo más eficiente posible. (Gutiérrez Pulido & De la Vara Salazar, 2008) La experimentación numérica se usará para comparar los resultados del algoritmo genético y genético + GRASP con la finalidad de saber si es que el propuesto mejorará los resultados a obtener. 2.1.7 Ruta de despacho Son rutas de transporte por donde irá el repartidor, estas toman en consideración el tiempo estimado del recorrido, kilometraje total de la unidad de transporte y buscan la disminución de costos y el mejoramiento en las entregas a los clientes. (García, 2010) 2.1.8 Inventario “Inventarios o Stocks son la cantidad de bienes o activos fijos que una empresa mantiene en existencia en un momento determinado, el cual pertenece al patrimonio de la empresa.” Existen distintos tipos de inventarios dependiendo del fin de los bienes que lo componen, así estos se pueden clasificar en inventarios de materia prima, productos en proceso, productos terminados, etc.; en el caso de las farmacias el inventario que se tomará en cuenta es el de productos terminados ya que se quiere llevar un control de los productos a vender. (Aguilar, 2009) 2.1.9 Transacción de salida Es el movimiento de inventario en el cual una cantidad de artículos son retirados del almacén. (Aguilar, 2009) 2.1.10 Transacción de entrada Es un movimiento de inventario donde se ingresan productos que han sido retornados por los clientes al percibir algún desperfecto o fallo en ellos. Estos elementos pueden no 19 regresar directamente al inventario de productos finales, si no que antes requieran una revisión para determinar su paradero. (Aguilar, 2009) 2.1.11 Control de Inventarios Es “Todo lo relativo al control y manejo de las existencias de determinados bienes, en la cual se aplican métodos y estrategias que pueden hacer rentable y productivo la tenencia de estos bienes y a la vez sirve para evaluar los procedimientos de entradas y salidas de dichos productos.” (Aguilar, 2009) Es decir que el control de inventarios se encarga de manejar los bienes haciendo que estos sean administrados de manera eficiente. 2.2 Marco Legal Teniendo en cuenta que el proyecto tendrá acceso a la información del cliente además de los medicamentos solicitados por él (receta médica del cliente), es necesario definir el marco legal al cual deberá estar alineada la solución. De este modo el proyecto debe cumplir con la Ley de Protección de Datos Personales. (LEY N° 29733, 2011) La ley de Protección de Datos Personales cuenta las obligaciones que debemos acatar cuando se usará información de esta índole, las que más destacan al momento de la ejecución de este proyecto se encuentran en dos artículos: Artículo 17, Confidencialidad de datos personales, el cual cita que todo personal encargado y que intervenga en cualquier parte del tratamiento de estos datos está en la obligación de guardar confidencialidad sobre la información que se encuentra en estos. (LEY N° 29733, 2011) Artículo 28, Obligaciones, el cual cita las acciones que deben cumplir todas las personas que tengan acceso a estos datos como efectuar el tratamiento de datos solo bajo consentimiento informado, no recopilar datos personales por medios fraudulentos, sustituir o suprimir datos personales, usar los datos personales para finalidades distintas a aquellas que motivaron su recopilación, entre otros. (LEY N° 29733, 2011) 20 Capítulo 3. Estado del Arte Para el estado del arte se usó el método tradicional, donde se buscó en fuentes como artículos, libros, otras tesis, entre otros con el objetivo de encontrar soluciones comerciales ya existentes en el mercado, algoritmos que solucionen el problema de enrutamiento de vehículos y otras posibles soluciones que apoyen a poder resolver el problema planteado. 3.1 Revisión y discusión 3.1.1 Artículos Algoritmo genético para problemas de ruteo con entrega y recolección del producto y con restricciones de ventana de horario Este artículo pretende comparar los resultados de la solución del problema de enrutamiento de vehículos con ventanas de tiempo usando un algoritmo genético y un algoritmo de ramificación y corte. Los resultados muestran que empleando un algoritmo genético se establecer un 100% de confiabilidad. (López Pérez & Badii, 2005) 3.1.2 Productos Comerciales Enrutamiento 1. Google Maps Google Maps es un sistema de navegación y ubicación que permite, además de localizar distintas direcciones, también puede ubicar diferentes locaciones como grifos o farmacias y permite al usuario obtener una posible ruta para llegar desde su ubicación actual a su destino. (Google, s.f.) 2. Waze Es una aplicación de navegación que se basa en la información a tiempo real que brindan los usuarios sobre el tráfico, de esta manera otros usuarios pueden usar estos datos para saber la ruta o nivel de congestión de las vías por las que se van a desplazar. (Waze Mobile, s.f.) 21 Gestión de repartos 1. Sistema de inventario de SOFTBRILLIANCE Softbrilliance es una empresa peruana dedicada al desarrollo e implementación de software empresarial que cuenta con más de 9 años en el mercado y ha brindado servicio a conocidas empresas del país como EsSalud y el banco BCP con lo que puede dar fe de su confiabilidad y calidad de servicio. Softbrilliance brinda un sistema que permite automatizar la gestión y administración de almacenes como las transacciones, entradas, salidas y transferencias de insumos, productos terminados, materia prima, etc. Cuenta a su vez con un control de movimiento diario y emisión de distintos reportes como el Kárdex y verificarlos a diferentes niveles. (Softbrilliance, s.f.) 2. EPICOR administración de almacenes Epicor es una compañía fundada en 1972 que se dedica a brindar soluciones de software para compañías de manufactura, distribución, ventas y servicios. Sus años en el negocio e historias de éxito la hacen una compañía confiable en la actualidad. Entre las distintas soluciones que brinda, el sistema de almacenes permite una administración total de estos, control de inventarios, procesamiento de órdenes multicanal, entre otros. Además, puede gestionar el rastreo de las entradas y salidas de los productos como también planear la recolección, empaquetado y transporte de estos bienes. (EPICOR, s.f.) 3. AhorroMED AhorroMED es una aplicación móvil para teléfonos inteligentes que permite conocer en tiempo real información sobre distintos medicamentos. La aplicación funciona ingresando el nombre del medicamento para luego mostrar un mapa con las distintas boticas y farmacias cercanas que cuentan con dicho producto, además de tener la opción de revisar el precio que tiene este, dirección y teléfono de cada uno de los diferentes establecimientos. (Ministerio de Salud, 2017) 22 3.1.3 Tesis Tesis de Joseph Gallart Suárez El trabajo de tesis de Joseph Gallart Suárez desarrolló un algoritmo GRASP para resolver el problema de enrutamiento de vehículos con capacidad cuyos resultados muestran que usando este algoritmo metaheurístico se logran mejores resultados que utilizando algoritmos generales o heurísticos. (Gallart Suárez, 2011) Tesis de Luis Grimaldo Bañón Felix El trabajo de tesis de Luis Bañón implementa un sistema de información para distribución de productos electrodomésticos optimizando los costos, este proyecto implementa dos algoritmos en la solución, uno de ubicación de productos dentro del medio de transporte y otro de ruteo, este último es parecido al problema expuesto ya que optimiza costos en la selección de la ruta. El algoritmo de ruteo utilizado es GRASP ya que para ese tipo de problema da la solución más confiable. (Bañón Felix, 2013) Tesis de Miguel Ángel Ortega Bulnes El trabajo de tesis de Miguel Ortega desarrolla un sistema de gestión de taxis que optimiza las rutas de transporte, aquí se puede apreciar que el proceso de optimización se hace por medio de un algoritmo de optimización de colonia de hormigas (OCH) que presenta mejores resultados que otros algoritmos como GRASP. (Ortega Bulnes, 2010) 3.2 Conclusiones Luego de analizar las distintas soluciones como los distintos algoritmos no se llegó a encontrar una solución a la medida que permita brindar despacho de productos tomando en cuenta otros establecimientos, además se puede deducir que es necesario usar un algoritmo heurístico para resolver de manera más eficiente el problema de enrutamiento de vehículos con ventana de tiempo. Por lo tanto, el proyecto de fin de carrera desarrollará un sistema de entrega a domicilio para una cadena de establecimientos tomando en cuenta el stock de todas las farmacias dentro de un rango previamente establecido y los repartidores que se encuentren en el área, y no solo a los que perteneces al establecimiento donde se recibe el pedido, con el fin de optimizar la oferta de stock presente en estos locales. Además, implementará un algoritmo heurístico para resolver el problema de enrutamiento multipunto de vehículos con ventana de tiempo. 23 También, según la bibliografía leída se optará por usar un algoritmo genético para generar la solución más óptima de enrutamiento, pero usando un algoritmo GRASP, como lo proponen las tesis consultadas, para la generación inicial del algoritmo genético. Capítulo 4. Presentación de los resultados esperados En el presente capítulo se describen cada uno de los resultados a obtener por cada objetivo específico planteado para el desarrollo del sistema desarrollo del sistema, abarca desde la recepción de datos hasta la comparación de resultados con aplicaciones existentes. 4.1 OE1 Modelar el proceso de recepción, procesamiento y entrega de un pedido Para el modelado del proceso, se preguntó de manera informal en las farmacias encuestadas sobre cómo era el proceso de reparto a domicilio. Además, para obtener mayor información sobre el proceso se comunicó vía telefónica, a manera de cliente, con farmacias que ofrecen el servicio y se anotó qué datos eran solicitados para la realización de la entrega a domicilio. Luego se procederá a realizar un proceso similar al obtenido en los diferentes medios de obtención de información. 4.1.1 Recepción La venta de medicamentos con entrega a domicilio comienza con la recepción de los pedidos en alguna central telefónica de la cadena de establecimientos donde el cliente solicita determinados productos. En este proceso se obtiene la información necesaria para poder realizar el pedido, la cual se detalla a continuación: • Datos del cliente. • Dirección. • Lista de productos deseados. 4.1.2 Procesamiento de la información En este proceso se halla la forma en que va a ser entregado el pedido, es decir cuáles son las farmacias que van a cumplir con el pedido, cuál es el orden para visitarlas, qué motorizado realizará el pedido y qué ruta seguirá para entregar la orden. 24 Selección de farmacias Con la dirección del pedido y la lista de productos se seleccionan las farmacias de tal manera que el recorrido total sea el mínimo y la cantidad de productos que recoger en cada una sea el máximo además que cuente con un motorizado libre o que aún no ha partido y está dentro del tiempo de espera, establecido por la empresa, antes de determinar la ruta final. De ser el caso el límite de pedidos por motorizado también se puede usar como restricción para la selección de éste. El punto usado para determinar las farmacias a recorrer siempre es la dirección del primer pedido ya que, al momento de la recepción de este, se ubica al motorizado en un local específico, de no realizarse de esta manera podría darse el caso que los motorizados listos para salir sean informados que los pedidos han sido cancelados y dados a otro motorizado, lo cual generaría pérdidas de tiempo en la empresa por falta de coordinación de las tareas a realizar. Enrutamiento Cada vez que termine el tiempo de espera de un motorizado libre, se procederá a hallar la ruta que este recorrerá siempre y cuando tenga pedidos por entregar, para hallarla se usa la lista obtenida en el punto anterior como referencia de los lugares por donde el repartidor debe pasar, además de un mapa cargado en el sistema, una lista de calles (puntos adyacentes entre cada lugar del mapa) y la lista de acciones a realizar en cada uno de los lugares por donde pasará, por ejemplo si el lugar es una farmacia, el repartidor recogerá n productos y si es un punto de entrega, repartirá m productos. 4.1.3 Despacho Luego que se tiene la ruta por donde pasará el repartidor, se le entrega un mapa con la ruta a seguir y una lista de productos a recoger y entregar en cada punto. Con esto el motorizado ya puede salir a realizar las entregas. 4.1.4 Diagrama de procesos A continuación, se presentarán los diagramas de los procesos principales del sistema. 25 Atender Pedido El proceso de atención del pedido inicia con la recepción de la llamada de un cliente. Luego se solicitan los datos necesarios para realizar el servicio, que son, los datos del cliente, la dirección del envío y la lista de productos que desea. Después se solicita la confirmación del pedido al cliente, donde este puede modificar, cancelar o aceptar el pedido. Finalmente se procede a generar el pedido. (Ver Ilustración 5) Ilustración 5 Modelamiento del proceso de recepción de un pedido. Editar Productos El proceso de edición de productos comienza con la selección de la farmacia donde se quiere editar. Luego, se selecciona el producto a editar y se modifican los datos de este producto, en caso se quiera registrar un nuevo producto, se elige la opción de crear y se ingresan los datos del nuevo producto. Finalmente se aceptan los cambios. (Ver Ilustración 6) Ilustración 6 Modelamiento del proceso de edición de un producto 26 Editar Motorizados El proceso de edición de motorizados comienza con la selección de la farmacia donde se quiere editar. Luego, se selecciona la opción para mostrar a los motorizados de esa farmacia, ahí se elige al motorizado a editar y se cambian sus datos, en caso se quiera registrar un nuevo motorizado, se selecciona la opción de crear y se ingresan los datos del nuevo motorizado, que se agregará a la lista de motorizados general y a la lista de motorizados de esa farmacia. Finalmente se aceptan los cambios. (Ver Ilustración 7) Ilustración 7 Modelamiento del proceso de edición de un motorizado. 4.2 OE2 Diseño de un algoritmo para la ubicación de los locales farmacéuticos a recorrer. Como se explicó en 4.1.2 Selección de farmacias, se busca que el orden de las farmacias a recorrer sea el más óptimo, en este caso que recorra menos distancia y que recoja la mayor cantidad de productos por farmacia. Para determinar la distancia entre cada punto se usó la función Haversine, que determina la distancia en metros entre dos puntos conociendo la latitud y longitud de ambos puntos. (Movable Type Scripts, s.f.) El algoritmo se puede apreciar en la Ilustración 8. 27 Ilustración 8 Implementación de la función Harvesine en JavaScript (Movable Type Scripts, s.f.) 4.2.1 Función Objetivo La función objetivo busca minimizar las farmacias a recorrer para realizar el pedido. Sea p0 el punto de entrega F.O.: MIN (Σ (Dijkm)) Donde: Dijk es la distancia de la farmacia Fi con motorizado disponible j y que posee el producto Km al punto p0 Km es la lista de productos {k1, k2, k3,..., km} a conseguir 28 4.2.2 Pseudocódigo Input p0: punto de entrega F = {F1, F2,..., Fn} lista de todos los puntos por pasar. Output M = {M1F1, M2F2,..., MmFo} lista de medicamentos por farmacia FS = {F1, F2,..., Fo} lista de farmacias a recoger. HallarFarmacias(p0, F[]){ hallarDistanciaP0F (p0,F[],distancia[]) ordenarAscendente F[], distancia[]) Mientras ( F[].tamaño > 0 y Pedidos[].tamaño <> 0) hacer f = F[0] Si ( MejorFarmacia(f, M[][], Pedidos[]) F[].remove(0) D[].remove(0) FS[].agregaAlFinal(f) HallarFarmacias(f, F[]) Si (Pedidos[].tamaño = 0 y Pedidos[]tamaño ==0) Encontró solución <- M[][], FS[] Sino No encontró solución } Donde: • hallarDistanciaP0F - Determina la distancia en metros, que existe desde el punto de entrega p0 a todas las posibles farmacias. • ordenarAscendente - Ordena de menor a mayor la distancia del punto de entrega p0 a todas las farmacias en F entre la cantidad de productos del pedido a completar en esa farmacia, dando como resultado que la mejor farmacia a escoger se encuentre en la primera posición. • MejorFarmacia - Verifica si se cumplen las condiciones para elegir esa farmacia (productos de la lista y motorizado disponible la primera vez). • agregarAlFinal - Agrega la farmacia en la lista de órdenes de recojo, junto con la lista de productos a obtener ahí. 4.2.3 Ejemplo Para un conjunto de puntos que se muestran en la Ilustración 9, donde cada punto rojo del gráfico representa una farmacia y siendo el punto azul el destino de entrega, además de que los productos en cada farmacia están representados como un conjunto [ ], para el pedido de los productos [A, B, C, D, E] primero se determinarían los costos de ir a cada farmacia, luego se determinaría que la farmacia que cumple de manera óptima el pedido es la farmacia 1, donde se recogen los productos [A, B, E], después se repite el mismo cálculo para determinar que la farmacia 2 terminaría con el producto. 29 Ilustración 9 Ejemplo de funcionamiento del algoritmo de selección de farmacias 4.2.4 Validación Para la validación de los resultados de este algoritmo se realizaron casos, cada uno con una respuesta esperada y se verificó si el algoritmo llega o no a ese resultado. La Tabla 6 muestra las pruebas realizadas. Tabla 6 Pruebas del algoritmo de selección Pedido Farmacias Farmacia Farmacias Farmacia recorridas inicial recorridas inicial (esperadas) (esperada) 10 Productos 3 Farmacia 2 3 Farmacia 2 8 Productos 3 Farmacia 1 3 Farmacia 1 12 Productos 4 Farmacia 2 4 Farmacia 2 15 Productos 3 Farmacia 8 3 Farmacia 8 Evaluando los resultados podemos concluir que los datos han sido hallados correctamente por el algoritmo. 30 4.3 OE3 Diseñar un algoritmo GRASP Construcción y Genético que asigne el recorrido que hará el repartidor. El algoritmo GRASP se usará para generar la población inicial que usará el algoritmo genético para hallar la más óptima solución para el enrutamiento. 4.3.1 GRASP Construcción Para hallar la población inicial se partirá usará el orden de recorrido de farmacias y de acciones a realizar obtenidos con el algoritmo del punto 4.3, Luego se comenzará a recorrer el mapa siguiendo ese orden, para cada punto se preguntará cuáles son los puntos adyacentes a él, y se seleccionará primero algún punto que sea punto de entrega, para poder determinar si es que ya se podría entregar el pedido, de no poderse se seleccionará una farmacia, si es que esta está en los puntos adyacentes, para poder recoger más productos que puedan completar los pedidos, si es que no existe ninguna farmacia se elegirá un punto al azar para seguir con el recorrido, esto continuará hasta que se cumplan todos los pedidos o no se encuentre una solución 31 Pseudocódigo Input FS[] = lista de farmacias a recorrer P[] = lista de puntos de entrega L[] = lista de puntos del mapa Pedidos[] = lista de pedidos Medicamentos[] = lista de medicamentos max_tiempo Output R[][] = lista de posibles soluciones graspConstrucción(){ p0 = F[0] recoger_productos(p0, Medicamentos[],Pedidos[]) remover(F[], pi) N[] = hallaVecinos() Si (estaEnPedidos(Pedidos[],pi)) Si (completaPedidos(pi)) remover(P[], pi) remover(Pedidos[],pi) Si (no hay más pedidos) FIN Si no graspCostruccion() SI No Si (existeFarmaciaEnVecinos()) pi = punto adyacente Anterior = pi graspConstruccion() Si No pi = elijeVecinoAlAzar Anterior = pi Si (tiempo > max_tiempo) FIN Si no graspConstrucción() } Donde: • recogerProductos () - Agrega el producto y farmacia a la orden de recojo. • remover (P [], pi) - Remueve el pedido pi de la lista de pedidos P[]. • estaEnPedidos (Pedidos [], pi) - Verifica si el nuevo punto pi es un punto de entrega. • completaPedidos (pi) – Verifica si el pedido pi está completo. • existeFarmaciaEnVecinos () – Verifica si alguna farmacia (punto) se encuentra en la lista de puntos vecinos actuales. • hallaVecinos () – Devuelve una lista de puntos vecinos con el punto actual. • elijeVecinos () – Elije al Azar un punto en la lista de puntos vecinos. 32 Ejemplo Para un conjunto de puntos como se muestran en la Ilustración 10, y partiendo del punto 1 (señalado con una flecha verde) el algoritmo generaría 3 posibles soluciones que cumplen con recoger la totalidad del pedido. Estas soluciones muestran el recorrido a realizar, por ejemplo, para la imagen inferior izquierda, el motorizado partiría de la farmacia 1 al 2, del 2 al 8, del punto 8 al 9, del 9 al 5, el cual es una farmacia donde culminaría de recoger todos los productos del pedido, desde este punto regresaría al punto 9 que es donde se entregaría el pedido. Ilustración 10 Ejemplo del funcionamiento del algoritmo de enrutamiento (Grasp Construcción) 4.3.2 Algoritmo Genético El algoritmo genético se usará para mejorar la solución del recorrido para la entrega de productos, tomando como población inicial un conjunto de soluciones obtenidas por el algoritmo GRASP. Cada solución de la población inicial contiene puntos fijos por los que debe pasar el motorizado además de puntos de recorrido entre estos puntos fijos. Función Objetivo La función objetivo muestra recorrer el mínimo número de puntos para realizar con éxito el reparto del producto. 33 Sea: t0 el punto de partida del recorrido. Jn el conjunto de farmacias o puntos de entrega por donde debe pasar {j1, j2, j3,..., jn}. kjn el conjunto de acciones que se realizan en cada punto jn {kj1, kj2,..., kjn}. (Adquisición de producto si es una farmacia o entrega de pedido si es un punto de entrega). F.O. : MIN ( Σ( DTij1kj1 ) + Σ( DTij2kj2 ) + … + Σ( DTj(n-1)jnkjn )) Donde: D es la distancia total de la trama Tij que recorre alguno de los puntos de jn. Tij1kj1 es la trama de un punto de jn a otro donde en el punto j1 se realiza la acción kj1. Cromosomas Los cromosomas del algoritmo genético están determinados por cada uno de estos tramos fijos a recorrer. Selección de padres Para la selección de padres se elegirá usando el método de la ruleta, donde se tomarán a los 10 mejores padres y luego se elegirá uno de ahí, teniendo en cuenta que un padre tendrá mayor posibilidad de salir si presenta una mejor función objetivo (FO). Mutación Para la mutación se seleccionará al azar un padre de la generación actual y el nuevo individuo tendrá todos sus cromosomas. Control de aberraciones Para controlar la creación de los nuevos individuos, estos no entrarán a la nueva generación si es que su FO no cumple con un mínimo valor, determinado como un porcentaje de la mejor solución de la generación actual. 34 Pseudocódigo Input R[][] = lista de posibles soluciones F[] = lista de farmacias P[] = lista de puntos de entrega max_generaciones max_por_generacion Output S[] = Solución G[] = lista de generaciones FO_actual = hallarFO(R[][]) Genético(){ Pi = población inicial Mientras ( G[].tamaño < max_generaciones) G[].add(Pi) GEN[] = generación actual Mientras ( GEN[].tamaño < max_por_generación) elegiPadres() Hijo = crossover(hijo) FO = hallaFO(Hijo) Si ( FO <= FO_actual) GEN[].add(Hijo) FO_actual = hallarFOGen(GEN[][]) Pi = GEN[] } Donde: • hallarFO(sol) – Calcula la Función objetivo de una solución sol • elijePadres () – Elije dos padres por el método de la ruleta. • crossover (hijo) – Halla el nuevo individuo “hijo” usando la información de los dos padres previamente hallados. • hallarFOGen () – Halla la mejor solución en la generación. 35 Ejemplo En la Ilustración 11 se muestra un conjunto soluciones donde número en rojo son los puntos por donde, necesariamente, tiene que pasar el repartidos. Para hallar una nueva solución, se escogen 2 soluciones por el método de la ruleta Ilustración 11 Ejemplo del funcionamiento del algoritmo de enrutamiento (Genético) 4.4 OE4: Realizar una experimentación numérica entre los resultados obtenidos del algoritmo genético y genético + GRASP 4.4.1 Resultados de ambos algoritmos Para realizar la experimentación numérica se usarán los mismos datos de entrada para ambos algoritmos. La ilustración 12 muestra de detalle de cada pedido, la cantidad de puntos recorridos y la distancia total recorrida usando cada uno de los algoritmos. 36 Ilustración 12 Datos de entrada y salida de la ejecución de ambos algoritmos. 4.4.2 Experimentación numérica Para la experimentación se debe partir de un punto de comparación, en este caso puede ser la cantidad de puntos recorridos o la distancia total recorrida; como la distancia ente dos puntos no es constante se usará la distancia total recorrida como medio de comparación. Teniendo en cuenta que el mejor algoritmo será aquel halle una menor distancia a recorrer. Sean las variables: X = Distancia total recorrida para realizar un pedido usando el algoritmo genético. Y = Distancia total recorrida para realizar un pedido usando el algoritmo genético + GRASP. Se establecen las siguientes hipótesis: H0: μX – μY = 0 H1: μX – μY >0 H0 significa que las distancias recorridas halladas mediante ambos algoritmos son iguales H1 significa que la distancia hallada usando el algoritmo genético + GRASP es menor a la hallada usando solo el algoritmo genético. 37 Como ambos resultados son relacionados pues se usan los mismos datos de entrada, solo bastaría con comprobar que estos siguen una distribución normal para poder usar la distribución T-Student para analizar las hipótesis. Para demostrar que un conjunto de datos sigue una distribución normal basta con que su gráfica se asemeje a una función gaussiana, comúnmente llamada campana de Gauss. Las ilustraciones 13 y 14 muestran las gráficas de los resultados de ambos algoritmos, luego se puede decir que ambos siguen una distribución normal. Ilustración 13 Gráfico de la distribución normal de los resultados usando el algoritmo genético. Ilustración 14 Gráfico de la distribución normal de los resultados usando el algoritmo genético + GRASP. 38 Usando RStudio se cargan los datos y se procesan usando distribución T-Student para un nivel de confianza de 95%. La ilustración 15 muestra los datos cargados en RStudio y la ilustración 16 muestra la función ejecutada y el resultado de esta. Ilustración 15 Datos cargados en RStudio. Ilustración 16 Ejecución de la función T-Student en RStudio. Analizando el resultado se observa que p-value (1.564 x 10-5) < 0.05 por lo que se rechaza la hipótesis H0 y se acepta H1. Entonces se puede afirmar que, usando el algoritmo genético + GRASP se recorrerá menor distancia que usando sólo el algoritmo genético. 39 4.5 OE5 Diseñar e implementar un módulo que use el algoritmo de selección de farmacias 4.5.1 Estructura de datos Zona geográfica Para la selección de la zona geográfica en la que se realizará la tesis, se tomó en consideración el número total de farmacias de una misma cadena, así se escogió la zona de Pueblo Libre (ver Ilustración 17 e Ilustración 18) y la cadena de farmacias MiFarma ya que cuenta con 10 locales en esta zona. La relación de los locales pertenecientes a esta zona se encuentra en la Tabla 7 Ilustración 17 Imagen de la zona de Pueblo Libre 40 Ilustración 18 Imagen de la zona delimitada para el proyecto Tabla 7 Lista de establecimientos MiFarma en el distrito de Pueblo Libre Farmacia Dirección Farmacia Dirección 1 Av. Simón Bolívar 2250 6 Av. Simón Bolívar 910 2 Av. Brasil 1598 7 Av. La Marina 594 3 Calle José Leguía y Menéndez 8 Av. Antonio José de Sucre Nro. 1016 1190 4 Av. José Antonio de Sucre nro. 9 Av. Simón Bolívar 1157 613 5 Av. Simón Bolívar 1001 10 Av. Brasil 2714 Mapa Para guardar el mapa de manera que pueda ser procesado por los algoritmos, se establecieron puntos en cada esquina de la zona determinada y luego se determinaron los posibles tramos entre cada punto, es decir, los puntos adyacentes para cada ubicación, para de esta manera, poder saber cómo recorrer el mapa. Luego de establecer esos puntos y conexiones se consiguieron 416 puntos y 1326 conexiones, tal como lo muestra la Ilustración 19. 41 Ilustración 19 Imagen de los puntos que forman la zona del proyecto Medicamentos Para la carga de medicamentos se usó el Listado de Productos Farmacéuticos Seleccionados para Compra Nacional del Año 2010, que cuenta con 287 medicamentos. Con esto se trata de simular la comunicación entre el sistema y la base de datos de inventarios de la cadena de farmacias. La interacción de la base de datos de inventarios (SQL) con el sistema se realiza por medio de consultas directas a esta base de datos, por lo que, de ser implementado manera real, se necesitará tener las credenciales y nombres de las tablas de la base de datos de la farmacia. La Ilustración 20 muestra la lista de medicamentos. 42 Ilustración 20 Tabla de medicamentos a usar en el proyecto Carga de datos Para la carga de datos se usó MySql y un servidor local y una función en java para leer los datos de farmacias (en formato xml exportado por Google Maps), los datos de medicamentos (en formato Excel) y los puntos adyacentes (en formato Excel). A continuación, se muestra el modelo de datos (ver Ilustración 21), donde se pueden identificar las principales relaciones tales como: • La relación de la tabla “almacen” con la tabla “producto” la cual define que en un almacén pueden existir varios productos. • La relación de la tabla “pedido” con “repartido” para identificar qué repartidor está asociado a este pedido, además la relación con la tabla “detallePedido” que indica cuáles productos son los que conforman el pedido. • La relación de la tabla “mapa” con la tabla “tramo”, cada objeto en “mapa” está determinado por un punto donde se guarda su latitud y longitud, luego “tramo” contiene las conexiones de estos puntos que delimitarán hacia dónde se puede ir desde un punto específico. 43 Ilustración 21 Diagrama de base de datos Tipo de datos Para la implementación de los algoritmos se usarán listas de objetos, pues estas ofrecen un acceso más rápido que los arreglos convencionales, aparte de contar con otras funciones que harán que la implementación del sistema sea óptima. Para el nombre de funciones se usará camelCase y para nombrar variables snake_case. A continuación, se presenta la lista de tipos de dato por variable (Tabla 8). 44 Tabla 8 Tipos de datos. Variable Tipo de dato Descripción Información de farmacias, Double, Integer, String Estas variables ofrecen productos, motorizados, información de etc. IdFarmacia, Precio, IdProductos, entre otros. Lista de pedido Lista de Lista de Objetos Tiene la información de los pedidos, y la lista de productos de cada uno de ellos. Lista de recorrido Lista Objetos Lista ordenada que tiene información de los puntos a recorrer para realizar el pedido. Lista de orden de Lista de Lista de Objetos Tiene la información de productos los productos a recoger en cada farmacia. 4.5.2 Especificación de requisitos En la Tabla 9 se especificarán los requisitos que debe cumplir el sistema para poder brindar un buen sistema de reparto a domicilio, teniendo en cuenta las consideraciones previamente descritas que se deben tomar para evitar los problemas presentes en estos servicios. Estos van desde la creación del pedido hasta la ruta que seguirá el motorizado usando un mapa. Tabla 9 Especificación de requisitos. Número Requisito 1 El sistema permitirá ingresar un pedido dado una lista de productos, información del cliente y una dirección de entrega. 2 El sistema, haciendo uso de un algoritmo, hallará una ruta óptima para realizar el pedido. 3 El sistema permitirá editar, modificar y agregar productos en una farmacia. 4 El sistema permitirá editar, modificar y agregar motorizados en una farmacia. 5 El sistema tendrá como salida un mapa donde se señaliza el recorrido a seguir usando una línea. 6 El sistema permitirá validar si se puede completar un pedido, haciendo uso del inventario de las farmacias. 45 4.5.3 Arquitectura del sistema Vista de despliegue Cliente – Dentro se encuentran los componentes de la interfaz gráfica, lógica del negocio del sistema, que vendría a ser el algoritmo y la muestra de resultados. Lógica del negocio – Aquí se encuentra el sistema de entrega a domicilio, así como el algoritmo de enrutamiento y la librería gráfica que permitirá dibujar el mapa con la ruta especificada. Servidor Web – Dentro se encuentra el servidor de base de datos MySQL por el cual se realizarán las peticiones de almacenamiento o muestra de datos. En la Ilustración 22 se pueden observar estos componentes. Ilustración 22 Vista de despliegue del sistema. 4.5.4 Diagrama de flujo del algoritmo El proceso inicia con la recepción de un pedido, luego de solicitar los datos del cliente, dirección del punto de entrega y la lista de productos que lo conforman, éstos se usan para determinar las farmacias que cumplirán con el pedido. 46 El cálculo de las farmacias se realiza de la siguiente manera: primero se halla la distancia entre el punto destino con cada una de las farmacias, luego se elige a la farmacia más cercana que tenga la mayor cantidad de productos que podría recoger y algún motorizado disponible, después y mientras existan productos por recoger, se toma la dirección de esta farmacia y procede a hacer el cálculo una vez más. Finalmente, el sistema retorna la lista con las farmacias a recorrer y qué producto recoger en cada una de ellas. La Ilustración 23 muestra el flujo del proceso. Ilustración 23 Diagrama de flujo del algoritmo de selección de farmacias. 4.5.5 Implementación del algoritmo Luego de programar el algoritmo y cargar los datos de las farmacias, productos por farmacia y productos se procedió a hacer las pruebas del módulo. Resultados Para un pedido de 4 productos, la Ilustración 24 e Ilustración 25 muestran la pantalla de creación de pedido y la salida del algoritmo de selección de farmacias para un pedido de cuatro productos. En la farmacia1 se recogerán los productos Agua destilada 1L, Agua destilada 2ml. Y Adenosina 2ml, y en la farmacia2 se recogerá la Acitrenina. • Agua destilada 1L. • Agua destilada 2ml. 47 • Adenosina 2ml. • Acitrenina. Esta además indica que producto se recoge en que farmacia. Ilustración 24 Creación del pedido. Ilustración 25 Salida del algoritmo de selección de farmacias. La Ilustración 26 muestra la salida del algoritmo GRASP para el mismo ejemplo mostrado anteriormente. 48 Cada número representa un punto en el mapa y el orden de recorrido de la ruta. Ejemplo: Para los tres primeros números el despacho se comenzará en el punto 18 luego al 19 y después al 17. Ilustración 26 Salida del algoritmo GRASP para hallar el recorrido. La Ilustración 27 muestra la salida del algoritmo Genético que es una lista de puntos a recorrer. Para el mismo ejemplo de la parte anterior, se puede observar que los puntos recorridos se han reducido. 49 Ilustración 27 Salida del algoritmo Genético. Pantallas Para esta sección se realizaron las pantallas principales para la muestra e ingreso de medicamentos, farmacias y pedidos. La Ilustración 28 muestra la pantalla principal del sistema, el botón Realizar Pedido se utiliza para crear un pedido, y el botón Ver Farmacias accede a las opciones d edición tanto de farmacias, como motorizados y productos. 50 Ilustración 28 Pantalla principal del sistema. La Ilustración 29 presenta la lista de farmacias, mostrando la dirección de cada una de ellas, al seleccionar una farmacia se pueden editar los datos usando el recuadro de la derecha. Ilustración 29 Pantalla de lista de farmacias del sistema. La Ilustración 30 muestra la lista de productos para una farmacia, además al seleccionar un producto se pueden editar sus datos en el recuadro derecho, también se puede acceder a agregar productos usando el botón Agregar Productos. 51 Ilustración 30 Pantalla que lista los productos en una farmacia. En la Ilustración 31 se muestra la pantalla de ingreso de pedidos, para culminar con un pedido es necesario ingresar el nombre de la persona, su dirección y la lista de productos que el cliente va a solicitar. El botón “>>” sirve para agregar un producto seleccionado al pedido y el botón “<<” remueve un producto seleccionado del pedido. Ilustración 31 Pantalla de ingreso de pedidos. 52 En la Ilustración 32 se muestra la pantalla de edición de productos, en esta pantalla se puede editar el nombre, y la cantidad del producto existente en cada farmacia. Ilustración 32 Pantalla de edición de productos. En la Ilustración 33 se muestra la pantalla de edición de motorizados, al seleccionar un motorizado se puede editar el nombre y la farmacia que tiene ese producto. Ilustración 33 Pantalla de edición de motorizados. 4.5.6 Validación Para que el resultado de las pruebas se vea de una manera más ordenada, la validación de resultados se mostrará en las pruebas del siguiente objetivo específico, ya que para que el siguiente objetivo sea válido, tiene que contar con datos correctos provenientes de este objetivo. 53 4.6 OE6: Implementar una vista que, usando el algoritmo implementado anteriormente muestre el recorrido en un mapa 4.6.1 Mapa que muestra la ruta de despacho. La Ilustración 34 muestra la salida del recorrido en el sistema, luego de haber ingresado una lista de productos y con un punto de entrega. La línea roja muestra el recorrido que deberá seguir el motorizado para realizar la entrega, los círculos azules muestran donde se encuentran las farmacias por las que deberá pasar para completar el pedido, en este caso son dos farmacias, y el circulo verde muestra el punto de entrega. Ilustración 34 Ventana que muestra la ruta a seguir. 4.6.2 Casos de prueba del sistema planteado frente a Google Maps. Para los casos de prueba se muestran ambos resultados, Google Maps y sistema, usando Google Maps para dibujar el recorrido y tomando los puntos de salida del sistema para la muestra de resultados de este. 54 En las ilustraciones 35 y 36 se muestran los resultados, usando 3 generaciones y 10 generaciones. Ilustración 35 Salida del algoritmo genético usando 3 generaciones. Ilustración 36 Salida del algoritmo genético usando 10 generaciones. 55 La Ilustración 37 muestra la salida de Google Maps para el mismo ejemplo. Ilustración 37 Recorrido usando Google Maps. En la Tabla 10 se puede observar que, si bien solo con 3 generaciones la solución del algoritmo está lejos de la óptima (hallada con Google Maps), mientras más se optimice el resultado, es decir se creen más generaciones, la solución final se acercará más a la de Google Maps. El resultado va mejorando con más generaciones, pues por cada una de ellas calcula la mejor solución con los mejores datos de la anterior, así, como cada una de las generaciones es mejor que la pasada, se puede decir que, a más generaciones, mejor será el resultado. Tabla 10 Casos de prueba. Casos de prueba con comparación del algoritmo vs Google Maps Generación Algoritmo Google Maps Descripción Mejor resultado (puntos) (puntos) 3 generaciones 30 puntos 13 puntos Prueba con pedido Google Maps a completar en dos farmacias. 10 17 puntos 13 puntos Prueba con pedido Google Maps generaciones a completar en dos farmacias. 56 Casos de prueba con comparación del algoritmo vs Google Maps Generación Algoritmo Google Maps Descripción Mejor resultado (puntos) (puntos) 3 generaciones 25 puntos 12 puntos Prueba con pedido Google Maps de 4 productos en una farmacia. 10 16 puntos 12 puntos Prueba con pedido Google Maps generaciones de 4 productos en una farmacia. 3 generaciones 14 puntos 14 puntos Prueba con pedido Ambos de 4 productos en una farmacia 3 generaciones 20 puntos 20 puntos Prueba con pedido Ambos de 2 productos en una farmacia 57 Capítulo 5. Conclusiones y trabajos futuros. 5.1 Conclusiones En esta sección se presentarán las conclusiones del sistema, además se presentarán los posibles trabajos futuros con lo que se puede optimizar el resultado o mejorar su desempeño. Conclusiones y trabajos futuros Se puede observar que la interacción del sistema para la toma de pedidos es rápida y no presenta tiempos largos de carga de datos, además, el resultado del enrutamiento se acerca al proporcionado por Google Maps mientras más tiempo se procese la información. De esta manera podemos concluir que: Las conclusiones que se obtuvieron en cada uno de los objetivos realizados en el proyecto son las siguientes: • Para el Objetivo Específico 1 se describió el proceso de entrega a domicilio, lo cual permitió establecer una estructura a seguir al momento de desarrollar el sistema. • Para el Objetivo Específico 2 se diseñó un algoritmo que elija las farmacias a recorrer de una manera óptima, luego de realizar la validación de los resultados se puede concluir que éstos son correctos y servirán para desarrollar los siguientes objetivos de manera adecuada. • Para el Objetivo Específico 3 se diseñaron un algoritmo GRASP y un algoritmo Genético con la finalidad que sirvan para hallar la ruta más óptima a recorrer por el motorizado luego de recibir un pedido, así, estos resultados ayudarán a que el recorrido sea más corto y de esta manera se ahorre tiempo y dinero en el traslado de los productos, luego de realizar pruebas de estos algoritmos se puede concluir que éstos funcionan correctamente y se usarán como proceso principal para todo el sistema. • Para el Objetivo Específico 4, se desarrolló el sistema de despacho de manera que se puedan ingresar pedidos correctamente, además este sistema también permite editar la cantidad de productos por farmacia, agregar o quitar productos en éstas, y editar a los distintos motorizados localizados en las farmacias sin errores. Finalmente, este sistema también genera la lista de puntos a recorrer por el motorizado que luego serán usados para crear el mapa del recorrido. 58 El resultado obtenido por este sistema se acerca al resultado de ruteo usando Google Maps, y dependiendo de la complejidad y tiempo para encontrar la solución éste llega a obtener una ruta igual a la que podría ser obtenida por el servicio de mapas de Google. • Para el Objetivo Específico 5, se desarrolló la vista que muestra la ruta a recorrer en un mapa usando los resultados previamente calculados. Después de realizar los casos de prueba del sistema se puede decir que los resultados obtenidos son correctos. Además, el sistema usa la interfaz gráfica de Netbeans para dibujar la ruta, ayudándose únicamente de una imagen del mapa de la zona, por esta razón este sistema no necesita estar conectado a la red para funcionar, con esto, el sistema se podría implementar en farmacias o centros médicos remotos que no tienen acceso a internet. En conclusión, el sistema cumple con los requerimientos previamente especificados para cumplir con el servicio de entrega a domicilio, además, al no usar internet para procesar los datos, puede ser usado en locaciones sin acceso a este servicio sin perjudicar su desempeño, por este lado el sistema es superior a Google Maps o cualquier otra aplicación que necesite internet para funcionar aun cuando sus resultados solo llegan a ser iguales a los obtenidos con estas aplicaciones. 5.2 Trabajos futuros • Se podría crear un módulo independiente que se encargue de la carga de datos para formar el mapa, de esta manera no se tendría que realizar manualmente. • Usando el localizador del GPS de los celulares de los motorizados se podría crear un módulo que presente el estado del envío en tiempo real. • Al tener el inventario real de las farmacias se podría implementar un módulo que mande una alerta de reposición de un producto específico cuyo inventario está por debajo de un límite establecido. • Se pueden crear hilos en el programa para que cada uno de ellos devuelva una solución, así el desempeño del sistema mejoraría. 59 Bibliografía Aguilar, D. (2009). Administración de inventarios en almacenes. En Logística y Operación. Apache. (s.f.). Apache HTTP server proect. Obtenido de https://httpd.apache.org/ Bañón Felix, L. G. (2013). Análisis, Diseño e Implementación de un sistema de información para planificar la distribución de productos electrodomésticos optimizando los costos. Beck, K., & Andres, C. (2005). Extreme Programming Explained: embrace change (Segunda Edición ed.). Addison-Wesley. Bitbucket. (s.f.). Bitbucket. Obtenido de https://bitbucket.org/product/features Capital. (21 de 09 de 2017). 5 razones para implementar el servicio de delivery en tu negocio. Obtenido de Capital: http://www.capital.com.pe/actualidad/5-razones- para-implementar-el-servicio-de-delivery-en-tu-negocio-noticia-1078074 Carrer Planner. (s.f.). "DELIVERER, OUTSIDE". Obtenido de Carrer Planer.com: https://dot-job-descriptions.careerplanner.com/DELIVERER-OUTSIDE.cfm draw.io. (s.f.). draw.io. Obtenido de https://about.draw.io El Comercio. (14 de 05 de 2017). Farmacias ganan espacio en la canasta de cuidado personal. Obtenido de El Comercio: http://elcomercio.pe/economia/negocios/farmacias-ganan-espacio-canasta- cuidado-personal-420132 EPICOR. (s.f.). Administración de Almacenes. Obtenido de http://www.epicor.com/lac/solutions/warehouse-management-system.aspx Gallart Suárez, J. (2011). Análisis, diseño e implementación de un algoritmo meta heurístico GRASP que permita resolver el problema de rutas de vehículos con capacidad. García, L. (2010). Gestión logística integral: las mejores prácticas en la cadena de abastecimientos. Ecoe Ediciones. Goldberg, D. E., & Holland, J. H. (1988). Genetic algorithms and machine learning. En Machine learning (págs. 95-99). Google. (s.f.). Google Maps. Obtenido de https://www.google.com/maps/about/ Google. (s.f.). Google Sheets. Obtenido de https://www.google.com/sheets/about/ Gutiérrez Pulido, H., & De la Vara Salazar, R. (2008). Análisis y diseño de experimentos (Segunda Edición ed.). McGraw-Hill. 60 INEI. (2014). Encuesta Nacional de Satisfacción de Usuarios de Aseguramiento Universal en Salud 2014. Kantar Worldpanel. (29 de 08 de 2017). Hogares peruanos cautelosos en su consumo. Obtenido de Kantar Worldpanel: https://www.kantarworldpanel.com/pe/Noticias/hogares-peruanos-cautelosos- en-su-consumo Kontoravdis, G., & Bard, J. F. (1995). A GRASP for the Vehicle Routing Problem with Time Windows. En ORSA Journal on Computing (págs. 10-23). La República. (21 de 03 de 2014). El comercio electrónico en el Perú, ¿cuál es la realidad del país? Obtenido de La República: http://larepublica.pe/21-03- 2014/el-comercio-electronico-en-el-peru-cual-es-la-realidad-del-pais La República. (07 de 03 de 2015). Congestión vehicular se concentra en 134 puntos críticos de Lima. Obtenido de La República: http://larepublica.pe/07-03- 2015/congestion-vehicular-se-concentra-en-134-puntos-criticos-de-lima LEY N° 29733. (03 de Julio de 2011). Ley de protección de datos personales. Ministerio de Justicia. López Pérez, J. F., & Badii, M. (2005). Algoritmo genético para un problema de ruteo con entrega y recolección de producto y con restricciones de ventana de horario. En Ciencia UANL (Vol. 8). Michalewicz, Z., & Fogel, D. B. (s.f.). Traditional Methods—Part 1. En How to Solve It: Modern Heuristics (págs. 55-81). Springer Berlin Heidelberg. Microsoft. (s.f.). Visual Studio. Obtenido de https://www.visualstudio.com/vs/ Ministerio de Salud. (24 de 07 de 2017). Ministra de Salud lanza AhorroMED, el aplicativo móvil para consulta de precios de medicamentos y ubicación de farmacias. Obtenido de Ministerio de Salud: http://www.minsa.gob.pe/?op=51¬a=24189 Movable Type Scripts. (s.f.). Calculate distance, bearing and more between Latitude/Longitude points. Obtenido de https://www.movable- type.co.uk/scripts/latlong.html MySQL. (s.f.). MySQL. Obtenido de https://www.mysql.com/products/ MySQL. (s.f.). MySQL connectors. Obtenido de https://dev.mysql.com/downloads/connector/ Netbeans. (s.f.). Netbeans. Obtenido de https://netbeans.org/about/index.html 61 Ortega Bulnes, M. Á. (2010). Desarrollo de un sistema de gestión de servicio de taxis que optimiza rutas de transporte. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Pérez, D., & Perez, I. (2006). El Producto Concepto y Desarrollo. España: Escuela de Negocios EOI. PhpMyAdmin. (s.f.). PhpMyAdmin. Obtenido de http://www.phpmyadmin.net Pressman, R. S. (2005). Software Engineering a practitioner's approach. Palgrave Macmillan. RPP. (04 de 08 de 2017). Conductores no respetan las normas de tránsito en La Victoria. Obtenido de RPP Noticias: http://rpp.pe/lima/actualidad/conductores- no-respetan-las-normas-de-transito-en-la-v-noticia-1068563 RStudio. (s.f.). RStudio. Obtenido de https://www.rstudio.com/products/rstudio/ Softbrilliance. (s.f.). Inventario - Sistema de Logística. Obtenido de http://www.sbperu.net/logistica-p2.html Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. En Operations research (págs. 254-265). Source Forge. (s.f.). Java Excel API. Obtenido de http://jexcelapi.sourceforge.net/ Sublime Text. (s.f.). Sublime Text. Obtenido de https://www.sublimetext.com Waze Mobile. (s.f.). https://www.waze.com/es-419. 62 Anexos Encuesta a trabajadores de farmacias o boticas que se encargan de la recepción de pedidos de entrega a domicilio Nombre: _____________________________________________________ 1. ¿Cómo funciona el servicio de entrega a domicilio con el que cuenta? ☐Central telefónica ☐No cuenta con el servicio ☐Teléfono en el local 2. Si es que el producto no se encuentra disponible, ¿Puede saber el establecimiento más cercano donde encontrarlo? ☐Sí ☐No 3. ¿Cuenta con motorizados en su local? ☐Sí ☐No 4. Si cuenta con motorizados, ¿Qué pedidos atienden? ☐Solo los del local ☐Los que le comisione la central 63 Encuesta a trabajadores que se encargan de realizar las entregas a domicilio Nombre: _____________________________________________________ 1. Cuando le entregan un pedido, ¿Cómo haces para ubicar en la dirección del destino? ☐Mapa ☐Conocimientos Propios 2. Si la respuesta anterior fue “Mapa”, ¿Con qué mapa cuenta? ☐Propio, lo llevo durante el recorrido ☐Del local, lo uso como referencia 3. ¿En todo momento del día tiene pedidos por despachar? ☐Sí ☐No 4. Si la respuesta anterior fue “No”, ¿Cuántas horas al día, aproximadamente, no tiene pedidos que repartir? _______________________