Roulette Wheel Selection based Heuristic Algorithm for the Orienteering Problem

Authors

  • Madhushi Verma IIT (BHU), Varanasi- 221005.
  • Mukul Gupta IIT (BHU),Varanasi- 221005.
  • Bijeeta Pal IIT (BHU), Varanasi- 221005.
  • Prof. K. K. Shukla IIT (BHU), Varanasi- 221005.

DOI:

https://doi.org/10.24297/ijct.v13i1.2933

Keywords:

Orienteering problem, complete graphs, incomplete graphs, roulette wheel selection method, Heuristic algorithm.

Abstract

Orienteering problem (OP) is an NP-Hard graph problem. The nodes of the graph are associated with scores or rewards and the edges with time delays. The goal is to obtain a Hamiltonian path connecting the two necessary check points, i.e. the source and the target along with a set of control points such that the total collected score is maximized within a specified time limit. OP finds application in several fields like logistics, transportation networks, tourism industry, etc. Most of the existing algorithms for OP can only be applied on complete graphs that satisfy the triangle inequality. Real-life scenario does not guarantee that there exists a direct link between all control point pairs or the triangle inequality is satisfied. To provide a more practical solution, we propose a stochastic greedy algorithm (RWS_OP) that uses the roulette wheel selection
method, does not require that the triangle inequality condition is satisfied and is capable of handling both complete as well as incomplete graphs. Based on several experiments on standard benchmark data we show that RWS_OP is faster, more efficient in terms of time budget utilization and achieves a better performance in terms of the total collected score as
compared to a recently reported algorithm for incomplete graphs.

Downloads

Download data is not yet available.

Author Biographies

Madhushi Verma, IIT (BHU), Varanasi- 221005.

Department of Computer Science and Engineering

Mukul Gupta, IIT (BHU),Varanasi- 221005.

Department of Computer Science and Engineering

Bijeeta Pal, IIT (BHU), Varanasi- 221005.

Department of Computer Science and Engineering

Prof. K. K. Shukla, IIT (BHU), Varanasi- 221005.

Department of Computer Science and Engineering

Downloads

Published

2014-04-02

How to Cite

Verma, M., Gupta, M., Pal, B., & K. Shukla, P. K. (2014). Roulette Wheel Selection based Heuristic Algorithm for the Orienteering Problem. INTERNATIONAL JOURNAL OF COMPUTERS &Amp; TECHNOLOGY, 13(1), 4127–4145. https://doi.org/10.24297/ijct.v13i1.2933

Issue

Section

Research Articles