University of Illinois Urbana-Champaign

Deterministic annealing algorithm: tutorial, application to pickup and delivery problem and computational aspects

Parekh, Pratik Mayur

Content Files
PAREKH-THESIS-2015.pdf

Permalink

https://hdl.handle.net/2142/78688

Description

Title
Deterministic annealing algorithm: tutorial, application to pickup and delivery problem and computational aspects
Author(s)
Parekh, Pratik Mayur
Issue Date
2015-04-30
Department of Study
Mechanical Sci & Engineering
Discipline
Mechanical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Date of Ingest
2015-07-22T22:34:01Z
Keyword(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$.
Graduation Semester
2015-5
Type of Resource
text
Permalink
http://hdl.handle.net/2142/78688
Copyright and License Information
Copyright 2015 Pratik Mayur Parekh

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Mechanical Science and Engineering