Log in

Relevant bibliographies by topics / Lin-Kernighan Algorithm / Journal articles

To see the other types of publications on this topic, follow the link: Lin-Kernighan Algorithm.

Journal articles on the topic 'Lin-Kernighan Algorithm'

Author: Grafiati

Published: 3 June 2025

Last updated: 31 July 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 46 journal articles for your research on the topic 'Lin-Kernighan Algorithm.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Liu, Yu Zhong, and Hua Ping Yu. "A Dynamic Edge Exchanged Ant Colony Algorithm for TSP Problem." Applied Mechanics and Materials 687-691 (November 2014): 1608–11. http://dx.doi.org/10.4028/www.scientific.net/amm.687-691.1608.

Full text

Abstract:

Aimed at solving premature convergence and low speed in heuristic algorithms for TSP problems, this paper analyzed the principle of Max-Min Ant colony algorithm (MMAS) and Lin-Kernighan algorithm, then proposed a dynamic exchange of Max-Min Ant colony algorithm (MMAS-LK). The new algorithm used MMAS to initially a set of the solutions in the early state, then utilized the improved Lin-Kernighan algorithm for local optimization, and dynamic adjustment parameters according to the process of computing avoid falling into local optimum. The simulation results showed that the proposed algorithm comp

APA, Harvard, Vancouver, ISO, and other styles

2

Mann, Zoltán, András Orbán, and Viktor Farkas. "Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning." International Journal of Applied Mathematics and Computer Science 17, no. 2 (2007): 249–67. http://dx.doi.org/10.2478/v10006-007-0022-3.

Full text

Abstract:

Evaluating the Kernighan-Lin Heuristic for Hardware/Software PartitioningIn recent years, several heuristics have been proposed for the hardware/software partitioning problem. One of the most promising directions is the adaptation of the Kernighan-Lin algorithm. The Kernighan-Lin heuristic was originally developed for circuit partitioning, but it has been adapted to other domains as well. Moreover, numerous improvements have been suggested so that now several variants of the original algorithm exist. The aim of this paper is to systematically evaluate the possibilities of applying the Kernigha

APA, Harvard, Vancouver, ISO, and other styles

3

Crişan, Gloria Cerasela, Camelia-M. Pintea, Petrică C. Pop, and Oliviu Matei. "Economical connections between several European countries based on TSP data." Logic Journal of the IGPL 28, no. 1 (2019): 33–44. http://dx.doi.org/10.1093/jigpal/jzz069.

Full text

Abstract:

Abstract A fluent economical collaboration between countries is a major need. European flows of trade and people are supported by efficient connections between main localities from a geographic region, in many cases overriding national borders. This paper introduces three traveling salesmen problem instances based on freely available geographic coordinates of the main cities of France, Portugal and Spain. These instances are unified, generating other four larger instances: three with all pairs of countries and one instance with the settlements from all the three countries. The study includes a

APA, Harvard, Vancouver, ISO, and other styles

4

Chua, C. B., and Kan Chen. "Learning Algorithm for the Uniform Graph Partitioning Problem." International Journal of Modern Physics C 09, no. 02 (1998): 331–39. http://dx.doi.org/10.1142/s012918319800025x.

Full text

Abstract:

We study the uniform graph partitioning problem using the learning algorithm proposed by one of us. We discuss the characteristics of the learning algorithm and compare the performance of the algorithm empirically with the Kernighan–Lin algorithm on a range of instances. Even with a simple implementation, the learning algorithm is capable of producing very good results.

APA, Harvard, Vancouver, ISO, and other styles

5

De Carvalho, Emerson Bezerra, Elizabeth Ferreira Gouvêa Goldbarg, and Marco Cesar Goldbarg. "A Multi-objective Version of the Lin-Kernighan Heuristic for the Traveling Salesman Problem." Revista de Informática Teórica e Aplicada 25, no. 1 (2018): 48. http://dx.doi.org/10.22456/2175-2745.76452.

Full text

Abstract:

The Lin and Kernighan’s algorithm for the single objective Traveling Salesman Problem (TSP) is one of the most efficient heuristics for the symmetric case. Although many algorithms for the TSP were extended to the multi-objective version of the problem (MTSP), the Lin and Kernighan’s algorithm was still not fully explored. Works that applied the Lin and Kernighan’s algorithm for the MTSP were driven to weighted sum versions of the problem. We investigate the LK from a Pareto dominance perspective. The multi-objective LK was implemented within two local search schemes and applied to 2 to 4-obje

