edu.mit.ll.group43.surfaceoptimization.dp.factory.cost
Class AllGapsForceSpotCostStrategy

java.lang.Object
  extended by edu.mit.ll.group43.surfaceoptimization.dp.factory.cost.CostStrategy
      extended by edu.mit.ll.group43.surfaceoptimization.dp.factory.cost.SpotCostStrategy
          extended by edu.mit.ll.group43.surfaceoptimization.dp.factory.cost.OneGapSpotCostStrategy
              extended by edu.mit.ll.group43.surfaceoptimization.dp.factory.cost.OneGapForceSpotCostStrategy
                  extended by edu.mit.ll.group43.surfaceoptimization.dp.factory.cost.AllGapsForceSpotCostStrategy
Direct Known Subclasses:
LenientAllGapsForceSpotCostStrategy

public class AllGapsForceSpotCostStrategy
extends OneGapForceSpotCostStrategy

Solves for the shortest path through the CPS network by implementing the All Gaps Force heuristic. This algorithm considers all gaps in the projected takeoff sequence that the aircraft currently being scheduled could possibly fit into, with respect to its spot ready time and unimpeded taxi time. These gaps may be "forced" to fit the current aircraft in them, which involves rescheduling the last aircraft of the gap so that no runway delay is incurred. The spot release time for the current aircraft that minimizes the additional delay by forcing a gap or scheduling it to take off last is solved for.

Author:
William Hawkins

