TY - CONF

T1 - Extended Hypercube Models for Large Scale Spatial Queueing Systems

AU - Boyacı, Burak

AU - Geroliminis, Nikolas

PY - 2012/1/22

Y1 - 2012/1/22

N2 - Different than the conventional queueing systems, in spatial queues, servers travel to the customers and provide service on the scene. This property makes them applicable to emergency response (e.g. ambulances, police, fire brigades) and on-demand transportation systems (e.g. shuttle bus services, paratransit, taxis). The difference between the spatial queues and conventional queueing systems is various types of customers and servers and different service rates for different customer-server pairs. For the Markovian arrival and service characteristics, one of the methods to find system performance measures is to model and calculate steady state probability of the Markov chain for the hypercube queueing model.One of the obstacles on the way to apply hypercube queueing models to real life problems is the size of the problem; it grows exponentially with the number of servers and a linear system with exponential number of variables should be solved for each instance. In this research, in order to increase scalability of the problem, we propose two new models. In addition to that, we modeled the problem by using Monte Carlo simulation and tested the convergence and stability properties of the simulation results and compare them with stationary distributions. In the final part, a mixed integer linear programming formulation is given for optimal server configuration with different objectives improving different performance measures. As a future work, we are planning to use the optimal solutions of this formulation to evaluate different dispatching policies.

AB - Different than the conventional queueing systems, in spatial queues, servers travel to the customers and provide service on the scene. This property makes them applicable to emergency response (e.g. ambulances, police, fire brigades) and on-demand transportation systems (e.g. shuttle bus services, paratransit, taxis). The difference between the spatial queues and conventional queueing systems is various types of customers and servers and different service rates for different customer-server pairs. For the Markovian arrival and service characteristics, one of the methods to find system performance measures is to model and calculate steady state probability of the Markov chain for the hypercube queueing model.One of the obstacles on the way to apply hypercube queueing models to real life problems is the size of the problem; it grows exponentially with the number of servers and a linear system with exponential number of variables should be solved for each instance. In this research, in order to increase scalability of the problem, we propose two new models. In addition to that, we modeled the problem by using Monte Carlo simulation and tested the convergence and stability properties of the simulation results and compare them with stationary distributions. In the final part, a mixed integer linear programming formulation is given for optimal server configuration with different objectives improving different performance measures. As a future work, we are planning to use the optimal solutions of this formulation to evaluate different dispatching policies.

UR - http://www.trb.org/AnnualMeeting/TRBAnnualMeetingOnline.aspx

M3 - Conference paper

T2 - 91st Annual Meeting of the Transportation Research Board

Y2 - 22 January 2012 through 26 January 2012

ER -