日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

交通経路設計arXiv:2207.04505

交通経路設計における経路追加の性質について

On the properties of path additions for traffic routing

シェア:XThreadsFacebookLINEはてブBluesky

交通ネットワークに経路を追加したときの総旅行時間への影響を、自己利益的なUEと協調的なMC/SOで比較し、協調的経路では単調性が成り立つことなどを証明した。

著者: Matteo Bettini, Amanda Prorok

分類: cs.MA, cs.RO, cs.SY, eess.SY

原文アブストラクト

In this paper we investigate the impact of path additions to transport networks with optimised traffic routing. In particular, we study the behaviour of total travel time, and consider both self-interested routing paradigms, such as User Equilibrium (UE) routing, as well as cooperative paradigms, such as classic Multi-Commodity (MC) network flow and System Optimal (SO) routing. We provide a formal framework for designing transport networks through iterative path additions, introducing the concepts of trip spanning tree and trip path graph. Using this formalisation, we prove multiple properties of the objective function for transport network design. Since the underlying routing problem is NP-Hard, we investigate properties that provide guarantees in approximate algorithm design. Firstly, while Braess' paradox has shown that total travel time is not monotonic non-increasing with respect to path additions under self-interested routing (UE), we prove that, instead, monotonicity holds for cooperative routing (MC and SO). This result has the important implication that cooperative agents make the best use of redundant infrastructure. Secondly, we prove via a counterexample that the intuitive statement `adding a path to a transport network always grants greater or equal benefit to users than adding it to a superset of that network' is false. In other words we prove that, for all the routing formulations studied, total travel time is not supermodular with respect to path additions. While this counter-intuitive result yields a hardness property for algorithm design, we provide particular instances where, instead, the property of supermodularity holds. Our study on monotonicity and supermodularity of total travel time with respect to path additions provides formal proofs and scenarios that constitute important insights for transport network designers.

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  3. 3newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  4. 4NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  5. 5UC BerkeleyとNVIDIAの研究者、AIエージェントでロボット制御コードを仮想環境で改善研究・技術

PR・アフィリエイト広告

FRONTIER(GPU搭載BTOパソコン)

FRONTIER(GPU搭載BTOパソコン)の公式広告バナーFRONTIERでGPU搭載PCを見る ↗
PR本紙発行元 EmplifAI