EURO2016 edition:28 location:Poznan, Polen date:3-6 July 2016
The optimization problem, considered in this research, is about determining the best set of possible improvements of an incomplete road network such that the total travel time on the network is minimized. Three possible improvements are studied in this research: (re-)opening pedestrian zones for vehicles, widening existing roads and converting existing roads into one-way roads with a higher speed. The total costs of the selected set of improvements may not exceed a given budget. A Mixed Integer Programming formulation is presented to determine the best set of improvements. Due to the complexity of the problem, a heuristic is introduced to find near-optimal solutions for cases of realistic size. This heuristic iterates between a construction part and an analysis part. During the construction part, routes for the vehicles are constructed in the current network using a fast Variable Neighborhood Search. In the second part of the heuristic, the constructed routes are analyzed heuristically in order to determine a good set of improvements for the network. Since the selected improvements in the set can interfere with each other, this determined set is tested again in the construction part. The performance of our heuristic is evaluated on a set of benchmark instances based on a realistic road network with a varying number of customers and vehicles. Additionally, the solution quality is compared to that of solutions obtained using exact solution techniques.