Tourism 2

Tourism 2

(file name: tourism2.pl)

Having abandoned Connor's previous attempt at tour planning, Anh asks the tour members to indicate which locations they would like to see. As an added complication, each location is only open for certain hours, and visiting different locations require different amounts of time.

Anh wishes to find the tour which is most fair. Let n be the number of locations overall. A person's satisfaction is:

  • n if all desired locations are visited on the tour
  • the number of visited desired locations otherwise.

The objective is to choose a set of locations which maximizes the satisfaction of the least satisfied person.

Input format

An input file for LP systems contains the following facts:

  • One fact people(N) specifying the number of people.
  • One fact locations(M) specifying the number of locations.
  • One fact preferences(K) specifying the number of preferences.
  • A relation consisting of facts location(L, D, O, C) specifying the visit duration D, opening hour O, closing hour C of a location L.
  • A relation consisting of facts prefer(P, L) indicating that person P wants to visit location L.

An input file for Minizinc specifies the number of people (people), locations (locations) and preferences (preferences), the visit duration (duration), opening hours (open) and closing hours (close) for each location, and the person (preferer) and location (preference) corresponding to each preference.

Output format

The output should contain exactly one fact of the form satisfaction(S), where S is the optimal satisfaction (i.e., the satisfaction value of the least satisfied person for the model that has the maximum such satisfaction of the least satisfied person).

Examples

LP inputMinizinc intputOutput
people(2).
locations(3).
preferences(4).
location(1, 1, 9, 11).
location(2, 1, 9, 11).
location(3, 1, 9, 11).
prefer(1, 1).
prefer(2, 1).
prefer(2, 2).
prefer(2, 3).
people = 2;
locations = 3;
preferences = 4;
duration = [1, 1, 1];
open = [9, 9, 9];
close = [11, 11, 11];
preferer = [1, 2, 2, 2];
preference = [1, 1, 2, 3];
satisfaction(2).
people(3).
locations(4).
preferences(4).
location(1, 2, 9, 12).
location(2, 1, 9, 12).
location(3, 3, 9, 15).
location(4, 6, 12, 18).
prefer(1, 1).
prefer(1, 2).
prefer(2, 3).
prefer(2, 4).
people = 3;
locations = 4;
preferences = 4;
duration = [2, 1, 3, 6];
open = [9, 9, 9, 12];
close = [12, 12, 15, 18];
preferer = [1, 1, 2, 2];
preference = [1, 2, 3, 4];
satisfaction(1). 
people(3).
locations(4).
preferences(4).
location(1, 2, 9, 12).
location(2, 1, 9, 12).
location(3, 3, 9, 15).
location(4, 6, 12, 18).
prefer(1, 1).
prefer(1, 2).
prefer(2, 3).
prefer(3, 4).
people = 3;
locations = 4;
preferences = 4;
duration = [2, 1, 3, 6];
open = [9, 9, 9, 12];
close = [12, 12, 15, 18];
preferer = [1, 1, 2, 3];
preference = [1, 2, 3, 4];
satisfaction(0). 

ċ
Graeme Gange,
Aug 30, 2017, 2:28 AM
Comments