Solving the shortest route cut and fill problem using simulated annealing.

Wakefield, R, Vaughan, D, Jacobson, S, Sewell, E and Henderson, D 2003, 'Solving the shortest route cut and fill problem using simulated annealing.', European Journal of Operational Research, vol. 145, no. 1, pp. 72-84.


Document type: Journal Article
Collection: Journal Articles

Title Solving the shortest route cut and fill problem using simulated annealing.
Author(s) Wakefield, R
Vaughan, D
Jacobson, S
Sewell, E
Henderson, D
Year 2003
Journal name European Journal of Operational Research
Volume number 145
Issue number 1
Start page 72
End page 84
Total pages 13
Publisher Elsevier
Abstract This paper introduces the shortest route cut and fill problem (SRCFP). The SRCFP is a NP-hard discrete optimization problem for leveling a construction project site, where the objective is to find a vehicle route that minimizes the total distance traveled by a single earthmoving vehicle between cut and fill locations. An optimal vehicle route is a route that minimizes the total haul distance that a single earthmoving vehicle travels. Simulated annealing algorithms are formulated to address the SRCFP. To assess the effectiveness of simulated annealing on the SRCFP, a greedy algorithm is constructed to compute an upper bound and the Held-Karp 1-tree lower bound is used to compute a lower bound. Extensive computational results are reported using several randomly generated instances of the SRCFP.
Subject Information Systems not elsewhere classified
Keyword(s) heuristics
simulated annealing
traveling salesperson problem
local search algorithms
shortest route problem.
DOI - identifier 10.1016/S0377-2217(02)00206-0
Copyright notice © 2002 Elsevier Science B.V. All rights reserved.
ISSN 0377-2217
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 25 times in Scopus Article | Citations
Altmetric details:
Access Statistics: 223 Abstract Views  -  Detailed Statistics
Created: Mon, 06 Dec 2010, 11:15:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us