## Files in this item

FilesDescriptionFormat

application/pdf

PAREKH-THESIS-2015.pdf (1MB)
(no description provided)PDF

## Description

 Title: Deterministic annealing algorithm: tutorial, application to pickup and delivery problem and computational aspects Author(s): Parekh, Pratik Mayur Department / Program: Mechanical Sci & Engineering Discipline: Mechanical Engineering Degree Granting Institution: University of Illinois at Urbana-Champaign Degree: M.S. Genre: Thesis Subject(s): Deterministic Annealing Algorithm Computational Aspects Abstract: The deterministic annealing (DA) method, used for the solution of several nonconvex problems, offers the ability to avoid shallow local minima of a given cost surface and the ability to minimize the cost function even when there are many local minima. The method is established in a probabilistic framework through basic information-theoretic techniques such as maximum entropy and random coding. It arises naturally in the context of statistical mechanics by the emulation of a physical process whereby a solid is slowly cooled and at zero temperature assumes its minimum energy configuration. We start with the introduction to DA method and then present a tutorial to describe the algorithm steps. Also, we discuss the connections of DA method with Statistical Mechanics and Rate-Distortion Theory. Next, we present the application of DA method to pickup and deliver scheduling problem with time windows. Finally, a computational complexity analysis for DA is presented for a given temperature schedule. The case study focuses on the geometric cooling law $T(t)=\rho T(t-1), 0<\rho<1$, where $T(t)$ is the temperature at time $t$. Issue Date: 2015-04-30 Type: Thesis URI: http://hdl.handle.net/2142/78688 Rights Information: Copyright 2015 Pratik Mayur Parekh Date Available in IDEALS: 2015-07-22 Date Deposited: May 2015
﻿