A new type of vehicle routing problem （VRP）, multiple vehicle routing problem integrated reverse logistics （MVRPRL）, is studied. In this problem, there is delivery or pickup （or both） and uncertain features in t...A new type of vehicle routing problem （VRP）, multiple vehicle routing problem integrated reverse logistics （MVRPRL）, is studied. In this problem, there is delivery or pickup （or both） and uncertain features in the demands of the clients. The deliveries of every client as uncertain parameters are expressed as triangular fuzzy numbers. In order to describe MVRPRL, a multi-objective fuzzy programming model with credibility measure theory is constructed. Then the simulationbased tabu search algorithm combining inter-route and intra-route neighborhoods and embedded restarts are designed to solve it. Computational results show that the tabu search algorithm developed is superior to sweep algorithms and that compared with handling each on separate routes, the transportation costs can be reduced by 43% through combining pickups with deliveries.展开更多
Breadth-first search(BFS) is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effecti...Breadth-first search(BFS) is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effective solution, GPU-acceleration achieves the state-of-the-art result of 3.3×109 traversed edges per second on a NVIDIA Tesla C2050 GPU. A novel vertex frontier based GPU BFS algorithm is proposed, and its main features are three-fold. Firstly, to obtain a better workload balance for irregular graphs, a virtual-queue task decomposition and mapping strategy is introduced for vertex frontier expanding. Secondly, a global deduplicate detection scheme is proposed to remove reduplicative vertices from vertex frontier effectively. Finally, a GPU-based bottom-up BFS approach is employed to process large frontier. The experimental results demonstrate that the algorithm can achieve 10% improvement over the state-of-the-art method on diverse graphs. Especially, it exhibits 2-3 times speedup on low-diameter and scale-free graphs over the state-of-the-art on a NVIDIA Tesla K20 c GPU, reaching a peak traversal rate of 11.2×109 edges/s.展开更多
Many cognitive studies have indicated that the path simplicity may be as important as its distance travelled.However,the optimality of paths for current navigation system is often judged purely on the distance travell...Many cognitive studies have indicated that the path simplicity may be as important as its distance travelled.However,the optimality of paths for current navigation system is often judged purely on the distance travelled or time cost,and not the path simplicity.To balance these factors,this paper presented an algorithm to compute a path that not only possesses fewest turns but also is as short as possible by utilizing the breadth-first-search strategy.The proposed algorithm started searching from a starting point,and expanded layer by layer through searching zero-level reachable points until the endpoint is found,and then deleted unnecessary points in the reverse direction.The forward searching and backward cleaning strategies were presented to build a hierarchical graph of zero-level reachable points,and form a fewestturn-path graph(G^(*)).After that,a classic Dijkstra shortest path algorithm was executed on the G^(*) to obtain a fewestturn-and-shortest path.Comparing with the shortest path in Baidu map,the algorithm in this work has less than half of the turns but the nearly same length.The proposed fewest-turn-and-shortest path algorithm is proved to be more suitable for human beings according to human cognition research.展开更多
In the domain of autonomous industrial manipulators,precise positioning and appropriate posture selection in path planning are pivotal for tasks involving obstacle avoidance,such as handling,heat sealing,and stacking....In the domain of autonomous industrial manipulators,precise positioning and appropriate posture selection in path planning are pivotal for tasks involving obstacle avoidance,such as handling,heat sealing,and stacking.While Multi-Degree-of-Freedom(MDOF)manipulators offer kinematic redundancy,aiding in the derivation of optimal inverse kinematic solutions to meet position and posture requisites,their path planning entails intricate multiobjective optimization,encompassing path,posture,and joint motion optimization.Achieving satisfactory results in practical scenarios remains challenging.In response,this study introduces a novel Reverse Path Planning(RPP)methodology tailored for industrial manipulators.The approach commences by conceptualizing the manipulator’s end-effector as an agent within a reinforcement learning(RL)framework,wherein the state space,action set,and reward function are precisely defined to expedite the search for an initial collision-free path.To enhance convergence speed,the Q-learning algorithm in RL is augmented with Dyna-Q.Additionally,we formulate the cylindrical bounding box of the manipulator based on its Denavit-Hartenberg(DH)parameters and propose a swift collision detection technique.Furthermore,the motion performance of the end-effector is refined through a bidirectional search,and joint weighting coefficients are introduced to mitigate motion in high-power joints.The efficacy of the proposed RPP methodology is rigorously examined through extensive simulations conducted on a six-degree-of-freedom(6-DOF)manipulator encountering two distinct obstacle configurations and target positions.Experimental results substantiate that the RPP method adeptly orchestrates the computation of the shortest collision-free path while adhering to specific posture constraints at the target point.Moreover,itminimizes both posture angle deviations and joint motion,showcasing its prowess in enhancing the operational performance of MDOF industrial manipulators.展开更多
An effective heuristic algorithm for solving the minimum makespan problem of job shop scheduling is presented. With a given feasible solution as a start point, we use Taboo Search technique to get a schedule for each ...An effective heuristic algorithm for solving the minimum makespan problem of job shop scheduling is presented. With a given feasible solution as a start point, we use Taboo Search technique to get a schedule for each neighbor of all its neighbors, and select the best one of the schedules as the new start point. We repeat the procedure, unless the new start point is not better than the proceeding one. To make sure of better results, we introduce reverse technique to the algorithm as well. The computational experiments of the 45 standard instances show that our algorithm yields better results than TSAB algorithm.展开更多
Web crawlers are an important part of modern search engines.With the development of the times,data has exploded and humans have entered a“big data era”.For example,Wikipedia carries the knowledge from all over the w...Web crawlers are an important part of modern search engines.With the development of the times,data has exploded and humans have entered a“big data era”.For example,Wikipedia carries the knowledge from all over the world,records the realtime news that occurs every day,and provides users with a good database of data,but because of the large amount of data,it puts a lot of pressure on users to search.At present,single-threaded crawling data can no longer meet the requirements of text crawling.In order to improve the performance and program versatility of single-threaded crawlers,a high-speed multi-threaded web crawler is designed to crawl the network hyper-scale text database.Multi-threaded crawling uses multiple threads to process web pages in parallel,combining breadth-first and depth-first algorithms to control web crawling.The practice project is based on the Python language to achieve multi-threaded optimization network hyper-large-scale text database-Wikipedia book crawling method,the project is inspired by the article on the Wikipedia article in the Big Data Digest public number.展开更多
Software reverse engineering and reengineering techniques are most often applied to reconstruct the software archi-tecture with respect to quality constraints, or non-functional requirements such as maintainability or...Software reverse engineering and reengineering techniques are most often applied to reconstruct the software archi-tecture with respect to quality constraints, or non-functional requirements such as maintainability or reusability. In this paper, the performance improvement of distributed software is modeled as a search problem that is solved by heuristic search algorithms such as genetic search methods. To achieve this, firstly, all aspects of the distributed execution of a software is specified by an analytical performance evaluation function that not only evaluates the current deployment of the software from the performance perspective but also can be applied to propose the near-optimal object deploy-ment for that software. This analytical function is applied as the Heuristic search objective function. In this paper a novel statement reordering method is also presented which is used to generate the search objective function such that the best solution in the search space can be found.展开更多
基金The National Natural Science Foundation of China(No.70772059)Youth Science and Technology Innovation Foundation of Nanjing Agriculture University(No.KJ06029)
文摘A new type of vehicle routing problem （VRP）, multiple vehicle routing problem integrated reverse logistics （MVRPRL）, is studied. In this problem, there is delivery or pickup （or both） and uncertain features in the demands of the clients. The deliveries of every client as uncertain parameters are expressed as triangular fuzzy numbers. In order to describe MVRPRL, a multi-objective fuzzy programming model with credibility measure theory is constructed. Then the simulationbased tabu search algorithm combining inter-route and intra-route neighborhoods and embedded restarts are designed to solve it. Computational results show that the tabu search algorithm developed is superior to sweep algorithms and that compared with handling each on separate routes, the transportation costs can be reduced by 43% through combining pickups with deliveries.
基金Projects(61272142,61103082,61003075,61170261,61103193)supported by the National Natural Science Foundation of ChinaProject supported by the Program for New Century Excellent Talents in University of ChinaProjects(2012AA01A301,2012AA010901)supported by the National High Technology Research and Development Program of China
文摘Breadth-first search(BFS) is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effective solution, GPU-acceleration achieves the state-of-the-art result of 3.3×109 traversed edges per second on a NVIDIA Tesla C2050 GPU. A novel vertex frontier based GPU BFS algorithm is proposed, and its main features are three-fold. Firstly, to obtain a better workload balance for irregular graphs, a virtual-queue task decomposition and mapping strategy is introduced for vertex frontier expanding. Secondly, a global deduplicate detection scheme is proposed to remove reduplicative vertices from vertex frontier effectively. Finally, a GPU-based bottom-up BFS approach is employed to process large frontier. The experimental results demonstrate that the algorithm can achieve 10% improvement over the state-of-the-art method on diverse graphs. Especially, it exhibits 2-3 times speedup on low-diameter and scale-free graphs over the state-of-the-art on a NVIDIA Tesla K20 c GPU, reaching a peak traversal rate of 11.2×109 edges/s.
基金This research was supported by the National Natural Science Foundation of China(Nos.41471332 and 41101354)the National High Technology Research and Development Program of China(863 Program)(No.2013AA12A302)+1 种基金the Fundamental Research Funds for the Central Universities(No.ZYGX2011J077)the Fund of China Scholarship Council.
文摘Many cognitive studies have indicated that the path simplicity may be as important as its distance travelled.However,the optimality of paths for current navigation system is often judged purely on the distance travelled or time cost,and not the path simplicity.To balance these factors,this paper presented an algorithm to compute a path that not only possesses fewest turns but also is as short as possible by utilizing the breadth-first-search strategy.The proposed algorithm started searching from a starting point,and expanded layer by layer through searching zero-level reachable points until the endpoint is found,and then deleted unnecessary points in the reverse direction.The forward searching and backward cleaning strategies were presented to build a hierarchical graph of zero-level reachable points,and form a fewestturn-path graph(G^(*)).After that,a classic Dijkstra shortest path algorithm was executed on the G^(*) to obtain a fewestturn-and-shortest path.Comparing with the shortest path in Baidu map,the algorithm in this work has less than half of the turns but the nearly same length.The proposed fewest-turn-and-shortest path algorithm is proved to be more suitable for human beings according to human cognition research.
基金supported by the National Natural Science Foundation of China under Grant No.62001199Fujian Province Nature Science Foundation under Grant No.2023J01925.
文摘In the domain of autonomous industrial manipulators,precise positioning and appropriate posture selection in path planning are pivotal for tasks involving obstacle avoidance,such as handling,heat sealing,and stacking.While Multi-Degree-of-Freedom(MDOF)manipulators offer kinematic redundancy,aiding in the derivation of optimal inverse kinematic solutions to meet position and posture requisites,their path planning entails intricate multiobjective optimization,encompassing path,posture,and joint motion optimization.Achieving satisfactory results in practical scenarios remains challenging.In response,this study introduces a novel Reverse Path Planning(RPP)methodology tailored for industrial manipulators.The approach commences by conceptualizing the manipulator’s end-effector as an agent within a reinforcement learning(RL)framework,wherein the state space,action set,and reward function are precisely defined to expedite the search for an initial collision-free path.To enhance convergence speed,the Q-learning algorithm in RL is augmented with Dyna-Q.Additionally,we formulate the cylindrical bounding box of the manipulator based on its Denavit-Hartenberg(DH)parameters and propose a swift collision detection technique.Furthermore,the motion performance of the end-effector is refined through a bidirectional search,and joint weighting coefficients are introduced to mitigate motion in high-power joints.The efficacy of the proposed RPP methodology is rigorously examined through extensive simulations conducted on a six-degree-of-freedom(6-DOF)manipulator encountering two distinct obstacle configurations and target positions.Experimental results substantiate that the RPP method adeptly orchestrates the computation of the shortest collision-free path while adhering to specific posture constraints at the target point.Moreover,itminimizes both posture angle deviations and joint motion,showcasing its prowess in enhancing the operational performance of MDOF industrial manipulators.
基金Supported bythe National Basic Research Programof China (973 Pragram G1998030600)
文摘An effective heuristic algorithm for solving the minimum makespan problem of job shop scheduling is presented. With a given feasible solution as a start point, we use Taboo Search technique to get a schedule for each neighbor of all its neighbors, and select the best one of the schedules as the new start point. We repeat the procedure, unless the new start point is not better than the proceeding one. To make sure of better results, we introduce reverse technique to the algorithm as well. The computational experiments of the 45 standard instances show that our algorithm yields better results than TSAB algorithm.
基金This research is funded by the Open Foundation for the University Innovation Platform in the Hunan Province,grant number 16K013Hunan Provincial Natural Science Foundation of China,grant number 2017JJ2016+2 种基金2016 Science Research Project of Hunan Provincial Department of Education,grant number 16C0269.Accurate crawler design and implementation with a data cleaning function,National Students innovation and entrepreneurship of training program,grant number 201811532010.This research work is implemented at the 2011 Collaborative Innovation Center for Development and Utilization of Finance and Economics Big Data Property,Universities of Hunan Province.Open Foundation for the University Innovation Platform in the Hunan Province,grant number 16K013Hunan Provincial Natural Science Foundation of China,grant number 2017JJ20162016 Science Research Project of Hunan Provincial Department of Education,grant number 16C0269.This research work is implemented at the 2011 Collaborative Innovation Center for Development and Utilization of Finance and Economics Big Data Property,Universities of Hunan Province.Open project,grant number 20181901CRP03,20181901CRP04,20181901CRP05.
文摘Web crawlers are an important part of modern search engines.With the development of the times,data has exploded and humans have entered a“big data era”.For example,Wikipedia carries the knowledge from all over the world,records the realtime news that occurs every day,and provides users with a good database of data,but because of the large amount of data,it puts a lot of pressure on users to search.At present,single-threaded crawling data can no longer meet the requirements of text crawling.In order to improve the performance and program versatility of single-threaded crawlers,a high-speed multi-threaded web crawler is designed to crawl the network hyper-scale text database.Multi-threaded crawling uses multiple threads to process web pages in parallel,combining breadth-first and depth-first algorithms to control web crawling.The practice project is based on the Python language to achieve multi-threaded optimization network hyper-large-scale text database-Wikipedia book crawling method,the project is inspired by the article on the Wikipedia article in the Big Data Digest public number.
文摘Software reverse engineering and reengineering techniques are most often applied to reconstruct the software archi-tecture with respect to quality constraints, or non-functional requirements such as maintainability or reusability. In this paper, the performance improvement of distributed software is modeled as a search problem that is solved by heuristic search algorithms such as genetic search methods. To achieve this, firstly, all aspects of the distributed execution of a software is specified by an analytical performance evaluation function that not only evaluates the current deployment of the software from the performance perspective but also can be applied to propose the near-optimal object deploy-ment for that software. This analytical function is applied as the Heuristic search objective function. In this paper a novel statement reordering method is also presented which is used to generate the search objective function such that the best solution in the search space can be found.
