Abstract

Resumen: Este trabajo se enfoca en dar solución a un problema real de planificación de transportes o ruteo de vehículos, definido gracias al aporte de una empresa colombiana del sector de servicios de transporte por carretera. El problema consiste en realizar la programación de operaciones de transporte internacional entre dos países, Colombia y Venezuela, para un horizonte de tiempo con múltiples variantes; entre ellas podemos resaltar: una flota heterogénea de vehículos y tráileres, múltiples depots (clientes), restricciones de ventanas de tiempo en los depots, diversas modalidades de servicio, entre otras. El objetivo es obtener una programación de recursos (vehículos y tráileres) para la atención de la demanda de solicitudes de servicios de transportes en un horizonte de tiempo, minimizando la distancia recorrida en estado vacío de los vehículos para el periodo. La solución se realizó a través de la implementación de la metaheurística Recocido Simulado (SA, Simulated Annealing), la cual se probó iniciando con soluciones factibles generadas por dos algoritmos heurísticos; el primero se basa en la heurística clásica conocida como el vecino más cercano y el segundo genera soluciones de forma aleatoria. Los resultados del Recocido Simulado usando las soluciones generadas con el primer algoritmo, no mostraron una mejora frente a dicha solución inicial, contrario a lo hallado con el uso de las soluciones del segundo método, donde se alcanzó hasta cerca de un 50% de mejora Abstract: This work focuses on finding a solution to a real problem of transport planning or vehicle routing, which has been defined with the collaboration of a Colombian company from the road transport service industry. The problem consists of scheduling the international transport operations between two countries, Colombia and Venezuela, over a time horizon, with multiple variants; such as: a heterogeneous fleet of vehicles and trailers, multiple depots (customers), time windows constraints in the depots, various service modalities, among others. The goal is to schedule the resources (vehicles and trailers) in order to meet the demand for transport service requests on a given time horizon, minimizing the distance traveled by the vehicles while empty. A solution to the problem is given by a Simulated Annealing (SA) Metaheuristic, which was tested by using two types of heuristics to generate the initial feasible solution; the first one is based on the classic “Nearest Neighbor” heuristic, while the second one generates random feasible solutions. The results of the Simulated Annealing using the first algorithm to generate the initial solution did not show any improvement over it, contrary to what was found by using the second method, which obtained up to around 50% of improvemen

Abstract

