A two-phase metaheuristic to determine the best network change in an incomplete network
Corrinne Luteyn, Reginald Dewil, Pieter Vansteenwegen · Lirias · 2016
The optimization problem, considered in this research, is about determining the best possible improvement of an incomplete network such that the total travel time of the vehicles on the network is minimized. Three possible improvements are studied in this research: adding an extra road to the network, widening one of the existing roads and converting an existing road into a one-way road with a higher speed. Due to the complexity of the problem, a metaheuristic is introduced to find nearoptimal solutions for cases of realistic size. is metaheuristic combines 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 metaheuristic, the constructed routes are analyzed heuristically in order to determine a good improvement of the network. Benchmark instances are created based on a realistic road network with varying numbers of customers and vehicles. The results show that a reduction in total travel time of the vehicles of up to more than 3% can be obtained by improving the network. Moreover, the total travel time in the network which is improved by our metaheuristic is on average only 0.09% longer than in the optimally improved network.