welcome: please sign in

Revision 2 as of 2011-01-10 09:59:31

Clear message
location: ProblemsDescription / FastfoodOptimization

Fastfood Optimization

Problem Description

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 McBurger 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 format

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.

Output format

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.

NOTES:

1. 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.

2. 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.

Example

Author(s)

Author: Wolfgang Faber
Affiliation: