Simulation of waiting queues of planes in an airport using double ended queue

Hello All,
I have this Problem as an assignment :
An airport has two landing runways. When planes arrive near the airport,they will have to join one queue. A plane arriving near the airport at a random time Tarrival, will be instructed to join the queue and it might have to wait (remain airborne) in that landing queue a time Twait until one of the two runways becomes free and ready to receive it. If both runways become free at the same time, the first runway has the higher priority. Once a plane lands on the beginning of a runway, that runway becomes occupied for a fixed time Tlanding until the plane docks (This is the service time).
Use the DEQ template class you implemented in to develop a program to simulate
the airport queue operations with the objective of computing the average wait time in the landing queue.
Assume the following:
• The time (clock) unit is one minute
• A fixed simulation period Tmax
• The same fixed time Tlanding for both runways to complete landing.
• A random arrival time Tarrival with a fixed average inter-arrival time ∆T
• No plane will leave the queue until it lands.
You might start your simulation using a “standard run” with:
Tmax = 6 hours, Tlanding = 10 minutes, ∆T = 6 minutes
After that, you might investigate the effect of varying arrival rates to simulate prime and slack times of the day, or if the amount of time to complete landing is changed.

Actually, I don't know what to do or how it can be implemented, and i have implemented the DEQ class as follows:
Header file(.h)
// File: DEQ.h
// Linked List Double Ended Queue class definition
#ifndef DEQ_H
#define DEQ_H

template <class Type>

class DEQ
{
public:


DEQ(); // Constructor to Construct an empty DEQ
~DEQ(); // Destructor to Destroy DEQ
bool DEQisEmpty() const; // Test if DEQ is empty
void Add_Front(Type); // Add an element at the front
void Add_Rear(Type); // Add an element at the rear
void Remove_Front(); // Remove the element at the front
void Remove_Rear(); // Remove the element at the rear
Type View_Front(); // Retrieve the front element without removal
Type View_Rear(); // Retrieve the rear element without removal
int DEQ_Length() const; // Retrieve number of elements in the DEQ
void Display_DEQ(); // Display all elements of DEQ

private:
// Node Class
class node
{
public:
Type e; // DEQ element
node *next; // pointer to next node
}; // end of class node declaration

typedef node * NodePointer;

NodePointer front, rear; // Pointers
int count; // length

};

#endif // DEQ_H

The implementation file (.cpp)
// File:DEQ.cpp
// Linked List Double Ended Queue Class implementation

#include <iostream>
#include "DEQ.h"
using namespace std;

// Class Constructor.
template <class Type>
DEQ<Type>::DEQ()
{
front = NULL; rear = NULL; count = 0;
}

// Class Destructor.
template <class Type>
DEQ<Type>::~DEQ()
{
NodePointer cursor;
while (front != NULL)
{
cursor = front;
front = front->next;
delete cursor;
}
}


// Test if DEQ is empty, return True if DEQ is empty.
template <class Type>
bool DEQ<Type>::DEQisEmpty() const
{
return (count == 0);
}

// Add a node with data (v) at the front of the DEQ.
// the new node becomes the front node.
template <class Type>
void DEQ<Type>::Add_Front(Type v)
{
NodePointer pnew = new node;
pnew->e = v;
if (DEQisEmpty())
{
front = pnew;
rear = pnew;
pnew->next = NULL;
}
else
{
pnew->next = front;
front = pnew;
}
count++;
}
// Add a node with data (v) at the rear of the DEQ.
// the new node becomes the rear node.
template <class Type>
void DEQ<Type>::Add_Rear(Type v)
{
NodePointer pnew = new node;
pnew->e = v;
pnew->next = NULL;
if (DEQisEmpty())
{
front = pnew;
rear = pnew;
}
else
{
rear->next = pnew;
rear = pnew;
}
count++;
}

// Remove the element at the front of the DEQ.
// Next node becomes front node.
template <class Type>
void DEQ<Type>::Remove_Front( )
{
NodePointer cursor;
if (DEQisEmpty())
cout << "Double Ended Queue is Empty" << endl;
else
{
cursor = front;
front = front->next;
delete cursor;
count--;
}
}

// Remove the element at the rear of the DEQ.
// Previous node becomes rear node.
template <class Type>
void DEQ<Type>::Remove_Rear()
{
NodePointer cursor, prev = NULL;
if (DEQisEmpty())
cout << "Double Ended Queue is Empty" << endl;
else
{
cursor = front;
while (cursor->next != NULL)
{
prev = cursor;
cursor = cursor->next;
}
prev->next = NULL;
rear = prev;
delete cursor;
count--;
}
}

