Return to search

A Cycle-Trade Heuristic for the Weighted k-Chinese Postman Problem

This study aims to answer whether a heuristic that trades cycles between the tours in a solution would show good results when trying to solve the Weighted k-Chinese Postman Problem for undirected graphs, of varying size, representing neighbourhoods in Sweden.A tabu search heuristic was implemented with each iteration consisting of giving a cycle from the most expensive tour to the cheapest. The heuristic performed increasingly well for graphs of increasing size, although the solution quality decreased when increasing the number of tours to be used in the solution. It is suspected that the cause for this behavior is due to the heuristic only giving cycles from the most expensive tour, not considering trading cycles from other tours in the solution. It is believed that a heuristic considering more than only the most expensive tour when trading cycles would produce even better solutions.

Identiferoai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-153631
Date January 2018
CreatorsHölscher, Anton
PublisherLinköpings universitet, Artificiell intelligens och integrerade datorsystem
Source SetsDiVA Archive at Upsalla University
LanguageEnglish
Detected LanguageEnglish
TypeStudent thesis, info:eu-repo/semantics/bachelorThesis, text
Formatapplication/pdf
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.002 seconds