Warehouse Problem
Dennis Shasha
Omniheurist Course
Computer Science
Description
You are given
-
a warehouse consisting of a 50 by 100 grid
-
goods can be picked out from any point on the grid
-
there are crane train tracks traversing the roof
-
there are 20 train cars
-
orders come for different goods here and there
-
a set of orders of specific items and specific quantities at specific locations
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:
-
good(id, volume, value)
-
warehouse(id, latitude, longitude, volume)
-
truck(id, volume)
-
order(id, goodid, goodquantity, latitude, longitude)
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:
-
goodwarehouse(warehouseid, goodid, quantity) -- naturally
this should not violate the warehouse volume constraint
-
truckwarehouse(warehouseid, truckid) -- each truck must start
at only one warehouse.
-
schedule(truckid, legid, starttime, endtime)
-- each legid is globally unique.
A leg can be a loading event or a delivery event
or a travel event.
-
travelleg(legid, startlat, startlong, endlat, endlong)
-- the time should be consistent with the distance travelled.
-
loadleg(legid, goodid, goodquantity) -- this should not violate
the truck capacity and the warehouse should have the
goods required; the time should be 10 minutes.
-
deliveryleg(legid, goodid, goodquantity) -- the truck should have
the goods specified.
The time should be 10 minutes.