// Retrieve the front element without removal.
template <class Type>
Type DEQ<Type>::View_Front( )
{
if (DEQisEmpty())
{
cout << "Double Ended Queue is Empty" << endl;
return -1;
}
else
return (front->e);
}

// Retrieve the rear element without removal.
template <class Type>
Type DEQ<Type>::View_Rear()
{
if (DEQisEmpty())
{
cout << "Double Ended Queue is Empty" << endl;
return -1;
}
else
return (rear->e);
}

// DEQ Length
template <class Type>
int DEQ<Type>::DEQ_Length() const
{
return count;
}

// Display all elements of DEQ
template<class Type>
void DEQ<Type>::Display_DEQ()
{
NodePointer cursor = front;
if (DEQisEmpty())
cout << "Double Ended Queue is Empty" << endl;
else
{
cout << "The elements of the Double Ended Queue are:\t";
while (cursor!= NULL)
{
cout << cursor->e << " ";
cursor = cursor->next;
} // end while
cout << endl;
}
}
Disclaimer: you indicate no problem with your DEQ class, so I didn’t read through it.

It may help to draw pictures:
Arriving airplanes

  ^__A_      ------------------------
     V        ^__A_   ^__A_   ^__A_
                 V       V       V           Airplanes leaving the queue to land
             ------------------------     ^__A_
                Airplanes in Queue          V
                                                    ==============================

Other information associated with each airplane:
  • Time the airplane arrives (and enters the queue)
  • Time the airplane begins to land (and exits the queue)

Needed:
  • Random arrival time, normal distribution spanning ∆T minutes
  • Time it takes to land ("service time"), TLanding
  • Simulation time: Tmax

Queue/dequeue:
  • Planes queue when they arrive
  • Planes dequeue when they begin to land


Hypothesis:
  Given two runways, you should be able to land 2 airplanes every TLanding minutes.
  So then, to avoid congestion in the sky (buildup in the queue), you should ideally have an
  airplane arriving every (TLanding / 2) minutes, on average.

  More than that and the queue will fill up.
  Less than that and the queue will empty.


Hints:

You’ll need a running average. The average is (sum of time each airplane spent in queue) / (number of airplanes that went through the queue). To keep a running average, save that division for last. Hence, you will need two pieces of information to update each time you dequeue a plane.

For the simulation, you will need to keep track of the time == the number of minutes that have passed since the beginning of the simulation.

Do it in two passes:

  1. arrive and enqueue a bunch of planes
     (generate a whole bunch of ∆T (and enqueue) while their sum < Tmax)

  2. land all the planes in the queue
     (update the current time to the next available runway time,
      dequeue a plane and update the running average,
      reset the runway’s next available time to the (current time + TLanding))
     while current time < Tmax

Compute the average and display it to the user.
Your assignment does not give instructions on what to display to the user, but the average is minimal. You might also want to display the number of airplanes still in the queue at the end of the Tmax time.

Check that various runs work as hypothesized above.


Hope this helps.
There are some problems with DEQ:
Remove_Front() needs to update rear if you remove the last item.
Remove_Rear() will probably crash when removing the last item. It also needs to update front in that case.
You might want Vew_Front and View_Rear to return a reference rather than a copy of the item.
Addendum: variance

Also not stated with your homework was how to compute the “fixed average inter-arrival time ∆T”, which requires a bit of math you may not be familiar with, or even if you are, how to achieve it in C++.

What your professor is saying is that he wants the average arrival time to be ∆T, but he also wants it randomized. This is done using a Normal Distribution, which is statistics. (Yep. Hopefully you had a good Stat 1 teacher, because a crappy one leaves you with nothing sensible.)

To compute random values from a normal distribution you need the mean (which is your “fixed average inter-arrival time ∆T” — remember, “mean” is another word for “average”), and you need a variance.

The variance is how far off the average you are willing to accept. In plain English, what is the most time that will pass before another plane arrives?

If you want to accept the full Tmax time, you can do that. If you are at a busy airport, you might want to drop it down to 10-15 minutes or so. Heck, you can use the ∆T. Whatever it is, you have to choose one. 
For bonus points (with me, at least), you could totally randomize the variance between Tdelta and Tmax. :o]


Next, comes the randomization part. C++ makes this particularly easy. You will first need the basics:

