检索结果-内蒙古大学图书馆

A backtracking algorithm for Solving the Nearly Equitable Strong Edge-coloring Problem on Transportation Network

NETWORKS & SPATIAL ECONOMICS 2025年第1期25卷 219-248页

作者： Zhang, Kai Dong, Yu Cheng, Lin Chen, Xinyuan Cheng, Qixiu Liu, Zhiyuan Hong Kong Polytech Univ Fac Engn Dept Ind & Syst Engn Kowloon Hong Kong Peoples R China Southeast Univ Sch Transportat Jiulonghu Campus Nanjing 211100 Peoples R China Nanjing Univ Aeronaut & Astronaut Coll Civil Aviat Nanjing 210016 Peoples R China Univ Bristol Business Sch Bristol BS8 1PY England

Faced with the challenges of continuously expanding traffic network scales and increasing travel demands in practical engineering problems, the computation required by traditional algorithms for solving large-scale traffic assignment problem (TAP) is expanding, making it increasingly difficult to balance computational efficiency and accuracy. The search for effective decomposition methods suitable for large-scale TAP has been a prominent focus. However, the complexity of the transportation network topology makes it challenging for existing traffic assignment algorithms to decompose the network. This paper utilizes the edge color theory from graph theory, the topology of transportation networks is deeply analyzed, and the characteristics of two-way edge coloring are defined in transportation networks. To further decompose the network at the level of link variables, a backtracking algorithm is presented for solving the nearly equitable strong edge-coloring (NESEC) problem. The proposed algorithm provides a theoretical foundation for modeling parallel traffic assignment based on the alternative direction method of multipliers (ADMM). The backtracking algorithm makes NESEC results easier for the ADMM-based traffic assignment model to perform parallel computation and enables the parallel calculation on thousands of link-based subproblems on large-scale TAP. The proposed algorithm was validated by conducting numerical experiments.

关键词： Transportation network Edge-coloring backtracking algorithm Traffic assignment Link-based subproblems

来源：评论

学校读者我要写书评

暂无评论

backtracking algorithm-based Disassembly Sequence Planning 25

Backtracking Algorithm-based Disassembly Sequence Planning

引用

25th CIRP Life Cycle Engineering (LCE) Conference

作者： Li, Bingbing Ding, Li Rajai, Mark Hu, Di Zheng, Shengzi Calif State Univ Northridge Dept Mfg Syst Engn & Management Northridge CA 91330 USA Hefei Univ Technol Intelligent Mfg Inst Hefei 230088 Anhui Peoples R China Tianjin Univ Sci & Technol Coll Mech Engn Tianjin 300457 Peoples R China

Disassembly sequence planning (DSP) is one of the core research themes of product life cycle design. Effective DSP can reduce product life cycle costs as well as their environmental effects and provides a theoretical future foundation for recycling and improving sustainability performance. The problem with current heuristic artificial intelligence algorithms is that the outcome may have a local extremum: therefore, it may not generate the exact or even the approximate optimum solution. For a specific sequence planning problem, some algorithm parameters need to be adjusted in order to generate a perfect solution. In this study, the objective is to create new DSP by integrating a constraint satisfaction problem (CSP) based on backtracking algorithms. First, the relationship between DSP and the CSP was analysed. Then, the DSP was converted into a CSP based on a disassembly constraint graph (DCG). The solution flowchart of DSP and the CSP-associated algorithms, based on backtracking algorithms, are presented in this article for a dishwasher recycling case study. The outcome of this study shows that the created method can effectively find all of the feasible disassembly sequences as well as the optimum sequence for recycling. Ultimately, these results can be effectively applied to more appliances for future use. (C) 2018 The Authors. Published by Elsevier B.V.

关键词： Dishwasher recycling disassembly sequence planning disassembly constraint graph backtracking algorithm

来源：评论

学校读者我要写书评

暂无评论

backtracking algorithm based Multi-Relay Selection in High Altitude Platforms System

Backtracking Algorithm based Multi-Relay Selection in High A...

引用

IEEE/CIC International Conference on Communications in China (ICCC)

作者： Wang, Tingting Lu, Yang Zhang, Donglei Cui, Gaofeng Wang, Weidong Beijing Univ Posts & Telecommun Lab Informat & Elect Technol Beijing 100876 Peoples R China Global Energy Interconnect Res Inst Co Ltd State Grid Lab Elect Power Commun Network Technol Beijing 102209 Peoples R China

ISBN: (纸本)9781538670057

