Login | Register

Analysis of the Dynamic Travelling Salesman Problem with Different Policies

Title:

Analysis of the Dynamic Travelling Salesman Problem with Different Policies

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

[thumbnail of sim41.pdf]
Preview
Text (application/pdf)
sim41.pdf - Accepted Version
746kB
[thumbnail of sim41_pdfa.pdf]
Preview
Text (application/pdf)
sim41_pdfa.pdf - Accepted Version
670kB

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: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 By: SANTIAGO RAVASSI
Deposited On:20 Jun 2012 15:38
Last Modified:21 Oct 2019 14:47
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

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top