Vellore Institute of Technology (VIT) is a private university located in&nbsp;Tamil Nadu, India. Founded in 1984, as Vellore Engineering College, the institution offers 20 undergraduate, 34 postgraduate, four integrated and four research programs. It has campuses in Vellore, Amravati, Bhopal and Chennai.

VIT is one of the top ranked private universities in India according to NIRF, THE and QS Rankings.&nbsp;Govt. of India has recognized&nbsp;VIT, Vellore as an&nbsp;Institution of Eminence. This has allowed VIT to take independent quality initiatives and move up in world ranking.

&nbsp;

&nbsp;

VIT University

This paper deals with one-To-many multidimensional unbalanced assignment problem with two conflicting objectives, where the first objective minimises the total processing time and the other maximises the overall productivity/profit on performing n jobs by m (m &lt;n) persons at h distinct time horizons. It is assumed that each job is operated by exactly one person, whereas a person is permitted to perform more than one job at distinct time horizons. This problem is modelled with binary programming, and has potential applications in scheduling, timetabling, human resource allocations, etc. An efficient pattern recognition technique-based Lexi-search algorithm (LSA) is developed, which is capable of enumerating the Pareto optimal solutions. A comparative study is performed between the LSA and genetic algorithm (GA) on the relaxed version of the present model. The descriptive statistical analysis of CPU runtime of LSA on distinct random instances indicates that it is taking reasonably less computational runtime.

VIT Unitversity

Department of Mathematics

School of Advanced Sciences

Vellore Campus

International Journal of Bio-Inspired Computation

An ISO/IEC 24745 compliant ECG template protection based on linear prediction coding

This paper introduces a novel practical variant, namely an open close multiple travelling salesmen problem with single depot (OCMTSP) that concerns the generalization of classical travelling salesman problem (TSP). In OCMTSP, the overall salesmen can be categorized into internal/permanent and external/outsourcing ones, where all the salesmen are positioned at the depot city. The primary objective of this problem is to design the optimal route such that all salesmen start from the depot/base city, and then visit a given set of cities. Each city is to be visited precisely once by exactly one salesman, and only the internal salesmen have to return to the depot city whereas the external ones need not return. To find optimal solutions, an exact pattern recognition technique based Lexi-search algorithm (LSA) is developed which has been subjected in Matlab. Comparative computational results of the LSA have been made with the existing methods for general multiple travelling salesman problem (MTSP). Further, to test the performance of LSA, computational experiments have been carried out on some benchmark as well as randomly generated test instances for OCMTSP, and results are reported. The overall computational results demonstrate that the proposed LSA is efficient in providing optimal and sub-optimal solutions within the considerable CPU times.

Fulltext

Decision Science Letters

An open close multiple travelling salesman problem with single depot

The degree constrained k-cardinality minimum spanning tree problem: a lexi-search algorithm

This paper deals with the bi-criteria travelling salesman subtour problem with time threshold (BTSSP-T), which comes from the family of the travelling salesman problem (TSP) and is NP-hard in the strong sense. The problem arises in several application domains, mainly in routing and scheduling contexts. Here, the model focuses on two criteria: total travel distance and gains attained. The BTSSPT aims to determine a subtour that starts and ends at the same city and visits a subset of cities at a minimum travel distance with maximum gains, such that the time spent on the tour does not exceed the predefined time threshold. A zero-one integer-programming problem is adopted to formulate this model with all practical constraints, and it includes a finite set of feasible solutions (one for each tour). Two algorithms, namely, the Lexi-Search Algorithm (LSA) and the Tabu Search (TS) algorithm have been developed to solve the BTSSP-T problem. The proposed LSA implicitly enumerates the feasible patterns and provides an efficient solution with backtracking, whereas the TS, which is metaheuristic, will give the better approximate solution. A numerical example is demonstrated in order to understand the search mechanism of the LSA. Numerical experiments are carried out in the MATLAB environment, on the different benchmark instances available in the TSPLIB domain as well as on randomly generated test instances. The experimental results show that the proposed LSA works better than the TS algorithm in terms of solution quality and, computationally, both LSA and TS are competitive.

World University root node

European Physical Journal Plus

Bi-criteria travelling salesman subtour problem with time threshold

The minimum vertex cover problem (MVCP) is a well-known NP complete combinatorial optimization problem. The aim of this paper is to present an approximation algorithm for minimum vertex cover problem (MVCP). The algorithm construction is based on articulation points/cut vertices and leaf vertices/pendant vertices. The proposed algorithm assures the near optimal or optimal solution for a given graph and can be solved in polynomial time. A numerical example is illustrated to describe the proposed algorithm. Comparative results show that the proposed algorithm is very competitive compared with other existing algorithms.

Trends in Mathematics Advances in Algebra and Analysis

An Articulation Point-Based Approximation Algorithm for Minimum Vertex Cover Problem

This paper deals with a variant of minimum spanning tree problem with multiple constraints, which includes degree, weight and budgeting constraints simultaneously together. To model the problem, a zero-one programming is incorporated. An exact solution procedure called pattern recognition technique-based lexi-search algorithm is developed. A suitable numerical illustration is given to check the applicability of the developed algorithm. Furthermore, the algorithm is programmed in C and tested with randomly generated hard instances, computational results are also reported. The overall results reveal that the proposed algorithm is fairly proficient in the sense of both acquiring the optimal solutions and computational time. Copyright © 2018 Inderscience Enterprises Ltd.

