TY - JOUR
T1 - Probabilistic solution discovery algorithm for the orienteering problem
AU - Ramirez-Marquez, José Emmanuel
AU - Kulturel-Konak, Sadan
AU - Sanseverino, Claudio M.Rocco
PY - 2010/7
Y1 - 2010/7
N2 - Orienteering is a competition where participants have a specific time to travel between initial and final locations. This competition is known as the orienteering problem (OP) where the objective is to maximise the reward of visiting sites while not violating constraints on time and final location. Although very good solutions can be obtained via search space heuristics, their coding, development and implementation still require extensive familiarisation and background on the technique of choice. This paper presents an evolutionary algorithm that offers simple and efficient analysis for the OP via three interrelated steps: solution generation via Monte Carlo (MC) simulation; analysis and computation of the reward and distance of these solutions and an evolutionary technique that drives the selection of potentially optimal solutions. The algorithm is tested against benchmark techniques for problems previously solved in the literature and newly developed larger size test problems.
AB - Orienteering is a competition where participants have a specific time to travel between initial and final locations. This competition is known as the orienteering problem (OP) where the objective is to maximise the reward of visiting sites while not violating constraints on time and final location. Although very good solutions can be obtained via search space heuristics, their coding, development and implementation still require extensive familiarisation and background on the technique of choice. This paper presents an evolutionary algorithm that offers simple and efficient analysis for the OP via three interrelated steps: solution generation via Monte Carlo (MC) simulation; analysis and computation of the reward and distance of these solutions and an evolutionary technique that drives the selection of potentially optimal solutions. The algorithm is tested against benchmark techniques for problems previously solved in the literature and newly developed larger size test problems.
KW - OP
KW - Optimisation
KW - Orienteering problem
KW - PSDA
KW - Probabilistic solution discovery algorithm
UR - http://www.scopus.com/inward/record.url?scp=77954438517&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77954438517&partnerID=8YFLogxK
U2 - 10.1504/ijise.2010.033996
DO - 10.1504/ijise.2010.033996
M3 - Article
AN - SCOPUS:77954438517
SN - 1748-5037
VL - 6
SP - 45
EP - 61
JO - International Journal of Industrial and Systems Engineering
JF - International Journal of Industrial and Systems Engineering
IS - 1
ER -