research-article

Improved genetic algorithm for minimum latency problem

Authors:

Ban Ha Bang,

Nguyen Duc NghiaAuthors Info & Claims

SoICT '10: Proceedings of the 1st Symposium on Information and Communication Technology

Pages 9 - 15

https://doi.org/10.1145/1852611.1852614

Published: 27 August 2010 Publication History

Get Access

Abstract

Minimum Latency Problem (MLP), also known as traveling repairman problem, in general case, is proved to be NP--hard. This paper presents several new techniques based on the scheme of the genetic algorithm for solving MLP. The experimental results on the proposed algorithm show that it gives the approximation ratio which is about 1.9 times higher than the lower bound on the optimal solution.

References

[1]

S. Sahni, T. Gonzalez. P-complete approximation problem. Journal of the ACM 23 (1976) 555--565.

Digital Library

Google Scholar

[2]

A. Blum, P. Chalasani, D. Coppersmith, W. Pulleyblank, P. Raghavan, M. Sudan. The minimum latency problem. Proceedings of the 26th ACM Symposium on the Theory of Computing (Montreal, Quebec, Canada, 1994), 163--171.

Digital Library

Google Scholar

[3]

Wu, B. Y, Z.-N. Huang and F.-J. Zhan. Exact algorithms for the minimum latency problem. Information Processing Letters, vol. 92(6), (2004) 303--309.

Digital Library

Google Scholar

[4]

S. Arora and G. Karakostas. Approximation schemes for minimum latency problems. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (STOC'99), pages 688--693, New York, May 1999. Association for Computing Machinery.

Digital Library

Google Scholar

[5]

M. Goemans and J. Kleinberg. An improved approximation ratio for the minimum latency problem. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 152--158, New York/Philadelphia, Jan. 28--30 1996. ACM/SIAM.

Digital Library

Google Scholar

[6]

Aaron Archer, Asaf Levin, David Williamson. A Faster, Better Approximation Algorithm for the Minimum Latency Problem. Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 2003.

Digital Library

Google Scholar

[7]

Kamalika Chaudhuri, Brighten Goldfrey, Satish Rao, and Kunai Talwar. Path, Tree and minimum latency tour. In Proceedings of the 44^th Annual IEEE Symposium on the Foundations of Computer Science, (2003) 36--45.

Digital Library

Google Scholar

[8]

Aaron Archer and Anna Blasiak. Improved approximation algorithms for the minimum latency problem via prize-collecting stroll. In proceedings of the Symposium on Discrete Algorithms (SODA), January 17--19, 2010.

Digital Library

Google Scholar

[9]

R. J. V Wiel and N. V. Sahinidis. Heuristic bounds and test problem generation for the time dependent traveling salesman problem. Transportation Science, 29(2), 1995.

Google Scholar

[10]

Ban Ha Bang, Nguyen Duc Nghia. Genentic algorithm for solving Minimum Latency Problem. Jounal of Science & Technology Technical Universities, 7-1, 2009, ISSN 0869-3980.

Google Scholar

[11]

M. Rocha and J. Neves. Preventing Premature Convergence to Local Optima in Genetic Algorithms via Random Offspring Generation. Multiple Approaches to Intelligent Systems, 12th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, IEA/AIE-99, Cairo, Egypt, 1999.

Digital Library

Google Scholar

[12]

C. Nilsson. Heuristics for the Traveling Salesman Problem. Theoretica Computer Science Reports, Linkoping university, 2003 - cs.uwaterloo.ca.

Google Scholar

[13]

Grefenstette J et al. Genetic algorithms for the traveling salesman problem. Proc. Intern. Conf. of Genetic Algorithms and their applications, pp. 160--165, 1985.

Digital Library

Google Scholar

[14]

http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95

Google Scholar

Cited By

View all

Önder Uzun GKara İ(2021)New formulations for the traveling repairman problem with time windowsExpert Systems with Applications: An International Journal10.1016/j.eswa.2021.114863176:COnline publication date: 15-Aug-2021
https://dl.acm.org/doi/10.1016/j.eswa.2021.114863
Ban H(2021)A metaheuristic for the delivery man problem with time windowsJournal of Combinatorial Optimization10.1007/s10878-021-00716-241:4(794-816)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1007/s10878-021-00716-2
Ban H(2019)An efficient two-phase metaheuristic algorithm for the time dependent traveling Salesman problemRAIRO - Operations Research10.1051/ro/201900653:3(917-935)Online publication date: 10-Jul-2019
https://doi.org/10.1051/ro/2019006
Show More Cited By

Index Terms

Improved genetic algorithm for minimum latency problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
  2. Mathematical software

Recommendations

An improved genetic algorithm with conditional genetic operators and its application to set-covering problem

The genetic algorithm (GA) is a popular, biologically inspired optimization method. However, in the GA there is no rule of thumb to design the GA operators and select GA parameters. Instead, trial-and-error has to be applied. In this paper we present an ...
Solving the Graph Planarization Problem Using an Improved Genetic Algorithm

An improved genetic algorithm for solving the graph planarization problem is presented. The improved genetic algorithm which is designed to embed a graph on a plane, performs crossover and mutation conditionally instead of probability. The improved ...
An improved genetic algorithm encoded by adaptive degressive ary number

Genetic algorithm (GA) is a random search algorithm, which has been commonly used to solve optimization problems. A new encoding method of GA, adaptive degressive ary number encoding, is proposed in this paper. This paper firstly introduces the N-ary ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SoICT '10: Proceedings of the 1st Symposium on Information and Communication Technology

August 2010

186 pages

ISBN:9781450301053

DOI:10.1145/1852611

Conference Chair:
Nguyen Trong Giang
Hanoi University of Science and Technology, Vietnam
,
General Chairs:
Nguyen Thuc Hai
Hanoi University of Science and Technology, Vietnam
,
Huynh Quyet Thang
Hanoi University of Science and Technology, Vietnam

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 August 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoICT '10

SoICT '10: Symposium on Information and Communication Technology 2010

August 27 - 28, 2010

Hanoi, Vietnam

Acceptance Rates

Overall Acceptance Rate 147 of 318 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
240
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Önder Uzun GKara İ(2021)New formulations for the traveling repairman problem with time windowsExpert Systems with Applications: An International Journal10.1016/j.eswa.2021.114863176:COnline publication date: 15-Aug-2021
https://dl.acm.org/doi/10.1016/j.eswa.2021.114863
Ban H(2021)A metaheuristic for the delivery man problem with time windowsJournal of Combinatorial Optimization10.1007/s10878-021-00716-241:4(794-816)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1007/s10878-021-00716-2
Ban H(2019)An efficient two-phase metaheuristic algorithm for the time dependent traveling Salesman problemRAIRO - Operations Research10.1051/ro/201900653:3(917-935)Online publication date: 10-Jul-2019
https://doi.org/10.1051/ro/2019006
Ban H(2019)A RVND+ILS Metaheuristic to Solve the Delivery Man Problem with Time WindowsComputational Data and Social Networks10.1007/978-3-030-34980-6_6(63-69)Online publication date: 11-Nov-2019
https://doi.org/10.1007/978-3-030-34980-6_6

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

An improved genetic algorithm with conditional genetic operators and its application to set-covering problem

Solving the Graph Planarization Problem Using an Improved Genetic Algorithm

An improved genetic algorithm encoded by adaptive degressive ary number