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
- EP ID EP650514
- DOI 10.24297/ijct.v13i1.2933
- Views 81
- Downloads 0
ARTFSC Average Relative Term Frequency Sentiment Classification
Sentiment Classification refers to the computational techniques for classifying whether the sentiments of text are positive or negative. Statistical Techniques based on Term Presence and Term Frequency, using Support Vec...
Fault Tolerant Heterogeneous Limited Duplication Scheduling algorithm for Decentralized Grid
Fault tolerance is one of the most desirable property in decentralized grid computing systems, where computational resources are geographically distributed. These resources collaborate in order to execute workflow applic...
Analyze the Future: Cloud Computing, a New Phase in Information Technology Infrastructure Management
The use of cloud computing is becoming widespread, but systematic study of its managerial implications is lacking. This paper examines cloud computing in the context of other major changes in Information Technology (IT)...
Conceptual Overlapping Clustering for Effective Selection of Parental Rice Varieties
The process of rice breeding involves producing new rice varieties as a cross of parental rice varieties followed by rigorous testing and examination phase for purity, productivity and resistivity to regional climatic co...
Script Recovery from Scanned Document Image
Document digitization with scanner in text document images which have distortions that deteriorate the quality of the document. We propose a goal-oriented rectification methodology to recover the document from distorted...