Avignon VRP

Person proposing the project : Rosa Figueiredo (rosa.figueiredo@univ-avignon.fr); Francesco Di Pellegrini (francesco.de-pellegrini@univ-avignon.fr) Location of the internship: LIA-CERI, Avignon (ceri.univ-avignon.fr) Context: The trainee will study a routing-collecting problem where a system of stations is considered. A vehicle is responsible for collecting information generated continuously in the stations and to deliver it to the base station. The objective is to determine the vehicle route and the collection operations, both physical and wireless, in order to maximize the amount of information collected during a time horizon. Many works in the literature have address vehicle routing problems in the presence of wireless transmission. However, most of them focusing on the study of protocols/policies for routing and data collection. Only a small set of works addresses the development of vehicle routing strategies, most cases, in a two-phase manner (see [2]). This work will help to fill this gap focusing on the design of a vehicle route from scratch together with a wireless transmission planning. Recently, in a previous work [1], we introduced three mixed integer programming (MIP) models for this problem. An extensive computational study was reported to compare the performance of a solver based on each one of the models. The proposed MIP models are able to solve instances with up to 20 stations and 70 time periods, in 1 hour of computation. Fast matheuristics were also developed in order to solve the problem on larger networks (100 stations ; 120 time periods). Objectives: The trainee will: 1. characterize and describe the optimal solution of the problem for certain network topologies (for ex. star, grid, cycle), 2. study periodicity on the remaining information at the stations after a sequence of vehicle routings for certain network topologies (for ex. star, grid, cycle), 3. enrich the version of the problem and the existent models by considering the existence of multiple vehicles and technological constraints. References: 1. Luis Flores-Luyo, Agostinho Agra, Rosa Figueiredo, Eladio Ocaña, Mixed integer formulations for a routing problem with information collection in wireless networks, European Journal of Operational Research, 280, pp 621-638, 2020. 2. M. Di Francesco, S.K. Das, and G. Anastasi. Data collection in wireless sensor networks with mobile elements: A survey. ACM Transactions on Sensor Networks, 8(1):1?31, 2011. Topics related to the internship: Operations Research; Network Optimization; Wireless Sensor Networks, Integer Programming, Matheuristic