KUET Institutional Repository (Khulna University of Engineering & Technology)
Not a member yet
1045 research outputs found
Sort by
An Efficient Representation of Higher Dimensional Arrays and its Evaluation
No full textThis thesis is submitted to the Department of Computer Science and Engineering, Khulna University of Engineering & Technology in partial fulfillment of the requirements for the degree of Master of Science in Computer Science and Engineering, July 2016.Cataloged from PDF Version of Thesis.Includes bibliographical references (pages 60-63).Scientilic and engineering computing requires storing and operating on flooded amount of
data having very high number of dimensions. Traditional multidimensional array is widely
popular for implementing higher dimensional data but its performance diminishes with
increased number of dimensions. On the other side, traditional row-column view of two-dimensional
data is facile for implementation, imagination and visualization. This thesis
represents a scheme for higher dimensional array implementation and operation with row-column
abstraction which can fit an n-dimensional array into a single 2-dimensional array.
A mathematical function fits odd dimensions along row-direction and even dimensions
along column direction which gives lower index computation cost, higher data locality and
better sequential access of memory. Performance of the proposed matricization is
measured with matrix-matrix addition/subtraction and multiplication operation which give
70% and 72% improvement respectively for dense data. But most real world data is sparse
and degree of data sparsity increases with increased number of dimensions. A loop
transformation technique which access odd dimensions fast and then even dimensions is
proposed to store any dimensional sparse arrays. In traditional scheme, n numbers of one-dimensional
auxiliary arrays are necessary to store n-dimensional array but our scheme requires two one-dimensional auxiliary arrays only which gives 16 times space improvement for 32-dimensional sparse data. Traditionally, the compression ratio is inversely proportional to the number of dimensions but it is independent of number of dimensions in our scheme. The operation on stored sparse data is measured with matrix-matrix addition/subtraction and multiplication which show up to 70% improvement.Md. Abu Hanif ShaikhMaster of Science in Computer Science and Engineerin
Solving Capacitated Vehicle Routing Problem through Clustering with Variant Sweep Algorithm and Route Optimization using Swarm Intelligence
No full textThis thesis is submitted to the Department of Computer Science and Engineering, Khulna University of Engineering & Technology in partial fulfillment of the requirements for the degree of Master of Science in Computer Science and Engineering, May, 2016.Cataloged from PDF Version of Thesis.Includes bibliographical references (pages 51-55).Capacitated Vehicle Routing Problem (CVRP) is a real life constraint satisfaction problem in
which customers are optimally assigned to individual vehicles (considering their capacity) to
keep total travel distance of the vehicles as minimum as possible while serving customers.
Various methods are used to solve CVRP in last few decades, the most popular way of solving
CVRP is splitting the task into two different phases: firstly, assigning customers under different
vehicles and secondly, finding optimal route of each vehicle. Sweep clustering algorithm is
well studied for clustering nodes. On the other hand, route optimization is simply a traveling
salesman problem (TSP) and a number of TSP optimization methods are applied for this
purpose. This study investigates a variant of Sweep algorithm for clustering nodes and different
Swarm Intelligence (SI) based methods for route generation to get optimal CVRP solution. In
conventional Sweep algorithm, cluster formation starts from 00 and consequently advance
toward 3600 to consider all the nodes. In this study, a variant Sweep cluster is investigated from
different starting angle. A heuristic based adaptive method is developed to select cluster
formation starting angle. On the other hand, two well-known optimization methods (i.e.,
Genetic Algorithm and Ant Colony Optimization) and two recent SI based algorithms (i.e.,
Producer-Scrounger Method and Velocity Tentative Particle Swarm Optimization) are
considered for route optimization. The experimental results on a large number of benchmark
CVRPs revealed that different starting angles have positive effect on Sweep clustering and
finally, VTPSO is able to produce better solution than other SI methods. Finally, the proposed
mythology is found to achieve better CVRP solutions for several problems when compared
with several prominentZahrul Jannat PeyaMaster of Science in Computer Science and Engineerin
