Breadcrumb

 
 

Analysis of the Dynamic Traveling Salesman Problem with Different Policies

Title:

Analysis of the Dynamic Traveling Salesman Problem with Different Policies

Ravassi, Santiago (2011) Analysis of the Dynamic Traveling Salesman Problem with Different Policies. Masters thesis, Concordia University.

[img]
Preview
PDF - Accepted Version
729Kb
[img]
Preview
PDF - Accepted Version
654Kb

Abstract

We propose and analyze new policies for the traveling salesman problem in a dynamic and stochastic environment (DTSP). The DTSP is defined as follows: demands for service arrive in time according to a Poisson process, are independent and uniformly distributed in a Euclidean region of bounded area, and the time service is zero; the objective is to reduce the time the
server takes to visit to all the present demands for the first time. We start by analyzing the nearest neighbour (NN) policy since it has the best performance for the dynamic vehicle routing problem (DTRP), a closely related problem to the DTSP. We next introduce the random start policy whose efficiency is similar to that of the NN, and we observe that when the random start policy is delayed, it behaves like the DTRP with the NN policy. Finally, we introduce the partitioning policy, and show that, relative to other policies, it reduces the expected time that demands are swept from the region for the first time.

Divisions:Concordia University > Faculty of Arts and Science > Mathematics and Statistics
Item Type:Thesis (Masters)
Authors:Ravassi, Santiago
Institution:Concordia University
Degree Name:M. Sc.
Program:Mathematics
Date:08 December 2011
Thesis Supervisor(s):Popovic, Lea
Keywords:dynamic traveling salesman problem, Markov chains, martingale, ergodic theorem, Monte Carlo simulation, simulated annealing
ID Code:973636
Deposited By:SANTIAGO RAVASSI
Deposited On:20 Jun 2012 11:38
Last Modified:20 Jun 2012 11:38
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Document Downloads

More statistics for this item...

Concordia University - Footer