New Methods for Solving the Minimum Weighted Latency Problem

• Author / Creator

  Ziqi Wei

• In this thesis, I study the methods to solve an NP-hard problem, minimum weighted latency problem (MWLP). The well-studied NP-hard problem minimum latency problem (MLP) can be seen as a special case of MLWP. I introduce the motivation of studying MWLP at the beginning. After describing the existing methods, I propose a Mixed Integer Programming algorithm for MWLP. As for the main body of this thesis, I study the heuristic algorithms for MWLP. I use five different classic heuristics to test the effectiveness of heuristic when solving MWLP. After that, two new meta-heuristics are proposed and tested. Both of them produce better results compared to the classic ones. At last, I describe two real-world applications for this problem. MWLP model is tested and proved effective for both applications.

• Subjects / Keywords

  • Heuristic
  • P system
  • MWLP
  • VND

• Graduation date

  Fall 2018

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/R3QV3CK85

• License

  Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.