Shipping Problem
Dennis Shasha
Omniheurist Course
Computer Science
Description
You are given
-
a set of
goods having physical volume, and value.
-
a set of warehouses having some volume at certain locations
-
a set of trucks having a certain volume each
-
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.