APA, Harvard, Vancouver, ISO, and other styles

6

WANG, Dong, Ya LI, Chen WU, and Dong-mei LIN. "New strategy for improving performance of chained Lin-Kernighan algorithm." Journal of Computer Applications 32, no. 2 (2013): 425–27. http://dx.doi.org/10.3724/sp.j.1087.2012.00425.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Ezhilarasi, G. A., and K. S. Swarup. "Network decomposition using Kernighan–Lin strategy aided harmony search algorithm." Swarm and Evolutionary Computation 7 (December 2012): 1–6. http://dx.doi.org/10.1016/j.swevo.2012.07.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Ulyanov, M. V., and M. I. Fomichev. "Research of Features of the Combined Algorithm for Solving the Asymmetric Traveling Salesman Problem." INFORMACIONNYE TEHNOLOGII 27, no. 1 (2021): 3–8. http://dx.doi.org/10.17587/it.27.3-8.

Full text

Abstract:

The exact algorithm that implements the Branch and Boimd method with precomputed tour which is calculated by Lin-Kernighan-Helsgaun metaheuristic algorithm for solving the Traveling Salesman Problem is concerned here. Reducing the number of decision tree nodes, which are created by the Branches and Bound method, due to a "good" precomputed tour leads to the classical balancing dilemma of time costs. A tour that is close to optimal one takes time, even when the Lin-Kernighan-Helsgaun algorithm is used, however it reduces the working time of the Branch and Bound method. The problem of determinin

APA, Harvard, Vancouver, ISO, and other styles

9

郁, 湧. "Research on the Improvement of Kernighan-Lin Algorithm for Graph Partitioning." Computer Science and Application 09, no. 05 (2019): 849–54. http://dx.doi.org/10.12677/csa.2019.95095.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Wang, Shi Gang, Yu Juan Wang, Guan Xiong Wu, and Yi Li Fu. "Application of Intelligence Fusion Algorithm in Path Optimization Problem." Applied Mechanics and Materials 151 (January 2012): 632–36. http://dx.doi.org/10.4028/www.scientific.net/amm.151.632.

Full text

Abstract:

In CAD/CAM integration system, the problem of the path optimization to be thorough researched. Through numerical describe of information elements, by using graph theory of traveling salesman problem，set up the mathematical model of path optimization problem. Based on ant colony algorithm and lin-kernighan (LK) algorithm, an intelligence fusion algorithm is put forward. With group of holes processing as an example, the group of holes drilling tool path of optimized, and realize the CAD/CAM many features of optimization, which greatly improve the processing precision and efficiency.

APA, Harvard, Vancouver, ISO, and other styles

11

Zheng, Jiongzhi, Kun He, Jianrong Zhou, Yan Jin, and Chu-Min Li. "Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 14 (2021): 12445–52. http://dx.doi.org/10.1609/aaai.v35i14.17476.

Full text

Abstract:

We address the Traveling Salesman Problem (TSP), a famous NP-hard combinatorial optimization problem. And we propose a variable strategy reinforced approach, denoted as VSR-LKH, which combines three reinforcement learning methods (Q-learning, Sarsa and Monte Carlo) with the well-known TSP algorithm, called Lin-Kernighan-Helsgaun (LKH). VSR-LKH replaces the inflexible traversal operation in LKH, and lets the program learn to make choice at each search step by reinforcement learning. Experimental results on 111 TSP benchmarks from the TSPLIB with up to 85,900 cities demonstrate the excellent per

APA, Harvard, Vancouver, ISO, and other styles

12

Zhang, Zhenqiang, Sile Ma, and Xiangyuan Jiang. "Research on Multi-Objective Multi-Robot Task Allocation by Lin–Kernighan–Helsgaun Guided Evolutionary Algorithms." Mathematics 10, no. 24 (2022): 4714. http://dx.doi.org/10.3390/math10244714.

Full text

Abstract:

Multi-robot task allocation (MRTA) and route planning are crucial for a large-scale multi-robot system. In this paper, the problem is formulated to minimize the total energy consumption and overall task completion time simultaneously, with some constraints taken into consideration. To represent a solution, a novel one-chromosome representation technique is proposed, which eases the consequent genetic operations and the construction of the cost matrix. Lin–Kernighan–Helsgaun (LKH), a highly efficient sub-tour planner, is employed to generate prophet generation beforehand as well as guide the ev

