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

A shortest path approach to the multiple-vehicle routing problem with split pick-ups

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL 2006年第4期40卷 265-284页

作者： Lee, CG Epelman, MA White, CC Bozer, YA Univ Toronto Dept Mech & Ind Engn Toronto ON Canada Univ Michigan Dept Ind & Operat Engn Ann Arbor MI 48109 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA USA

We consider a multiple-vehicle routing problem with split pick-ups (mVRPSP). This problem involves multiple suppliers, a single depot, and a fleet of identical capacity trucks responsible for delivering supplies from the suppliers to the depot. Any supplier may be visited by more than one truck, thus allowing split pick-ups. The problem is to determine, for each truck, which suppliers to visit and the size of loads to pick up so as to minimize the total transportation cost for the fleet, which depends on the number of trucks used and their routes. We develop a fundamentally new model for the mVRPSP, a deterministic dynamic program (DP). Although the most natural DP formulation results in a DP with uncountably-infinite state and action spaces, an optimality-invariance condition we establish leads to an equivalent DP with finite state and action spaces. This DP formulation leads to a new exact algorithm for solving the mVRPSP, based on a shortest path search algorithm, which is conceptually simple and easy to implement. Crown Copyright (c) 2005 Published by Elsevier Ltd. All rights reserved.

关键词： vehicle routing split deliveries/pick-ups dynamic programming shortest path algorithms

来源：评论

学校读者我要写书评

暂无评论

Adaptive travel time path selection in hierarchical index road network

Adaptive travel time path selection in hierarchical index ro...

引用

IEEE International Conference on Systems, Man and Cybernetics

作者： Sukul, Adisak Bhattarakosol, Pattarasinee Chulalongkorn Univ Fac Sci Dept Math Bangkok 10330 Thailand

ISBN: (纸本)9781424400997

It is the truth that spending life on the road is not fun. Therefore, every driver is searching for the "shortest path" for their traveling. Since the real objective is the smallest time frame that the driver spends on the road before arriving at the required destination. Various methods have been proposed to solve the problem of this shortest path under the hierarchical index road network. Unfortunately that none of them has considered the situation of traveling in the congestion traffic mode. This paper presents a solution, called an adaptive travel-time path selection algorithm, to obtain the shortest path where the shortest travel-time has been achieved. The experiment had shown that the selected path obtaining from the proposed algorithm has less time complexity than the previous existing methods.

关键词： spatial database Geographic Information System GIS shortest path algorithms hierarchical data database index

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for solving shortest paths on nearly acyclic directed graphs 05

Efficient algorithms for solving shortest paths on nearly ac...

引用

Australasian Symposium on Theory of Computing

作者： Shane Saunders Tadao Takaoka University of Canterbury Christchurch New Zealand

This paper presents new algorithms for computing shortest paths in a nearly acyclic directed graph G = (V, E). The new algorithms improve on the worst-case running time of previous algorithms. Such algorithms use the ... 详细信息

ISBN: (纸本)1920682236

This paper presents new algorithms for computing shortest paths in a nearly acyclic directed graph G = (V, E). The new algorithms improve on the worst-case running time of previous algorithms. Such algorithms use the concept of a 1-dominator set. A 1-dominator set divides the graph into a unique collection of acyclic subgraphs, where each acyclic subgraph is dominated by a single associated trigger vertex. The previous time for computing a 1-dominator set is improved from O(mn) to O(m), where m = |E| and n = |V|. Efficient shortest path algorithms only spend delete-min operations on trigger vertices, thereby making the computation of shortest paths through non-trigger vertices easier. Under this framework, the time complexity for the all-pairs shortest path (APSP) problem is improved from O(mn + nr log r) to O(mn + r² log r), where r is the number of triggers. Here the second term in the complexity results from delete-min operations in a heap of size r. The time complexity of the APSP problem on the broader class of nearly acyclic graphs, where trigger vertices correspond to any precomputed feedback vertex set, is similarly improved from O(mn + nr²) to O(mn + r³). This paper also mentions that the 1-dominator set concept can be generalised to define a bidirectional 1-dominator set and k-dominator sets.

