|
Title:
|
SOLVING A CLASS OF TIME-DEPENDENT COMBINATORIAL OPTIMIZATION PROBLEMS WITH ABSTRACTION, TRANSFORMATION AND SIMULATED ANNEALING |
|
Author(s):
|
Rigoberto Diaz , Lixin Tao , Michael Gargano , Fred Grossman , Michael W. Tao |
|
ISBN:
|
972-98947-3-6 |
|
Editors:
|
Nuno Guimarães and Pedro Isaías |
|
Year:
|
2004 |
|
Edition:
|
Single |
|
Keywords:
|
Time-dependent combinatorial optimization problems, problem transformation, meta-heuristics, simulated annealing. |
|
Type:
|
Full Paper |
|
First Page:
|
1535 |
|
Last Page:
|
1542 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
A class of intractable time-dependent problems is identified and abstracted into a mathematical model. Based on some critical observation on the model, a problem transformation algorithm is proposed to significantly shrink the solution space while maintaining equivalency to the original problem. Simulated annealing is adopted as the base of the solution strategy. Comprehensive experiments are conducted to study the sensitivity of the algorithm to the values of its multiple parameters. Extensive performance evaluation shows that the proposed algorithm significantly outperforms the best published alternative algorithms for the same problem class in terms of both solution quality and running time. |
|
|
|
|
|
|
