Bérczi, Kristóf (ELTE MI)
Road
Surveillance Optimization - An Asymmetric Vehicle Routing Problem with Visiting
Frequencies
In this talk we describe a real life optimization problem related to route
planning of public road surveillance vehicles. The public roads must be checked
regularly with a predetermined visiting frequency depending on the road
category and traffic intensity. The surveillance is made by multiple vehicles
starting from and arriving at their own garages. The traveling and surveying
speeds are different, and these predefined speed values also vary with the type
of the road. Finally, the daily maximum working time is also limited. Then, the
goal it to minimize the total travel time or distance of the surveillance
vehicles while taking all the parameters and side constraints above.
The problem may be considered as a Periodic Vehicle Routing Problem with a highly asymmetric length function. We discuss several variants of the problem depending on the allowed visiting patterns of each road segment and on whether or not the roads are preassigned to the surveillance vehicles. We present heuristic and integer linear programming based schemes to solve these large scale optimization problems. The proposed algorithms are tested on real life problem instances in a framework of a pilot project initiated by the Hungarian PublicRoad Nonprofit Private Limited Company.
The talk is held in Hungarian!
Az előadás nyelve magyar!
Date: Oct 15, Tuesday 4:15pm
Place: BME, Building „Q”, Room
QBF13