Ravassi, Santiago (2011) Analysis of the Dynamic Traveling Salesman Problem with Different Policies. Masters thesis, Concordia University.
sim41.pdf - Accepted Version
sim41_pdfa.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)|
|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|
|Deposited By:||SANTIAGO RAVASSI|
|Deposited On:||20 Jun 2012 15:38|
|Last Modified:||05 Nov 2016 01:58|
Repository Staff Only: item control page