skip to main content

Attention:

The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 11:00 PM ET on Thursday, October 10 until 2:00 AM ET on Friday, October 11 due to maintenance. We apologize for the inconvenience.


This content will become publicly available on December 4, 2024

Title: Turn Constrained Shortest Path
Given a transportation network, a source node s, a destination node t , and the number of maximum possible turnings b , the Turn-Constrained Shortest Path (TCSP) problem is to find the route that minimizes the travel distance and meets the turn-constraint. The TCSP problem is important for societal applications such as shipping and logistics, emergency route planning, and traffic management services. We propose novel approaches for TCSP to meet the turn-constraint while minimizing the travel distance for the vehicle route. Experiments using real-world datasets demonstrated that the proposed algorithms can minimize the travel distance and meet the turn-constraint; furthermore, it has comparable solution quality to the unconstrained shortest path and significantly reduces the computational cost.  more » « less
Award ID(s):
1844565
NSF-PAR ID:
10487843
Author(s) / Creator(s):
;
Publisher / Repository:
IEEE
Date Published:
Journal Name:
International Conference on Smart Communities: Improving Quality of Life using AI, Robotics and IoT (HONET)
ISSN:
1949-4092
ISBN:
979-8-3503-3111-0
Page Range / eLocation ID:
1 to 6
Subject(s) / Keyword(s):
constrained shortest route, routing service, emergency management
Format(s):
Medium: X
Location:
Boca Raton, FL, USA
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    Urban street networks are subject to a variety of random disruptions. The impact of movement restrictions (e.g., one-way or left-turn restrictions) on the ability of a network to overcome these disruptions—that is, its resilience—has not been thoroughly studied. To address this gap, this paper investigates the resilience of one-way and two-way square grid street networks with and without left turns under light traffic conditions. Networks are studied using a simplified routing algorithm that can be examined analytically and a microsimulation that describes detailed vehicle dynamics. In the simplified method, routing choices are enumerated for all possible origin–destination (OD) combinations to identify how the removal of a link affects operations, both when knowledge of the disruption is and is not available at the vehicle’s origin. Disruptions on two-way networks that allow left turns tend to have little impact on travel distances because of the availability of multiple shortest paths between OD pairs and the flexibility in route modification. Two-way networks that restrict left turns at intersections only have a single shortest-distance path between any OD pair and thus experience larger increases in travel distance, even when the disruption is known ahead of time. One-way networks sometimes have multiple shortest-distance routes and thus travel distances increase less than two-way network without left turns when links are disrupted. These results reveal a clear tradeoff between improved efficiency and reduced resilience for networks that have movement restrictions, and can be used as a basis to study network resilience under more congested scenarios and in more realistic network structures. 
    more » « less
  2. Traditionally vehicles act only as servers in transporting passengers and goods. With increasing sensor equipment in vehicles, including automated vehicles, there is a need to test algorithms that consider the dual role of vehicles as both servers and sensors. The paper formulates a sequential route selection problem as a shortest path problem with on-time arrival reliability under a multi-armed bandit setting, a type of reinforcement learning model. A decision-maker has to make a finite set of decisions sequentially on departure time and path between a fixed origin-destination pair such that on-time reliability is maximized while travel time is minimized. The upper confidence bound algorithm is extended to handle this problem. Several tests are conducted. First, simulated data successfully verifies the method, then a real-data scenario is constructed of a hotel shuttle service from midtown Manhattan in New York City providing hourly access to John F. Kennedy International Airport. Results suggest that route selection with multi-armed bandit learning algorithms can be effective but neglecting passenger scheduling constraints can have negative effects on on-time arrival reliability by as much as 4.8% and combined reliability and travel time by 66.1%. 
    more » « less
  3. null (Ed.)
    We consider the problem of collective exploration of a known n- node edge-weighted graph by k mobile agents that have limited energy but are capable of energy transfers. The agents are initially placed at an arbitrary subset of nodes in the graph, and each agent has an initial, possibly different, amount of energy. The goal of the exploration problem is for every edge in the graph to be traversed by at least one agent. The amount of energy used by an agent to travel distance x is proportional to x. In our model, the agents can share energy when co-located: when two agents meet, one can transfer part of its energy to the other. For an n-node path, we give an O(n+k) time algorithm that either nds an exploration strategy, or reports that one does not exist. For an n-node tree with l leaves, we give an O(n+lk^2) algorithm that finds an exploration strategy if one exists. Finally, for the general graph case, we show that the problem of deciding if exploration is possible by energy-sharing agents is NP-hard, even for 3-regular graphs. In addition, we show that it is always possible to find an exploration strategy if the total energy of the agents is at least twice the total weight of the edges; moreover, this is asymptotically optimal. 
    more » « less
  4. Traveling to different destinations is a major part of our lives. We visit a variety of locations both during our daily lives and when we are on vacation. How can we find the best way to navigate from one place to another? Perhaps we can test all of the different ways of traveling between two places, but another method is to use mathematics and computation to find a shortest path between them. In this article, we discuss how to construct shortest paths and introduce Dijkstra’s algorithm to minimize the total cost of a path, where the cost may be the travel distance, the travel time, or some other quantity. We also discuss how to use shortest paths in the real world to save time and increase traveling efficiency. 
    more » « less
  5. This paper considers resource constrained path planning for a Dubins agent. Resource constraints are modeled as path integrals that exert a path-dependent load on the agent that must not exceed an upper bound. A backtracking mechanism is proposed for the Hybrid-A* graph search algorithm to determine the minimum time path in the presence of the path loading constraint. The new approach is built on the premise that inadmissibility of a node on the graph must depend on the loading accumulated along the path taken to arrive at its location. Conventional hybrid-A* does not account for this fact, causing it to become suboptimal or even infeasible in the presence of resource constraints. The new approach helps "reset'' the graph search by backing away from a node when the loading constraint is exceeded, and redirecting the search to explore alternate routes to arrive at the same location, while keeping the path load under its stipulated threshold. Backtracking Stopping criterion is based on relaxation of the path load along the search path. Case studies are presented and numerical comparisons are made with the Lagrange relaxation method to solving equivalent resource-constrained shortest path problems. 
    more » « less