A two-stage approach to the orienteering problem with stochastic weights

L. Evers, K.M. Glorie, S.L. van der Ster, A.I. Barros, H. Monsuur

Abstract

The Orienteering Problem (OP) is a routing problem which has many interesting applications in logistics, tourism and defense. The aim of the OP is to find a maximum profit path or tour, which is feasible with respect to a capacity constraint on the total weight of the selected arcs. In this paper we consider the Orienteering Problem with Stochastic Weights (OPSWs) to reflect uncertainty in real-life applications. We approach this problem by formulating a two-stage stochastic model with recourse for the OPSW where the capacity constraint is hard. The model takes into account the effect that stochastic weights have on the expected total profit value to be obtained, already in the modeling stage. Since the expected profit is in general non-linear, we introduce a linearization that models the total profit that can be obtained for a given tour and a given scenario of weight realizations. This linearization allows for the application of Sample Average Approximation (SAA). The SAA solution asymptotically converges to the optimal solution of the two-stage model, but is computationally expensive. Therefore, to solve large instances, we developed a heuristic that exploits the problem structure of the OPSW and explicitly takes the associated uncertainty into account. In our computational experiments, we evaluate the benefits of our approach to the OPSW, compared to both a standard deterministic approach, and a deterministic approach that is extended with utilization of real-time information. © 2013 Elsevier Ltd.
Original languageEnglish
Pages (from-to)248-260
JournalComputers and Operations Research
Volume43
Issue numberMarch
DOIs
StatePublished - 2014

Cite this

Evers, L., Glorie, K. M., van der Ster, S. L., Barros, A. I., & Monsuur, H. (2014). A two-stage approach to the orienteering problem with stochastic weights. Computers and Operations Research, 43(March), 248-260. DOI: 10.1016/j.cor.2013.09.011

Evers, L.; Glorie, K.M.; van der Ster, S.L.; Barros, A.I.; Monsuur, H. / A two-stage approach to the orienteering problem with stochastic weights.

In: Computers and Operations Research, Vol. 43, No. March, 2014, p. 248-260.

Research output: Scientific - peer-reviewArticle

@article{4bd0c58c6956466598d74046d0bd8d24,
title = "A two-stage approach to the orienteering problem with stochastic weights",
abstract = "The Orienteering Problem (OP) is a routing problem which has many interesting applications in logistics, tourism and defense. The aim of the OP is to find a maximum profit path or tour, which is feasible with respect to a capacity constraint on the total weight of the selected arcs. In this paper we consider the Orienteering Problem with Stochastic Weights (OPSWs) to reflect uncertainty in real-life applications. We approach this problem by formulating a two-stage stochastic model with recourse for the OPSW where the capacity constraint is hard. The model takes into account the effect that stochastic weights have on the expected total profit value to be obtained, already in the modeling stage. Since the expected profit is in general non-linear, we introduce a linearization that models the total profit that can be obtained for a given tour and a given scenario of weight realizations. This linearization allows for the application of Sample Average Approximation (SAA). The SAA solution asymptotically converges to the optimal solution of the two-stage model, but is computationally expensive. Therefore, to solve large instances, we developed a heuristic that exploits the problem structure of the OPSW and explicitly takes the associated uncertainty into account. In our computational experiments, we evaluate the benefits of our approach to the OPSW, compared to both a standard deterministic approach, and a deterministic approach that is extended with utilization of real-time information. © 2013 Elsevier Ltd.",
author = "L. Evers and K.M. Glorie and {van der Ster}, S.L. and A.I. Barros and H. Monsuur",
year = "2014",
doi = "10.1016/j.cor.2013.09.011",
volume = "43",
pages = "248--260",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier Limited",
number = "March",

}

Evers, L, Glorie, KM, van der Ster, SL, Barros, AI & Monsuur, H 2014, 'A two-stage approach to the orienteering problem with stochastic weights' Computers and Operations Research, vol 43, no. March, pp. 248-260. DOI: 10.1016/j.cor.2013.09.011

A two-stage approach to the orienteering problem with stochastic weights. / Evers, L.; Glorie, K.M.; van der Ster, S.L.; Barros, A.I.; Monsuur, H.

In: Computers and Operations Research, Vol. 43, No. March, 2014, p. 248-260.

Research output: Scientific - peer-reviewArticle

TY - JOUR

T1 - A two-stage approach to the orienteering problem with stochastic weights

AU - Evers,L.

AU - Glorie,K.M.

AU - van der Ster,S.L.

AU - Barros,A.I.

AU - Monsuur,H.

PY - 2014

Y1 - 2014

N2 - The Orienteering Problem (OP) is a routing problem which has many interesting applications in logistics, tourism and defense. The aim of the OP is to find a maximum profit path or tour, which is feasible with respect to a capacity constraint on the total weight of the selected arcs. In this paper we consider the Orienteering Problem with Stochastic Weights (OPSWs) to reflect uncertainty in real-life applications. We approach this problem by formulating a two-stage stochastic model with recourse for the OPSW where the capacity constraint is hard. The model takes into account the effect that stochastic weights have on the expected total profit value to be obtained, already in the modeling stage. Since the expected profit is in general non-linear, we introduce a linearization that models the total profit that can be obtained for a given tour and a given scenario of weight realizations. This linearization allows for the application of Sample Average Approximation (SAA). The SAA solution asymptotically converges to the optimal solution of the two-stage model, but is computationally expensive. Therefore, to solve large instances, we developed a heuristic that exploits the problem structure of the OPSW and explicitly takes the associated uncertainty into account. In our computational experiments, we evaluate the benefits of our approach to the OPSW, compared to both a standard deterministic approach, and a deterministic approach that is extended with utilization of real-time information. © 2013 Elsevier Ltd.

AB - The Orienteering Problem (OP) is a routing problem which has many interesting applications in logistics, tourism and defense. The aim of the OP is to find a maximum profit path or tour, which is feasible with respect to a capacity constraint on the total weight of the selected arcs. In this paper we consider the Orienteering Problem with Stochastic Weights (OPSWs) to reflect uncertainty in real-life applications. We approach this problem by formulating a two-stage stochastic model with recourse for the OPSW where the capacity constraint is hard. The model takes into account the effect that stochastic weights have on the expected total profit value to be obtained, already in the modeling stage. Since the expected profit is in general non-linear, we introduce a linearization that models the total profit that can be obtained for a given tour and a given scenario of weight realizations. This linearization allows for the application of Sample Average Approximation (SAA). The SAA solution asymptotically converges to the optimal solution of the two-stage model, but is computationally expensive. Therefore, to solve large instances, we developed a heuristic that exploits the problem structure of the OPSW and explicitly takes the associated uncertainty into account. In our computational experiments, we evaluate the benefits of our approach to the OPSW, compared to both a standard deterministic approach, and a deterministic approach that is extended with utilization of real-time information. © 2013 Elsevier Ltd.

U2 - 10.1016/j.cor.2013.09.011

DO - 10.1016/j.cor.2013.09.011

M3 - Article

VL - 43

SP - 248

EP - 260

JO - Computers and Operations Research

T2 - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - March

ER -

Evers L, Glorie KM, van der Ster SL, Barros AI, Monsuur H. A two-stage approach to the orienteering problem with stochastic weights. Computers and Operations Research. 2014;43(March):248-260. Available from, DOI: 10.1016/j.cor.2013.09.011