# -------------- # INPUT DATA # -------------- set FLEETS; # {D9S,72S,72L,...,L11}: 3-char fleet codes set CITIES; # {ATL,BOS,CVG,...,YYZ}: 3-char city codes set TIMES circular; # {0000,0001,...,2359}: a circular set of # char strings denoting minutes of the day set LEGS within {c1 in CITIES, c2 in CITIES, t1 in TIMES, t2 in TIMES: c1 <> c2 and t1 <> t2}; # (c1,c2,t1,t2) represents the existence of a flight # that leaves c1 at t1 and arrives in c2 at t2 set HOOKS within {(c1,c2,t1,t2) in LEGS, (c3,c4,t3,t4) in LEGS: c2 = c3}; # pairs of flights that must use the same plane param cost {FLEETS,LEGS} >= 0; param BIG := 999999; # cost[f,c1,c2,t1,t2] is the cost for a plane of fleet f # to fly leg (c1,c2,t1,t2); if the cost >= BIG, # the plane cannot be used on that leg param turn_time {FLEETS,CITIES} symbolic in TIMES; param turn {f in FLEETS, c in CITIES} := ord(turn_time[f,c],TIMES); # turn[f,c] is the minimum time in minutes between # landing and takeoff for a plane of fleet f at city c param size {FLEETS} >= 0; # size[f] is the number of planes in fleet f # -------------- # DERIVED DATA # -------------- set SERV_CITIES {f in FLEETS} := union {(c1,c2,t1,t2) in LEGS: cost[f,c1,c2,t1,t2] < BIG} {c1,c2}; # for each fleet, the set of cities that it serves set OP_TIMES {f in FLEETS, c in SERV_CITIES[f]} circular by TIMES := setof {(c,c2,t1,t2) in LEGS: cost[f,c,c2,t1,t2] < BIG} t1 union setof {(c1,c,t1,t2) in LEGS: cost[f,c1,c,t1,t2] < BIG} next(t2,TIMES,turn[f,c]); # for each fleet and city served by that fleet, # the set of possible arrival/departure times at that city, # with arrival time adjusted for the turn requirement # -------------- # MODEL # -------------- minimize Total_Cost; node Gate {f in FLEETS, c in SERV_CITIES[f], OP_TIMES[f,c]}; # for each fleet and city served by that fleet, # there is a node for each possible time arc Fly {f in FLEETS, (c1,c2,t1,t2) in LEGS: cost[f,c1,c2,t1,t2] < BIG} integer >= 0, <= 1, from Gate[f,c1,t1], to Gate[f,c2,next(t2,TIMES,turn[f,c2])], obj Total_Cost cost[f,c1,c2,t1,t2]; arc Sit {f in FLEETS, c in SERV_CITIES[f], t in OP_TIMES[f,c]} integer >= 0, from Gate[f,c,t], to Gate[f,c,next(t)]; # network arcs for flights, and for planes on the ground subj to Service {(c1,c2,t1,t2) in LEGS}: sum {f in FLEETS: cost[f,c1,c2,t1,t2] < BIG} Fly[f,c1,c2,t1,t2] = 1; # each leg must be served by some fleet subj to Capacity {f in FLEETS}: sum {(c1,c2,t1,t2) in LEGS: cost[f,c1,c2,t1,t2] < BIG and ord(t2,TIMES) < ord(t1,TIMES)} Fly[f,c1,c2,t1,t2] + sum {c in SERV_CITIES[f]} Sit[f,c,last(OP_TIMES[f,c])] <= size[f]; # number of planes used is the number in the air at the # last time (arriving "earlier" than they leave) # plus the number on the ground at the last time in each city subj to Same {f in FLEETS, (c1,c2,t1,t2,c3,c4,t3,t4) in HOOKS: cost[f,c1,c2,t1,t2] < BIG}: Fly[f,c1,c2,t1,t2] = if cost[f,c3,c4,t3,t4] < BIG then Fly[f,c3,c4,t3,t4] else 0; # for two legs that are part of the same flight, # a plane from the same fleet must be assigned