User equilibria for a parallel queueing system with state dependent routing

Abstract

Consider a system of two queues in parallel, one of which is a a <...|M|1 single-server infinite capacity queue, and the other a a <...|G ((N))|a batch service queue. A stream of general arrivals choose which queue to join, after observing the current state of the system, and so as to minimize their own expected delay. We show that a unique user equilibrium (user optimal policy) exists and that it possesses various monotonicity properties, using sample path and coupling arguments. This is a very simplified model of a transportation network with a choice of private and public modes of transport. Under probabilistic routing (which is equivalent to the assumption that users have knowledge only of the mean delays on routes), the network may exhibit the Downs-Thomson paradox observed in transportation networks with expected delay increasing as the capacity of the a <...|M|1 queue (private transport) is increased. We give examples where state-dependent routing mitigates the Downs-Thomson effect observed under probabilistic routing, and providing additional information on the state of the system to users reduces delay considerably.