APA, Harvard, Vancouver, ISO, and other styles

13

Helsgaun, Keld. "Solving the equality generalized traveling salesman problem using the Lin–Kernighan–Helsgaun Algorithm." Mathematical Programming Computation 7, no. 3 (2015): 269–87. http://dx.doi.org/10.1007/s12532-015-0080-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Majid, Yousefikhoshbakht, and Dolatnejad Azam. "BRAIN Journal - An Efficient Combined Meta-Heuristic Algorithm for Solving the Traveling Salesman Problem." BRAIN - Broad Research in Artificial Intelligence and Neuroscience 7, no. 3 (2016): 125–38. https://doi.org/10.5281/zenodo.1044961.

Full text

Abstract:

ABSTRACT The traveling salesman problem (TSP) is one of the most important NP-hard Problems and probably the most famous and extensively studied problem in the field of combinatorial optimization. In this problem, a salesman is required to visit each of n given nodes once and only once, starting from any node and returning to the original place of departure. This paper presents an efficient evolutionary optimization algorithm developed through combining imperialist competitive algorithm and lin-kernighan algorithm called (MICALK) in order to solve the TSP. The MICALK is tested on 44 TSP instan

APA, Harvard, Vancouver, ISO, and other styles

15

Chen, Haorui. "Optimization Methods of Multi-Core Embedded System." Highlights in Science, Engineering and Technology 71 (November 28, 2023): 153–62. http://dx.doi.org/10.54097/hset.v71i.12686.

Full text

Abstract:

With the development of the Internet of everything technology, embedded system has become one of the most common computing systems. Embedded system has high portability, but there are often stronger limitations in energy consumption, real-time and so on. In this work, have improved some traditional optimization algorithms, and finally get a task scheduling sequence, which can reduce the total execution time and cost of the task. Firstly, the multi-module division is used to divide multiple tasks into different modules, improve the classical Kernighan-Lin (KL) algorithm and clustering algorithm

APA, Harvard, Vancouver, ISO, and other styles

16

Kuang, Linghong, Kunliang Si, and Jing Zhang. "Anonymous group structure algorithm based on community structure." PeerJ Computer Science 10 (September 18, 2024): e2244. http://dx.doi.org/10.7717/peerj-cs.2244.

Full text

Abstract:

A social network is a platform that users can share data through the internet. With the ever-increasing intertwining of social networks and daily existence, the accumulation of personal privacy information is steadily mounting. However, the exposure of such data could lead to disastrous consequences. To mitigate this problem, an anonymous group structure algorithm based on community structure is proposed in this article. At first, a privacy protection scheme model is designed, which can be adjusted dynamically according to the network size and user demand. Secondly, based on the community char

APA, Harvard, Vancouver, ISO, and other styles

17

Wang, Bai Lin, Tie Ke Li, and Heng Bo Ge. "Neighborhood Search Heuristic for 2-Machine Flowshop Scheduling Problem with Limited Waiting Times." Applied Mechanics and Materials 411-414 (September 2013): 1894–97. http://dx.doi.org/10.4028/www.scientific.net/amm.411-414.1894.

Full text

Abstract:

The flowshop scheduling problem with limited waiting time constraints widely exists in the production process featured by high temperature and continuity. The constraints require that the waiting time of any job between two consecutive machines is not greater than a given upper bound. In this paper, the problem with two-machine settings and the objective of makespan is studied. First, a lower bound and some characters of minimum makespan are analyzed. Further, a solving idea is suggested by a transformation into an asymmetry TSP. Based on these characteristics and the solving idea, a neighborh

APA, Harvard, Vancouver, ISO, and other styles

18

Tinós, Renato, Darrell Whitley, and Gabriela Ochoa. "A New Generalized Partition Crossover for the Traveling Salesman Problem: Tunneling between Local Optima." Evolutionary Computation 28, no. 2 (2020): 255–88. http://dx.doi.org/10.1162/evco_a_00254.

Full text

Abstract:

Generalized Partition Crossover (GPX) is a deterministic recombination operator developed for the Traveling Salesman Problem. Partition crossover operators return the best of [Formula: see text] reachable offspring, where [Formula: see text] is the number of recombining components. This article introduces a new GPX2 operator, which finds more recombining components than GPX or Iterative Partial Transcription (IPT). We also show that GPX2 has O([Formula: see text]) runtime complexity, while also introducing new enhancements to reduce the execution time of GPX2. Finally, we experimentally demons

