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 10.1007/s00186-020-00722-w

[img]
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: Published Online
Status: In Press
Schools: Mathematics
Publisher: Springer Verlag (Germany)
ISSN: 1432-2994
Date of First Compliant Deposit: 8 July 2020
Date of Acceptance: 5 July 2020
Last Modified: 24 Jul 2020 10:13
URI: http://orca.cf.ac.uk/id/eprint/133164

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics