European Conference on Operational Research edition:27 location:Glasgow date:12-15 July 2015
In this research, a number of Vehicle Routing Problems, in which only a subset of the customers has a demand, are considered in an incomplete network. We have investigated what would be the best improvement of this incomplete network, such that the total travel time of the vehicles in these routing problems is minimized. Three possible improvements, the possibility to add an extra road to the network, to widen one of the existing roads or to convert an existing road into a one-way road with a higher speed, are individually studied in this research. For each improvement, a Mixed Integer Programming formulation is presented to determine the best improvement. Due to the complexity of the problem, a heuristic is introduced to find good solutions in more realistic cases. This heuristic consists of two parts, a construction part and an analysis part. During the construction part, routes for the vehicles are constructed in the current network using a Variable Neighborhood Search. In the second part of the heuristic, the constructed routes are analyzed to determine a good improvement of the network. A case study with a set of scenarios with a different number of customers and a different number of vehicles is executed. The results show that a reduction in total travel time of the vehicles of about 2% can be obtained by improving the network. However, the total travel time in the heuristically improved network is only about 0.16% larger than in the optimally improved network.