1206J/1677J/ESD215J Airline Schedule Planning Cynthia barnhart spring 2003
1.206J/16.77J/ESD.215J Airline Schedule Planning Cynthia Barnhart Spring 2003
1.206J/16.77J/ESD. 215] Airline Schedule planning: Multi-commodity Flows Outline Applications Problem definition Formulations olutions Computational results Integer multi-commodity network flow problems Integer multi-commodity network flow solutions Branch-and-price: combination of branch-and-bound and column generation Results 2/212021 Barnhart 1.206J/16.77J/ES D 2 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 2 1.206J/16.77J/ESD.215J Airline Schedule Planning: Multi-commodity Flows Outline – Applications – Problem definition – Formulations – Solutions – Computational results – Integer multi-commodity network flow problems – Integer multi-commodity network flow solutions • Branch-and-price: combination of branch-and-bound and column generation – Results
Application I Package flow problem(express package delivery operation) Shipments have specific origins and destinations and must be routed over a transportation network Each set of packages with a common origin destination pair is called a commodity Time windows(availability and delivery time associated with packages The objective might be to minimize total costs find a feasible flow 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 3 Application I • Package flow problem (express package delivery operation) – Shipments have specific origins and destinations and must be routed over a transportation network – Each set of packages with a common origindestination pair is called a commodity • Time windows (availability and delivery time) associated with packages – The objective might be to minimize total costs, find a feasible flow,
Application II Passenger mix problem Given a fixed schedule of flights, a fixed fleet assignment and a set of customer demands for air travel service on this fleeted schedule, the airline's objective is to maximize revenues by accommodating as many high fare passengers as possible For some flights, demand exceeds seat supply and passengers must be spilled to other itineraries of either the same or another airline 2/212021 Barnhart 1.206J/16.77J/ES D 2 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 4 Application II • Passenger mix problem – Given a fixed schedule of flights, a fixed fleet assignment and a set of customer demands for air travel service on this fleeted schedule, the airline's objective is to maximize revenues by accommodating as many high fare passengers as possible – For some flights, demand exceeds seat supply and passengers must be spilled to other itineraries of either the same or another airline
Application Ill Message routing problem In a telecommunications or computer network, requirements exist for transmission lines and message requests, or commodities The problem is to route the messages from heir origins to their respective destinations at minimum cost 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 5 Application III • Message routing problem – In a telecommunications or computer network, requirements exist for transmission lines and message requests, or commodities. – The problem is to route the messages from their origins to their respective destinations at minimum cost
MCF Networks Set of nodes Each node associated with the supply of or demand for commodities ● Set of arcs Cost per unit commodity flow Capacity limiting the total flow of all commodities and/ or the flow of individual commodities 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 6 MCF Networks • Set of nodes – Each node associated with the supply of or demand for commodities • Set of arcs – Cost per unit commodity flow – Capacity limiting the total flow of all commodities and/ or the flow of individual commodities
MCF Commodity definitions a commodity may originate at a subset of nodes in the network and be destined for another subset of nodes a commodity may originate at a single node and be destined for a subset of the nodes A commodity may originate at a single node and be destined for a single node 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 7 MCF Commodity Definitions • A commodity may originate at a subset of nodes in the network and be destined for another subset of nodes • A commodity may originate at a single node and be destined for a subset of the nodes • A commodity may originate at a single node and be destined for a single node
MCF Objectives Flow the commodities through the networks from their respective origins to their respective destinations at minimum cost Expressed as distance, money, time, etc Ahuja, Magnanti and Orlin(1993)--survey of multi-commodity flow models and solution rocedures 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 8 MCF Objectives • Flow the commodities through the networks from their respective origins to their respective destinations at minimum cost – Expressed as distance, money, time, etc. • Ahuja, Magnanti and Orlin (1993)-- survey of multi-commodity flow models and solution procedures
MCF Problem formulations Linear programs Network flow problems Capacity constraints limit flow of individua commodities Conservation of flow constraints ensure flow balance for individual commodities Flow non-negativity constraints With side constraints Bundle constraints restrict total flow of ALL commodities on an arc 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 9 MCF Problem Formulations -- Linear Programs • Network flow problems – Capacity constraints limit flow of individual commodities – Conservation of flow constraints ensure flow balance for individual commodities – Flow non-negativity constraints • With side constraints – Bundle constraints restrict total flow of ALL commodities on an arc
MCF COnstraint matrix Network flc problem commodity k=1 Network flow problem, commodity k=2 Network flow problem commodity k=3 Network flow ommodity k=4 Bundle constraints limiting total flow of all commodities to arc capacities 2/212021 Barnhart 1.206J/16.77J/ESD. 15J
2/21/2021 Barnhart 1.206J/16.77J/ESD.215J 10 MCF Constraint Matrix Network flow problem, commodity k=1 Bundle constraints limiting total flow of all commodities to arc capacities Network flow problem, commodity k=2 Network flow problem, commodity k=3 Network flow problem, commodity k=4
