This paper studies a new kind of dynamic multi-stage facility layout problem under dynamic business environment, in which new machines may be added into, or old machines may be removed from the plant. We define this p...
详细信息
This paper studies a new kind of dynamic multi-stage facility layout problem under dynamic business environment, in which new machines may be added into, or old machines may be removed from the plant. We define this problem first on the basis of unequal area machines and continual presentation of layouts. Compared with nodes and arcs of the flow chart, we convert this problem into a shortestpath problem by studying its cost function and machine adding/removing heuristic rules, and the corresponding mathematical model for this problem is established. An auction algorithm is proposed here to solve the shortestpath problem. Finally, a shortestpath based simulated annealing algorithm is presented to solve the optimization problem. Parameters of the SP based SA algorithm are discussed to improve the performance of the algorithm. Some cases are used to verify the proposed algorithm. (C) 2009 Elsevier Ltd. All rights reserved.
In social media directed links can represent anything from close friendship to common interests. Such directed links determine the flow of information and hence indicate an individual influence on others. The influenc...
详细信息
ISBN:
(纸本)9789811031533;9789811031526
In social media directed links can represent anything from close friendship to common interests. Such directed links determine the flow of information and hence indicate an individual influence on others. The influence of a person X over person Y is defined as the ratio of Y's investment that Y makes on X. Most contemporary networks return source-target paths in an online social network as a result of search ranked by degrees of separation. This approach fails to reflect tie of social strength (i.e., intimacy of two people in terms of interaction), and does not reflect asymmetric nature of social relations (i.e., if a person X invests time or effort in person Y, then the reverse is not necessarily true). In this paper, it is proved that in social graph result can prove to be more effective by incorporating the concept of directed and weighted influence edges taking into account both asymmetry and tie strength. The study is based on two real-world networks: Twitter capturing its retweet data and DBLP capturing its author-coauthor relationship. The experiments have been conducted based on two algorithms-Dijkstra shortest path algorithm and influence-based strongest pathalgorithm. Then a comparative study was done capturing different cases in which strongest pathalgorithm was better than shortest path algorithm in different cases.
There are a number of transportation applications that require the use of a heuristic shortest path algorithm rather than one of the standard, optimal algorithms. This is primarily due to the requirements of some tran...
详细信息
There are a number of transportation applications that require the use of a heuristic shortest path algorithm rather than one of the standard, optimal algorithms. This is primarily due to the requirements of some transportation applications where shortestpaths need to be quickly identified either because an immediate response is required (e.g., in-vehicle route guidance systems) or because the shortestpaths need to be recalculated repeatedly (e.g., vehicle routing and scheduling). For this reason a number of heuristic approaches have been advocated for decreasing the computation time of the shortest path algorithm. This paper presents a survey review of various heuristic shortest path algorithms that have been developed in the past. The goal is to identify the main features of different heuristic strategies, develop a unifying classification framework, and summarize relevant computational experience. (c) 2005 Elsevier Ltd. All rights reserved.
Implementing managed lanes, such as high-occupancy toll lanes, within existing urban highway corridors has become increasingly common in cities that want to provide a reliable transportation option but lack sufficient...
详细信息
Implementing managed lanes, such as high-occupancy toll lanes, within existing urban highway corridors has become increasingly common in cities that want to provide a reliable transportation option but lack sufficient right-of-way to construct new corridors. This study develops a framework that utilizes a shortest path algorithm to compare before and after commute routes and estimate the change in door-to-door travel time offered by managed lane facilities. Using this modeling approach, a case study is explored for the Northwest Corridor (NWC) managed lane facility located in the Atlanta, Georgia, region. The shortestpath routines predict that the facility provides a 21.0% - 27.1% decrease in door-to-door travel time for the NWC managed lane users, and a 5.8% – 12.0% travel time decrease for non-NWC general-purpose lane users, for corridor travelers departing home between 6:30 and 8:30 A.M. (traversing the corridor between 6:30 A.M. and 10:00 A.M.). This framework can be easily customized and applied to any other commute route/time change assessment for major managed lane projects.
Purpose - shortestpath problem has always been a hot topic in the study of graph theory, because of its wide application field, extending from operational research to the disciplines of geography, automatic control, ...
详细信息
Purpose - shortestpath problem has always been a hot topic in the study of graph theory, because of its wide application field, extending from operational research to the disciplines of geography, automatic control, computer science and traffic. According to its concrete application, scholars in the relevant field have presented many algorithms, but most of them are solely improvements based on Dijkstra algorithm. The purpose of this paper is to enrich the kinds of (and improve the efficiency of) the shortest path algorithms. Design/methodology/approach - This paper puts forward an improved calculation method of shortestpath using cellular automata model, which is designed to search the shortestpath from one node to another node. Cellular state set is adjusted with combination of breeding and mature states. Evolution rule is improved to enhance its parallelism. At the same time, recording manner of cellular state turnover is modified to record all information sources. Findings - The result indicates that the improved algorithm is correct and more efficient, in that it could reduce the times of cellular state turnover;meanwhile, it can solve multi-paths problem. Originality/value - In this paper, cellular state set in exiting shortest path algorithm based on cellular automata theory is adjusted;evolution rule is improved;and recording manner of cellular state turnover is modified to record all information sources. All of which make the parallelism of this algorithm enhanced and the multi-paths problem solved.
This paper defines the adjacent cost matrix and the path matrix based on the directed weighted-graph, and defines a new operator that 'summarization then minimum' replace 'multiplication then summarization...
详细信息
This paper defines the adjacent cost matrix and the path matrix based on the directed weighted-graph, and defines a new operator that 'summarization then minimum' replace 'multiplication then summarization' between two adjacent cost matrixs, named 'minimum of summarization sequence between two multiplication position elements of the two matrixs'. Based on this new matrix operator, this paper proposes a new algorithm to the shortestpath problem within a directed graph. This algorithm can get the global shortestpath out for any types of graph. Dijkstra algorithm is a well-known good solution to the shortestpath problem, but it will result out a fake path to some kinds of graph. The algorithm presented by this paper completely overcome this phenomena out of Dijikstra algorithm.
The anatomical therapeutic chemical (ATC) classification system is a widely accepted drug classification scheme. This system comprises five levels and includes several classes in each level. Drugs are classified into ...
详细信息
The anatomical therapeutic chemical (ATC) classification system is a widely accepted drug classification scheme. This system comprises five levels and includes several classes in each level. Drugs are classified into classes according to their therapeutic effects and characteristics. The first level includes 14 main classes. In this study, we proposed two network-based models to infer novel potential chemicals deemed to belong in the first level of ATC classification. To build these models, two large chemical networks were constructed using the chemical-chemical interaction information retrieved from the Search Tool for Interactions of Chemicals (STITCH). Two classic network algorithms, shortestpath (SP) and random walk with restart (RWR) algorithms, were executed on the corresponding network to mine novel chemicals for each ATC class using the validated drugs in a class as seed nodes. Then, the obtained chemicals yielded by these two algorithms were further evaluated by a permutation test and an association test. The former can exclude chemicals produced by the structure of the network, i.e., false positive discoveries. By contrast, the latter identifies the most important chemicals that have strong associations with the ATC class. Comparisons indicated that the two models can provide quite dissimilar results, suggesting that the results yielded by one model can be essential supplements for those obtained by the other model. In addition, several representative inferred chemicals were analyzed to confirm the reliability of the results generated by the two models. This article is part of a Special Issue entitled: Accelerating Precision Medicine through Genetic and Genomic Big Data Analysis edited by Yudong Cai & Tao Huang.
shortestpath Tree Problem has always been a popular problem but with the devise of Dijkstra's algorithm, SPT and many related problems received immense intention of researchers. shortestpath Tree plays an import...
详细信息
ISBN:
(纸本)9783642221903
shortestpath Tree Problem has always been a popular problem but with the devise of Dijkstra's algorithm, SPT and many related problems received immense intention of researchers. shortestpath Tree plays an important role in many applications like robot navigation, games, transportation and communication routing, etc. In many applications like network and vehicle routing, fast and reliable recovery from the failure is desired. Recovery from these failed links need means and/or plan, with least additional healing cost for the prolongation of the process with no or minimum delay. This paper presents an approach to recover from undesirable state of link failure(s) back to the normal state of working. A shortestpath tree is being extracted from the graph with alternate path at each point (junction) keeping the cost as low as possible.
The bidirectional shortestpath problem has important applications in VLSI floor planning and other areas. We introduce a new algorithm to solve bidirectional shortestpath problems using parallel architectures provid...
详细信息
The bidirectional shortestpath problem has important applications in VLSI floor planning and other areas. We introduce a new algorithm to solve bidirectional shortestpath problems using parallel architectures provided by general purpose computing on graphics processing units. The algorithm performs parallel searches from the source and sink using Dijkstra's classic approach modified with pruning and early termination. We achieve substantial speedup over a parallel method that performs a single parallel search on the GPGPU from the source to all other nodes but early terminates when the shortestpath to the specified target node is found. Experimental results demonstrate a speedup of nearly 2x over the parallel method that performs a parallel search from the source with early termination on the GPGPU.
With the rapid development of the internet, mobile medical care also develops rapidly, but the ＂three long and one short＂ problems in the hospital is still unsolved. We present a system of rational planning of walki...
详细信息
With the rapid development of the internet, mobile medical care also develops rapidly, but the ＂three long and one short＂ problems in the hospital is still unsolved. We present a system of rational planning of walking route for patients based on WeChat platform. We firstly introduce the intelligent guidance and the considering the spatial distance among different departments, the shortestpath waiting system is designed by using the backtracking method. The simulation results of the shortest path algorithm in this paper show that the algorithm can effectively plan the clinic route to save time while providing convenience for patients.
暂无评论