Alternative Formulations for o-D Commodity case Node-Arc Formulation Decision variables: flow of commodity k on each arc ii Path formulation Decision variables: flow of commodity k on each path for k Tree?' or Sub-network?", Formulation Define: super commodity: set of all(O-D)commodities with the same origin o(or destination d Decision variables: quantity of the super commodity k as signed to each“ tree or“sub- network>, for k Formulations are equivalent 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 11 Alternative Formulations for O-D Commodity Case • Node-Arc Formulation – Decision variables: flow of commodity k on each arc ij • Path Formulation – Decision variables: flow of commodity k on each path for k • “Tree” or “Sub-network” Formulation – Define: super commodity: set of all (O-D) commodities with the same origin o (or destination d) – Decision variables: quantity of the super commodity k’ assigned to each “tree” or “sub-network” for k’ • Formulations are equivalent
Sample network a 4 b 3 Arcs Commodities 11 cost capy # quant 20 11 132 10 21415 20 324 10 434 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 12 Sample Network Commodities # o d quant 1 1 3 5 2 1 4 15 3 2 4 5 4 3 4 10 Arcs i j cost capy 1 2 1 20 1 3 2 10 2 3 3 20 2 4 4 10 3 4 5 40 1 2 3 4 a b c d e
Notation Parameters Decision variables A: set of all network arcs number of units K: set of all commodities of commodity k N: set of all network nodes O(k)D(k]: origin [ destination assigned to arc 1j node for commodity k k per unit cost of commodity k on arc ij total capacity on arc 1 assume u. k is unlimited for each k and each ij dk: total quantity of commodity k 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 13 Notation Parameters • A: set of all network arcs • K: set of all commodities • N: set of all network nodes • O(k) [D(k)]: origin [destination] node for commodity k • cij k : per unit cost of commodity k on arc ij • uij : total capacity on arc ij (assume uij k is unlimited for each k and each ij) • dk : total quantity of commodity k Decision Variables • xij k : number of units of commodity k assigned to arc ij