welcome: please sign in
location: ProblemsDescription / FastfoodOptimalityCheck

Fastfood Optimality Check

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.

We are to verify whether a given schema for constructing depots is optimal (among all construction schemas that construct the same number of depots as in the given schema). If it is, then there should not be any answer set; if it is not optimal, answer sets should encode a better solution.

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

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

depot(N,K) represents the fact that a depot is to be constructed at the restaurant named N, located at kilometer K, in the construction scheme, the optimality of which is to be checked. Example: depot(breisgau_ost,761).

Output format

Answer sets should contain a better construction scheme as atoms of the form altdepot(N,K), where N is the name of the associated restaurant and K the kilometer at which it is located. If the input construction scheme is optimal, no answer set should be printed.


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.



Author: Wolfgang Faber
Affiliation: University of Calabria, Italy

ASP Competition 2011: ProblemsDescription/FastfoodOptimalityCheck (last edited 2011-01-10 10:39:02 by CarmenSantoro)