IDEAS home Printed from https://ideas.repec.org/a/spr/queues/v92y2019i3d10.1007_s11134-019-09614-1.html
   My bibliography  Save this article

An exact root-free method for the expected queue length for a class of discrete-time queueing systems

Author

Listed:
  • A. Oblakova

    (University of Twente)

  • A. Al Hanbali

    (King Fahd University of Petroleum and Minerals)

  • R. J. Boucherie

    (University of Twente)

  • J. C. W. Ommeren

    (University of Twente)

  • W. H. M. Zijm

    (University of Twente)

Abstract

For a class of discrete-time queueing systems, we present a new exact method of computing both the expectation and the distribution of the queue length. This class of systems includes the bulk-service queue and the fixed-cycle traffic-light (FCTL) queue, which is a basic model in traffic-control research and can be seen as a non-exhaustive time-limited polling system. Our method avoids finding the roots of the characteristic equation, which enhances both the reliability and the speed of the computations compared to the classical root-finding approach. We represent the queue-length expectation in an exact closed-form expression using a contour integral. We also introduce several realistic modifications of the FCTL model. For the FCTL model for a turning flow, we prove a decomposition result. This allows us to derive a bound on the difference between the bulk-service and FCTL expected queue lengths, which turns out to be small in most of the realistic cases.

