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 92
- Downloads 0
Can Ali Pass the Program? An Empirical Study of a Blind ICT Student challenges at Arab Open University
We live in visually oriented society, in which the computer is becoming as commonplace and integral part of every student’s educational experience. It plays essential role in transforming the way in which postsecondary...
Technological Approaches in Applied Social learning
Industry 4.0 covers the readiness of achieving expertise that impacts the society, strategy, talent and technology. Individual, social and economic demands pose ever-changing challenges for education and training even in...
An Instance Selection Algorithm Based On Reverse k Nearest Neighbor
Classification is one of the most important data mining techniques. It belongs to supervised learning. The objective of classification is to assign class label to unlabelled data. As data is growing rapidly, handling it...
Occlusion Detection in M-FISH Human Chromosome Images
Automation of Chromosome Analysis has long been considered a tedious task due to the partial occlusion of chromosomes. This calls for a non-trivial, dedicated procedure to segment chromosomes. In this paper, a new method...
Logical Circuits for Extended Content Matching in Hardware Based NIDPS
In this paper we present logical circuits for efficient detection of rolled out contents. As network speed increases and security matters there is a demand for implementation of hardware based Network Intrusion Detecti...