APA, Harvard, Vancouver, ISO, and other styles

19

Ulyanov, M. V., and M. I. Fomichev. "Combined Algorithm for Solving the Asymmetric Traveling Salesman Problem as Applied to Transport Logistics Problems." Informacionnye Tehnologii 28, no. 3 (2022): 141–47. http://dx.doi.org/10.17587/it.28.141-147.

Full text

Abstract:

The traveling salesman problem is to find a Hamiltonian cycle with the minimum sum of the weights of arcs in a complete oriented asymmetric graph. Despite its simple formulation, the traveling salesman problem is NP-hard. The Branch and Bound method is the basis of the most time efficient algorithm for solving the traveling salesman problem, delivering the exact solution. However, for a number of applied problems, the time to obtain a solution using this algorithm is practically unacceptable. Despite the majority of heuristic algorithms developed for the traveling salesman problem, for some ap

APA, Harvard, Vancouver, ISO, and other styles

20

A., Samuel, Bosede A., and John C. "Towards Solving Travelling Salesperson Problem using Hybrid of Genetic Algorithm and Lin-Kernighan Algorithm: A Comparative Evaluation with Neural Network Model." International Journal of Computer Applications 179, no. 7 (2017): 11–19. http://dx.doi.org/10.5120/ijca2017915953.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Semenkina, O. E., and E. A. Popov. "Nature-Inspired Algorithms for Solving a Hierarchical Scheduling Problem in Short-Term Production Planning." Herald of the Bauman Moscow State Technical University. Series Instrument Engineering, no. 3 (126) (June 2019): 46–63. http://dx.doi.org/10.18698/0236-3933-2019-3-46-63.

Full text

Abstract:

The paper deals with the scheduling problem relevant in many fields, such as project management, lesson scheduling or production scheduling. In practice, using optimisation methods to solve the scheduling problem is considerably restricted by the fact that in the real world, problem statement involves high dimensionality, high production process complexity and many nontrivial constraints. These specifics mean that even merely searching for a feasible solution becomes a difficult task. Consequently, in order to solve the problem in a reasonable amount of time it is necessary to use problem-orie

APA, Harvard, Vancouver, ISO, and other styles

22

Yan, Junjie, Yichen Xu, Haohao Yuan, and Chunhua Xue. "UAV Onboard STAR-RIS Service Enhancement Mechanism Based on Deep Reinforcement Learning." Sensors 25, no. 6 (2025): 1943. https://doi.org/10.3390/s25061943.

Full text

Abstract:

UAVs and reconfigurable intelligent surfaces (RISs) have emerged as promising solutions to enhance communication coverage and performance. However, existing studies primarily focus on optimizing the amplitude and phase shift of a STAR-RIS without considering the impact of varying UAV hovering angles on signal reflection and transmission. In this paper, we propose a novel STAR-RIS-assisted UAV service enhancement mechanism that dynamically adjusts reflection/transmission regions based on the real-time user distribution, significantly improving the channel quality for both edge and occluded user

APA, Harvard, Vancouver, ISO, and other styles

23

Ezhilarasi, G. A., and K. S. Swarup. "Corrigendum to “Network decompostion using Kernighan–Lin strategy aided harmony search algorithm” [Swarm Evol. Comput. 7C (2012) 1–6]." Swarm and Evolutionary Computation 11 (August 2013): 55. http://dx.doi.org/10.1016/j.swevo.2013.05.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Wang, Yu-ting, Jun-qing Li, Kai-zhou Gao, and Quan-ke Pan. "Memetic Algorithm based on Improved Inver–over operator and Lin–Kernighan local search for the Euclidean traveling salesman problem." Computers & Mathematics with Applications 62, no. 7 (2011): 2743–54. http://dx.doi.org/10.1016/j.camwa.2011.06.063.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Huang, Xianfei, and Gaocai Wang. "Saving Energy and High-Efficient Inspection to Offshore Wind Farm by the Comprehensive-Assisted Drone." International Journal of Energy Research 2024 (February 8, 2024): 1–14. http://dx.doi.org/10.1155/2024/6209170.

Full text

Abstract:

