This example is based on the "Fast Food" problem, number 662 of volume VI of the ACM programming contests problem set archive (http://acm.uva.es/p/v6/662.html).
The fastfood chain Mc Burger owns several restaurants along a highway. Recently, they have decided to build several depots along the highway, each one located at a restaurant and supplying several of the q restaurants with the needed ingredients. Each of the restaurants will be supplied by the nearest depot. If two or more depots are equidistantly nearest to a restaurant, it is supplied by exactly one of these. Naturally, the depots should be placed so that the average distance between a restaurant and its assigned depot is minimized, or equivalently that the sum of supply distances is minimized.
Instance have been created based on data taken from the website of "Tank&Rast", the company which runs most of the German autobahn service stations.
Input: restaurant/2, number_depots/1
Instances are given as facts over two predicates, restaurant/2 and number_depots/1.
restaurant(N,K) represents that a restaurant named N (this is a constant consisting of lowercase ASCII characters with enclosed underscores) is located at kilometer K of the highway (K is a nonnegative integer less than or equal to 910). Example: restaurant(auetal_nord,270).
number_depots(N) specifies the number N of depots to be built. Any input contains exactly one fact of this kind.
Instances are given as facts over one predicate, depot/2.
Answer sets should contain construction schemes as atoms of the form depot(N,K), where N is the name of the restaurant to which a depot should be annexed and K the kilometer at which it is located.
Input: restaurant(a,1). restaurant(b,2). restaurant(c,7). restaurant(d,100). number_depots(2).
Possible output: depot(b,2). depot(d,100).
- Issues about directions on the highway (e.g. that some restaurants are reachable only going in one particular direction on the highway) are not considered, it is hence assumed that all restaurants are connected to both directions of the highway.
- There can be more than one depot at a given kilometer. This occurs rather frequently in the data, when there are restaurants on both sides of the motorway.
Type: Search/NP Competition: M&S only
Like the checking version of this problem, this scenario challenges both modelling and computational capabilities of participant systems on a 'battlefield' which requires some arithmetics and aggregate constructs. In this variant, optimization makes evaluation expectedly harder.
- Author: Wolfgang Faber
- Affiliation: University of Calabria, Italy