排序方式: 共有5条查询结果,搜索用时 46 毫秒
1
1.
We present some reoptimization techniques for computing (shortest) hyperpath weights in a directed hypergraph. These techniques are exploited to improve the worst-case computational complexity (as well as the practical performance) of an algorithm finding the K shortest hyperpaths in acyclic hypergraphs. 相似文献
2.
We compare two different models for multicriterion routing in stochastic time-dependent networks: the classic “time-adaptive” model and the more flexible “history-adaptive” one. We point out several properties of the sets of efficient solutions found under the two models. We also devise a method for finding supported history-adaptive solutions. 相似文献
3.
Relund Nielsen Lars; Allan Andersen Kim; Pretolani Daniele 《IMA Journal of Management Mathematics》2003,14(3):271-303
In relevant application areas, such as transportation and telecommunications,there has recently been a growing focus on random time-dependentnetworks (RTDNs), where arc lengths are represented by time-dependentdiscrete random variables. In such networks, an optimal routingpolicy does not necessarily correspond to a path, but ratherto an adaptive strategy. Finding an optimal strategy reducesto a shortest hyperpath problem that can be solved quite efficiently. The bicriterion shortest path problem, i.e. the problem offinding the set of efficient paths, has been extensively studiedfor many years. Recently, extensions to RTDNs have been investigated.However, no attempt has been made to study bicriterion strategies.This is the aim of this paper. Here we model bicriterion strategy problems in terms of bicriterionshortest hyperpaths, and we devise an algorithm for enumeratingthe set of efficient hyperpaths. Since the computational effortrequired for a complete enumeration may be prohibitive, we proposesome heuristic methods to generate a subset of the efficientsolutions. Different criteria are considered, such as expectedor maximum travel time or cost; a computational experience isreported. 相似文献
4.
Lars Relund Nielsen Erik Jørgensen Søren Højsgaard 《Annals of Operations Research》2011,190(1):289-309
In agriculture Markov decision processes (MDPs) with finite state and action space are often used to model sequential decision
making over time. For instance, states in the process represent possible levels of traits of the animal and transition probabilities
are based on biological models estimated from data collected from the animal or herd. 相似文献
5.
Lars Relund Nielsen Kim Allan Andersen Daniele Pretolani 《European Journal of Operational Research》2014
In this paper we address optimal routing problems in networks where travel times are both stochastic and time-dependent. In these networks, the best route choice is not necessarily a path, but rather a time-adaptive strategy that assigns successors to nodes as a function of time. Nevertheless, in some particular cases an origin–destination path must be chosen a priori, since time-adaptive choices are not allowed. Unfortunately, finding the a priori shortest path is an NP-hard problem. 相似文献
1