Facing the method’s limitations of the existing drone inspection on offshore wind farms, we adopt a new comprehensive-assisted drone automated inspection scheme under the comprehensive assistance. Our objectives are saving energy and high-efficient inspection. The such inspection is used to formulating the two mixed-integer nonlinear programming problems based on two new drone basic models: the mobile edge computing driven drone computation system model and the drone flight model. To solve the problems, we split them into four subproblems, and a new improved heuristic algorithm is created to a

APA, Harvard, Vancouver, ISO, and other styles

26

MOODY, JAMES, and PETER J. MUCHA. "Portrait of Political Party Polarization." Network Science 1, no. 1 (2013): 119–21. http://dx.doi.org/10.1017/nws.2012.3.

Full text

Abstract:

To find out, we measure co-voting similarity networks in the US Senate and trace individual careers over time. Standard network visualization tools fail on dense highly clustered networks, so we used two aggregation strategies to clarify positional mobility over time. First, clusters of Senators who often vote the same way capture coalitions, and allow us to measure polarization quantitatively through modularity (Newman, 2006; Waugh et al., 2009; Poole, 2012). Second, we use role-based blockmodels (White et al., 1976) to identify role positions, identifying sets of Senators with highly similar

APA, Harvard, Vancouver, ISO, and other styles

27

Kovács, László, László Iantovics, and Dimitris Iakovidis. "IntraClusTSP—An Incremental Intra-Cluster Refinement Heuristic Algorithm for Symmetric Travelling Salesman Problem." Symmetry 10, no. 12 (2018): 663. http://dx.doi.org/10.3390/sym10120663.

Full text

Abstract:

The Symmetric Traveling Salesman Problem (sTSP) is an intensively studied NP-hard problem. It has many important real-life applications such as logistics, planning, manufacturing of microchips and DNA sequencing. In this paper we propose a cluster level incremental tour construction method called Intra-cluster Refinement Heuristic (IntraClusTSP). The proposed method can be used both to extend the tour with a new node and to improve the existing tour. The refinement step generates a local optimal tour for a cluster of neighbouring nodes and this local optimal tour is then merged into the global

APA, Harvard, Vancouver, ISO, and other styles

28

Kovács, László, Laszlo Barna Iantovics, and Dimitris Iakovidis. "IntraClusTSP—An Incremental Intra-Cluster Refinement Heuristic Algorithm for Symmetric Travelling Salesman Problem." Symmetry 10, no. 12 (2018): 663. https://doi.org/10.3390/sym10120663.

Full text

Abstract:

The Symmetric Traveling Salesman Problem (sTSP) is an intensively studied NP-hard problem. It has many important real-life applications such as logistics, planning, manufacturing of microchips and DNA sequencing. In this paper we propose a cluster level incremental tour construction method called Intra-cluster Refinement Heuristic (IntraClusTSP). The proposed method can be used both to extend the tour with a new node and to improve the existing tour. The refinement step generates a local optimal tour for a cluster of neighbouring nodes and this local optimal tour is then merged into the global

APA, Harvard, Vancouver, ISO, and other styles

29

Naganawa, Hisatoshi, Enna Hirata, Nailah Firdausiyah, and Russell G. Thompson. "Logistics Hub and Route Optimization in the Physical Internet Paradigm." Logistics 8, no. 2 (2024): 37. http://dx.doi.org/10.3390/logistics8020037.

Full text

Abstract:

Background: The global logistics industry is facing looming challenges related to labor shortages and low-efficiency problems due to the lack of logistics facilities and resources, resulting in increased logistics delays. The Physical Internet is seen as a way to take logistics into the next generation of transformation. This research proposes a Physical Internet-enabled system that allows multiple companies to efficiently share warehouses and trucks to achieve operational efficiency and reduce CO2 emissions. Methods: We propose a novel demography-weighted combinatorial optimization model util

APA, Harvard, Vancouver, ISO, and other styles

30

Leapheng, Uon, Calvin Alexander Ng, Francis Gregory Ng, Sharaful-Ilmi Paduman, and Alvin Chua. "A Novel Approach to Optimize Numerical Control Codes Using a Systematic Block Management Method." International Journal of Automation and Smart Technology 9, no. 1 (2025): 23–32. https://doi.org/10.5875/ausmt.v9i1.1728.

Full text

Abstract:

The numerical control (NC) codes generated from Computer Aided Manufacturing (CAM) software follow the sequence of adding elements to the design. As an alternative, it would be quite beneficial in cost-reduction to optimize the manufacturing sequence to minimize the run time. Accordingly, this paper introduces a novel approach to optimize the numerical control codes generated from a CAM software package using a systematic block management method. To improve the drilling sequence, contours are also considered as block entities in a traveling salesman problem (TSP) with modifications to systemat

APA, Harvard, Vancouver, ISO, and other styles

31

Leapheng, Uon, Calvin Alexander Ng, Francis Gregory Ng, Sharaful-Ilmi Paduman, and Alvin Chua. "A Novel Approach to Optimize Numerical Control Codes Using a Systematic Block Management Method." International Journal of Automation and Smart Technology 9, no. 1 (2025): 23–32. https://doi.org/10.5875/me442d79.

Full text

Abstract:

The numerical control (NC) codes generated from Computer Aided Manufacturing (CAM) software follow the sequence of adding elements to the design. As an alternative, it would be quite beneficial in cost-reduction to optimize the manufacturing sequence to minimize the run time. Accordingly, this paper introduces a novel approach to optimize the numerical control codes generated from a CAM software package using a systematic block management method. To improve the drilling sequence, contours are also considered as block entities in a traveling salesman problem (TSP) with modifications to systemat

APA, Harvard, Vancouver, ISO, and other styles

32

Rodionov, Alexey, and Tulkin Matkurbanov. "Planning UAV Flight Trajectories for Monitoring Large Areas." Informatics and Automation 24, no. 3 (2025): 791–827. https://doi.org/10.15622/ia.24.3.3.

Full text

Abstract:

Modern agriculture covers vast areas, and effective monitoring of these territories plays a key role in precision farming. Wireless sensor networks are widely used to obtain real-time information on the condition of agricultural crops. However, manually collecting data from such sensors (deployed across a sensor network) is challenging. At the same time, unmanned aerial vehicles (UAVs) are increasingly used to provide automated and highly accurate data collection. This article addresses the problem of constructing an optimal UAV trajectory to efficiently collect data from distributed sensor no

APA, Harvard, Vancouver, ISO, and other styles

33

Bevilaqua, Andre, Diego Bevilaqua, and Keiji Yamanaka. "Parallel island based Memetic Algorithm with Lin–Kernighan local search for a real-life Two-Echelon Heterogeneous Vehicle Routing Problem based on Brazilian wholesale companies." Applied Soft Computing 76 (March 2019): 697–711. http://dx.doi.org/10.1016/j.asoc.2018.12.036.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Tüű-Szabó, Boldizsár, Péter Földesi, and László T. Kóczy. "An Efficient Tour Construction Heuristic for Generating the Candidate Set of the Traveling Salesman Problem with Large Sizes." Mathematics 12, no. 19 (2024): 2960. http://dx.doi.org/10.3390/math12192960.

Full text

Abstract:

In this paper, we address the challenge of creating candidate sets for large-scale Traveling Salesman Problem (TSP) instances, where choosing a subset of edges is crucial for efficiency. Traditional methods for improving tours, such as local searches and heuristics, depend greatly on the quality of these candidate sets but often struggle in large-scale situations due to insufficient edge coverage or high time complexity. We present a new heuristic based on fuzzy clustering, designed to produce high-quality candidate sets with nearly linear time complexity. Thoroughly tested on benchmark instan

APA, Harvard, Vancouver, ISO, and other styles

35

Ali, Hamid, Muhammad Zaid Rafique, Muhammad Shahzad Sarfraz, Muhammad Sheraz Arshad Malik, Mohammed A. Alqahtani, and Jehad Saad Alqurni. "A novel approach for solving travelling thief problem using enhanced simulated annealing." PeerJ Computer Science 7 (March 16, 2021): e377. http://dx.doi.org/10.7717/peerj-cs.377.

Full text

Abstract:

Real-world optimization problems are getting more and more complex due to the involvement of inter dependencies. These complex problems need more advanced optimizing techniques. The Traveling Thief Problem (TTP) is an optimization problem that combines two well-known NP-Hard problems including the 0/1 knapsack problem and traveling salesman problem. TTP contains a person known as a thief who plans a tour to collect multiple items to fill his knapsack to gain maximum profit while incurring minimum cost in a standard time interval of 600 s. This paper proposed an efficient technique to solve the

