Improving an Incomplete Road Network by Small ArcChanges

In most Routing Problems, it is assumed that the considered road network is complete and fixed. However, in practice, this is usually not the case. Most existing road networks are, for example, incomplete, since there is no direct connection between each pair of locations. In this research, the possibility to improve an incomplete road network by some small arc changes is investigated. Three possible changes 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. Different procedures are proposed to find the best improvement such that the total travel time of the vehicles on the network is minimized. This improvement can be the best single change or the best set of changes given a budget constraint.

The first procedure combines a construction part and an analysis part with a testing stage. During the construction part, routes for the vehicles are constructed in the existing 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 improvement for the network. Since the selected improvements in a set can interfere with each other, the determined improvement is tested during the testing stage. The second approach is an Adaptive Large Neighborhood Search of which the main structure is based on a Simulated Annealing algorithm. New solutions are generated by a large neighborhood, which consists of a set of destroy and a set of repair methods.

To test the proposed procedure, 32 benchmark instances are constructed from a real road network. These benchmark instances have one up to four vehicles available to serve 20 up to 150 customers. Based on the experiments on these test networks can be concluded that improving an incomplete road network by a single change leads in average to a reduction in travel time of about 1.5%. Furthermore, if the network is improved by a set of changes given a budget allowing a combination of around three improvements, the average reduction is about 5%.

Registration with Remy Spliet, spliet@ese.eur.nl, is required for availability of lunch.