Suggested Citation

  • A. Oblakova & A. Al Hanbali & R. J. Boucherie & J. C. W. Ommeren & W. H. M. Zijm, 2019. "An exact root-free method for the expected queue length for a class of discrete-time queueing systems," Queueing Systems: Theory and Applications, Springer, vol. 92(3), pages 257-292, August.
    • Handle: RePEc:spr:queues:v:92:y:2019:i:3:d:10.1007_s11134-019-09614-1
    DOI: 10.1007/s11134-019-09614-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11134-019-09614-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s11134-019-09614-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Neuts, Marcel F., 1984. "Matrix-analytic methods in queuing theory," European Journal of Operational Research, Elsevier, vol. 15(1), pages 2-12, January.
    2. M. S. van den Broek & J. S. H. van Leeuwaarden & I. J. B. F. Adan & O. J. Boxma, 2006. "Bounds and Approximations for the Fixed-Cycle Traffic-Light Queue," Transportation Science, INFORMS, vol. 40(4), pages 484-496, November.
    3. J. S. H. van Leeuwaarden, 2006. "Delay Analysis for the Fixed-Cycle Traffic-Light Queue," Transportation Science, INFORMS, vol. 40(2), pages 189-199, May.
    4. M. A. A. Boon & A. J. E. M. Janssen & J. S. H. Leeuwaarden & R. W. Timmerman, 2019. "Pollaczek contour integrals for the fixed-cycle traffic-light queue," Queueing Systems: Theory and Applications, Springer, vol. 91(1), pages 89-111, February.
    5. Ahmad Hanbali & Roland Haan & Richard Boucherie & Jan-Kees Ommeren, 2012. "Time-limited polling systems with batch arrivals and phase-type service times," Annals of Operations Research, Springer, vol. 198(1), pages 57-82, September.
    6. A. J. E. M. Janssen & J. S. H. Van Leeuwaarden, 2008. "Back to the roots of the M/D/s queue and the works of Erlang, Crommelin and Pollaczek," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 62(3), pages 299-313, August.
    7. J. N. Darroch & G. F. Newell & R. W. J. Morris, 1964. "Queues for a Vehicle-Actuated Traffic Light," Operations Research, INFORMS, vol. 12(6), pages 882-895, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Boon, Marko & Janssen, Guido & van Leeuwaarden, Johan & Timmerman, Rik, 2023. "Optimal capacity allocation for heavy-traffic fixed-cycle traffic-light queues and intersections," Transportation Research Part B: Methodological, Elsevier, vol. 167(C), pages 79-98.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. M. A. A. Boon & A. J. E. M. Janssen & J. S. H. Leeuwaarden & R. W. Timmerman, 2019. "Pollaczek contour integrals for the fixed-cycle traffic-light queue," Queueing Systems: Theory and Applications, Springer, vol. 91(1), pages 89-111, February.
    2. Yang, Qiaoli & Shi, Zhongke & Yu, Shaowei & Zhou, Jie, 2018. "Analytical evaluation of the use of left-turn phasing for single left-turn lane only," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 266-303.
    3. Boon, Marko A.A. & van Leeuwaarden, Johan S.H., 2018. "Networks of fixed-cycle intersections," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 254-271.
    4. Gao, Yuhong & Qu, Zhaowei & Song, Xianmin & Yun, Zhenyu & Xia, Yingji, 2021. "A novel relationship model between signal timing, queue length and travel speed," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 583(C).
    5. Yang, Qiaoli & Shi, Zhongke, 2018. "Effects of the design of waiting areas on the dynamic behavior of queues at signalized intersections," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 509(C), pages 181-195.
    6. António Pacheco & Maria Lurdes Simões Simões & Paula Milheiro-Oliveira, 2017. "Queues with Server Vacations as a Model for Pretimed Signalized Urban Traffic," Transportation Science, INFORMS, vol. 51(3), pages 841-851, August.
    7. Hofleitner, Aude & Herring, Ryan & Bayen, Alexandre, 2012. "Arterial travel time forecast with streaming data: A hybrid approach of flow modeling and machine learning," Transportation Research Part B: Methodological, Elsevier, vol. 46(9), pages 1097-1122.
    8. Comert, Gurcan, 2016. "Queue length estimation from probe vehicles at isolated intersections: Estimators for primary parameters," European Journal of Operational Research, Elsevier, vol. 252(2), pages 502-521.
    9. Yang, Qiaoli & Shi, Zhongke, 2021. "The queue dynamics of protected/permissive left turns at pre-timed signalized intersections," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 562(C).
    10. Comert, Gurcan, 2013. "Effect of stop line detection in queue length estimation at traffic signals from probe vehicles data," European Journal of Operational Research, Elsevier, vol. 226(1), pages 67-76.
    11. Boon, Marko & Janssen, Guido & van Leeuwaarden, Johan & Timmerman, Rik, 2023. "Optimal capacity allocation for heavy-traffic fixed-cycle traffic-light queues and intersections," Transportation Research Part B: Methodological, Elsevier, vol. 167(C), pages 79-98.
    12. Arnaud Devos & Joris Walraevens & Herwig Bruneel, 2024. "Analysis of A Two-queue Discrete-time Model with Random Alternating Service Under High Occupancy in One Queue," Methodology and Computing in Applied Probability, Springer, vol. 26(4), pages 1-21, December.
    13. Comert, Gurcan & Cetin, Mecit, 2009. "Queue length estimation from probe vehicle location and the impacts of sample size," European Journal of Operational Research, Elsevier, vol. 197(1), pages 196-202, August.
    14. Pedro Cesar Lopes Gerum & Andrew Reed Benton & Melike Baykal-Gürsoy, 2019. "Traffic density on corridors subject to incidents: models for long-term congestion management," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 795-831, December.
    15. Herwig Bruneel & Arnaud Devos, 2024. "Explicit Solutions for Coupled Parallel Queues," Mathematics, MDPI, vol. 12(15), pages 1-31, July.
    16. Britt W. J. Mathijsen & A. J. E. M. Janssen & Johan S. H. Leeuwaarden & Bert Zwart, 2018. "Robust heavy-traffic approximations for service systems facing overdispersed demand," Queueing Systems: Theory and Applications, Springer, vol. 90(3), pages 257-289, December.
    17. Recker, Will & Zhenhg, Xing & Chu, Lianyu, 2010. "Development of an Adaptive Corridor Traffic Control Model," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt3tx5b17h, Institute of Transportation Studies, UC Berkeley.
    18. Vladimir Vishnevsky & Olga Semenova, 2021. "Polling Systems and Their Application to Telecommunication Networks," Mathematics, MDPI, vol. 9(2), pages 1-30, January.
    19. Recker, Will, 2008. "Development of an Adaptive Corridor Traffic Control Model," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt1sq7049f, Institute of Transportation Studies, UC Berkeley.
    20. Varga, Balázs & Tettamanti, Tamás & Kulcsár, Balázs & Qu, Xiaobo, 2020. "Public transport trajectory planning with probabilistic guarantees," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 81-101.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:queues:v:92:y:2019:i:3:d:10.1007_s11134-019-09614-1. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.