Login | Register

Analysis of the Dynamic Traveling Salesman Problem with Different Policies


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.

PDF - Accepted Version
PDF - Accepted Version


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.
Date:8 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 On:20 Jun 2012 15:38
Last Modified:20 Jun 2012 15: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


Downloads per month over past year

Back to top Back to top