In High Altitude Platforms (HAPs) system, rain fading is a burning problem needed to be settled. Because of the limited transmitting power and insufficient surface area of the aircraft, HAPs is unable to apply traditional rain attenuation mitigation technologies. In this paper, we propose a backtracking algorithm based multi-relay selection scheme (BA-MRS) to solve this problem. In the BA-MRS scheme, we use cooperative diversity technology to provide additional diversity gain, and utilize beamforming technology to enhance the antenna gain and suppress the interference between users. So as to speed up the search process, we set a selection criterion for the backtracking algorithm, which can reduce the size of the search space efficiently. Simulation results show that the proposed scheme can achieve a near-optimal performance with a lower complexity.

关键词： HAPs rain attenuation beamforming cooperative diversity backtracking algorithm

来源：评论

学校读者我要写书评

暂无评论

The high performing backtracking algorithm and heuristic for the sequence-dependent setup times flowshop problem with total weighted tardiness

引用

ENGINEERING OPTIMIZATION 2016年第9期48卷 1571-1592页

作者： Zheng, Jun-Xi Zhang, Ping Li, Fang Du, Guang-Long South China Univ Technol Sch Comp Sci & Engn Guangzhou Guangdong Peoples R China

Although the sequence-dependent setup times flowshop problem with the total weighted tardiness minimization objective exists widely in industry, work on the problem has been scant in the existing literature. To the authors' best knowledge, the NEH_EWDD heuristic and the Iterated Greedy (IG) algorithm with descent local search have been regarded as the high performing heuristic and the state-of-the-art algorithm for the problem, which are both based on insertion search. In this article firstly, an efficient backtracking algorithm and a novel heuristic (HPIS) are presented for insertion search. Accordingly, two heuristics are introduced, one is NEH_EWDD with HPIS for insertion search, and the other is the combination of NEH_EWDD and both the two methods. Furthermore, the authors improve the IG algorithm with the proposed methods. Finally, experimental results show that both the proposed heuristics and the improved IG (IG*) significantly outperform the original ones.

关键词： flowshop scheduling heuristic backtracking algorithm setup times total weighted tardiness

来源：评论

学校读者我要写书评

暂无评论

The message management asynchronous backtracking algorithm

引用

JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE 2008年第2期20卷 95-110页

作者： Jiang, Hong Vidal, Jose M. Univ S Carolina Columbia SC 29208 USA

In this paper we show how the asynchronous backtracking algorithm, a well-known distributed constraint satisfaction algorithm, produces unnecessary messages and introduce our optimized algorithm, message management asynchronous backtracking, which reduces the number of messages the agents send. The message management mechanism removes the redundant messages, keeps the message queue updated, and handles messages by package instead of individually in order to improve efficiency. Our test results shows that the algorithm significantly reduces the total number of messages sent and drastically reduces the number of cycles used when solving instances of the graph colouring problem.

关键词： constraint satisfaction problem backtracking algorithm distributed hyper-resolution multiagent system

来源：评论

学校读者我要写书评

暂无评论

backtracking algorithm-based Disassembly Sequence Planning

引用

Procedia CIRP 2018年 69卷 932-937页

作者： Bingbing Li Li Ding Mark Rajai Di Hu Shengzi Zheng Department of Manufacturing Systems Engineering & Management California State Univeristy Northridge Northridge CA 91330 U.S. Intelligent Manufacturing Institute Hefei University of Technology Hefei Anhui 230088 China College of Mechnial Engineering Tianjin University of Science and Technology Binhai Tianjin 300457 China

Disassembly sequence planning (DSP) is one of the core research themes of product life cycle design. Effective DSP can reduce product life cycle costs as well as their environmental effects and provides a theoretical future foundation for recycling and improving sustainability performance. The problem with current heuristic artificial intelligence algorithms is that the outcome may have a local extremum; therefore, it may not generate the exact or even the approximate optimum solution. For a specific sequence planning problem, some algorithm parameters need to be adjusted in order to generate a perfect solution. In this study, the objective is to create new DSP by integrating a constraint satisfaction problem (CSP) based on backtracking algorithms. First, the relationship between DSP and the CSP was analysed. Then, the DSP was converted into a CSP based on a disassembly constraint graph (DCG). The solution flowchart of DSP and the CSP-associated algorithms, based on backtracking algorithms, are presented in this article for a dishwasher recycling case study. The outcome of this study shows that the created method can effectively find all of the feasible disassembly sequences as well as the optimum sequence for recycling. Ultimately, these results can be effectively applied to more appliances for future use.

关键词： Dishwasher recycling disassembly sequence planning disassembly constraint graph backtracking algorithm

来源：评论

学校读者我要写书评

暂无评论

Application of backtracking algorithm in College Dormitory Assignment Management

Application of Backtracking Algorithm in College Dormitory A...