关键词： shortest path complexity classes vertex head algorithms paths shortest path algorithms directed graphs solidification Set (Psychology) efficient algorithm heap Byways

来源：评论

学校读者我要写书评

暂无评论

System design through subsystem selection using physical programming

引用

AIAA JOURNAL 2003年第6期41卷 1089-1096页

作者： Patel, M Lewis, KE Maria, A Messac, A SUNY Buffalo Dept Mech & Aerosp Engn Buffalo NY 14206 USA Rensselaer Polytech Inst Dept Mech Aerosp & Nucl Engn Troy NY 12180 USA

The design of complex systems can involve the selection of several subsystem designs. We investigate the problem of selecting discrete concepts from multiple, coupled subsystems. This problem is one where measures of merit for both subsystem (local) and system (global) levels are present. An approach is developed to obtain the sets of preferred subsystem design concepts. Graph theory is used to represent the coupled selection problem where the nodes of the graph are the subsystem design choices and the arcs connecting the nodes indicate the relationships between the subsystems. Optimization techniques from graph theory and physical programming are combined to form an approach to model and solve this problem. This approach can be used to identify a given number of successful, or feasible, subsystem combinations that represent design alternatives. Once the promising subsystem designs are obtained at the conceptual design stage, focus can be restricted to these chosen design alternatives for further testing and refinement at a later embodiment design stage. Although the examples presented in this paper involve conceptual design, the presented approach can be used with any coupled discrete selection problem.

关键词： Radiators Fuselages shortest path algorithms Lift to Drag Ratio American Society of Mechanical Engineers Aircraft Design Pareto Frontier Aspect Ratio Dynamic Programming Algorithm Fuel Consumption

来源：评论

学校读者我要写书评

暂无评论

Implementing parallel shortest path for parallel transportation applications

引用

PARALLEL COMPUTING 2001年第12期27卷 1537-1568页

作者： Hribar, MR Taylor, VE Boyce, DE Northwestern Univ ECE Dept Evanston IL 60208 USA Pacific Univ Dept Math Sci Forest Grove OR USA Univ Illinois Dept Civil & mat Engn Chicago IL 60607 USA

shortest path algorithms are required by several transportation applications;furthermore, the shortest path computation in these applications can account for a large percentage of the total execution time. Since these algorithms are very computationally intense, parallel processing can provide the compute power and memory required to solve large problems quickly. Therefore, good parallel shortest algorithms are critical for efficient parallel implementations of transportation applications. The experimental work related to parallel shortest path algorithms has focused on the development of parallel algorithms;however, very little work has been done with analyzing and understanding the performance impact of various implementation issues. In this paper, we conduct a thorough experimental analysis of parallel shortest path algorithms for sparse networks, concentrating on three implementation issues: (1) choice of shortest path algorithm, (2) termination detection and (3) network decomposition. The paper focuses on the choice of shortest path algorithm and network decomposition since the work on termination detection was published previously. We determine that all three issues affect the communication and convergence of the shortest path algorithm. Furthermore, we find that communicating the most information at a time results in the best convergence;this is contrary to most scientific applications where it is optimal to minimize communication. (C) 2001 Published by Elsevier Science B.V.

关键词： parallel transportation applications parallel shortest path network decomposition shortest path algorithms parallel performance traffic equilibrium

来源：评论

学校读者我要写书评

暂无评论

On algorithms for permuting large entries to the diagonal of a sparse matrix

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2001年第4期22卷 973-996页

作者： Duff, IS Koster, J Rutherford Appleton Lab Didcot OX11 0QX Oxon England CERFACS Toulouse France

We consider bipartite matching algorithms for computing permutations of a sparse matrix so that the diagonal of the permuted matrix has entries of large absolute value. We discuss various strategies for this and consider their implementation as computer codes. We also consider scaling techniques to further increase the relative values of the diagonal entries. Numerical experiments show the effect of the reorderings and the scaling on the solution of sparse equations by a direct method and by preconditioned iterative techniques.

