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

Shone, Rob, Knight, Vincent A. ORCID: https://orcid.org/0000-0002-4245-0638 and Harper, Paul R. ORCID: https://orcid.org/0000-0001-7894-4907 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

Preview

PDF - Published Version Available under License Creative Commons Attribution. Download (675kB) | Preview

Abstract

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:	11 May 2023 17:48
URI:	https://orca.cardiff.ac.uk/id/eprint/133164

Actions (repository staff only)

Edit Item