Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/13889
Title: Design and analysis of algorithms for solving some stochastic vehicle routing and scheduling problems
Authors: TENG SUYAN
Keywords: Metaheuristics; Vehicle Routing Problem with Stochastic Demands; Integer L-shaped Method; Time Constrained TSP; Column Generation
Issue Date: 24-Mar-2004
Source: TENG SUYAN (2004-03-24). Design and analysis of algorithms for solving some stochastic vehicle routing and scheduling problems. ScholarBank@NUS Repository.
Abstract: AbstractThis thesis addresses the vehicle routing problem with stochastic demands (VRPSD) and the multi-period time constrained traveling salesman problem (TCTSP). For the VRPSD, following a comparative study among heuristics available in the literature, we present three metaheuristics, simulated annealing, threshold accepting and tabu search for solving it. For the multi-period TCTSP, several heuristics are proposed for the problem in a rolling schedule environment. Then, the problem is formulated as a set-covering problem and its linear programming relaxation is solved to optimality by a column generation scheme to get an upper bound. For small size problems with long service time, the heuristics are compared against the upper bound; for other cases, they are compared among themselves. Finally, the TCTSP is extended to the stochastic case with random travel and service times. The problem is formulated as a stochastic program with recourse and solved by an integer L-shaped algorithm.
URI: http://scholarbank.nus.edu.sg/handle/10635/13889
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
TengSY.pdf1.75 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

242
checked on Dec 18, 2017

Download(s)

213
checked on Dec 18, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.