Los rápidos avances tecnológicos han permitido una nueva generación de redes denominadas USN (Ubiquitous Sensor Network), donde los dispositivos móviles y pequeños sensores están presentes en todas partes y se entremezclan en las actividades cotidianas del ser humano. Esta nueva generación de redes permitirá ofrecer diferentes servicios a usuarios, a través de arquitecturas computacionales que integrarán: nuevas tecnologías, aplicaciones tecnológicas, redes de comunicaciones y otros servicios especializados. Con las redes USN se amplían las posibilidades de desarrollo tecnológico, sobre todo en el diseño de “ciudad inteligente”, y en otros sectores importantes de la economía como el agrícola y de transporte, entre otros. La investigación recoge una mirada a las principales propuestas realizadas en diferentes ámbitos por instituciones referentes - en especial en lo definido por la Unión Internacional de Telecomunicaciones – UIT/ITU, que han intentado estandarizar una arquitectura de referencia para este tipo de redes con el fin de reducir las complejidades de integración, el uso de múltiples tecnologías, la heterogeneidad de los diferentes protocolos existentes y facilitar: la interconexión, la comunicación y futuros desarrollos en este campo. A partir de una revisión sistemática y completa en la investigación, se logró la construcción del Estado del Arte que determinó las necesidades y características que deben ser satisfechas por una arquitectura de referencia para las redes USN, en especial, lo referente a calidad de servicio debido a que estas redes por su gran crecimiento y volumen de datos recolectados, no podrán atender la demanda requerida en los próximos años. La investigación aborda un estudio de la implementación de la calidad de servicio en Redes USN, teniendo en cuenta factores como el tiempo, la pérdida de información, diferenciación de servicios de emergencia y la capacidad de la red. Por ejemplo, en entornos inalámbricos es necesario alcanzar estabilidad y poca variabilidad en el tiempo tanto en la transmisión de los datos como en las peticiones realizadas por los diferentes actores. Además, se incorpora en cada una de las capas definidas de la arquitectura de referencia, la calidad de servicio como un componente esencial para garantizar la capacidad de la red para transmitir datos con los niveles de servicio adecuados de acuerdo con cada servicio definido. En las capa de la arquitectura se definen elementos estructurales que permiten pasar entre cada una los parámetros y métricas definidos, que evitan la pérdida o retraso de paquetes asociados a aplicaciones o servicios determinados previamente como críticos. Para el caso de las Redes USN integradas a los servicios ITS, fue necesario asociar un servicio de emergencia al conductor de un vehículo por estados de somnolencia como un evento súbito tal como se propone en (Garcés, Salgado, Andrés, and Henry, 2015). En este caso, los paquetes se transmiten con una clase de servicio mayor a las demás haciendo que en cada capa, la información/paquete tenga un tratamiento especial y prioritario durante su envío al middleware o en otros casos, a las aplicaciones o servicios finales. Dentro de la investigación, se analizaron los protocolos usados actualmente, revisando los modelos que soportan los volúmenes de datos requeridos por este tipo de redes, determinando aplicar en la capa MAC diferenciación de servicio, asociando clases de servicio sobre los paquetes y haciendo que la transmisión de estos, se sintonicen con las demás capas de la Red y con toda la arquitectura. Establecida la necesidad de contar con un modelo de diferenciación de servicio, se determinaron los requerimientos de calidad de servicio. Con la prueba de concepto se pudo utilizar un modelo continúo (transmisión de datos en intervalos de tiempo periódico) y orientado por consultas en donde los datos son solicitados por un receptor, dando origen a un Modelo Hibrido con datos y peticiones en intervalos de tiempo bien definidos a lo largo de la Red USN y de la Arquitectura en general. Por otro lado, y avanzando en el conocimiento de estas redes, dentro de la investigación se propuso una arquitectura de referencia aplicable a un caso de estudio de orden nacional e internacional, tomando el área de los Sistemas Inteligentes de Transporte SIT/ITS, como un sector fundamental en el desarrollo de las naciones y del cual se tiene pleno conocimiento por parte de los involucrados en la investigación. Abstract. The rapid technological advances have allowed a new generation of networks called USN (Ubiquitous Sensor Network), where the mobile devices and small sensors are present everywhere and are intermingled in the daily activities of the human being. This new generation of networks will allow to offer different services to users, through computational architectures that will integrate: New technologies, technological applications, communications networks and other specialized services. With the USN networks the possibilities of technological development are extended, especially in the design of "smart city", and in other important sectors of the economy as the agricultural and transport, among others. The research takes a look at the main proposals made in different fields by relevant institutions - especially as defined by the International Telecommunication Union, ITU-, which have tried to standardize a reference architecture for this type of networks in order to Reduce the complexity of integration, the use of multiple technologies, the heterogeneity of the different existing protocols and facilitate interconnection, communication and future developments in this field. From a systematic and complete review in the investigation, the State of the Art was achieved, which determined the needs and characteristics that must be satisfied by a reference architecture for the USN networks, especially the quality of service due to the fact that these networks due to their great growth and volume of data collected, will not be able to meet the demand demanded in the coming years. The research addresses a study of the implementation of quality of service in USN Networks, taking into account factors such as time, loss of information, differentiation of emergency services and network capacity. For example, in wireless environments it is necessary to achieve stability and little variability in time both in the transmission of data and in the requests made by different actors. In addition, quality of service is included in each of the defined layers of the reference architecture as an essential component to guarantee the capacity of the network to transmit data with the appropriate levels of service according to each defined service. In the layers of the architecture are defined structural elements that allow to pass between each one the defined parameters and metrics, that avoid the loss or delay of packages associated with applications or services previously determined as critical. In the case of USN networks integrated with the ITS services, it was necessary to associate an emergency service to the driver of a vehicle by states of drowsiness as a sudden event as proposed in (Garcés, Salgado, Andrés, and Henry, 2015). In this case, the packets are transmitted with a higher class of service than the others, causing the information / packet to have special and priority treatment during its delivery to the middleware or in other cases to the final applications or services. In the research, we analyzed the protocols currently used, reviewing the models that support the data volumes required by this type of networks, determining to apply service differentiation in the MAC layer, associating service classes on the packets and making the transmission of these, be tuned with the other layers of the Network and with all the architecture. Establishing the need to have a service differentiation model, the quality of service requirements were determined. With the proof of concept it was possible to use a continuous model (data transmission in periodic time intervals) and oriented by queries where the data are requested by a receiver, giving origin to a Hybrid Model with data and requests in good time intervals defined throughout the USN Network and Architecture in general. On the other hand, and advancing in the knowledge of these networks, the research proposed a reference architecture applicable to a national and international case study, taking the area of Intelligent Transport Systems SIT / ITS, as a Fundamental sector in the development of the nations and of which it is had full knowledge on the part of those involved in the investigation.