引用

2nd IEEE International Conference on Computer Science and Information Technology

作者： Wang, Wen-fa Li, Zhu-lin Ma, Yan Yanan Univ Inst Comp Sci Yaan Shan Xi Peoples R China Yanan Univ Software R&D Ctr Yaan Shan Xi Peoples R China

ISBN: (纸本)9781424445189

The multi-constraint conditions, including the entrance examination for college, the region and the dormitory classification and so on, were analyzed and studied enough by assigning management dormitory reasonably. A new backtracking algorithm based on matrix storage was proposed, and the realization detail of the algorithm was discussed. Further, the complexity of the algorithm was analyzed. The analysis result show the algorithm is more efficient comparing the similar method, and the application result show it is effective and reasonable in practice.

关键词： backtracking algorithm matrix storage multi-constraint conditions dormitory assignment management

来源：评论

学校读者我要写书评

暂无评论

A Novel Topology Reconfiguration backtracking algorithm for 2D REmesh Networks-on-Chip 8th

A Novel Topology Reconfiguration Backtracking Algorithm for ...

引用

8th International Symposium on Parallel Architectures, algorithms, and Programming (PAAP)

作者： Niu, Na Fu, Fang-Fa Li, Hang Lai, Feng-Chang Wang, Jin-Xiang Harbin Inst Technol Microelect Ctr Harbin 150001 Heilongjiang Peoples R China

ISBN: (纸本)9789811064425;9789811064418

This paper presents a fault-tolerant topology reconfiguration backtracking algorithm to tolerate faulty cores in 2D REmesh based (reconfigurable mesh based) Networks-on-Chip. This new algorithm can be dynamically reconfigured to support irregular topologies caused by faulty cores in a REmesh network without destroying the integrity of topologies. In addition, the proposed reconfigure method has a high-level fault-tolerance capability and therefore it is capable to tolerate more faulty components in more complicated faulty situations without additional hardware costs. The reliability performance and fault-tolerance capability of the reconfiguration backtracking algorithm in a 2D REmesh network are evaluated through appropriate simulations. The experimental results show that in different sizes of topologies (the max size is 7 x 8), when less than 10.7% faulty cores occur, more than 91.5% successful reconfiguration rate can be achieved. In addition, in the 7 x 8 REmesh, when the faulty core reaches 7, the successful reconfiguration rate has reached 61.49%, which enhanced 9.74% compared with the TRARE algorithm.

关键词： Topology reconfiguration backtracking algorithm NOCs Fulty cores REmesh

来源：评论

学校读者我要写书评

暂无评论

Practical Implementation of a Quantum backtracking algorithm 46th

Practical Implementation of a Quantum Backtracking Algorithm

引用

46th International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM)

作者： Martiel, Simon Remaud, Maxime Atos Quantum R&D F-78340 Les Clayes Sous Bois France

ISBN: (纸本)9783030389192;9783030389185

In previous work, Montanaro presented a method to obtain quantum speedups for backtracking algorithms, a general meta-algorithm to solve constraint satisfaction problems (CSPs). In this work, we derive a space efficient implementation of this method. Assume that we want to solve a CSP with m constraints on n variables and that the domain in which these variables take their value is of cardinality d. Then, we show that the implementation of Montanaro's backtracking algorithm can be done by using O(n log d) data qubits. We detail an implementation of the predicate associated to the CSP with an additional register of O(logm) qubits. We explicit our implementation for graph coloring and SAT problems, and present simulation results. Finally, we discuss the impact of the usage of static and dynamic variable ordering heuristics in the quantum setting.

关键词： backtracking algorithm Quantum walk CSP Graph coloring SAT

来源：评论

学校读者我要写书评

暂无评论

Applying the Method for Solving Traveling Salesman Problem Based on backtracking algorithm to Order Picking

引用

Open Journal of Optimization 2016年第2期5卷 84-89页

作者： Jie Zhu Ying Huang Lijuan Xu School of Information Beijing Wuzi University Beijing China

In the distribution center, the way of order picking personnel to pick goods has two kinds: single picking and batch picking. Based on the way of the single picking and assumed warehouse model, in order to reduce the walking path of order picking, the order picking problem is transformed into the traveling salesman problem in this paper. Based on backtracking algorithm, the order picking path gets optimized. Finally verifing the optimization method under the environment of VC++6.0, order picking path in the warehouse model get optimized, and compared with the traditional order picking walking paths. The results show that in small and medium-sized warehouse, the optimization method proposed in this paper can reduce order picking walking path and improve the work efficiency as well as reduce the time cost.

关键词： Single Picking Path Optimization Traveling Salesman Problem backtracking algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：