How to Whack Moles
(2004)
In the classical whack-a-mole game moles that pop up at
certain locations must be whacked by means of a hammer before they
go under ground again. The goal is to maximize the number of moles
caught. This problem can be formulated as an online optimization problem:
Requests (moles) appear over time at points in a metric space and
must be served (whacked) by a server (hammer) before their deadlines
(i.e., before they disappear). An online algorithm learns each request
only at its release time and must base its decisions on incomplete information.
We study the online whack-a-mole problem (wham) on the real
line and on the uniform metric space. While on the line no deterministic
algorithm can achieve a constant competitive ratio, we provide competitive
algorithms for the uniform metric space. Our online investigations
are complemented by complexity results for the offline problem.
Today's telecommunication networks are configured statically. Whenever a connection
is established, the customer has permanent access to it. However, it is
observed that usually the connection is not used continuously. At this point, dynamic
provisioning could increase the utilization of network resources. WDM
based Optical Transport Networks (OTNs) will shortly allow for fast dynamic
network reconfiguration. This enables optical broadband leased line services on
demand. Since service requests competing for network resources may lead to service
blocking, it is vital to use appropriate strategies for routing and wavelength
assignment in transparent optical networks. We simulate the service blocking
probabilities of various dynamic algorithms for this problem using a well-founded
traffic model for two realistic networks. One of the algorithms using shortest path
routings performs best on all instances. Surprisingly, the tie-breaking rule between
equally short paths in different wavelengths decides between success or
failure.
Given a set of service requests (events), a set of guided servers (units),
and a set of unguided service contractors (conts), the vehicle dispatching problem
VDP is the task to find an assignment of events to units and conts as well as tours
for all units starting at their current positions and ending at their home positions
(dispatch) such that the total cost of the dispatch is minimized.
The cost of a dispatch is the sum of unit costs, cont costs, and event costs. Unit
costs consist of driving costs, service costs and overtime costs; cont costs consist of
a fixed cost per service; event costs consist of late costs linear in the late time, which
occur whenever the service of the event starts later than its deadline.
The program ZIBDIP based on dynamic column generation and set partitioning
yields solutions on heavy-load real-world instances (215 events, 95 units) in less
than a minute that are no worse than 1% from optimum on state-of-the-art personal
computers.
Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable
first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain ``subinstances'' (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later.
We introduce the novel concept of an Online Target Date Assignment Problem (OnlineTDAP) as a general framework for online problems with this nature. Requests for the OnlineTDAP become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e.g., an appointment with a customer for a
washing machine repair). The cost at a target date is given by the downstream cost, the optimal cost of processing all requests
at that date w.r.t. some fixed downstream offline optimization problem (e.g., the cost of an optimal dispatch for service
technicians). We provide general competitive algorithms for the OnlineTDAP independently of the particular downstream problem,
when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the particular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman.
Under high load, the automated dispatching of service vehicles for
the German Automobile Association (ADAC) must reoptimize a dispatch for
100{150 vehicles and 400 requests in about ten seconds to near optimality. In
the presence of service contractors, this can be achieved by the column generation
algorithm ZIBDIP. In metropolitan areas, however, service contractors
cannot be dispatched automatically because they may decline. The problem:
a model without contractors yields larger optimality gaps within ten seconds.
One way out are simplified reoptimization models. These compute a shortterm
dispatch containing only some of the requests: unknown future requests
will in
uence future service anyway. The simpler the models the better the
gaps, but also the larger the model error. What is more significant: reoptimization
gap or reoptimization model error? We answer this question in
simulations on real-world ADAC data: only the new models ShadowPrice and
ZIBDIPdummy can keep up with ZIBDIP.