关键词： sparse matrices bipartite weighted matching shortest path algorithms direct methods iterative methods preconditioning

来源：评论

学校读者我要写书评

暂无评论

An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2000年第3期125卷 486-502页

作者： Ziliaskopoulos, A Wardell, W Northwestern Univ Robert R McCormick Sch Engn & Appl Sci Evanston IL 60208 USA

In this paper, we present a time-dependent intermodal optimum path algorithm for multimodal transportation networks that accounts for delays at mode and are switching points, The correctness and computational complexity of the algorithm are proved. A simple representation of the mode-to-mode switching options is introduced that results in a substantially improved design, with computational complexity independent of the number of modes and fixed schedule lines for typical transit and freight networks. The algorithm is implemented, coded, and computationally tested on realistic size networks with promising results. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： transportation shortest path algorithms freight transportation

来源：评论

学校读者我要写书评

暂无评论

TOPOGRAPHIC DISTANCE AND WATERSHED LINES

引用

SIGNAL PROCESSING 1994年第1期38卷 113-125页

作者： MEYER, F Centre de Morphologie Mathématique 35 Rue Saint Honoré 77305 Fontainebleau France

The watershed line is the basic tool for segmenting images in mathematical morphology. A rigorous definition is given in terms of a distance function called topographic distance. If the topographical function is itself a distance function, then the topographical distance becomes identical with the geodesic distance function and the watershed becomes identical with the skeleton by zone of influence. The classical shortest paths algorithms of the graph theory are then revisited in order to derive new watershed algorithms, which are either new or more easy to implement in hardware.

关键词： TOPOGRAPHIC DISTANCE WATERSHED LINE SEGMENTATION shortest path algorithms MATHEMATICAL MORPHOLOGY

来源：评论

学校读者我要写书评

暂无评论

A FAST DISTRIBUTED shortest-path ALGORITHM FOR A CLASS OF HIERARCHICALLY CLUSTERED DATA-NETWORKS

引用

IEEE TRANSACTIONS ON COMPUTERS 1992年第6期41卷 710-724页

作者： ANTONIO, JK HUANG, GM TSAI, WK TEXAS A&M UNIV SYST DEPT ELECT ENGNCOLLEGE STNTX 77843 UNIV CALIF IRVINE DEPT ELECT & COMP ENGNIRVINECA 92717

A new distributed algorithm is presented that can be used to solve the single-destination shortest path (SDSP) problem or the all-pairs shortest path (APSP) problem for a class of clustered data networks. The network graph is assumed to be characterized with a balanced hierarchically clustered (BHC) topology. The BHC topology is introduced in this paper and is shown to be a realistic characterization for a large class of interconnected data networks. For certain types of BHC topologies, the SDSP problem can be solved with computation and communication time complexities of O(log n), assuming one processor is available at each of the n number of nodes. Assuming p processors are available at each node, computation and communication time complexities of O((n/p)log n) and O(n log n) are achievable, respectively, for solving the APSP problem. It is also shown that the algorithm converges in an asynchronous environment. Therefore, some of the difficulties associated with synchronizing the order of events can be avoided in the actual implementation of the proposed algorithm.

关键词： ASYNCHRONOUS COMPUTATION DATA NETWORKS DISTRIBUTED COMPUTATION DYNAMIC PROGRAMMING HIERARCHICAL NETWORK TOPOLOGIES HIERARCHICAL ROUTING algorithms OPTIMAL ROUTING PARALLEL COMPUTATION shortest path algorithms TIME COMPLEXITY

来源：评论

学校读者我要写书评

暂无评论

IMPROVEMENTS FOR THE THRESH X2 shortest-path ALGORITHM

引用

OPERATIONS RESEARCH LETTERS 1987年第5期6卷 227-232页

作者： DIVOKY, JJ College of Business The University of Akron Akron OH 44325 USA

The Thresh X2 algorithm has been shown to dominate other shortest path algorithms over a wide variety of conditions. When used on random networks which have exponentially or normally distributed edge weights the perfo... 详细信息

关键词： shortest path algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：