Time dependent Travel Times in Location and Routing Problems

With increasing traffic volume and the resulting increasing traffic congestions in cities, logistics service providers, service technicians and taxi services are facing great problems in starting their service at the agreed starting times. The service providers usually have agreed fixed pickup times of the parcel or the passenger or fixed starting times for the services. Geographic Information Systems (GIS) and available road network data make it possible, that very good or even near optimal solutions for vehicle routing problems and vehicle location problems can be calculated. Although, the distance information is usually based on static information which is precalculated based on the road type and on the average speed which is usually rideable on the corresponding road type. It is not considered how many cars use this street during the day - on specific times during the day. It is not considered when (potential) congestions occur. The defined travel times are not modified for different times during the day. The shortest route from two visit points is not modified. This fact can lead to infeasible solutions - it happens very often that e.g. service technicians cannot start their service because they are caught up in a traffic jam. Nowadays Global Positioning Systems (GPS) can be used to monitor the exact position of vehicles at every point in time during the day. By using this technology it is possible to calculate time dependent travel times for the major roads and streets in a city. These data are available and can be used to improve the vehicle routing and vehicle location solutions in cities with available floating car data. In the Vienna region an application by collecting floating car data was installed. There are about 800 taxis which are used to collect data and provide good information on time dependent travel times during the day. In the past years a fairly large number on solution techniques for static vehicle routing problems and vehicle location problems have been developed. Already very large scale problems with complex side constraints and real world characteristics can be solved. These excellent results on frontier research for VRP and VLP problems provide a profound basis to integrate real world information such as time dependent travel times to even more improve the solution quality of vehicle routing and vehicle location problems. The integration of FCD in vehicle routing and locations problems is especially for the following applications of practical relevance. 1.) Vehicle location for breakdown service providers, police, emergency service providers, fire departments. These emergency service providers have to locate their vehicles in such a way that the maximum required response time can be fulfilled. In order to reach always the maximum required response time it is necessary to reallocate vehicles during the day when time dependent travel times are also considered. 2.) Vehicle routing solutions for parcel services and taxi services. Exact forecasted pickup times have to be fulfilled. Re-planning has to be performed when time dependent travel times are considered. In the proposed project the knowledge about time dependent travel times has to be exploited and the use of FCD in heuristic optimization techniques (e.g. variable neighbourhood search, scatter search) should be integrated. The algorithms should be modified that this additional information can be used in order to improve the heuristic solution methods and to provide more realistic solutions.