Date of Award

August 2023

Degree Type

Thesis

Degree Name

Master of Science

Department

Computer Science

First Advisor

Tian Zhao

Committee Members

Christine Cheng, Xiao Qin

Abstract

Dial-A-Ride is a transport system heavily constrained by following fleet size, vehicle capacity, and a fixed number of requests (pickup and drop-off points) with time windows. It is often modelled as Integer Programming, various solutions are proposed using heuristics. One such heuristic is "Tabu Search". Tabu Search is very CPU intensive with its process of search, therefore many modern computing techniques like using GPUs have been employed to make it efficient.

As with many other greedy algorithms, the local optima is not always the same as the global optima, so it is not possible to go past the local optima using greedy techniques for this problem. It is often modelled as Integer Programming, with the search space being very big, there are proven to not be so efficient. So, many heuristics have been proposed in the past, one such heuristic is "Tabu Search". The local search of this heuristic uses memory to keep track of recent moves made and tries to avoid them for specified iterations (marks as Tabu) and also continues to explore the neighbourhood search space even with the degradation optimization function value, thus helping the algorithm to go past the local optima towards global optima.

This thesis focuses on limitations of parallelizing DARP-TS for multi-core CPU, discussing major factors like (i) number of good moves in the neighbourhood and how we can estimate a value for N\_SIZE (number of parallel moves to make in each iteration), (ii) difference between a CPU core and a GPU core in the context of thread scheduling, memory layout and memory limitations, (iii) proposes few data-structures to keep the memory allocations low thus reducing the time for garbage collection and (iv) proposes an incremental way of calculating the value of optimization function in the local search phase which helps in mapping the execution and evaluation of N\_SIZE moves in each iteration onto the multiple CPU cores.

Download

Share

COinS