Constructor Summary
AllGapsForceSpotCostStrategy(int cps, MinimumSeparationCalculator<? extends WeightClass> calc)
           
 
Method Summary
 int adjustTakeOffs(java.util.ArrayList<Aircraft> takeOffSequence, int startIndex, int endIndex)
          Modifies the given takeoff sequence to not have any conflicts at the runway, and returns the delay caused by this.
 void clearBestFields()
          Initializes the fields that hold values associated with the current aircraft being placed.
 void clearCurrFields()
          Initializes the fields that hold values associated with the current predecessor node.
 void compareNormalApproach(java.util.ArrayList<Aircraft> normalSequence, int normalDelay, int normalRelease)
          Determines if the given "normal" sequence, which schedules the current aircraft to take off last, is better than any of the sequences that force gaps.
 void computeValues(Aircraft a, Aircraft b, Aircraft current, java.util.ArrayList<Aircraft> takeOffSequence)
          Considers what would happen if the current aircraft were scheduled to take off between aircraft a and b.
 int earliestGap(java.util.ArrayList<Aircraft> releaseSequence, Aircraft current, int limit)
          Returns the index of the earliest aircraft it should look at "forcing" (i.e.
 int getEdgeWeight(NetworkEdge edge)
          Returns the additional delay associated with scheduling the current aircraft according to the All Gaps Force heuristic algorithm for the given edge in the network.
 int normalSafePrevTimeBound(java.util.ArrayList<Aircraft> releases, Aircraft current)
          Calculates the "predecessor bound" that should be used when scheduling the current aircraft to take off last in the current projected takeoff sequence.
 void scheduleCurrentAircraft(SmartCPSNetworkNode node, Aircraft current)
          Solves for the best schedule where the current aircraft's optimal spot release time is the most recently calculated, when following the previous node currently being considered.
 void setBestReleaseSequences(SmartCPSNetworkNode node)
          Sets the best release sequence of the given node.
 void setOptimalValues(NetworkEdge edge, int distance)
          Sets the optimal values for the current node and its last aircraft, and saves the spot release sequence that corresponds to those values to the node.
 java.util.ArrayList<Aircraft> sortedReleases(java.util.ArrayList<Aircraft> sequence)
          Returns an ArrayList of cloned aircraft from the given sequence, sorted in order of their optimal spot release time.
 void updateBestValues()
          Checks the best values found for the current previous node being looked at against the best values found among all previous nodes for the current node whose last aircraft is being scheduled.
 void updateCurrValues(java.util.ArrayList<Aircraft> sequence, int totalDelay, int release)
          Updates the best sequence found so far for this node and its associated values if the given sequence is valid and incurs less delay than the one currently saved, or if there is no currently saved best sequence for this node.
 void updateScheduleForSequence(java.util.ArrayList<Aircraft> releases, Aircraft current)
          Solves for the best schedule where the current aircraft's optimal spot release time is the most recently calculated, when following the previous node currently being considered, when basing this optimal schedule on the one given.
 
Methods inherited from class edu.mit.ll.group43.surfaceoptimization.dp.factory.cost.OneGapForceSpotCostStrategy
initializeFirstStage, safePrevTimeBound, safePrevTimeBound, sortedAlphasSoFar, sortedAlphasSoFar
 
Methods inherited from class edu.mit.ll.group43.surfaceoptimization.dp.factory.cost.OneGapSpotCostStrategy
canFitBefore, earliestRelease, earliestReleaseAfter, earliestReleaseAfter, earliestReleaseBetween, earliestReleaseBetween
 
Methods inherited from class edu.mit.ll.group43.surfaceoptimization.dp.factory.cost.SpotCostStrategy
earliestRelease, earliestRelease
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

AllGapsForceSpotCostStrategy

public AllGapsForceSpotCostStrategy(int cps,
                                    MinimumSeparationCalculator<? extends WeightClass> calc)
Method Detail

setOptimalValues

public void setOptimalValues(NetworkEdge edge,
                             int distance)
Sets the optimal values for the current node and its last aircraft, and saves the spot release sequence that corresponds to those values to the node.

Overrides:
setOptimalValues in class OneGapForceSpotCostStrategy
Parameters:
edge -
distance -

setBestReleaseSequences

public void setBestReleaseSequences(SmartCPSNetworkNode node)
Sets the best release sequence of the given node.

Parameters:
node -

clearBestFields

public void clearBestFields()
Initializes the fields that hold values associated with the current aircraft being placed.


clearCurrFields

public void clearCurrFields()
Initializes the fields that hold values associated with the current predecessor node.


sortedReleases

public java.util.ArrayList<Aircraft> sortedReleases(java.util.ArrayList<Aircraft> sequence)
Returns an ArrayList of cloned aircraft from the given sequence, sorted in order of their optimal spot release time.

Parameters:
sequence -
Returns:

adjustTakeOffs

public int adjustTakeOffs(java.util.ArrayList<Aircraft> takeOffSequence,
                          int startIndex,
                          int endIndex)
Modifies the given takeoff sequence to not have any conflicts at the runway, and returns the delay caused by this. Only looks at the aircraft between and including the given start and end indexes.

Parameters:
takeOffSequence -
startIndex -
endIndex -
Returns:

computeValues

public void computeValues(Aircraft a,
                          Aircraft b,
                          Aircraft current,
                          java.util.ArrayList<Aircraft> takeOffSequence)
Considers what would happen if the current aircraft were scheduled to take off between aircraft a and b. Updates the best sequence found so far if the resulting sequence is valid and incurs less delay than the one currently saved as the best sequence. The takeoff sequence should be cloned, and a and b should be clones from that sequence. The presence of the sequence allows for other aircraft to be adjusted if necessary based on b's movement. The current aircraft should also be a clone.

Parameters:
a -
b -
current -
takeOffSequence -

updateCurrValues

public void updateCurrValues(java.util.ArrayList<Aircraft> sequence,
                             int totalDelay,
                             int release)
Updates the best sequence found so far for this node and its associated values if the given sequence is valid and incurs less delay than the one currently saved, or if there is no currently saved best sequence for this node.

Parameters:
sequence -
totalDelay -
release -

earliestGap

public int earliestGap(java.util.ArrayList<Aircraft> releaseSequence,
                       Aircraft current,
                       int limit)
Returns the index of the earliest aircraft it should look at "forcing" (i.e. the earliest "b").

Parameters:
releaseSequence -
current -
limit -
Returns:

compareNormalApproach

public void compareNormalApproach(java.util.ArrayList<Aircraft> normalSequence,
                                  int normalDelay,
                                  int normalRelease)
Determines if the given "normal" sequence, which schedules the current aircraft to take off last, is better than any of the sequences that force gaps. If it is, then the best sequence for the current previous node being looked at is updated, along with its associated values.

Parameters:
normalSequence -
normalDelay -
normalRelease -

scheduleCurrentAircraft

public void scheduleCurrentAircraft(SmartCPSNetworkNode node,
                                    Aircraft current)
Solves for the best schedule where the current aircraft's optimal spot release time is the most recently calculated, when following the previous node currently being considered.

Parameters:
node -
current -

normalSafePrevTimeBound

public int normalSafePrevTimeBound(java.util.ArrayList<Aircraft> releases,
                                   Aircraft current)
Calculates the "predecessor bound" that should be used when scheduling the current aircraft to take off last in the current projected takeoff sequence.

Parameters:
releases -
current -
Returns:

updateScheduleForSequence

public void updateScheduleForSequence(java.util.ArrayList<Aircraft> releases,
                                      Aircraft current)
Solves for the best schedule where the current aircraft's optimal spot release time is the most recently calculated, when following the previous node currently being considered, when basing this optimal schedule on the one given.

Parameters:
releases -
current -

updateBestValues

public void updateBestValues()
Checks the best values found for the current previous node being looked at against the best values found among all previous nodes for the current node whose last aircraft is being scheduled. Updates the best values if the values for the current previous node are better.


getEdgeWeight

public int getEdgeWeight(NetworkEdge edge)
Returns the additional delay associated with scheduling the current aircraft according to the All Gaps Force heuristic algorithm for the given edge in the network.

Overrides:
getEdgeWeight in class OneGapForceSpotCostStrategy
Parameters:
edge -
Returns: