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

1206J/1677J/ESD215J Airline Schedule Planning Cynthia barnhart spring 2003

1.206J/16.77J/ESD.215J Airline Schedule Planning Cynthia Barnhart Spring 2003

1206J/16.7ESD215J Multi-commodity network Flows A Keypath Formulation Outline Path formulation for multi-commodity flow problems revisited Keypath formulation Example K . eypath solution algorithm Column generation Row generation 2/212021 Barnhart 1.206J/16.77J/ESD. 15J

2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 2 1.206J/16.77J/ESD.215J Multi-commodity Network Flows: A Keypath Formulation • Outline – Path formulation for multi-commodity flow problems revisited – Keypath formulation – Example – Keypath solution algorithm • Column generation • Row generation

Path notation Sets Parameters(cont A: set of all network arcs Cp: per unit cost of K: set of all commoditi commodity k on path N: set of all network nodes k 1 if path p contains Parameters arc ij; and =0 otherwise u: : total capacity on arc dk: total quantity of Decision variables commodity k fp: fraction of total quantity PK: set of all paths for or commode k assigned commodity k, for all k to pa 2/212021 Barnhart 1.206J/16.77J/ESD. 15J

2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 3 Path Notation Sets A: set of all network arcs K:set of all commodities N: set of all network nodes Parameters uij : total capacity on arc ij dk : total quantity of commodity k P k : set of all paths for commodity k, for all k Parameters (cont.) cp : per unit cost of commodity k on path p = ij p cij k ij p : = 1 if path p contains arc ij; and = 0 otherwise Decision Variables fp : fraction of total quantity of commodity k assigned to path p

The path Formulation revisited MINIMIZE∑ k∈ KPEpk dk c/p sbgk2k∈K① Sui vie∈ pek=11k∈K f≥0bp∈P,k∈K 21-Feb-21 1.224J/ESD.204J

21-Feb-21 1.224J/ESD.204J 4 The Path Formulation Revisited MINIMIZE  k K  pP k dk c p f p subject to: pP k  k K dk f pij p  uij  ijA pP k f p = 1  kK f p  0  pP k ,  kK

The Keypa ath Concept The path formulation for MCF problems can be recast equivalently as follow Assign all flow of commodity k to a selected path p, called the keypath, for each commodity kek Often the keypath is the minimum cost path for k The resulting flow assignment is often infeasible One or more arc capacity constraints are violated If the resulting flows are feasible and the keypaths are minimum cost, the flow assignment is optimal Solve a linear programming formulation to minimize the cost of adjusting flows to achieve feasibility Flow adjustments involve removing flow of k from its keypath p and placing it on alternative path p'Epk, for each k∈K 2/212021 Barnhart 1.206J/16.77J/ESD. 15J

2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 5 The Keypath Concept • The path formulation for MCF problems can be recast equivalently as follows: – Assign all flow of commodity k to a selected path p, called the keypath, for each commodity kK • Often the keypath is the minimum cost path for k • The resulting flow assignment is often infeasible – One or more arc capacity constraints are violated • If the resulting flows are feasible and the keypaths are minimum cost, the flow assignment is optimal – Solve a linear programming formulation to minimize the cost of adjusting flows to achieve feasibility • Flow adjustments involve removing flow of k from its keypath p and placing it on alternative path p’P k , for each kK

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

Optimality conditions for the path Formulation f, and i,o*R are optimal for all k and all if. 1. Primal feasibility is satisfied 2. Complementary slackness is satisfied 3. Dual feasibility is satisfied (reduced cost is non-negative for a minimization problem 21-Feb-21 1.224J/ESD.204J

21-Feb-21 1.224J/ESD.204J 9 Optimality Conditions for the Path Formulation f*p and * ij , * k are optimal for all k and all ij if: 1. Primal feasibility is satisfied 2. Complementary slackness is satisfied 3. Dual feasibility is satisfied (reduced cost is non-negative for a minimization problem)

Modified costs Definition: Reduced cost for path I, commodity k XyeA Ci dk/>jeA Ci K dk Sip(+ iea; dkS XieA Ti dk sip(k)+o jEA(C,K +Mi8 ∑A(c+m)6例+aak Definition: Let modified cost for arc jj and commodity k=cnk+兀; Reduced cost is non-negative for all commodity k variables if the modified cost of path requals or exceeds the modified cost of p(k)less o /dk 2/212021 Barnhart 1.206J/16.77J/ES D 2 15J

2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 10 Modified Costs Definition: Reduced cost for path r, commodity k = ijA cij k dk ij r - ijA cij k dk ij p(k) + ijA ijdk ij r - ijA ij dk ij p(k) +  k = ijA (cij k + ij ) ij r – ijA (cij k + ij ) ij p(k) +  k / dk Definition: Let modified cost for arc ij and commodity k = cij k + ij ➢ Reduced cost is non-negative for all commodity k variables if the modified cost of path r equals or exceeds the modified cost of p(k) less  k/ dk