Qianbin Chen, Ling Wang, Yuanpeng Gao et al. · China Communications · 2017
Cognitive radio networks (CRNs) are expected to improve spectrum utilization efficiently by allowing secondary users (SUs) to opportunistically access the licensed spectrum of primary users (PUs). In CRNs, source and destination SUs may achieve information interaction in an ad hoc manner. In the case that no direct transmission link between the SU transmission pairs is available, multi-hop relay SUs can be applied to forward information for the source and destination SUs, resulting in multi-hop CRNs. In this paper, we consider a multi-hop CRN consisting of multiple PUs, SU transmission pairs and relay SUs. Stressing the importance of transmission hops and the tradeoff between data rate and power consumption, we propose an energy efficient constrained shortest path first (CSPF)-based joint resource allocation and route selection algorithm, which consists of two sub-algorithms, i.e., CSPF-based route selection sub-algorithm and energy efficient resource allocation sub-algorithm. More specifically, we first apply CSPF-based route selection sub-algorithm to obtain the shortest candidate routes (SCRs) between the SU pair under the transmission constraints. Then, an energy efficient resource allocation problem of the SCRs is formulated and solved by applying iterative algorithm and Lagrange dual method. Simulation results demonstrate the effectiveness of the proposed algorithm.
Cited by 7
Ernesto de Queirós Vieira Martins, Marta Margarida Braz Pascoal, José Luis Esteves dos Santos · 1998
The shortest path problem is a classical network programming problem that has been extensively studied. The problem of determining not only the shortest path, but also listing the K shortest paths (for a given integer K > 1) is also a classical one but has not been studied so intensively, despite its obvious practical interest. Two different types of problems are usually considered: the unconstrained and the constrained K shortest paths problem. While in the former no restriction is considered in the definition of a path, in the constrained K shortest paths problem all the paths have to satisfy some condition -- for example, to be loopless. In this paper we are concerned with the unconstrained ranking shortest paths problem. In the first part the problem is viewed as a generalization of the classical shortest path problem; conditions for finiteness and for the optimality principle being satisfied are studied as well as labeling shortest path algorithms are generalized. In the second part \n...
Cited by 0
Yoichi Iwata, Yutaro Yamaguchi · arXiv (Cornell University) · 2019
We study a constrained shortest path problem in group-labeled graphs with nonnegative edge length, called the shortest non-zero path problem. Depending on the group in question, this problem includes two types of tractable variants in undirected graphs: one is the parity-constrained shortest path/cycle problem, and the other is computing a shortest noncontractible cycle in surface-embedded graphs. For the shortest non-zero path problem with respect to finite abelian groups, Kobayashi and Toyooka (2017) proposed a randomized, pseudopolynomial-time algorithm via permanent computation. For a slightly more general class of groups, Yamaguchi (2016) showed a reduction of the problem to the weighted linear matroid parity problem. In particular, some cases are solved in strongly polynomial time via the reduction with the aid of a deterministic, polynomial-time algorithm for the weighted linear matroid parity problem developed by Iwata and Kobayashi (2021), which generalizes a well-known fact that the parity-constrained shortest path problem is solved via weighted matching. In this paper, as the first general solution independent of the group, we present a rather simple, deterministic, and strongly polynomial-time algorithm for the shortest non-zero path problem. The algorithm is based on Dijkstra's algorithm for the unconstrained shortest path problem and Edmonds' blossom shrinking technique in matching algorithms; this approach is inspired by Derigs' faster algorithm (1985) for the parity-constrained shortest path problem via a reduction to weighted matching. Furthermore, we improve our algorithm so that it does not require explicit blossom shrinking, and make the computational time match Derigs' one. In the speeding-up step, a dual linear programming formulation of the equivalent problem based on potential maximization for the unconstrained shortest path problem plays a key role.
Cited by 0Open access
Pan Liu, Wulan Huang · Connection Science · 2022
Highly efficient algorithms for solving the time constrained shortest path problem have been highlighted over the past decades to reduce the cost of vehicle travel in the road network. The paper presents a novel graph algorithm comprising three stages to acquire a time constrained shortest path between any two nodes on the map. In the first stage, the undirected graph is transformed into a directed graph (DT graph) by deleting edges that must not be included in any of the time constrained shortest paths. A variant DT tree with the destination as the root and the source as the leaf is then constructed from the DT graph in the second stage. By finding the minimal difference value between leaves and the root of the variant DT tree, we can eventually obtain a time constrained shortest path from the variant DT tree in the third stage. Experimental results show that our algorithm not only requires less running time than some classical graph algorithms but also can work immediately in the first stage without knowing the information of both the destination and a specific time constraint.
Cited by 2Open access
John Canny, John Reif · 1987
We present the first lower bounds for shortest path problems (including euclidean shortest path) in three dimensions, and for some constrained motion planning problems in two and three dimensions. Our proofs are based a technique called free path encoding and use homotopy equivalence classes of paths to encode state. We first apply the method to the shortest path problem in three dimensions. The problem is to find the shortest path under an L p metric (e.g. a euclidean metric) between two points amid polyhedral obstacles. Although this problem has been extensively studied, there were no previously known lower bounds. We show that there may be exponentially many shortest path classes in single-source multiple-destination problems, and that the single-source single-destination problem is NP-hard. We use a similar proof technique to show that two dimensional dynamic motion planning with bounded velocity is NP-hard. Finally we extend the technique to compliant motion planni...
Cited by 0
Guy Desaulniers, Daniel L. Villeneuve · Transportation Science · 2000
This paper considers the shortest path problem with waiting costs (SPWC) as an extension to the shortest path problem with time windows. The problem consists of finding the minimum cost path in a network, where cost and time are two independent quantities associated with a path. Path feasibility is constrained by time windows at each node and a linear cost penalty is imposed for each unit of time spent waiting along the path. Starting from a known, nonlinear, integer programming formulation, we propose two alternative formulations for which algorithms already exist. First, we indicate how to transform the SPWC into a shortest path problem with time windows and linear node costs. Second, we prove that the SPWC can also be formulated as a two-resource generalized shortest path problem with resource constraints. Computational results used to compare these alternative formulations are presented.
Cited by 54
Wen‐Jui Li, Hung-ping Tsao, Osman Ulular · Networks · 1995
Abstract We study two related constrained shortest path problems in which the nodes are partitioned into series/parallel clusters. These and many other constrained shortest path problems occur in optimizing the layout of private networks embedded in a larger telecommunications network. The first problem deals with a situation in which, in addition to each edge being assigned a nonnegative integer weight, each node is also assigned a nonnegative integer weight, and the constraint on the path is that the total node weight incurred within each cluster should not exceed a given nonnegative integer /. The second problem considers two constraints: (i) a path cannot contain more than / nodes in one cluster and (ii) a path must traverse through at least one of a given set of special nodes in each of the traversed clusters. We propose efficient exact algorithms for solving both problems. Numerical examples are also provided.
Cited by 6
Ahmadi, Saman · Figshare · 2023
The first part of this thesis introduces two solution methods for energy-optimal path finding for Electric Vehicles (EVs). It also develops a complete pickup-and-delivery model with EVs. The second part addresses the key topics of bi-objective and weight constrained path finding. It first presents a new bi-objective search framework that improves the runtime and memory usage of the state of the art by several factors. It then introduces four fast algorithms for the weight constrained shortest path problem and show how our enhanced algorithms can improve the performance over the state of the art by several orders of magnitude.
Cited by 0Open access
Ahmadi, Saman · Monash University · 2023
The first part of this thesis introduces two solution methods for energy-optimal path finding for Electric Vehicles (EVs). It also develops a complete pickup-and-delivery model with EVs. The second part addresses the key topics of bi-objective and weight constrained path finding. It first presents a new bi-objective search framework that improves the runtime and memory usage of the state of the art by several factors. It then introduces four fast algorithms for the weight constrained shortest path problem and show how our enhanced algorithms can improve the performance over the state of the art by several orders of magnitude.
Cited by 0Open access
Yuanpeng Gao, Ling Wang, Rong Chai · 2017
In this paper, a multi-hop cognitive relay network consisting of multiple PU transmission pairs, SU transmission pairs and relay SUs is considered. To achieve the performance enhancement of multi-hop transmission links between SU pairs, an energy efficient constrained shortest path first (CSPF)-
Cited by 0Open access
Longcheng Liu, Yong He · Progress in Natural Science Materials International · 2006
Abstract In this paper, we consider two network improvement problems with given discrete values: the inverse minimum spanning tree problem and the reverse shortest-path problem, where the decrements of the weight of the edges are given discrete values. First for the three models of the inverse minimum spanning tree problem (the sum-type, the bottleneck-type and the constrained bottlenecktype), we present their respective strongly polynomial algorithms. Then, we show that the reverse shortest-path problem is strongly NP-complete. Supported by National Science Foundation of China (Grant No. 60021201)
Cited by 6
Y-L Chen, Dan B. Rinks, Kai Tang · Journal of the Operational Research Society · 2001
The time-constrained shortest path problem is an important generalisation of the classical shortest path problem and in recent years has attracted much research interest. We consider a time-schedule network, where every node in the network has a list of pre-specified departure times and departure from a node may take place only at one of these departure times. The objective of this paper is to find the first K minimum cost simple paths subject to a total time constraint. An efficient polynomial time algorithm is developed. It is also demonstrated that the algorithm can be modified for finding the first K paths for all possible values of total time.
Cited by 9
Luigi Di Puglia Pugliese, Francesca Guerriero · International Journal of Supply Chain and Inventory Management · 2015
This paper addresses the time dependent multi-objective constrained shortest path problem. Solving the problem aims at providing the user a Pareto-optimal solution associated with an efficient path. The solution process takes into account information given by the user in order to obtain a path, satisfying his/her requirements. For the first time, more than two criteria are considered and the reference point methodology is used to define the aggregation function. In addition, knapsack-like constraints are introduced in the formulation in order to model budget restrictions. Dynamic-programming-based algorithms are devised and tested on randomly generated networks and on real life instances derived from US city maps. The computational results underline that the proposed algorithms are able to solve the problem in a reasonable amount of time. This is a good result since the problem considered contains features of three NP-hard problems: the multi-objective, the constrained and the time dependent shortest path problems.
Cited by 0
Axel Parmentier · theses.fr (ABES) · 2016
This thesis develops algorithms for resource constrained shortest path problems, and uses them to solve the pricing subproblems of column generation approaches to some airline operations problems.Resource constrained shortest path problems are usually solved using a smart enumeration of the non-dominated paths. Recent improvements of these enumeration algorithms rely on the use of bounds on path resources to discard partial solutions. The quality of the bounds determines the performance of the algorithm. Our main contribution to the topic is to introduce a standard procedure to generate bounds on paths resources in a general setting which covers most resource constrained shortest path problems, among which stochastic versions. In that purpose, we introduce a generalization of the resource constrained shortest path problem where the resources are taken in a lattice ordered monoid. The resource of a path is the monoid sum of the resources of its arcs. The problem consists in finding a path whose resource minimizes a non-decreasing cost function of the path resource among the paths that satisfy a given constraint. Enumeration algorithms are generalized to this framework. We use lattice theory to provide polynomial procedures to find good quality bounds. The efficiency of the approach is proved through an extensive numerical study on deterministic and stochastic path problems. Interestingly, the bounding procedures can be seen as generalizations to lattice ordered monoids of some algebraic path problem algorithms which initially work with resources in a semiring.Given a set of flight legs operated by an airline, the aircraft routing and the crew pairing problem build respectively the sequences of flight legs operated by airplanes and crews at minimum cost. As some sequences of flight legs can be operated by crews only if they stay in the same aircraft, the two problems are linked. The current practice in the industry is to solve first the aircraft routing, and then the crew pairing problem, leading to a non-optimal solution. During the last decade, solution schemes for the integrated problem have been developed. We propose a solution scheme for the integrated problem based on two new ingredients: a compact integer program approach to the aircraft routing problem, and a new algorithm for the pricing subproblem of the usual column generation approach to the crew pairing problem, which is based on our resource constrained shortest path framework. We then generalize the algorithm to take into account delay propagation through probabilistic constraints. The algorithms enable to solve to near optimality Air France industrial instances
Cited by 0Open access
James C. A. Main · ArXiv.org · 2023
We study the memory requirements of Nash equilibria in turn-based multiplayer games on possibly infinite graphs with reachability, shortest path and Büchi objectives. We present constructions for finite-memory Nash equilibria in these games that apply to arbitrary game graphs, bypassing the finite-arena requirement that is central in existing approaches. We show that, for these three types of games, from any Nash equilibrium, we can derive another Nash equilibrium where all strategies are finite-memory such that the same players accomplish their objective, without increasing their cost for shortest path games. Furthermore, we provide memory bounds that are independent of the size of the game graph for reachability and shortest path games. These bounds depend only on the number of players. To the best of our knowledge, we provide the first results pertaining to finite-memory constrained Nash equilibria in infinite arenas and the first arena-independent memory bounds for Nash equilibria.
Cited by 0Open access
Alpár Jüttner, Csaba Király, Lydia Mirabel Mendoza-Cadena et al. · arXiv (Cornell University) · 2023
We consider the Shortest Odd Path problem, where given an undirected graph $G$, a weight function on its edges, and two vertices $s$ and $t$ in $G$, the aim is to find an $(s,t)$-path with odd length and, among all such paths, of minimum weight. For the case when the weight function is conservative, i.e., when every cycle has non-negative total weight, the complexity of the Shortest Odd Path problem had been open for 20 years, and was recently shown to be NP-hard. We give a polynomial-time algorithm for the special case when the weight function is conservative and the set $E^-$ of negative-weight edges forms a single tree. Our algorithm exploits the strong connection between Shortest Odd Path and the problem of finding two internally vertex-disjoint paths between two terminals in an undirected edge-weighted graph. It also relies on solving an intermediary problem variant called Shortest Parity-Constrained Odd Path where for certain edges we have parity constraints on their position along the path. Also, we exhibit two FPT algorithms for solving Shortest Odd Path in graphs with conservative weight functions. The first FPT algorithm is parameterized by $|E^-|$, the number of negative edges, or more generally, by the maximum size of a matching in the subgraph of $G$ spanned by $E^-$. Our second FPT algorithm is parameterized by the treewidth of $G$.
Cited by 0Open access
Gamal Sallam, Gagan Gupta, Bin Li et al. · arXiv (Cornell University) · 2018
With the advent of Network Function Virtualization (NFV), Physical Network Functions (PNFs) are gradually being replaced by Virtual Network Functions (VNFs) that are hosted on general purpose servers. Depending on the call flows for specific services, the packets need to pass through an ordered set of network functions (physical or virtual) called Service Function Chains (SFC) before reaching the destination. Conceivably for the next few years during this transition, these networks would have a mix of PNFs and VNFs, which brings an interesting mix of network problems that are studied in this paper: (1) How to find an SFC-constrained shortest path between any pair of nodes? (2) What is the achievable SFC-constrained maximum flow? (3) How to place the VNFs such that the cost (the number of nodes to be virtualized) is minimized, while the maximum flow of the original network can still be achieved even under the SFC constraint? In this work, we will try to address such emerging questions. First, for the SFC-constrained shortest path problem, we propose a transformation of the network graph to minimize the computational complexity of subsequent applications of any shortest path algorithm. Second, we formulate the SFC-constrained maximum flow problem as a fractional multicommodity flow problem, and develop a combinatorial algorithm for a special case of practical interest. Third, we prove that the VNFs placement problem is NP-hard and present an alternative Integer Linear Programming (ILP) formulation. Finally, we conduct simulations to elucidate our theoretical results.
Cited by 3Open access
Tetsuo Asano, Wolfgang Mulzer, Yajun Wang · 2010
Abstract. We present two space-efficient algorithms. First, we show how to report a simple path between two arbitrary nodes in a given tree. Using a technique called “computing instead of storing”, we can design a naive quadratic-time algorithm for the problem using only constant work space, i.e., O(log n) bits in total for the work space, where n is the number of nodes in the tree. Then, another technique “controlled recursion” improves the time bound to O(n 1+ε) for any positive constant ε. Second, we describe how to compute a shortest path between two points in a simple n-gon. Although the shortest path problem in general graphs is NL-complete, this constrained problem can be solved in quadratic time using only constant work space. 1
Cited by 0
Chawalit Jeenanunta, Antoine G. Hobeika, Ebru K. Bish et al. · 2004
In this dissertation, we consider two important problems pertaining to the analysis of transportation systems. The first of these is an approach-dependent, time-dependent, label-constrained shortest path problem that arises in the context of the Route Planner Module of the Transportation Analysis Simulation System (TRANSIMS), which has been developed by the Los Alamos National Laboratory for the Federal Highway Administration. This is a variant of the shortest path problem defined on a transportation network comprised of a set of nodes and a set of directed arcs such that each arc has an associated label designating a mode of transportation, and an associated travel time function that depends on the time of arrival at the tail node, as well as on the node via which this node was approached. The lattermost feature is a new concept injected into the time-dependent, label-constrained shortest path problem, and is used to model turnpenalties in transportation networks. The time spent at an intersection before entering the next link would depend on whether we travel straight through the intersection, or make a right turn at it, or make a left turn at it. Accordingly, we model this situation by incorporating within each link’s travel time function a dependence on the link via which
Cited by 0
Bijvoet, Bas · Mendeley Data · 2025
This real-world dataset supports a case study on urban freight distribution for HoReCa (hotels, restaurants, and cafés) in Amsterdam’s city center. It enables the simulation and optimization of multimodal two-echelon vehicle routing problems (2E-VRPs), where the first echelon uses waterborne transport (via canals) and the second echelon uses road-based transport. The dataset includes: Multimodal Networks: - A first-echelon (FE) network over Amsterdam’s canals, constrained by vessel profile compatibility (profile B), based on canal passage profiles of Amsterdam (in Dutch: doorvaartprofielen). - A second-echelon (SE) road network with both directed (vehicle) and undirected (walking) paths. Shortest Path Matrices: - Directed shortest path matrix for FE network routing. - Directed and undirected shortest path matrices for SE network routing. Demand Sets: - Ten daily demand scenarios for 1620 HoReCa establishments, generated using randomized procedures. Satellite Service Network Designs (SNDs): - A set of service network design scenarios that define which of the potential satellites (transshipment facilities) are active for each configuration. Geospatial Data: - Shapefiles for HoReCa locations, satellite locations, and FE and SE network segments and nodes, bundled with a QGIS project for visualization and spatial analysis. Figures: - Visualizations of the multimodal (canal and street) network canal and street networks, demand distributions, and satellite coverage. This dataset was developed in collaboration with the Municipality of Amsterdam and is intended to facilitate research on multimodal logistics, urban sustainability, policy-driven transport planning, and algorithmic developments in advanced 2E-VRPs within constrained city environments.
Cited by 0Open access