A Meta-Heuristic Algorithm Combining Between Tabu and Variable Neighborhood Search for the Minimum Latency Problem

• Autorzy: Ban H. B. , Nguyen D. N.

Identyfikatory

DOI

10.3233/FI-2017-1596

• Języki publikacji: EN

Abstrakty

EN

Minimum Latency Problem (MLP) is a class of NP-hard combinatorial optimization problems which has many practical applications. In this paper, we investigate the global structure of the MLP solution space to propose a suitable meta-heuristic algorithm for the problem, which combines Tabu search (TS) and Variable Neighborhood Search (VNS). In the proposed algorithm, TS is used to prevent the search from getting trapped into cycles, and guide VNS to escape local optima. In a cooperative way, VNS is employed to generate diverse neighborhoods for TS. We also introduce a novel neighborhoods’ structure for VNS and present a constant time operation for calculating the latency cost of each neighboring solution. Extensive numerical experiments and comparisons with the state of the art meta-heuristic algorithms in the literature show that the proposed algorithm is highly competitive, providing the new best solutions for several instances.

Słowa kluczowe

EN

minimum latency problem; tabu search; variable neighborhood search

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 156, nr 1
• Strony: 21--41
• Opis fizyczny: Bibliogr. 16 poz., rys., tab., wykr.

Twórcy

autor

Ban H. B.

• School of Information and Communication Technology, Hanoi University of Science and Technology, Hanoi, Vietnam

autor

Nguyen D. N.

• School of Information and Communication Technology, Hanoi University of Science and Technology, Hanoi, Vietnam

Bibliografia

• [1] Blum A, Chalasani P, Coppersmith D, Pulleyblank W, Raghavan P, Sudan M. The Minimum Latency Problem. In: Proc. STOC. ISBN 0-89791-663-8, 1994 pp. 163–171. doi:10.1145/195058.195125.
• [2] Archer A, Levin A, Williamson DP. A Faster, Better Approximation Algorithm for the Minimum Latency Problem. J. SIAM, 2008; 37(5):1472–1498. doi:10.1137/07068151X.
• [3] Arora S, Karakostas G. Approximation Schemes for Minimum Latency Problems. In: Proc. STOC. ISBN 1-58113-067-8, 1999 pp. 688–693. doi:10.1145/301250.301432.
• [4] Chaudhuri K, Godfrey B, Rao S, Talwar K. Paths, trees, and minimum latency tours. In: Proc. FOCS. 2003 pp. 36–45. doi:10.1109/SFCS.2003.1238179.
• [5] Goemans M, Kleinberg J. An improved approximation ratio for the minimum latency problem. Proc. SIAM SODA, 1998; 82(1):111–124. doi:10.1007/BF01585867.
• [6] Wu BY, Huang ZN, Zhan FJ. Exact Algorithms for the Minimum Latency Problem. J. Inf. Process. Lett., 2004; 92(6):303–309. doi:10.1016/j.ipl.2004.09.009.
• [7] Ban HB, Nguyen K, Ngo MC, Nguyen DN. An efficient exact algorithm for Minimum Latency Problem. J. PI, 2013; (10):167–174. doi:10.2201./NiiPi.2013.10.10.
• [8] Ban HB, Nguyen DN. Improved Genetic Algorithm for Minimum Latency Problem. In: Proc. SOICT. ISBN 978-1-4503-0105-3, 2010 pp. 9–15. doi:10.1145/1852611.1852614.
• [9] Mladenovic N, Hansen P. Variable neighborhood search. J. Operations Research, 1997; 24(11):1097–1100. doi:https://doi.org/10.1016/S0305-0548(97)00031-2.
• [10] Salehipour A, Sorensen K, Goos P, Braysy O. Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem. J. Operations Research, 2011; 9(2):189–209. doi:10.1007/s10288-011-0153-0.
• [11] Glover F, Laguna M. Tabu Search. Kluwer Academic Publishers, Norwell, MA, USA, 1997. ISBN 079239965X.
• [12] Feo TA, Resende MGC. Greedy Randomized Adaptive Search Procedures. J. Global Opt., 1995; 6(2): 109–133. doi:10.1007/BF01096763.
• [13] Johnson DS, McGeoch LA. The traveling salesman problem: A case study in local optimization in Local Search in Combinatorial Optimization. E. Aarts and J. K. Lenstra, eds., Norwell, MA, USA, 1997. ISBN 079239965X.
• [14] Reinelt G. TSPLIB, 1999. URL http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95.
• [15] Dongarra JJ. Performance of Various Computers Using Standard Linear Equations Software. J. SIGARCH Comput. Archit. News, 1992; 20(3):22–44. doi:10.1145/141868.141871.
• [16] Silva M, Subramanian A, Vidal T, Ochi L. A simple and effective metaheuristic for the Minimum Latency Problem. J. European Operations Research, 2012; 221(3):513–520. doi:https://doi.org/10.1016/j.ejor.2012.03.044.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).