Optimierungsnachmittag: Large Real World Location Problems & Multicommodity Flows Over Time: Algorithms and Complexity

I will focus in my talk on projects we are working on with
industrial partners and emphasis will be put on peculiarities
arising in the different application areas.

{\bf Location Problems in Supply Chain Management:} Structuring
global supply chain networks is a complex decision making process.
The typical inputs to such a process consist of a set of customer
zones to serve, a set of products to be manufactured and sold,
demand projections for the different customer zones, and
information about future conditions and costs (e.g.~transportation
and production). Given the above inputs, companies have to decide,
among other things, where to locate new service facilities
(e.g.~plants, warehouses), how to allocate procurement and
production activities to the various manufacturing facilities of
the network, and how to manage the distribution of products. The
presented model is now part of the software tool \emph{Supply
Chain Design} of the SAP AG which assists decisions-makers in the
strategic planning and design of supply chain networks.

{\bf Planning Sales Territories:} Sales territories are a common
tool to structure the operation of a companies' sales force.
Typically the territories are required to be balanced with respect
to measures like sales potential and workload and should be easily
accessible for the salespersons. To facilitate the management of
the territories they are made up by grouping together small sales
coverage units (e.g. zip code areas). The problem of sales
territory alignment is to propose such a grouping together with
locations for salespersons such that the managerially relevant
criteria are met. It can be modelled as a capacitated p-median
problem with side constraints and a number of algorithms have been
proposed to solve it. For practical purposes however it is
necessary to have very fast methods available that can handle
different combinations of requirements and restrictions.
Heuristics of this type have been developed and are embedded in
the so-called {\emph BusinessManager,} an ESRI ArcView extension
of {\emph Geomer GmbH,} Germany.


Multicommodity Flows Over Time: Algorithms and Complexity (Martin Skutella)

Flows over time have been introduced more than forty years ago by Ford and
Fulkerson and have many real-world applications such as, for example,
traffic control, evacuation plans, production systems, communication
networks, and financial flows. These flows are modeled in networks with
capacities and transit times on the arcs. The transit time of an arc
specifies the amount of time it takes for flow to travel from the tail to
the head of that arc. In contrast to the classical case of static flows, a
flow over time specifies a flow rate entering an arc for each point in time
and the capacity of an arc limits the rate of flow into the arc at each
point in time. We present recent approximation and complexity results for
flows over time with multiple commodities and costs. We will also touch the
more realistic setting of flow-dependent transit times and discuss new
models and algorithmic solutions.