Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Queueing Theory

  1. Jul 25, 2012 #1
    Hi

    At the bus stop -normally distributed service times and Poisson arrivals of passengers.
    To which queuing model should I be oriented for making a simulation of bus stop work?
    Regards
     
  2. jcsd
  3. Jul 25, 2012 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I assume you're asking for a standard name, similar to M/M/1, M/D/1, M/G/1.
    But the service implied in those models is not the same as for bus arrivals. A bus will service (usually) the entire queue in one go. The difference between bus arrival time and schedule may be normally distributed (but typically not: a few a little early, with a long tail of late ones), but that's not the same as 'service time' in standard queueing models.
    I suggest you consider a scheduled bus time, the distribution of the actual bus arrival, what that means for the time since the preceding bus, and the consequent queue length distribution when the bus arrives.
     
  4. Jul 26, 2012 #3
    Thank you Haruspex that's exactly what I mean.
    By schedule bus should be every 4 minutes but actual bus arrival is normally distributed.
    That's why I cannot find myself in a single model for example M/G/1
    What do you suggest?
    Thank you
     
  5. Jul 26, 2012 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I suggest what I suggested before:
    - take time t0 as the scheduled time for a bus arrival;
    - obtain a distribution for the time between the preceding bus and the next bus. This is awkward since in principle (according to the assumption they're independent and Gaussian) they could be in reversed order. For now, hope that doesn't matter.
    - based on that interval length distribution, obtain a distribution for the size of the queue when the next bus arrives.
     
  6. Jul 26, 2012 #5
    Thx.

    Interval length distribution -normal distribution.

    That's where the pain begins to chose model :)

    regards
     
  7. Jul 26, 2012 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Let the individual bus arrival time discrepancy from schedule be N(0,σ). The interval distribution will be N(T,σ√2). But for the next step, you want the absolute value of the interval time, so this folds the distribution left of 0 over to the right. (If that gets too nasty we may be able to ignore it without going too far wrong in reasonable situations.)
    The probability of k user arrivals in time t is (λt)ke-λt/k!. So the prob of k in a given bus arrival interval is
    [itex]\int^{+\infty}_{-\infty}\frac{(λ|t|)^ke^{-λ|t|}}{k!}.dF(t) = \frac{1}{2\sigma\sqrt{\pi}}\int^{0}_{-\infty}\frac{(-λt)^ke^{λt}}{k!}.e^{-\frac{(t-T)^2}{4\sigma^2}}.dt + \frac{1}{2\sigma\sqrt{\pi}}\int^{+\infty}_{0}\frac{(λt)^ke^{-λt}}{k!}.e^{-\frac{(t-T)^2}{4\sigma^2}}.dt[/itex]
    Right now, that's as far I can get. Will think about it more.
    OTOH, I'm not sure if this is heading where you want to go. What is the actual problem to be solved?
     
  8. Jul 27, 2012 #7
    Thank you very much for your answer.
    Actually I am working on a model of bus stop work.
    I have studied real data and I have concluded for a normal distribution in bus service times
    and Poisson distribution for passenger arrivals.
    Making assumptions about independence just to keep as simple as possible I want to arrive in a simulation so I can make the difference between bus working by scheduled times (every 4 minutes) and bus working for real (with small delays) just as you prescribed on previous messages.
    Thank you for helping.
    Regards
     
  9. Jul 28, 2012 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    OK, so let's say σ << T, so we can overlook the fact that the bus interarrival time can go negative. The prob of k people in a given bus arrival interval is then
    [itex]\frac{1}{2\sigma\sqrt{\pi}}\int^{+\infty}_{-\infty}\frac{(λt)^ke^{-λt}}{k!}.e^{-\frac{(t-T)^2}{4\sigma^2}}.dt[/itex]
    By suitable change of variable, the integral can be massaged into the form
    [itex]I = \int^{+\infty}_{-\infty}(t+c)^ke^{-t^2}.dt[/itex]
    I think the best that can be done with that is to expand the binomial term as a sum.
    [itex]I_r = \left(\stackrel{k}{r}\right)\int^{+\infty}_{-\infty}t^rc^{k-r}e^{-t^2}.dt[/itex]
    Because of the range of integration, the terms with odd powers of t will vanish. A further change of variable, w = t2, then produces
    [itex]I_{2r} = \frac{1}{2}\left(\stackrel{k}{2r}\right) \int_{-\infty}^{+\infty}w^{r-\frac{1}{2}}c^{k-2r}e^{-w}.dw[/itex]
    which produces a gamma function on r.
    Does this help?
     
  10. Jul 30, 2012 #9
    Thank you very much.
    You are being so helpful and it is so nice for you thinking as quite possible bus headway normally distributed because everybody seems to think only about Poisson arrivals and forget about bus headway as a service time (composition of several processes not just arrival).
    Your argument of gamma function on r seems OK but maybe I am missing something on the way it brings to a known queuing model (smth like M/G/...) because I can see it as the model of arrival but combination with normal service time (for client group service)seems to miss in normal queueing literature.
    Every book has M/M/... but hey where is my kind of model :(
    Am I wrong on my way of trying to view on the model?
    Best regards
     
  11. Jul 30, 2012 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    As I said in my first reply, 'service time' in your scenario is a different concept from that in the standard models.
    In all the standard models:
    - a server serves one customer each service time;
    - the service time random variable is measured from customer arrival at front of queue, and has no memory of prior state of the server.
    In yours:
    - the server (a bus) serves the entire queue in one hit;
    - service time is driven by a schedule independently of customers.
    An opportunity for you to contribute to the nomenclature? M/S/1 (S for schedule) perhaps?
     
  12. Jul 31, 2012 #11

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I meant to add that in consequence the service time can never be negative, so never Gaussian.
     
  13. Jul 31, 2012 #12

    chiro

    User Avatar
    Science Advisor

    Hey Mark J.

    Are you familiar with the Bayesian way of probability/statistical inference? If not I recommend you check it out since you can experiment with a lot of different priors for your rate used in the Poisson, and this area has a lot of results that can help derive situations or find them numerically (even if they are super-super complicated).
     
  14. Jul 31, 2012 #13
    My measurement in real system (times of bus arrivals) are all positive of course but anyway after several tests normal distribution seems to fit better regarding inter arrivals (time difference between 2 sequent buses) .

    So suppose service time is all about this Gaussian distribution or I kind of misunderstand ???

    Regards
     
  15. Jul 31, 2012 #14
    Chiro thank you for your answer.

    Perhaps you can direct me to any case similar to mine where is used Bayesian way of probability/statistical inference mentioned by you?
    It would really help
    Regards
     
  16. Jul 31, 2012 #15

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I didn't understand that last sentence.
    Let me repeat: in the meaning of 'service time' in the standard models, Gaussian makes no sense; in the rather different meaning of service time in your scenario, it does make sense. I'm merely trying to explain why (a) you won't find a standard model that does what you want, and (b) why some you discuss this with might tell you your Gaussian model is wrong.
    I'm quite prepared to believe Gaussian works for your bus interarrival times. It really can be negative, because buses could get out of order. Where that case gets tricky is that the customers don't care about bus order - they'll take the first that comes along. But as long as this is rare it shouldn't have much effect on the results.
     
  17. Jul 31, 2012 #16
    Yes what you say fits perfectly my case.
    Thank you for making it more clear to me.
    Regards
     
  18. Jul 31, 2012 #17

    chiro

    User Avatar
    Science Advisor

    This is an actual post describing looking at a simulation in R:

    http://tolstoy.newcastle.edu.au/R/e2/help/07/01/9219.html

    Another search response from google:

    https://www.google.com.au/url?sa=t&...sg=AFQjCNHgg00JebYIuPho-S9jmu6gAjjQCw&cad=rja

    Also note that as haruspex pointed out, you can't have negative rates. What you should do is instead use something like a chi-square or a gamma prior and then do inference on this.

    Alternatively another thing you could do is restrict your PDF to the positive real line and double the value of the PDF since the PDF of a Normal is symmetric, this will maintain the behaviour of the PDF and still keep the PDF valid (i.e. integrates to 1).

    If you want this option, then you should use something like R and use a simulation to sample from your modified 'normal' (I suggest you look into the Gamma priors though) and then generate a posterior given this prior (again look at first link for an idea of how to do this in R).
     
  19. Jul 31, 2012 #18
    Thank you for the fast response.
    Seems interesting I will have a look at it.
    Regards
     
  20. Aug 2, 2012 #19
    Hi Haruspex,

    If M/S/1 (S for schedule) where S is every 4 minutes we got still that problem of group service for the clients which gets really nasty in terms of comparing models.
    It should be some methods of comparing these 2 models the real one and the scheduled one but in my readings still not finding some approach to that.That is what you mean by contribute to the nomenclature if I get it right.
    Regards
     
  21. Aug 2, 2012 #20

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Sorry, you've lost me. Which of these two models (real/scheduled) is the one we've been discussing (regular arrival with Gaussian error), and what is the other model?
    I was (half seriously) proposing M/S/n as (new) terminology for a class of models that includes yours. In general, it wouldn't have to be Gaussian error, but it would involve an underlying regular service which operates independently of the queue. Could elaborate it to M/SG/ (scheduled with Gaussian error), M/SD/ (scheduled with no error, i.e. deterministic), etc.
    I didn't think through the '/1' part though. Could have this mean the maximum number in the queue serviced by one service event, so yours would be, say, M/SG/∞.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Queueing Theory
Loading...