Airports - Revision history

Admin: /* Data structure */

2017-06-19T18:40:19Z

Data structure

← Older revision		Revision as of 18:40, 19 June 2017
Line 89:		Line 89:

	Then we find a minimum path through all the nodes.		Then we find a minimum path through all the nodes.


			[[Category:Final Project]]

Admin: /* Input File */

2017-06-19T00:53:47Z

Input File

← Older revision		Revision as of 00:53, 19 June 2017
Line 30:		Line 30:

	n + 2 + m: ditto		n + 2 + m: ditto

			==Solution Notes==

			Airports problem:
			* Set of n airports, trying to provide m flights between the planes
			* We are provided with when the planes need to fly out of which airports at specified times

			Input file detials: see above

			START WITH THE FLIGHTS

			Draw a connection from node A to node B if the starting/ending times of these two flights is reconcilable

			Remember: this is a DAG

			Now, we can convert this into two DAGs, and find the maximum bipartite matching in this graph.

			The answer we are after is m - \|max bipartite matching\|

			What do we mean when we say "maximum matching"?

			We want maximum number of edges that connect two flights (u,v) (In other words, we want to maximize flight ''utility'' by matching up as many flights end-to-end as possible.)

			Maximum matching means we've "matched up" the most connections possible, and therefore maximized the utility of each flight.

			Any given ''matching'' that connects a node (flight) u in graph 1 to another node (flight) v in graph 2 is an edge representing a flight plan u to v. (Note that because flight times are not symmetric, graph 1 u to graph 2 v does not imply graph 1 v to graph 2 u. Although it may imply graph 2 u to graph 1 v. That is, <code>u->v</code> does not imply <code>v->u</code>

			We want to minimize the number of unmatched edges.

			Equivalent to minimizing flights arriving in a city and being stuck

			Equivalent to maximizing size of matching.

			Question:
			* Looking for paths that connect ''all nodes'' trips that visit ''all nodes'' while minimizing......... ?

			<flight source node> <flight destination node> <flight time>

			==Data structure==

			Start with the data structure:
			* Constant number of flights m
			* m are nodes, n are airports
			* Draw graph: vertices are FLIGHTS
			* Node i = flight i, node j = flight j
			* Edge ij = whether it is possible to fly (service from flight i -> flight j)
			* This graph should form a DAG
			* We want the minimum number of paths needed to coer all vertices
			* We want to find the minimum number of paths

			Algorithm:
			* Build a bipartite graph
			* All flights
			* copy of all flights
			* u1 -> v2 indicates a plane can service flight u2 and then service flight v2.
			* this is because we are not interested in "does this flight connect city A to city B" - rather, we're given a set of flights we have to make.
			* We need the flights to cover those paths, the only question is how we'll do it.

			Then we find a minimum path through all the nodes.

Admin: /* Problem Statement */

2017-06-19T00:44:51Z

Problem Statement

← Older revision		Revision as of 00:44, 19 June 2017
Line 10:		Line 10:

	The airline may add unscheduled flights to move the airplanes around if that would reduce total number of planes needed.		The airline may add unscheduled flights to move the airplanes around if that would reduce total number of planes needed.

			===Input File===

	Lines:		Lines:

Admin: Created page with "==Problem Statement== An airline company offers flights out of n airports, labeled from 1 to n. The flight time tij from airport i to airport j is known for each ij, althoug..."

2017-06-19T00:44:34Z

Created page with "==Problem Statement== An airline company offers flights out of n airports, labeled from 1 to n. The flight time tij from airport i to airport j is known for each ij, althoug..."

New page

==Problem Statement==

An airline company offers flights out of n airports, labeled from 1 to n.

The flight time tij from airport i to airport j is known for each ij, although it may not be the case that tij = tji.

Upon landing at a given airport, a plane must be inspected before flying again. Inspection time pi is dependent on the airport where the flight landed, not where previous flight originated.

Given a set of m flights that the airline company must provide, determine minimum number of planes company needs to purchase.

The airline may add unscheduled flights to move the airplanes around if that would reduce total number of planes needed.

Lines:

Line 1: n (number of airports) m (number of flights to maintain)

Line 2: (inspection times, pi, i = 1..n)

Line 3: j=1 (3-2), all the tij's (tii=0)

...

n+2 : j = n (n+2 - 2), all of the tij's

n+3: <source airport> <destination airport> <flight time>

...

n + 2 + m: ditto