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 journalJournal articlepeer-review

Published
Close
<mark>Journal publication date</mark>1/04/2015
<mark>Journal</mark>Transportation Research Part B: Methodological
Volume74
Number of pages31
Pages (from-to)151-181
Publication StatusPublished
Early online date24/02/15
<mark>Original language</mark>English

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.

Bibliographic note

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