Please use this identifier to cite or link to this item:
Title: Design and analysis of algorithms for solving some stochastic vehicle routing and scheduling problems
Keywords: Metaheuristics; Vehicle Routing Problem with Stochastic Demands; Integer L-shaped Method; Time Constrained TSP; Column Generation
Issue Date: 24-Mar-2004
Citation: 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.
Appears in Collections:Ph.D Theses (Open)

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



Page view(s)

checked on May 23, 2019


checked on May 23, 2019

Google ScholarTM


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