Warehouse Problem

Dennis Shasha

Omniheurist Course

Computer Science



You are given

You are to determine which warehouses to put which goods and which trucks over night for delivery the next day in such a way that you maximize the value delivered and minimize the cost. The cost of delivery to an address is a fixed cost of $1 per 100 kilograms plus 1 cent per kilometer. Time is 1 minute per kilometer. Trucks leave the warehouse at 7 AM. They must arrive at any given house before 7 PM (19:00) to be said to arrive on time. Loading at the warehouse takes 10 minutes and each delivery takes 10 minutes.

The format will be as follows:

To compute the distance, estimate that each degree of latitude is roughly 100 kilometers and similarly for longitude. So, given (lat1, long1) and (lat2, long2) compute 100*squareroot((lat1 - lat2)^2 + (long1-long2)^2).

Each team works by itself on the problem and is to deliver a schedule that details: