Roulette Wheel Selection based Heuristic Algorithm for the Orienteering Problem

Journal Title: INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGY - Year 2014, Vol 13, Issue 1

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 selectionmethod, 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 ascompared to a recently reported algorithm for incomplete graphs.

Authors and Affiliations

Madhushi Verma, Mukul Gupta, Bijeeta Pal, Prof. K. K. Shukla

Keywords

Related Articles

ENVIRONMENTAL IMPLICATIONS OF CELL PHONES PENETRATION AND DISPOSAL IN KENYA

Kenya has over six million active  mobile subscribers who may at some point want to replace or   get rid of old mobile phones. A big number of the mobile phones were recently switched off for not being genuine without...

The place of the stored procedures in the cloud databases

The software as a service model ensures not only cloud applications, but also cloud databases. In this paper we analyze the impact on stored procedures of the switch of the existing application to cloud applications and...

A Petri Net approach for representing Orthogonal Variability Models

The software product line (SPL) paradigm is used for developing software system products from a set of reusable artifacts, known as platform. The Orthogonal Variability Modeling (OVM) is a technique for representing and...

Balanced Scorecard Model for Hazards Risk Management at Limpopo River Basin A Country Participatory Approach for MCDA with Scenario Planning

This paper focuses on the application of both Balanced Scorecard (BSC) conceptual framework and Multi-criteria Decision Analysis (MCDA) a tool for Scenario Planning as a tool for Strategic Decision Thinking, on hazard ri...

Microfinance as Employment Generation Tool (Case Study of Pakistan 2001-02 to 2010-11)

The objective of this study is to know the contributions of Micro finance towards employment development through generating employment opportunities to the alit class of urban and rural community. For this purpose quanti...

Download PDF file
  • EP ID EP650514
  • DOI 10.24297/ijct.v13i1.2933
  • Views 84
  • Downloads 0

How To Cite

Madhushi Verma, Mukul Gupta, Bijeeta Pal, Prof. K. K. Shukla (2014). Roulette Wheel Selection based Heuristic Algorithm for the Orienteering Problem. INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGY, 13(1), 4127-4145. https://europub.co.uk/articles/-A-650514