Airport Pickup

Problem Description

Imagine a city composed of locations and possible driveways between these locations. (to be represented by a connected graph) One of this locations is an Airport. A set of vehicles are located around the city, and a collection of passengers are in the airport and need to be picked up by a vehicle.

Each passenger is carrying a collection of luggage, each with a weight. Each vehicle has a maximum weight loading capacity.

Find a plan to drive the vehicles to the airport and pickup all the passengers, one passenger per vehicle, making sure that each passenger is picked-up by a vehicle that is able to carry all of their luggage.

Input format

A) Atoms of the form location(L) listing the names of locations.

/B/) Atoms of the form driveway(L1, L2) where L1 and L2 are locations, indicating that it is possible to drive from L1 to L2 ( and from L2 to L1 ).

C) Atoms of the form veh(V,C) where V is the name of a vehicle and C is a number, the loading capacity of the vehicle.

D) For every vehicle an atom of the form at(V,L) where L is a location, indicating the initial location of a vehicle.

E) Atoms of the form luggage(P,[W0, W1, ..., Wn]) where P is the name of a passenger and [W0, W1, ..., Wn] is a list of weights of P's luggage items.

Output format

The output format is a sequence of instructions to pick up the passengers. This sequence is formed with the atoms drive(V,L,S) and pick(V,P,S) where:

A) drive(V,L,S) indicates vehicle V drives to location L at step S of the instruction sequence.

pick(V,P,S) indicated vehicle V picks-up passenger P at step S of the instruction sequence.

Sample input

location(park). location(airport). driveway(park. airport). veh(car1, 50). at(car1, park). luggage(bill, [20, 25]).

Sample output

drive(car1, airport, 0). pick(car1, bill, 1).

Author(s)

Author: A. Ricardo Morales
Affiliation: Texas Tech University, United States