Groupe d’études et de recherche en analyse des décisions

G-2003-50

Combining GPS, GIS and Optimization Algorithms for Road Network Monitoring

, et

Road network monitoring is an activity conducted daily by the Ministry of Transport of Quebec. The complete network must be monitored every two weeks. In this setting, the usual objective in arc routing of minimizing the total travel distance is irrelevant. The vehicles are equipped with GPS locating devices to monitor events and trace routes. Since most planned route are not completed because of events on the network, there is a need to continously re-plan and re-schedule routes. We developed a methodology to achieve this task by gathering data from the GPS trace, matching it to the planned routes within a GIS and then use mathematical algorithms to propose a new schedule with new routes. The interurban road network studied consists in a hierarchy of three classes of roads that have different monitoring standards. We tested three different methods using different objectives depending on the operators' needs. Results show that the method that implies rescheduling based on assignment and reconstruction of routes with an arc-adding method gives the best coverage for each class of road.

Nowadays, more transportation operators have devices like GPS to locate and manage their fleet of vehicles. The integration of such technologies to GIS and to OR models for arc routing in day to day operations is however a challenging task. This article addresses both the data processing issues and the optimization issues in order to design an efficient decision support system appropriate for the highly dynamic nature of the problem addressed.

, 20 pages