A Greedy Look-ahead Heuristic for Combinatorial Optimization: An Application to Vehicle Scheduling with Time Windows
作者:
AtkinsonJ. Ben,
期刊:
Journal of the Operational Research Society
(Taylor Available online 1994)
卷期:
Volume 45,
issue 6
页码: 673-684
ISSN:0160-5682
年代: 1994
DOI:10.1057/jors.1994.105
出版商: Taylor&Francis
关键词: combinatorial optimization;heuristics;look-ahead;time windows;vehicle scheduling
数据来源: Taylor
摘要:
AbstractThis paper describes a greedy heuristic for a class of combinatorial optimization problems; a central feature of the method being a look-ahead capability. The power of the heuristic is demonstrated through experimentation using a large, real-life vehicle scheduling problem with tight time-window constraints. Incorporation of the look-ahead feature gave an improvement in performance that was at least as great as, and in addition to, that which had been obtained through use of the well-known‘savings’method. Based upon the experimental results, some guidelines are proposed for the application of the heuristic to other problems. One of the conclusions is that designers of heuristics should give greater consideration to the inclusion of a look-ahead element in their algorithms.
点击下载:
PDF (5481KB)
返 回