Home > Research > Publications & Outputs > Approximation methods for large-scale spatial q...

Electronic data

  • boyaci2015151 postprint

    Rights statement: The final, definitive version of this article has been published in the Journal, Transportation Research Part B: Methodological 74, 2015, © ELSEVIER.

    Accepted author manuscript, 8.27 MB, PDF document

    Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License

Links

Text available via DOI:

View graph of relations

Approximation methods for large-scale spatial queueing systems

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published

Standard

Approximation methods for large-scale spatial queueing systems. / Boyaci, Burak; Geroliminis, Nikolas.
In: Transportation Research Part B: Methodological, Vol. 74, 01.04.2015, p. 151-181.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

Boyaci, B & Geroliminis, N 2015, 'Approximation methods for large-scale spatial queueing systems', Transportation Research Part B: Methodological, vol. 74, pp. 151-181. https://doi.org/10.1016/j.trb.2014.12.011

APA

Boyaci, B., & Geroliminis, N. (2015). Approximation methods for large-scale spatial queueing systems. Transportation Research Part B: Methodological, 74, 151-181. https://doi.org/10.1016/j.trb.2014.12.011

Vancouver

Boyaci B, Geroliminis N. Approximation methods for large-scale spatial queueing systems. Transportation Research Part B: Methodological. 2015 Apr 1;74:151-181. Epub 2015 Feb 24. doi: 10.1016/j.trb.2014.12.011

Author

Boyaci, Burak ; Geroliminis, Nikolas. / Approximation methods for large-scale spatial queueing systems. In: Transportation Research Part B: Methodological. 2015 ; Vol. 74. pp. 151-181.

Bibtex

@article{7c864230fbad43b4a326f0b5649a2889,
title = "Approximation methods for large-scale spatial queueing systems",
abstract = "Different than the conventional queueing systems, in spatial queueing systems (SQS) the service rate for each customer-server pairs differs and the server that intervenes for a specific customer is not known a priori, depending on the availability of servers at the moment a request was made. These features make the SQS computationally expensive (almost intractable for large scale) but at the same time more suitable for real-life problems with high reliability expectations. Emergency response and on-demand transportation systems are two similar systems that can be modeled with the SQS.In this research, we aim to solve facility location problems as SQS with stochastic demand and service time. The stochasticity concerned here is temporal and spatial, that emerges from the uncertainty in the demand and service time. In order to tackle this problem Larson (1974)'s 2n hypercube queueing model (HQM) is extended to 3n HQM. In this model, there are two different possible service types for each server: (i) service for locations in the proximity of a server (area of responsibility) and (ii) service for other locations where the first responsible server is busy during this event. In addition, to decrease the dimension of the problem, which is intractable due to their size, a new 3n aggregate hypercube queueing model (AHQM) is developed that treats group of servers (bins) in a similar manner by considering interactions among bins. An efficient graph partitioning algorithm is proposed to cluster servers in groups with an objective to minimize the interactions among groups. Both exact and approximate approaches are integrated inside two optimization methods (i.e. variable neighborhood search and simulated annealing) to find server locations that improve system performance. Computational experiments showed that both models are applicable to use inside optimization algorithms to find good server locations and to improve system performance measures of SQS.",
keywords = "spatial queues, hypercube queueing models, emergency response, approximation algorithms",
author = "Burak Boyaci and Nikolas Geroliminis",
note = "The final, definitive version of this article has been published in the Journal, Transportation Research Part B: Methodological 74, 2015, {\textcopyright} ELSEVIER. ",
year = "2015",
month = apr,
day = "1",
doi = "10.1016/j.trb.2014.12.011",
language = "English",
volume = "74",
pages = "151--181",
journal = "Transportation Research Part B: Methodological",
issn = "0191-2615",
publisher = "PERGAMON-ELSEVIER SCIENCE LTD",

}

RIS

TY - JOUR

T1 - Approximation methods for large-scale spatial queueing systems

AU - Boyaci, Burak

AU - Geroliminis, Nikolas

N1 - The final, definitive version of this article has been published in the Journal, Transportation Research Part B: Methodological 74, 2015, © ELSEVIER.

PY - 2015/4/1

Y1 - 2015/4/1

N2 - Different than the conventional queueing systems, in spatial queueing systems (SQS) the service rate for each customer-server pairs differs and the server that intervenes for a specific customer is not known a priori, depending on the availability of servers at the moment a request was made. These features make the SQS computationally expensive (almost intractable for large scale) but at the same time more suitable for real-life problems with high reliability expectations. Emergency response and on-demand transportation systems are two similar systems that can be modeled with the SQS.In this research, we aim to solve facility location problems as SQS with stochastic demand and service time. The stochasticity concerned here is temporal and spatial, that emerges from the uncertainty in the demand and service time. In order to tackle this problem Larson (1974)'s 2n hypercube queueing model (HQM) is extended to 3n HQM. In this model, there are two different possible service types for each server: (i) service for locations in the proximity of a server (area of responsibility) and (ii) service for other locations where the first responsible server is busy during this event. In addition, to decrease the dimension of the problem, which is intractable due to their size, a new 3n aggregate hypercube queueing model (AHQM) is developed that treats group of servers (bins) in a similar manner by considering interactions among bins. An efficient graph partitioning algorithm is proposed to cluster servers in groups with an objective to minimize the interactions among groups. Both exact and approximate approaches are integrated inside two optimization methods (i.e. variable neighborhood search and simulated annealing) to find server locations that improve system performance. Computational experiments showed that both models are applicable to use inside optimization algorithms to find good server locations and to improve system performance measures of SQS.

AB - Different than the conventional queueing systems, in spatial queueing systems (SQS) the service rate for each customer-server pairs differs and the server that intervenes for a specific customer is not known a priori, depending on the availability of servers at the moment a request was made. These features make the SQS computationally expensive (almost intractable for large scale) but at the same time more suitable for real-life problems with high reliability expectations. Emergency response and on-demand transportation systems are two similar systems that can be modeled with the SQS.In this research, we aim to solve facility location problems as SQS with stochastic demand and service time. The stochasticity concerned here is temporal and spatial, that emerges from the uncertainty in the demand and service time. In order to tackle this problem Larson (1974)'s 2n hypercube queueing model (HQM) is extended to 3n HQM. In this model, there are two different possible service types for each server: (i) service for locations in the proximity of a server (area of responsibility) and (ii) service for other locations where the first responsible server is busy during this event. In addition, to decrease the dimension of the problem, which is intractable due to their size, a new 3n aggregate hypercube queueing model (AHQM) is developed that treats group of servers (bins) in a similar manner by considering interactions among bins. An efficient graph partitioning algorithm is proposed to cluster servers in groups with an objective to minimize the interactions among groups. Both exact and approximate approaches are integrated inside two optimization methods (i.e. variable neighborhood search and simulated annealing) to find server locations that improve system performance. Computational experiments showed that both models are applicable to use inside optimization algorithms to find good server locations and to improve system performance measures of SQS.

KW - spatial queues

KW - hypercube queueing models

KW - emergency response

KW - approximation algorithms

U2 - 10.1016/j.trb.2014.12.011

DO - 10.1016/j.trb.2014.12.011

M3 - Journal article

VL - 74

SP - 151

EP - 181

JO - Transportation Research Part B: Methodological

JF - Transportation Research Part B: Methodological

SN - 0191-2615

ER -