APA, Harvard, Vancouver, ISO, and other styles

36

Müller, Felipe Martins, and Iaê Santos Bonilha. "Hyper-Heuristic Based on ACO and Local Search for Dynamic Optimization Problems." Algorithms 15, no. 1 (2021): 9. http://dx.doi.org/10.3390/a15010009.

Full text

Abstract:

Hyper-heuristics comprise a set of approaches that are motivated (at least in part) by the objective of intelligently combining heuristic methods to solve hard optimization problems. Ant colony optimization (ACO) algorithms have been proven to deal with Dynamic Optimization Problems (DOPs) properly. Despite the good results obtained by the integration of local search operators with ACO, little has been done to tackle DOPs. In this research, one of the most reliable ACO schemes, the MAX-MIN Ant System (MMAS), has been integrated with advanced and effective local search operators, resulting in a

APA, Harvard, Vancouver, ISO, and other styles

37

Bouhmala, Noureddine. "A Kernighan-Lin inspired algorithm for MAX-SAT." Science China Information Sciences 62, no. 11 (2019). http://dx.doi.org/10.1007/s11432-018-9786-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Boudour, R., and M. T. Laskri. "Outil de partitionnement hw/sw basé sur l’algorithme Kernighan/Lin amélioré." Revue Africaine de la Recherche en Informatique et Mathématiques Appliquées Volume 7, 2007 (November 26, 2007). http://dx.doi.org/10.46298/arima.1882.

Full text

Abstract:

International audience Partitioning of system functionality for implementation among multiple system components, such as among hardware and software components in codesign, is becoming an increasingly important topic. Various heuristics are used in automatic partitioning. In this paper, we present our tool, called AutoDec, implemented in Visual C++ 6.0. We verified that hierarchical clustering algorithm, based on closeness metrics, can be used to merge pieces of functionality before applying Kernighan/Lin algorithm, resulting in reduced execution time with often improvements in quality. In add

APA, Harvard, Vancouver, ISO, and other styles

39

Dib, Omar. "Novel hybrid evolutionary algorithm for bi-objective optimization problems." Scientific Reports 13, no. 1 (2023). http://dx.doi.org/10.1038/s41598-023-31123-8.

Full text

Abstract:

AbstractThis work considers the Bi-objective Traveling Salesman Problem (BTSP), where two conflicting objectives, the travel time and monetary cost between cities, are minimized. Our purpose is to compute the trade-off solutions that fulfill the problem requirements. We introduce a novel three-Phase Hybrid Evolutionary Algorithm (3PHEA) based on the Lin–Kernighan Heuristic, an improved version of the Non-Dominated Sorting Genetic Algorithm, and Pareto Variable Neighborhood Search, a multi-objective version of VNS. We conduct a comparative study with three existing approaches dedicated to solvi

APA, Harvard, Vancouver, ISO, and other styles

40

Soh, Mathurin, Baudoin Nguimeya Tsofack, and Clémentin Tayou Djamegni. "A Hybrid Algorithm Based on Multi-colony Ant Optimization and Lin-Kernighan for solving the Traveling Salesman Problem." Revue Africaine de Recherche en Informatique et Mathématiques Appliquées Volume 35 - Special issue... (October 28, 2023). http://dx.doi.org/10.46298/arima.8660.

Full text

Abstract:

In this article, a hybrid heuristic algorithm is proposed to solve the Traveling Salesman Problem (TSP). This algorithm combines two main metaheuristics: optimization of multi-colony ant colonies (MACO) and Lin-Kernighan-Helsgaun (LKH). The proposed hybrid approach (MACO-LKH) is a so-called insertion and relay hybridization. It brings two major innovations: The first consists in replacing the static visibility function used in the MACO heuristic by the dynamic visibility function used in LKH. This has the consequence of avoiding long paths and favoring the choice of the shortest paths more qui

APA, Harvard, Vancouver, ISO, and other styles

41

Ospina-Toro, Daniela, Eliana Mirledy Toro-Ocampo, and Ramón Alfonso Gallego-Rendón. "Metodología para creación de rutas alimentadoras en sistemas de transporte masivo." Revista Facultad de Ingeniería 26, no. 45 (2017). http://dx.doi.org/10.19053/01211129.v26.n45.2017.6052.

Full text

Abstract:

This paper proposes a methodology to identify feeder routes for areas disconnected to the Mass Transit System (MTS), in order to propose an alternative solution to the deficit in the number of passengers carried. The proposed methodology consists of two steps: (1) structuring scenarios for areas not connected to the transport system and (2) combining heuristic and exact techniques to solve the feeding routes problem considering in the restrictions the path length and passengers vehicle capacity. To model the problem, a comparison with the Location Routing problem is established, which is usual

APA, Harvard, Vancouver, ISO, and other styles

42

Cook, William, Stephan Held, and Keld Helsgaun. "Constrained Local Search for Last-Mile Routing." Transportation Science, November 8, 2022. http://dx.doi.org/10.1287/trsc.2022.1185.

Full text

Abstract:

Last-mile routing refers to the final step in a supply chain, delivering packages from a depot station to the homes of customers. At the level of a single van driver, the task is a traveling salesman problem. But the choice of route may be constrained by warehouse sorting operations, van-loading processes, driver preferences, and other considerations rather than a straightforward minimization of tour length. We propose a simple and efficient penalty-based local search algorithm for route optimization in the presence of such constraints, adopting a technique developed by Helsgaun to extend the

APA, Harvard, Vancouver, ISO, and other styles

43

Mathur, Robin Prakash, and Manmohan Sharma. "Graph-based application partitioning approach for computational offloading in mobile cloud computing." Recent Patents on Computer Science 12 (July 16, 2019). http://dx.doi.org/10.2174/2213275912666190716114033.

Full text

Abstract:

: Computational offloading is emerging as a popular field in mobile cloud computing (MCC). Modern applications are power and compute-intensive which leads to the energy, storage and processing issues in mobile devices. Using the offloading concept, a mobile device can offload its computation to the cloud servers and receives back the results on the device. An important question that arises in the offloading scenario is which part of the application needs to be offloaded remotely. In order to identify that, the application needs to be partitioned. In this paper, the graph partitioning approach

APA, Harvard, Vancouver, ISO, and other styles

44

Gantassi, Rahma, Zaki Masood, Quota Alief Sias, and Yonghoon Choi. "I‐QoS‐WSN‐S‐MDC: Improving Quality of Service of Wireless Sensor Networks Using a Smart Mobile Data Collector." IET Wireless Sensor Systems 15, no. 1 (2025). https://doi.org/10.1049/wss2.70005.

Full text

Abstract:

ABSTRACTQuality of service (QoS) and energy efficiency are two major factors that play an important role in wireless sensor network (WSNs) operation. Although it is often argued that these two factors are naturally consistent. WSNs demand additional QoS measures beyond the capabilities of clustering and routing protocols, such as stability and latency. This paper proposes a new routing protocol named improving quality of service of wireless sensor networks using a smart mobile data collector (I‐QoS‐WSN‐S‐MDC). I‐QoS‐WSN‐S‐MDC is an enhancement of the low energy adaptive clustering hierarchy‐km

APA, Harvard, Vancouver, ISO, and other styles

45

Zheng, Jiongzhi, Kun He, Jianrong Zhou, Yan Jin, and Chu-Min Li. "Reinforced Lin-Kernighan-Helsgaun algorithms for the traveling salesman problems." Knowledge-Based Systems, November 2022, 110144. http://dx.doi.org/10.1016/j.knosys.2022.110144.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Srinivas, Amedapu, and Leela Velusamy. "Community Detection Algorithm Based on High Degree Node Selection in Complex Networks." Journal of Machine and Computing, July 5, 2025, 1864–72. https://doi.org/10.53759/7669/jmc202505146.

Full text

Abstract:

B. Kamiński, P. Prałat, and F. Théberge, “Mining Complex Networks,” Nov. 2021, doi: 10.1201/9781003218869. S. S. Hussein and A. A. Farhan, “On Linear Algebraic and Graph Theoretic Methods,” Journal of Global Scientific Research, vol. 8, no. 11, pp. 3319–3326, 2023. C. He, X. Fei, Q. Cheng, H. Li, Z. Hu, and Y. Tang, “A Survey of Community Detection in Complex Networks Using Nonnegative Matrix Factorization,” IEEE Transactions on Computational Social Systems, vol. 9, no. 2, pp. 440–457, Apr. 2022, doi: 10.1109/tcss.2021.3114419. F. Gasparetti, G. Sansonetti, and A. Micarelli, “Community detecti

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!