Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

A conservative index heuristic for routing problems with multiple heterogeneous service facilities

Shone, Rob, Knight, Vincent A. and Harper, Paul R. 2020. A conservative index heuristic for routing problems with multiple heterogeneous service facilities. Mathematical Methods of Operations Research 92 , pp. 511-543. 10.1007/s00186-020-00722-w

[thumbnail of Shone2020_Article_AConservativeIndexHeuristicFor.pdf]
PDF - Published Version
Available under License Creative Commons Attribution.

Download (675kB) | Preview


We consider a queueing system with N heterogeneous service facilities, in which admission and routing decisions are made when customers arrive and the objective is to maximize long-run average net rewards. For this type of problem, it is well-known that structural properties of optimal policies are difficult to prove in general and dynamic programming methods are computationally infeasible unless N is small. In the absence of an optimal policy to refer to, the Whittle index heuristic (originating from the literature on multi-armed bandit problems) is one approach which might be used for decision-making. After establishing the required indexability property, we show that the Whittle heuristic possesses certain structural properties which do not extend to optimal policies, except in some special cases. We also present results from numerical experiments which demonstrate that, in addition to being consistently strong over all parameter sets, the Whittle heuristic tends to be more robust than other heuristics with respect to the number of service facilities and the amount of heterogeneity between the facilities.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Mathematics
Additional Information: This article is licensed under a Creative Commons Attribution 4.0 International License.
Publisher: Springer Verlag
ISSN: 1432-2994
Date of First Compliant Deposit: 8 July 2020
Date of Acceptance: 5 July 2020
Last Modified: 07 Jan 2021 11:16

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics