《航线进度计划》（英文版） 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