Vehicle routing problem for information collection in wireless network

Abstract

The vehicle routing problem is one of the most studied problems in Operations Re-search. Different variants have been treated in the past 50 years and with technological advances, new challenges appear. In this thesis, we introduce a new variation of the VRP appearing in wireless networks. The new characteristic added to this well-know problem is the possibility of pick-up information via wireless transmissions. In the con-text considered here, a unique base station is connected with the outside and a vehicle is responsible for collecting information via wireless connection to the vehicle when it is located in another sufficiently close station. Simultaneous transmissions are permitted. Time of transmission depends on the distance between stations, the amount of infor-mation transmitted, and other physical factors (e.g obstacles along the way, installed equipment). Information to be sent outside of the network is continuously generated in each station at a constant rate. The first contribution of this thesis is the introduction of a mixed ILP formulation for a variation in which it is only possible to send all the information or nothing during a wireless transmission. For this model three different strategies are investigated: maximizing total amount of information extracted an the end of the time horizon; maximizing the average of the information in the vehicle at each time point; and maximizing the satisfaction of each station at the end of the time horizon. Each strategy is translated as a different objective function for the mixed ILP formulation. The problem is then reformulated by accepting the option of sending only part of the information during a wireless transmission and considering only the first strategy,(i.e. maximizing the amount of information extracted at the end of the horizon time). For this new version, we present three mixed ILP formulations, each one with advantages and disadvantages. These mixed ILP models are compared according to the CPU time, amount of information collected, gap of unresolved instances, etc. Because in real life we need to solve problems with a large number of stations, in this thesis, we also propose heuristics methods for the second version of the problem introduced. We build some heuristics that do not depend on the mixed ILP model (as for example Greedy heuristics) and also matheuristcs. In our matheuristics our best model (a vehi-cle event model) is used as a base for the development of construction of Heuristics as well as local search heuristics.

En esta tesis damos un primer acercamiento al problema de construir rutas de vehículo para optimizar el recojo de información generada en las estaciones, vía física y wireless. Construimos un primer modelo matemático MIP y se propone tres posibles funciones objetivos, las cuales serán comparadas. Para este primer modelo asumimos que no es posible enviar la información por partes, es decir, se envía toda la información o no se envía nada, además veremos que este modelo solo puede resolver de forma exacta hasta un máximo de 10 estaciones y con un tiempo T = 30, lo cual sugiere encontrar mejores modelos. En este trabajo construimos también otros tres modelos matemáticos, modelo discreto, modelo visitas, modelo evento, todos ellos permiten enviar una parte de la información acumulada en una estación cercana hacia el vehículo, estos modelos serán comparados de acuerdo con su velocidad, en estos modelos podemos exhibir algunas instancias de 20 estaciones y un tiempo de T igual a 72 y otra de 8 estaciones y un tiempo de 240. Debido a que en los problemas reales el número de estaciones es mayor necesitamos de métodos no exactos llamado heurísticas, las cuales nos permite obtener soluciones cercanas a la exacta, en este trabajo daremos algunas heurísticas como heurística greedy, heurística de inserción, heurística fix and relax, heurística de intercambio, y por último haremos comparaciones entre ellas de acuerdo a la velocidad y a la calidad de la solución.