International Journal of Mathematics in Operational Research

An exact algorithm for multi-constrained minimum spanning tree problem

IOP Conference Series: Materials Science and Engineering

An exact algorithm fork-cardinality degree constrained clustered minimum spanning tree problem

Lidars (Laser radars) are the best suitable instruments to derive the range resolved parameters of atmosphere. Single wavelength and simple backscatter lidars have been widely used to study the height profiles of particle scattering and extinction in the atmosphere. However, atmospheric extinction derived using these lidars data undergo several assumptions and hence involve a significant amount of error in estimation of extinction. The Raman lidar methodology of deriving particle extinction in the atmosphere is a simplified straight-forward method that does not involve any assumptions. The Raman lidar method of atmospheric extinction computation employs derivative of logarithm of normalized range corrected Raman backscattered signal. Usually this causes gaps in the height profiles wherever there is a gradient in the signal under examination. In the present study, a new method is proposed to derive the particle extinction in the atmospheric boundary layer. In this new method, a scheme of alternative solution methodology has been proposed using "Finite Difference Technique". The method has an advantage that, it does not involve the gradient as compared to conventional technique and hence reduces the error. Using this method, the height profiles of particle extinction has been derived. A code in MATLAB is developed to derive the altitude distribution of aerosol extinction. In this connection, the NOAA-REDY site data has been used as the reference data for calculating the molecular extinction in the lower atmosphere.

International Journal of Engineering and Technology

Application of finite difference technique to Raman lidar signals to derive the altitude profiles of atmospheric aerosol extinction

The usual Transshipment Problem is to minimize the total cost for shipping the various capacities of the goods on the requirement of destinations from the available sources, well known N.P-Hard problem. Generally, the transshipment problem consist a unit cost on supplied goods to destinations from the sources. But in bulk transshipment the cost is independent of number of goods supplied to destinations, it is practical. In this paper we investigated a “variant of constrained bulk transshipment problem”. Let there are m-sources and n-destinations. The destinations can get its complete requirement from a source directly or through some destination. The practical constraint is considered as only fewer destinations will act as transshipment nodes i.e. a destination can get its complete requirement from a source through a permitted destination; this transshipment node can be utilized with the specified finite number of times in the optimal schedule. The cost of transportation of products from the sources to destination and destinations to destination is given. The total availability of the product at the sources is greater than or equal to the total requirement of the product at the destinations. Generally movement of a product from source to source or destinations to source is not natural, hence these possibilities are avoided and movement from destinations to destination is only considered. This is more generalized problem and comes under combinatorial programming problem. Often, the model is expressed as a zero-one programming problem. The objective of the problem is to minimize the total bulk cost of supplying the required products to the destinations with the restriction that any destination should get its supply from one source only, even when it gets from a destination. In the sequel, we have developed a Lexi Search Algorithm using Pattern Reorganization Technique to obtain the optimal solution. The concepts and algorithms developed are explained with a suitable example. The algorithm is tested and the experimental results indicate that the hard instance problems also solved in reasonable time. © Research India Publications.

Global Journal of Pure and Applied Mathematics

A variant constrained bulk transshipment problem

OPSEARCH

The problem of maximum flow with minimum attainable cost in a network

This study aims to optimize the number of nodes and arcs in a constructed network employing a given criteria. For this, we subject the constructed network using the methods like Shortest Path (SP), Critical Path (CP) and Max-Flow (MF) between any pair of nodes. A set of iterative algorithms have been generated using matrix operations to meet the above requirement, which is named as Pandit's algorithm. The equivalent algorithms for SP, CP and MF are hereby represented as Pandit's Mini-additive, Maxi-additive and Max-min algorithms respectively. The generated algorithms take less number of iterations when compared to the established methods. The proposed new algorithms are shown with suitable numerical examples and discuss their merits over the established methods. These new algorithms take less computational time and hence suggested for solving the bulk networks such as transportation GIS, telecommunication networks, information systems, project scheduling etc. © 2012 Operational Research Society of India.

A new approach for solving the network problems

The paper aims at obtaining an optimal route of a fleet of oildelivery tankers from a source to a number of service stations. The distance between any two stations and demand(s) for each station are given. The objective is to find an optimal route undertaken by tankers such that the requirements of stations are met, the total distance travelled by the Tankers and the backload of the Tankers is to be minimized under the considerations. Also, the Tanker should visit a pair of stations exactly once. Further, a tanker does not supply the requirements of the stations partially. Here the tanker carries back the residue to the depot the available amount of oil will be considered as Backload or undelivered oil when the Tanker returns to depot (source station) or the maximum utilization of the capacity of Tankers in a trip schedule. Dantzig and Ramser-[4] investigated the problem of "The Truck Dispatching Problem" without the minimum backload and obtained a near optimal solution with the dynamic programming approach. For obtaining the optimal solution of the same problem with minimum backload, we proposed the Lexicographic Search approach. The algorithm is tested using C-language and the computational details are also reported, observed that it takes less computational time for higher size of problems.