City Research Online

Abstract

Local search algorithms are used to produce solutions to combinatorial logistics problems such as the vehicle routing problem. Where the algorithms aim to minimise the number of vehicles needed to deliver goods.

Local search creates a first solution and that solution is the best until the heuristic finds a better one, hence it is argued that all existing local search algorithms make a series of improvements. Different local search algorithms locate these improvements with different improvement location mechanisms. Local Search also gives preference to using some improvements rather than others. To make these preference choices different local search algorithms use different improvement preference mechanisms.

Current local search algorithms intertwine improvement location and improvement preference mechanisms, making it difficult to identify if they are both having a positive impact and the scale of the impact. The thesis hypothesis states “Distinguishing between improvement location and improvement preference is feasible and useful when creating local search algorithms”. Distinguishing between improvement location and preference produced results that suggest how local search methods in current use can be improved.

The experiments compare methods of locating improvements and improvement preference. They use both whole non-improving solutions and partial solution changes, similar to Lin-Kemighan, to locate improvements. They also compare giving preference to small improvements or large improvements. The comparisons are done using the Solomon vehicle routing problem benchmarks. Using partial solution changes to locate improvements and giving preference to small improvements typically gave the highest quality solutions at the cost of doubling execution time. The results also show which methods of location and preference do well when only a small amount of execution time is available.

Publication Type:	Thesis (Doctoral)
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments:	School of Science & Technology > Computer Science School of Science & Technology > School of Science & Technology Doctoral Theses Doctoral Theses

Export

Downloads