Vehicle Routing is a good solution for the problem with which vehicles and in which order customers will be supplied from one or more depots. The complexity of the problem in reality often increases by additional restrictions: a limited capacity of the vehicles (i.e. volume, weight) or the demand of customer time windows. Applications exist not only in freight logistics of nearly all industries (i. e. furniture, waste management or food industry) but especially in Vehicle Routing of field representatives.
The example below shows the delivery of 24 customers in four routes from one depot.
For the solution of Vehicle Routing problems heuristics will be applicable because of the complexity. Efficient solution methods base on Genetic Algorithms, Simulated Annealing and Tabu Search. They use local search strategies where the sequence of orders or rather the allocation of orders to vehicles will be exchanged.
The planning of freight transports meets not only the challenge of increasing transport volume with limited capacity of the traffic infrastructure even in urban regions but also continual increasing demands on logistics companies with regard to response and delivery times. Empirical research carried has shown that substantial requirements – like flexibility of planning, detailed cost analyses or scalability for a large fleet of vehicles – remain unconsidered from the companies’ point of view. The target of Vehicle Routing software is the efficient coordination of transportation services in logistic networks considering stochastic information.
Wendt, O.; Stockheim, T.; Weiß, K.: Intelligente Tourenplanung mit DynaRoute; WIRTSCHAFTSINFORMATIK 47 (2005) 2; S. 135-140. König, W.; Wendt, O.: Kooperative Lokale Suche: Wann lohnt der Heterogenitätsverlust?; in Jahnke, B.; Wall, F.: IT-gestützte Betriebswirtschaftliche Entscheidungsprozesse; Wiesbaden (Gabler) 2001; S. 63-85. Wendt, O.: Tourenplanung durch Einsatz naturanaloger Verfahren; Wiesbaden (Gabler) 1995.
Method of Resolution
As a first step, different approaches of common standard software were analyzed and evaluated. A comprehensive investigation of the suppliers and of strengths and weaknesses of their methods and systems represents the Basis of this research project.
On this basis, the chair carried out an empirical study between 1,000 independent planning companies in cooperation with the Institute for Business Informatics of Goethe-Universität Frankfurt/Main. A third component within this project are the analysis of GPS data and the extraction of real planning scenarios. The figure shows typical breakpoints and Origin-Destination pairs for ten used vehicles of a medium-sized company within two months. Target of the accumulation and evaluation of these data is the development of stochastic models for travel time prediction.
Meta heuristics for Vehicle Routing based on research projects of the professor will be modified for the practical use to consider stochastic and individual planning criteria.
As a result the Software DynaRoute was developed in cooperation with VARLOG, a university spin off.
The current research focus lies on the development of Travel-Time-Prediction models for prediction of travel time. This enables the consideration of uncertainties like f. i. traffic delays and variable loading times. By this risks of delay and buffer times can be minimized. In addition, different data sources (f.i. digital maps and weather information) can be integrated to improve the prediction precision. The whole development and test and evaluation of the models base on real data and planning situations.
Contact person: Prof. Dr. Oliver Wendt, phone: +49 631 205 3771