Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

A real-life vehicle routing problem under uncertainty

Model, planning process, algorithmic aspects
: Simroth, A.

Borgwardt, K.-H. ; Univ. Augsburg:
OR and Global Business. International Conference Operations Research 2008 : Program and Abstracts; September 3rd - 5th 2008, University of Augsburg, Germany
Augsburg, 2008
International Conference Operations Research (OR) <2008, Augsburg>
Fraunhofer IVI ()
logistic planning; vehicle routing; planning under uncertainty

In this contribution we consider a real-life vehicle routing problem from the CEP market where one has to deal with uncertainties. Already its static version is hard to solve: It consists of serving pickups from or deliveries to customers with multiple depots, thereby respecting various constraints as vehicle capacity and suitability, multiple time windows of orders, availability of resources. The objective function is a weighted sum of different costs, including fixed costs for used vehicles, route lenght-, duration-, and load dependent costs, and penalty costs for violated soft constraints.
In the practical application one has to deal with uncertainties that appear in various forms: New orders arrive over the time and can be canceled again, customers to visit could not be met and so have to be revised later, order quantities can change, what becomes known in advance or not until realisation. Not least the time schedule of the routes is subject to change due to uncertain service and travel times.
Because of these a priori incomplete and uncertain information about the problem instance the process of creating route plans is a dynamic one: Existing plans permanently have to be adapted to the current situation and extended to cover added information. We describe this dynamic planning process, its modules and their interaction. The core our approach consists of an algorithm component that provides algorithms for adapting and repairing plans in real-time as well as for creating new plans and permanently improving the current plan in use.
The main idea of our algorithmic concept is to create robust plans, that are plans which can be easily adapted to new situations without loosing their solution quality. We describe our sampling-based algorithms used for this purpose.