1
2
3
#include <chrono>
#include <cmath>
#include <random> 
1
2
3
4
int main()
{
  // Times dictated by the assignment
  double TMax, TDelta, TLanding;

Get TMax, TDelta, and TLanding from the user. Then create your Normal Distribution:
1
2
3
4
5
  // Our random number generator
  std::mt19937 rng( std::chrono::high_resolution_clock::now().time_since_epoch().count() );
  
  // Our normal distribution, adjusted over the times input above
  std::normal_distribution<double> nd( TDelta, std::sqrt(VARIANCE) );

The text VARIANCE should be replaced with whatever you think is a good value. Again, you could easily replace it with TMax or TDelta or 15 or whatever seems a good amount of time.

Notice that if you replace it with 0 there will be no variance at all, and all planes will arrive exactly five minutes apart. And your simulation will become very boring, and you’ll likely get a poor grade.

In any case, now that you have all that, you can use it!
1
2
3
    // Now, inside a loop somewhere, whenever you want a ∆T
    // (time since the last plane arrived that another plane arrives)
    double arrival_delta = nd( rng );


Well, that’s it!
Hope this helps.
Spread the word (so your classmates aren’t lost on this detail either.)

[edit]
One more thing to note — any variance > ∆T means that the next airplane may arrive before the last airplane... When enqueuing that doesn’t really matter. Just in case any mathies stop by...
[/code]

[edit 2]
I made a mistake with the std::normal_distribution()’s arguments: the second argument is the standard deviation, which is the square root of the variance.
Sorry. Fixed above.

All this said, you COULD just grab a random number in the range 0..12 (inclusive) to get a ∆T of 6 minutes. See the relationship?
[/edit]
Last edited on
Thanks for your help.
I want to know what functions should be implemented to handle the problem.
Please i need a help and guide to proceed with the implementation.
Last edited on
@dhayden
Thanks for your notes. I have resolved the stated issues.
void DEQ<Type>::Remove_Rear()
{
NodePointer cursor = front, prev = NULL;
if (DEQisEmpty())
{
cout << "Double Ended Queue is Empty" << endl;
}

if (count == 1)
{
front = rear = NULL;
delete (cursor);
}
else
{
while (cursor->next != NULL)
{
prev = cursor;
cursor = cursor->next;
}
prev->next = NULL;
rear = prev;
delete cursor;
}
count--;
}

void DEQ<Type>::Remove_Front( )
{
NodePointer cursor = front;
if (DEQisEmpty())
{
cout << "Double Ended Queue is Empty" << endl;
}

if (count == 1)
{
front = rear = NULL;
delete (cursor);
}
else
{
front = front->next;
delete cursor;
}
count--;
}
Implementation is pretty straight forward. So far, I have practically given you this much:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <chrono>
#include <cmath>
#include <iostream>
#include <random>

#include "DEQ.h"

int main( int argc, char** argv )
try
{
  // Times dictated by the assignment
  double TMax, TDelta, TLanding;
  std::cout << "Please enter TMax, TLanding, and ∆T: ";
  std::cout.clear();
  std::cin >> TMax >> TLanding >> TDelta;

  // Let's choose a variance that will keep us from having airplanes arrive at negative differences
  double TVariance = TDelta / 2;

  // The random number generator
  std::mt19937 rng( std::chrono::high_resolution_clock::now().time_since_epoch().count() );
  
  // The normal distribution, adjusted over the times input above
  std::normal_distribution<double> nd( TDelta, std::sqrt( TVariance ) );

  // Track the RUNNING AVERAGE amount of time spent waiting in queue
  double total_time_spent_waiting     = 0;
  int    number_of_planes_that_landed = 0;

So, what next?

Since this is a simulation, you have to have something which tracks airplanes arriving and landing.

That you are required to use your DEQ class is a pretty big hint.

30
31
  // A queue to add planes to.
  DEQ <double> what_am_i;

The question you need to answer is: What is it that we are tracking with the queue?
I have already given you a good idea of what information is being tracked with each airplane above (http://www.cplusplus.com/forum/general/250056/#msg1101238).
 


The next step would be to fill up your queue with arriving airplanes. Start at (time) T = 0; stop when airplanes start arriving after T = TMax.

Hint: do this step first. Show your queue using your handy display_DEQ() function. Compile and play with your program to see what happens to the queue.


So, now you have a queue full of airplanes waiting to land. Rewind time back to T = 0 and start the second part of the simulation: landing the airplanes.

Let’s think about what it takes to dequeue and land an airplane. For what follows, let us make things extra simple (a good habit to get into) and assume that:
  • you only have a single runway
  • the runway is available at T == 0
  • once an airplane begins to land, the next time it is available is Tbegin-landing + TLanding

This means, of course, that you can immediately land the first airplane. The time the airplane dequeues and begins to land is: when the plane arrived! Right? (It cannot be T == 0, because the airplane had not arrived yet.)

So what is the earliest that the next airplane in the queue may land?

Hint: Figure out how to dequeue all the airplanes using only one runway. Again, make sure your program compiles. Run it and see what happens. Use cout to give yourself information about what is happening.


What next?
Each step takes working code you wrote and modifies it to slightly more advanced working code, which you can compile and play with. Next steps:

  • Figure out how to STOP dequeuing airplanes when the next available time to land an airplane exceeds TMax.
  • Figure out how to use two runways.

Final hints:
  • You do not need to put stuff in functions; everything goes in main()
  • Make efforts! This requires some thinking, but it is straight-forward enough that you can do it!

Good luck!
As a final note, here’s my run of the program, with extra commentary, using

    TMax = 120;     TLanding = 10;     ∆T = 6;     TVariance = 6/2

C:\Users\Michael\Programming\cpp\airplane_queue> a
Please enter TMax, TLanding, and ∆T: 120 10 6

(Planes arriving)
    9.6748 (delta =   9.6748)
   15.4919 (delta =   5.8171)
   17.7351 (delta =   2.2432)
   20.6046 (delta =   2.8695)
   26.0590 (delta =   5.4544)
   31.0762 (delta =   5.0172)
   37.5640 (delta =   6.4878)
   44.7281 (delta =   7.1642)
   47.1156 (delta =   2.3875)
   48.0143 (delta =   0.8986)
   49.6988 (delta =   1.6845)
   58.2591 (delta =   8.5602)
   63.4989 (delta =   5.2398)
   70.9912 (delta =   7.4924)
   77.2502 (delta =   6.2590)
   82.5401 (delta =   5.2900)
   89.1397 (delta =   6.5996)
   96.6400 (delta =   7.5003)
  105.7093 (delta =   9.0693)
  111.9157 (delta =   6.2064)
  114.3308 (delta =   2.4151)

(Planes landing)
  Plane (arrived at   9.6748) landing at time =   9.6748
  Plane (arrived at  15.4919) landing at time =  15.4919
  Plane (arrived at  17.7351) landing at time =  19.6748
  Plane (arrived at  20.6046) landing at time =  25.4919
  Plane (arrived at  26.0590) landing at time =  29.6748
  Plane (arrived at  31.0762) landing at time =  35.4919
  Plane (arrived at  37.5640) landing at time =  39.6748
  Plane (arrived at  44.7281) landing at time =  45.4919
  Plane (arrived at  47.1156) landing at time =  49.6748
  Plane (arrived at  48.0143) landing at time =  55.4919
  Plane (arrived at  49.6988) landing at time =  59.6748
  Plane (arrived at  58.2591) landing at time =  65.4919
  Plane (arrived at  63.4989) landing at time =  69.6748
  Plane (arrived at  70.9912) landing at time =  75.4919
  Plane (arrived at  77.2502) landing at time =  79.6748
  Plane (arrived at  82.5401) landing at time =  85.4919
  Plane (arrived at  89.1397) landing at time =  89.6748
  Plane (arrived at  96.6400) landing at time =  96.6400
  Plane (arrived at 105.7093) landing at time = 105.7093
  Plane (arrived at 111.9157) landing at time = 111.9157
  Plane (arrived at 114.3308) landing at time = 115.7093

The average wait time for 21 airplanes is   2.9974.
There are still 0 planes waiting to land.

C:\Users\Michael\Programming\cpp\airplane_queue> _


Wait time is minimal, and we managed to clear the entire queue. This makes sense, because at the ability to land an airplane every five minutes, with airplanes arriving about one every six minutes, the only reason we should have any wait time is because two planes arrived less than five minutes apart.

When you test your program, try lowering the ∆T to 5 minutes. You should see similar results, right?

What would happen if you lowered the ∆T to 3 minutes? Would you expect the queue to be emptied by the time time is up?

What about if you increased the ∆T to 10 minutes? Would the queue empty?

How about if you play with the time it takes to land an airplane. Can you find a relationship between ∆T and TLanding? What is the ratio for equilibrium?


Hope this helps.
Really Thanks a lot. Your comment was too helpful for me.
I discussed my professor about the problem and he clarified some notes to go through.
I will implement the dedicated functions from the professor and back here again if i face any issues
Last edited on
Topic archived. No new replies allowed.