共查询到20条相似文献,搜索用时 78 毫秒
1.
Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks 总被引:1,自引:0,他引:1
In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections.
These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a
road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The
method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual
graph approach in a set of randomly generated networks and Bogotá’s large-scale road network. Our computational experiments
show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing
time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions
that uses the proposed method as the core engine. 相似文献
2.
Cognitive and self-selective routing for sensor networks 总被引:1,自引:0,他引:1
Erol Gelenbe Peixiang Liu Boleslaw K. Szymanski Christopher Morrell 《Computational Management Science》2011,8(3):237-258
New approaches to Quality-of-Service (QoS) routing in wireless sensor networks which use different forms of learning are the
subject of this paper. The Cognitive Packet Network (CPN) algorithm uses smart packets for path discovery, together with reinforcement
learning and neural networks, while Self-Selective Routing (SSR) is based on the “Ant Colony” paradigm which emulates the
pheromone-based technique which ants use to mark paths and communicate information about paths between different insects of
the same colony (Koenig et al. in Ann Math Artif Intell 31(1–4): 41–76, 2001). In this paper, we present first experimental
results on a network test-bed to evaluate CPN’s ability to discover paths having the shortest delay, or shortest length. Then,
we present small test-bed experiments and large-scale network simulations to evaluate the effectiveness of the SSR algorithm.
Finally, the two approaches are compared with respect to their ability to adapt as network conditions change over time. 相似文献
3.
By repeatedly combining the source node’s nearest neighbor, we propose a node combination (NC) method to implement the Dijkstra’s algorithm. The NC algorithm finds the shortest paths with three simple iterative steps: find the nearest neighbor of the source node, combine that node with the source node, and modify the weights on edges that connect to the nearest neighbor. The NC algorithm is more comprehensible and convenient for programming as there is no need to maintain a set with the nodes’ distances. Experimental evaluations on various networks reveal that the NC algorithm is as efficient as Dijkstra’s algorithm. As the whole process of the NC algorithm can be implemented with vectors, we also show how to find the shortest paths on a weight matrix. 相似文献
4.
The quickest path problem is related to the classical shortest path problem, but its objective function concerns the transmission
time of a given amount of data throughout a path, which involves both cost and capacity. The K-quickest simple paths problem generalises the latter, by looking for a given number K of simple paths in non-decreasing order of transmission time.
Two categories of algorithms are known for ranking simple paths according to the transmission time. One is the adaptation
of deviation algorithms for ranking shortest simple paths (Pascoal et al. in Comput. Oper. Res. 32(3):509–520, 2005; Rosen et al. in Comput. Oper. Res. 18(6):571–584, 1991), and another is based on ranking shortest simple paths in a sequence of networks with fixed capacity lower bounds (Chen
in Inf. Process. Lett. 50:89–92, 1994), and afterwards selecting the K quickest ones.
After reviewing the quickest path and the K-quickest simple paths problems we describe a recent algorithm for ranking quickest simple paths (Pascoal et al. in Ann. Oper.
Res. 147(1):5–21, 2006). This is a lazy version of Chen’s algorithm, able to interchange the calculation of new simple paths and the output of each
k-quickest simple path.
Finally, the described algorithm is computationally compared to its former version, as well as to deviation algorithms.
相似文献
5.
在最短路修复合作博弈中,当灾后运输网络规模较大时,最优成本分摊问题难以直接求解。基于拉格朗日松弛理论,提出了一种最短路修复合作博弈成本分摊算法。该算法将最短路修复合作博弈分解为两个具有特殊结构的子博弈,进而利用两个子博弈的结构特性,可以{高效地}求解出二者的最优成本分摊,将这两个成本分摊相加,可以获得原博弈的一个近乎最优的稳定成本分摊。结果部分既包含运输网络的随机仿真,也包含玉树地震灾区的现实模拟,无论数据来源于仿真还是现实,该算法都能在短时间内为最短路修复合作博弈提供稳定的成本分摊方案。 相似文献
6.
We present a practical approach to Anstreicher and Lee’s masked spectral bound for maximum-entropy sampling, and we describe
favorable results that we have obtained with a Branch-and-Bound algorithm based on our approach. By representing masks in
factored form, we are able to easily satisfy a semidefiniteness constraint. Moreover, this representation allows us to restrict
the rank of the mask as a means for attempting to practically incorporate second-order information.
Supported in part by NSF Grant CCR-0203426. 相似文献
7.
Within the context of solving Mixed-Integer Linear Programs by a Branch-and-Cut algorithm, we propose a new strategy for branching.
Computational experiments show that, on the majority of our test instances, this approach enumerates fewer nodes than traditional
branching. On average, on instances that contain both integer and continuous variables the number of nodes in the enumeration
tree is reduced by more than a factor of two, and computing time is comparable. On a few instances, the improvements are of
several orders of magnitude in both number of nodes and computing time. 相似文献
8.
A New Multiobjective Dynamic Routing Method for Multiservice Networks: Modelling and Performance 总被引:1,自引:0,他引:1
There are potential advantages in formulating the routing problems in modern multiservice networks as multiple objective problems. This paper presents a novel hierarchical bi-level multiobjective dynamic routing model for multiservice networks. It is based on a bi-objective shortest path algorithm, with dynamically adapted soft-constraints, to compute alternative paths for each node pair and on a heuristic to synchronously select alternative routing plans for the network in a dynamic alternative routing context. It is a routing method which periodically changes alternative paths as a function of periodic updates of certain QoS related parameters obtained from real-time measurements. The performance of the proposed routing method is compared with two reference dynamic routing methods namely RTNR and DAR by means of a discrete-event simulator.A previous short version of this work was presented at INOC’03 (International Network Optimisation Conference). Work partially supported by programme POSI of the III EC programme cosponsored by FEDER and national funds. 相似文献
9.
Tatiana M. Tabirca Kenneth N. Brown Cormac J. Sreenan 《Journal of Mathematical Modelling and Algorithms》2011,10(4):371-391
The article introduces the concept of snapshot dynamic indices as centrality measures to analyse how the importance of nodes
changes over time in dynamic networks. In particular, the dynamic stress-snapshot and dynamic betweenness snapshot are investigated.
We present theoretical results on dynamic shortest paths in first-in first-out dynamic networks, and then introduce some algorithms
for computing these indices in the discrete-time case. Finally, we present some experimental results exploring the algorithms’
efficiency and illustrating the variation of the dynamic betweenness snapshot index for some sample dynamic networks. 相似文献
10.
Giacomo Nannicini Philippe Baptiste Gilles Barbier Daniel Krob Leo Liberti 《Computational Optimization and Applications》2010,45(1):143-158
Efficiently computing fast paths in large-scale dynamic road networks (where dynamic traffic information is known over a part
of the network) is a practical problem faced by traffic information service providers who wish to offer a realistic fast path
computation to GPS terminal enabled vehicles. The heuristic solution method we propose is based on a highway hierarchy-based
shortest path algorithm for static large-scale networks; we maintain a static highway hierarchy and perform each query on
the dynamically evaluated network, using a simple algorithm to propagate available dynamic traffic information over a larger
part of the road network. We provide computational results that show the efficacy of our approach. 相似文献
11.
Francesco Bruera Serafino Cicerone Gianlorenzo D’Angelo Gabriele Di Stefano Daniele Frigioni 《Mathematics in Computer Science》2008,1(4):709-736
Multi-level overlay graphs represent a speed-up technique for shortest paths computation which is based on a hierarchical decomposition of a weighted
directed graph G. They have been shown to be experimentally efficient, especially when applied to timetable information. However, no theoretical
result on the cost of constructing, maintaining and querying multi-level overlay graphs in a dynamic environment is known.
In this paper, we show theoretical properties of multi-level overlay graphs that lead us to the definition of a new data structure
for the computation and the maintenance of an overlay graph of G while weight decrease or weight increase operations are performed on G. Our solution is theoretically faster than the recomputation from scratch and allows queries that can be performed more efficiently
than running Dijkstra’s shortest paths algorithm on G.
This work was partially supported by the Future and Emerging Technologies Unit of EC (IST priority – 6th FP), under contract
no. FP6-021235-2 (project ARRIVAL). 相似文献
12.
Leo Liberti 《Mathematical Programming》2012,131(1-2):273-304
If a mathematical program has many symmetric optima, solving it via Branch-and-Bound techniques often yields search trees of disproportionate sizes; thus, finding and exploiting symmetries is an important task. We propose a method for automatically finding the formulation group of any given Mixed-Integer Nonlinear Program, and for reformulating the problem by means of static symmetry breaking constraints. The reformulated problem—which is likely to have fewer symmetric optima—can then be solved via standard Branch-and-Bound codes such as CPLEX (for linear programs) and Couenne (for nonlinear programs). Our computational results include formulation group tables for the MIPLib3, MIPLib2003, GlobalLib and MINLPLib instance libraries and solution tables for some instances in the aforementioned libraries. 相似文献
13.
We describe an O(n
4
hmin{logU,n
2logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds–Karp
capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails
scaling a relaxation parameter δ. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity
δ in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary
slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular
function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along
minimum cost paths of residual capacity at least δ. The shortest augmenting path subroutine we use is a variant of Dijkstra’s
algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running
time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the
first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow.
Received: August 6, 1999 / Accepted: July 2001?Published online October 2, 2001 相似文献
14.
This paper presents a co-evolutionary particle swarm optimization (PSO) algorithm, hybridized with noising metaheuristics,
for solving the delay constrained least cost (DCLC) path problem, i.e., shortest-path problem with a delay constraint on the
total “cost” of the optimal path. The proposed algorithm uses the principle of Lagrange relaxation based aggregated cost.
It essentially consists of two concurrent PSOs for solving the resulting minimization-maximization problem. The main PSO is
designed as a hybrid PSO-noising metaheuristics algorithm for efficient global search to solve the minimization part of the
DCLC-Lagrangian relaxation by finding multiple shortest paths between a source-destination pair. The auxiliary/second PSO
is a co-evolutionary PSO to obtain the optimal Lagrangian multiplier for solving the maximization part of the Lagrangian relaxation
problem. For the main PSO, a novel heuristics-based path encoding/decoding scheme has been devised for representation of network
paths as particles. The simulation results on several networks with random topologies illustrate the efficiency of the proposed
hybrid algorithm for the constrained shortest path computation problems. 相似文献
15.
Leo Liberti Nenad Mladenović Giacomo Nannicini 《Mathematical Programming Computation》2011,3(4):349-390
Finding good (or even just feasible) solutions for Mixed-Integer Nonlinear Programming problems independently of the specific
problem structure is a very hard but practically important task, especially when the objective and/or the constraints are
nonconvex. With this goal in mind, we present a general-purpose heuristic based on Variable Neighborhood Search, Local Branching,
a local Nonlinear Programming algorithm and Branch-and-Bound. We test the proposed approach on MINLPLib, comparing with several
existing heuristic and exact methods. An implementation of the proposed heuristic is freely available and can employ all NLP/MINLP
solvers with an AMPL interface as the main search tools. 相似文献
16.
In this paper, we extend Guo and Xia’s necessary condition which has been presented by Guo and Xia (Fuzzy optimizat Decis
Mak 5: 33–47, 2006) in order to study the finitely many constraints of fuzzy relation inequalities and optimize a linear objective
function on this region which is defined by the fuzzy max–min operator. The new condition provides a means for removing the
unnecessary paths resulting from Guo and Xia’s paths. Also, an algorithm and two numerical examples are offered to abbreviate
and illustrate the steps of the resolution process of the problem. 相似文献
17.
Yasmin A. Rios-Solis 《4OR: A Quarterly Journal of Operations Research》2008,6(2):191-194
This is a summary of the author’s PhD thesis supervised by Francis Sourd and Philippe Chrétienne and defended on 30 January
2007 at the Université Pierre et Marie Curie, Paris. The thesis is written in French and is available from the author upon
request. This work is about scheduling on parallel machines in order to minimize the total sum of earliness and tardiness
costs. To solve some variants of this problem we propose: an exact method based on continuous relaxations of convex reformulations
derived from a 0–1 quadratic program; a heuristic algorithm that relies on a new exponential size neighborhood search; finally,
a lower bound method based on a polynomial time solution of a preemptive scheduling problem for which the cost functions of
the jobs have been changed into so called position costs functions.
Partial funding provided by CONACyT (Mexican Council for Science&Technology). 相似文献
18.
In this paper, we consider the case of downside risk measures with cardinality and bounding constraints in portfolio selection.
These constraints limit the amount of capital to be invested in each asset as well as the number of assets composing the portfolio.
While the standard Markowitz’s model is a convex quadratic program, this new model is a NP-hard mixed integer quadratic program.
Realizing the computational intractability for this class of problems, especially large-scale problems, we first reformulate
it as a DC program with the help of exact penalty techniques in Difference of Convex functions (DC) programming and then solve
it by DC Algorithms (DCA). To check globality of computed solutions, a global method combining the local algorithm DCA with
a Branch-and-Bound algorithm is investigated. Numerical simulations show that DCA is an efficient and promising approach for
the considered problem.
相似文献
19.
Local branching is a general purpose heuristic method which searches locally around the best known solution by employing tree
search. It has been successfully used in Mixed-Integer Programming where local branching constraints are used to model the
neighborhood of an incumbent solution and improve the bound. We propose the integration of local branching in Constraint Programming
(CP). This integration is not simply a matter of implementation, but requires a number of significant extensions. The original
contributions of this paper are: the definition of an efficient and incremental bound computation for the neighborhood, a
cost-based filtering algorithm for the local branching constraint and a novel diversification strategy that can explore arbitrarily
far regions of the search tree w.r.t. the already found solutions. We demonstrate the practical value of local branching in
CP by providing an extensive experimental evaluation on the hard instances of the Asymmetric Traveling Salesman Problem with
Time Windows. 相似文献
20.
《European Journal of Operational Research》2005,165(1):97-107
We consider a variant of the constrained shortest path problem, where the constraints come from a set of forbidden paths (arc sequences) that cannot be part of any feasible solution. Two solution approaches are proposed for this variant. The first uses Aho and Corasick's keyword matching algorithm to filter paths produced by a k-shortest paths algorithm. The second generalizes Martins' deviation path approach for the k-shortest paths problem by merging the original graph with a state graph derived from Aho and Corasick's algorithm. Like Martins' approach, the second method amounts to a polynomial reduction of the shortest path problem with forbidden paths to a classic shortest path problem. Its significant advantage over the first approach is that it allows considering forbidden paths in more general shortest path problems such as the shortest path problem with resource constraints. 相似文献