Home > Research > Publications & Outputs > A conservative index heuristic for routing prob...

Links

Text available via DOI:

View graph of relations

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

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published

Standard

A conservative index heuristic for routing problems with multiple heterogeneous service facilities. / Shone, R.; Knight, V.A.; Harper, P.R.
In: Mathematical Methods of Operational Research, Vol. 92, No. 3, 01.12.2020, p. 511-543.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

Shone, R, Knight, VA & Harper, PR 2020, 'A conservative index heuristic for routing problems with multiple heterogeneous service facilities', Mathematical Methods of Operational Research, vol. 92, no. 3, pp. 511-543. https://doi.org/10.1007/s00186-020-00722-w

APA

Shone, R., Knight, V. A., & Harper, P. R. (2020). A conservative index heuristic for routing problems with multiple heterogeneous service facilities. Mathematical Methods of Operational Research, 92(3), 511-543. https://doi.org/10.1007/s00186-020-00722-w

Vancouver

Shone R, Knight VA, Harper PR. A conservative index heuristic for routing problems with multiple heterogeneous service facilities. Mathematical Methods of Operational Research. 2020 Dec 1;92(3):511-543. Epub 2020 Jul 22. doi: 10.1007/s00186-020-00722-w

Author

Shone, R. ; Knight, V.A. ; Harper, P.R. / A conservative index heuristic for routing problems with multiple heterogeneous service facilities. In: Mathematical Methods of Operational Research. 2020 ; Vol. 92, No. 3. pp. 511-543.

Bibtex

@article{fefb7003d1f74d91831f915a39fb58db,
title = "A conservative index heuristic for routing problems with multiple heterogeneous service facilities",
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. ",
keywords = "Dynamic programming, Queueing systems, Whittle index heuristic, Decision making, Structural optimization, Structural properties, Dynamic programming methods, Heterogeneous services, Multi-armed bandit problem, Number of services, Numerical experiments, Optimal policies, Routing decisions, Routing problems",
author = "R. Shone and V.A. Knight and P.R. Harper",
year = "2020",
month = dec,
day = "1",
doi = "10.1007/s00186-020-00722-w",
language = "English",
volume = "92",
pages = "511--543",
journal = "Mathematical Methods of Operational Research",
issn = "1432-2994",
publisher = "Physica-Verlag",
number = "3",

}

RIS

TY - JOUR

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

AU - Shone, R.

AU - Knight, V.A.

AU - Harper, P.R.

PY - 2020/12/1

Y1 - 2020/12/1

N2 - 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.

AB - 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.

KW - Dynamic programming

KW - Queueing systems

KW - Whittle index heuristic

KW - Decision making

KW - Structural optimization

KW - Structural properties

KW - Dynamic programming methods

KW - Heterogeneous services

KW - Multi-armed bandit problem

KW - Number of services

KW - Numerical experiments

KW - Optimal policies

KW - Routing decisions

KW - Routing problems

U2 - 10.1007/s00186-020-00722-w

DO - 10.1007/s00186-020-00722-w

M3 - Journal article

VL - 92

SP - 511

EP - 543

JO - Mathematical Methods of Operational Research

JF - Mathematical Methods of Operational Research

SN - 1432-2994

IS - 3

ER -