Student research opportunities

Geometric Soft-Constraints for Pragmatic Vehicle Routing

Project Code: CECS_813

This project is available at the following levels:
CS single semester, Engn4200, Engn R&D, Honours, Summer Scholar
Please note that this project is only for undergraduate students.

Keywords:

Metaheuristic Search, GPU Programming, Convex Hulls

Supervisors:

Dr Charles GRETTON
Dr Phil Kilby

Outline:

The state-of-the-art solution procedures for problems in
transportation logistics employ some manner of metaheuristic
search. Along those lines, at NICTA we have developed an award
winning system named Indigo. The latest version of Indigo uses
geometric features of vehicle routes in order to guide the
optimisation towards route and route schedules that logistics
practitioners are keen to implement. Presently a significant portion
of that functionality is executed serially on a CPU, with preliminary
GPU implementations in CUDA. By employing techniques, such as matrix
segmented scans and prefix scans, highly engineered GPU
implementations are significantly more efficient at computing the
geometric features of routes than CPU-based counterparts. In this
project the student will study and develop very fast algorithms for
computing the geometric features of vehicle routes using GPUs.

Goals of this project

(1) - Produce an OpenCL implementation of procedures for computing the
geometric properties of structures in transportation logistics.

(2) - Explore how to use those features to best guide state-of-the art
metaheuristics search in real-world vehicle routing problems.

(3*) - OPTIONAL. An excellent student might also choose to develop
fast shortest path procedures in OpenCL.

Requirements/Prerequisites

Ambitious hard working student with a strong track record in technical subjects.

A keen interest in Mathematical Optimisation and Metaheuristic Search.

Strong interest and abilities in computer programming. Preferably (not
required), strong knowledge of the GNU programming environment.

If in doubt, _please_ write to us...

Student Gain

Experience working at NICTA, a world-class ITC research organisation.

Graduate level knowledge of key topics in Operations Research,
specifically Transportation Logistics.

Background Literature

Srikanth, Durga Prasad Reddy. Kishore Kothapalli, R.Govindarajulu,
P.J.Narayanan. Parallelizing Two Dimensional Convex Hull on NVIDIA GPU
and Cell BE. International Conference on High Performance
Computing (HiPC) 2009, Students Research Symposium, Cochin, India,
2009, pp. 1–5.

Jean-Yves Potvin, Tanguy Kervahut, Bruno-Laurent Garcia, Jean-Marc
Rousseau: The Vehicle Routing Problem with Time Windows Part I: Tabu
Search. INFORMS Journal on Computing 8(2): 158-164 (1996)

Jean-Yves Potvin, Samy Bengio: The Vehicle Routing Problem with Time
Windows Part II: Genetic Search. INFORMS Journal on Computing 8(2):
165-172 (1996)