More Web Proxy on the site http://driver.im/

research-article

A simheuristic approach for the stochastic team orienteering problem

Authors:

Javier Panadero,

Jesica de Armas,

Christine S. M. Currie,

Angel A JuanAuthors Info & Claims

WSC '17: Proceedings of the 2017 Winter Simulation Conference

Article No.: 262, Pages 1 - 10

Published: 03 December 2017 Publication History

Abstract

The team orienteering problem is a variant of the well-known vehicle routing problem in which a set of vehicle tours are constructed in such in a way that: (i) the total collected reward received from visiting a subset of customers is maximized; and (ii) the length of each vehicle tour is restricted by a pre-specified limit. While most existing works refer to the deterministic version of the problem and focus on maximizing total reward, some degree of uncertainty (e.g., in customers' service times or in travel times) should be expected in real-life applications. Accordingly, this paper proposes a simheuristic algorithm for solving the stochastic team orienteering problem, where goals other than maximizing the expected reward need to be considered. A series of numerical experiments contribute to illustrate the potential of our approach, which integrates Monte Carlo simulation inside a metaheuristic framework.

References

[1]

Campbell, A., M. Gendreau, and B. Thomas. 2011. "The orienteering problem with stochastic travel and service times". Annals of Operations Research 186:61--81.

[2]

Chao, I.-M., B. Golden, and E. Wasil. 1996. "The team orienteering problem". European Journal of Operational Research 88:464--474.

[3]

Dang, D.-C., R. N. Guibadj, and A. Moukrim. 2013. "An effective PSO-inspired algorithm for the team orienteering problem". European Journal of Operational Research 229 (2): 332--344.

[4]

Dominguez, O., A. A. Juan, B. Barrios, J. Faulin, and A. Agustin. 2016. "Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet". Annals of Operations Research 236 (2): 383--404.

[5]

Dominguez, O., A. A. Juan, and J. Faulin. 2014. "A biased-randomized algorithm for the two-dimensional vehicle routing problem with and without item rotations". International Transactions in Operational Research 21 (3): 375--398.

[6]

Evers, L., K. Glorie, S. van der Ster, A. Barros, and H. Monsuur. 2014. "A two-stage approach to the orienteering problem with stochastic weights". Computers and Operations Research 43:248--260.

Digital Library

[7]

Faulin, J., M. Gilibert, A. A. Juan, X. Vilajosana, and R. Ruiz. 2008. "SR-1: A simulation-based algorithm for the capacitated vehicle routing problem". In Proceedings of the 40th Conference on Winter Simulation, edited by J. W. Fowler, R. G. Ingalls, S. Mason, R. Hill, L. Mnch, and O. Rose, 2708--2716: IEEE.

Digital Library

[8]

Ferreira, J., A. Quintas, and J. Oliveira. 2014. "Solving the team orienteering problem: developing a solution tool using a genetic algorithm approach". In Soft computing in industrial applications. Advances in Intelligent Systems and Computing: 223, 365--375. Springer.

[9]

Golden, B., L. Levy, and R. Vohra. 1987. "The orienteering problem". Naval Research Logistics 34:307--318.

[10]

Grasas, A., A. A. Juan, J. Faulin, J. de Armas, and H. Ramalhinho. 2017. "Biased Randomization of Heuristics using Skewed Probability Distributions: a survey and some applications". Computers & Industrial Engineering 110:216--228.

[11]

Gunawan, A., H. Lau, and P. Vansteenwegen. 2016. "Orienteering Problem: A survey of recent variants, solution approaches and applications". European Journal of Operational Research 255:315--332.

[12]

Ilhan, T., S. Iravani, and M. Daskin. 2008. "The orienteering problem with stochastic profits". IIE Transactions 40:406--421.

[13]

Juan, A., J. Faulin, R. Ruiz, B. Barrios, and S. Caballe. 2010. "The SR-GCWS hybrid algorithm for solving the capacitated vehicle routing problem". In Applied Soft Computing, Volume 10, 215--224. Elsevier.

Digital Library

[14]

Juan, A., J. Faulin, R. Ruiz, B. Barrios, M. Gilibert, and X. Vilajosana. 2009. "Using oriented random search to provide a set of alternative solutions to the capacitated vehicle routing problem". In Operations Research and Cyber-Infrastructure, Volume 47, 331--346. Springer US.

[15]

Juan, A., S. Grasman, J. Caceres-Cruz, and T. Bekta. 2014. "A simheuristic algorithm for the Single-Period Stochastic Inventory-Routing Problem with stock-outs". Simulation Modelling Practice and Theory 46:40--52.

[16]

Juan, A. A., J. Faulin, A. Ferrer, H. R. Lourenço, and B. Barrios. 2013. "MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems". Top 21 (1): 109--132.

[17]

Juan, A. A., J. Faulin, S. E. Grasman, M. Rabe, and G. Figueira. 2015. "A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems". Operations Research Perspectives 2 (1): 62--72.

[18]

Juan, A. A., J. Faulin, S. E. Grasman, D. Riera, J. Marull, and C. Mendez. 2011. "Using safety stocks and simulation to solve the vehicle routing problem with stochastic demands". Transportation Research Part C: Emerging Technologies 19 (5): 751--765.

[19]

Ke, L., L. Zhai, J. Li, and F. Chan. 2015. "Pareto mimic algorithm: an approach to the team orienteering problem". Omega 61:155--166.

[20]

Keshtkaran, M., K. Ziarati, A. Bettinelli, and D. Vigo. 2015. "Enhanced exact solution methods for the team orienteering problem". International Journal of Production Research 54:591--601.

[21]

Lau, H. C., W. Yeoh, P. Varakantham, D. T. Nguyen, and H. Chen. 2012. "Dynamic Stochastic Orienteering Problems for Risk-Aware Applications". CoRR abs/1210.4874.

Digital Library

[22]

Lin, S. 2013. "Solving the team orienteering problem using effective multi-start simulated annealing". Applied Soft Computing 13:1064--1073.

Digital Library

[23]

Papapanagiotou, V., R. Montemanni, and L. Gambardella. 2014. "Objective function evaluation methods for the orienteering problem with stochastic travel and service times". Journal of Applied Operations Research 6:16--29.

[24]

Tang, H., and E. Miller-Hooks. 2005. "A tabu search heuristic for the team orienteering problem". Computers & Operations Research 32 (6): 1379--1407.

Digital Library

[25]

Teng, S., H. Ong, and H. Huang. 2004. "An integer 1-shaped algorithm for time-constrained traveling salesman problem with stochastic travel and service times". Asia-Pacific Journal of Operational Research 21:241--257.

[26]

Verbeeck, C., P. Vansteenwegen, and E.-H. Aghezzaf. 2016. "Solving the stochastic time-dependent orienteering problem with time windows". European Journal of Operational Research 255:699--718.

Cited By

Rabe MChicaiza-Vaca JTordecilla RMartins LJuan A(2021)Supporting hospital logistics during the first months of the COVID-19 crisisProceedings of the Winter Simulation Conference10.5555/3522802.3522905(1-10)Online publication date: 13-Dec-2021
https://dl.acm.org/doi/10.5555/3522802.3522905
Bayliss CCopado-Mendez PPanadero JJuan AMartins L(2020)A simheuristic-learnheuristic algorithm for the stochastic team orienteering problem with dynamic rewardsProceedings of the Winter Simulation Conference10.5555/3466184.3466324(1254-1264)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.5555/3466184.3466324
Reyes-Rubiano LOspina-Trujillo CFaulin JMozos JPanadero JJuan AJohansson BJain S(2018)The team orienteering problem with stochastic service times and driving-range limitationsProceedings of the 2018 Winter Simulation Conference10.5555/3320516.3320876(3025-3035)Online publication date: 9-Dec-2018
https://dl.acm.org/doi/10.5555/3320516.3320876
Show More Cited By

A simheuristic approach for the stochastic team orienteering problem
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

Metaheuristics for the team orienteering problem

The Team Orienteering Problem (TOP) is the generalization to the case of multiple tours of the Orienteering Problem, known also as Selective Traveling Salesman Problem. A set of potential customers is available and a profit is collected from the visit ...
A simheuristic-learnheuristic algorithm for the stochastic team orienteering problem with dynamic rewards
WSC '20: Proceedings of the Winter Simulation Conference

In this paper, we consider the stochastic team orienteering problem with dynamic rewards (STOPDR) and stochastic travel times. In the STOPDR, the goal is to generate routes for a fixed set of vehicles such that the sum of the rewards collected is ...
A two-stage approach to the orienteering problem with stochastic weights

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

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WSC '17: Proceedings of the 2017 Winter Simulation Conference

December 2017

4389 pages

ISBN:9781538634271

Sponsors

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

IEEE Press

Publication History

Published: 03 December 2017

Check for updates

Qualifiers

Research-article

Conference

WSC '17

Sponsor:

SIGSIM

WSC '17: Winter Simulation Conference

December 3 - 6, 2017

Nevada, Las Vegas

Acceptance Rates

Overall Acceptance Rate 3,413 of 5,075 submissions, 67%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
25
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rabe MChicaiza-Vaca JTordecilla RMartins LJuan A(2021)Supporting hospital logistics during the first months of the COVID-19 crisisProceedings of the Winter Simulation Conference10.5555/3522802.3522905(1-10)Online publication date: 13-Dec-2021
https://dl.acm.org/doi/10.5555/3522802.3522905
Bayliss CCopado-Mendez PPanadero JJuan AMartins L(2020)A simheuristic-learnheuristic algorithm for the stochastic team orienteering problem with dynamic rewardsProceedings of the Winter Simulation Conference10.5555/3466184.3466324(1254-1264)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.5555/3466184.3466324
Reyes-Rubiano LOspina-Trujillo CFaulin JMozos JPanadero JJuan AJohansson BJain S(2018)The team orienteering problem with stochastic service times and driving-range limitationsProceedings of the 2018 Winter Simulation Conference10.5555/3320516.3320876(3025-3035)Online publication date: 9-Dec-2018
https://dl.acm.org/doi/10.5555/3320516.3320876
Panadero JJuan AMozos JCorlu COnggo BJohansson BJain S(2018)Agent-based simheuristicsProceedings of the 2018 Winter Simulation Conference10.5555/3320516.3320629(869-880)Online publication date: 9-Dec-2018
https://dl.acm.org/doi/10.5555/3320516.3320629

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents