《航线进度计划》（英文版） lec3 Airline Schedule planning

Additional Keypath Notation Parameters plk): keypath for commodity k ei: total initial (flow assigned to keypaths) on arc y ∑ k∈K d, spk :三 (k) ∑ change in cost when one unit of commod k is shifted from keypath p(k) to path r(Note: typically non-negative if p(k) has minimum cost Decision variables p/k: fraction of total quantity of commodity k removed from keypath plk) to path r 2/212021 Barnhart 1.206J/16.77J/ESD. 15J

2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 6 Additional Keypath Notation Parameters p(k) : keypath for commodity k Qij : total initial (flow assigned to keypaths) on arc ij =  k K dkij p(k) c r p(k) : = c r – c p(k) =  ij A c ijij r -  ij A c ijij p(k); change in cost when one unit of commodity k is shifted from keypath p(k) to path r (Note: typically non-negative if p(k) has minimum cost) Decision Variables f r p(k): fraction of total quantity of commodity k removed from keypath p(k) to path r

The Keypath Formulation Mn∑∑(mkm k∈K ∑∑44m6+∑∑dm k∈Kr∈P k∈Kr∈P Vi∈A ∑ p(k) Vk∈K p(k) ≥0 yr∈PVk∈K 2/212021 Barnhart 1.206J/16.77J/ESD. 15J

2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 7 The Keypath Formulation ( ) f r P k K f k K u Q ij A d f d f c d f r k p k r P r p k i j i j k K r P r k p k r i j k K r P r k p k p k i j k K r P r k p k r p k k k k k          −   − +               0 1 s.t. : Min ( ) ( ) ( ) ( ) ( ) ( ) ( )  

Associated dual variables DUals T::: the dual variable associated with the bundle constraint for arc ij (t is non-negative) o'. the dual variable associated with the commodity constraints(o is non-negative) Economic Interpretation TE:: the value of an additional unit of capacity on arc o/dk: the minimal cost to remove an additional unit of commodity k from its keypath and place on another path 2/21/2021 Barnhart 1.206J/16.77J/ES D 2 15J

2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 8 Associated Dual Variables Duals - ij : the dual variable associated with the bundle constraint for arc ij ( is non-negative) -  k : the dual variable associated with the commodity constraints ( is non-negative) Economic Interpretation  ij : the value of an additional unit of capacity on arc ij  k/dk : the minimal cost to remove an additional unit of commodity k from its keypath and place on another path