Temporally Flexible Transport Scheduling on Networks with Departure-Arrival Constriction and Nodal Capacity Limits Anqi Dong, Karl H. Johansson, Johan Karlsson Abstract We investigate the optimal transport (OT) problem over networks, wherein supply and demand are conceptualized as temporal marginals governing departure rates of particles from source nodes and arrival rates at sink nodes. This setting extends the classical OT framework, where all mass is conventionally assumed to depart at t = 0 t=0 and arrive at t = t f t=t_{f} . Our generalization accommodates departures and arrivals at specified times, referred as departure–arrival (DA) constraints. In particular, we impose nodal-temporal flux constraints at source and sink nodes, characterizing two distinct scenarios: (i) Independent DA constraints, where departure and arrival rates are prescribed independently, and (ii) Coupled DA constraints, where each particle’s transportation time span is explicitly specified. We establish that OT with independent DA constraints admits a multi-marginal optimal transport formulation, while the coupled DA case aligns with the unequal-dimensional OT framework. For line graphs, we analyze the existence and uniqueness of the solution path. For general graphs, we use a constructive path-based reduction and optimize over a prescribed set of paths. From a computational perspective, we consider entropic regularization of the original problem to efficiently provide solutions based on multi-marginal Sinkhorn method, making use of the graphical structure of the cost to further improve scalability. Our numerical simulation further illustrates the linear convergence rate in terms of marginal violation. Keywords: Optimal transport, graphical transportation, departure–arrival constraint, temporal flexibility, multi–marginal Sinkhorn algorithm 1 Introduction Network flow problems aim to optimize the movement of commodities across a network while satisfying flow capacity and conservation constraints. These models have broad applications in mathematics, computer science, and transportation optimization [ 1 ] , with notable examples including the maximum-flow and the minimum-cost flow problems [ 13 ] . The latter focuses on efficiently transporting goods or allocating resources (for instance, bandwidth and power) at minimal cost and plays a central role in the distribution of goods, information, and platoons [ 17 , 25 ] . In most of these classical formulations, time either does not appear explicitly or enters only through steady-state capacities rather than as a variable that can be controlled. In many networked logistics and service systems, however, time is the primary degree of freedom. Control here is, in essence, a schedule: a measured release of mass, orchestrated in time, that guides it through junctions and grants it passage downstream. In port drayage, cranes, yard blocks, and gates operate under tight time-varying capacity. Export cutoffs couple departures to required arrivals, so planning becomes a joint choice of path and crossing times that keeps equipment busy without queues [ 44 ] . In urban rail and bus transit, terminal departures and arrivals are prescribed, while headway and conflict windows impose capacity at stations and junctions. Operations hinge on pacing trains through dwell and merges, so that the timetable remains feasible [ 4 ] . In data-center service chains, each request traverses firewall, cache, and inference under per-function throughput and end-to-end latency targets. Admission and timing at each hop prevent overload and deliver service objectives [ 32 ] . These examples motivate a framework in which network transport cost, time-varying capacities, and departure–arrival specifications are unified in a scheduling-and-control viewpoint. The optimal transport (OT) problem, originally proposed by Monge [ 33 ] , later formalized by Kantorovich [ 28 ] , and more recently extended to dynamic formulations [ 3 ] , has attracted significant attention across mathematics [ 47 ] , control [ 8 , 9 , 18 ] , and computer science [ 38 ] . In particular, one considers two probability measures \mu and \nu and seeks a transportation plan that transfers mass from the former to the latter while minimizing a prescribed cost. The source distribution \mu represents the initial mass configuration, and the target distribution \nu specifies the demand. The Monge formulation [ 33 ] , with a quadratic cost in \mathbb{R}^{n} , seeks a transport map T:x\mapsto y=T(x) that minimizes the cost functional \displaystyle J(T):=\int_{\mathbb{R}^{n}}\|x-T(x)\|_{2}^{2}\;\mu(dx), (1) among admissible maps T that push \mu onto \nu . However, such a map may not always exist. The Kantorovich relaxation [ 28 ] reformulates the problem as an optimization over couplings between \mu and \nu . Instead of a deterministic transport map, it seeks a probability measure \pi on \mathbb{R}^{n}\times\mathbb{R}^{n} that has \mu and \nu as its marginals and minimizes \displaystyle J(\pi):=\int_{\mathbb{R}^{n}\times\mathbb{R}^{n}}\|x-y\|_{2}^{2}\;\pi(dx,dy). (2) This static view already captures the geometry of redistributing mass. Dynamic formulations interpret the same problem as continuous-time motion that moves \mu to \nu over a finite time horizon [ 3 ] , making the role of timing more explicit. A natural extension of OT relaxes the marginal constraints in the Kantorovich formulation and instead imposes upper and lower bounds on the marginal distributions or their cumulative functions [ 40 ] . Similarly, constraints can be imposed on the coupling itself, yielding a bi-marginal constraint of the form \underline{r}\leq\pi(dx,dy)\leq\overline{r} . Physical constraints along transport paths naturally arise in applications. Moment-type constraints were introduced in [ 39 , Section 4.6.3] and later generalized in [ 17 ] . Congestion effects as well as origin destination constraints, which can impede transport, have also been studied [ 23 , 25 ] . A path-dependent cost to mitigate congestion was considered in [ 6 ] , while [ 41 , Section 4] provides a comprehensive review of this topic. Constraints on probability densities have also been explored to model capacity limitations of transportation media [ 30 ] or dynamical flow constraints [ 22 ] . In addition, our recent work [ 45 ] focus on a specific flow-rate (also, momentum ) constraint imposed on momentum in a dynamic OT formulation, \underline{r}\leq\rho(t,x)v(t,x)\leq\overline{r}, which models a toll station. The same flow-rate bound was then reformulated within the multi-marginal Kantorovich framework [ 16 ] by introducing a “crossing time” as an additional marginal over the time variable, thereby the coupling jointly encodes where mass travels and when it passes each node. The present work builds on this line of thought and brings it into a network setting where time is the control input. We tie optimization and control by taking the schedule as the decision. Path-wise couplings and crossing-time profiles are chosen to minimize transport cost under marginal and capacity constraints. A schedule is a distribution of crossing times along each path. Boundary time profiles act as release and acceptance laws at the source and the sink. At each interior node, a single crossing-time profile meters flow and enforces conservation, since the same time index labels both incoming and outgoing mass under the capacity limit. From a network optimization perspective, our formulation can be viewed as minimum-cost flow problem with time flexibility. Classical minimum-cost flow fixes edge capacities and costs and optimizes how much mass uses each arc, while time either does not appear or is treated as a static resource. Here, the network and total transported mass are fixed, and time itself becomes control variable. The decision is when mass is allowed to traverse each node and edge, under explicit departure–arrival profiles and nodal throughput limits. In this sense, we lift minimum-cost flow from a static allocation problem to a path-wise scheduling problem while remaining within an optimal transport framework. Herein, we cast optimal transport on networks as a scheduling-and-control problem with time as the actuator. The framework is path-wise. Flows are represented by multi-dimensional couplings whose marginals encode source and sink distributions together with crossing-time profiles at interior nodes. In this way, release curves, delivery deadlines, and per-node throughput constraints are handled within a single optimal transport formulation rather than through ad hoc scheduling rules. To the best of the authors’ knowledge, this is the first framework that integrates departure–arrival specifications and time-varying nodal capacities into a path-wise optimal transport model on networks, provides structural conditions for well-posedness, and propose scalable Schrödinger-Fortet-Sinkhorn algorithm. The result is a unified description of network flow, timing, and capacity that fits naturally with boundary control, state constraints, and receding-horizon updates. We impose departure–arrival (DA) rationales in two regimes: i) Independent DA constraints: departure and arrival rates are prescribed separately as boundary controls. The schedule reshapes crossing times in order to satisfy both boundary laws and interior capacity limits. This setting is developed in Section 3 through Problems 1 and 1 ′ and leads to a multi-marginal optimal transport formulation with an additional time marginal at each node. ii) Coupled DA constraints: each particle’s transport duration is fixed, so the controller chooses a start time and the arrival time then follows deterministically. This regime is formulated in Section 4 as Problem 2 and 2 ′ . It yields an unequal-dimensional optimal transport problem with a hard link between release and delivery, suited to timetable and deadline-driven settings. Nodal flow-rate constraints act as state and input limits along each path and are enforced through cost terms and inequality constraints on crossing times. On line graphs, we provide feasibility and existence guarantees in Lemma 1 and Proposition 1 , and uniqueness guarantees in Theorems 1 and 2 . In the independent case, the cost satisfies a generalized Monge condition, while in the coupled case, it satisfies an x -twist condition as shown in Proposition 2 and Theorem 4 . These properties identify when a well-posed schedule exists and when it is uniquely determined by the DA and capacity specifications, and form the analytical backbone for the path-wise generalization and the entropic Sinkhorn-type algorithms that we develop later for large network instances. For general graphs, we introduce a node-aggregation reduction that preserves the transport dynamics while simplifying the topology. Nodes are collapsed into effective groups so that DA-constrained transport on large graphs can be analyzed and computed through lower-dimensional surrogates without losing the structure of capacities and schedules, as formalized in Problem 3 . This reduction keeps path-wise timing, nodal capacities, and DA specifications intact and therefore serves as a bridge between realistic network layouts and tractable line-graph models. On top of this reduction, we develop scalable algorithms based on entropic regularization and a graph-structured Sinkhorn scheme with shared nodal multipliers, summarized in Algorithm 1 . The shared multipliers act as time-indexed node prices that coordinate flow across all paths passing through a node and enforce both boundary and capacity constraints. The resulting alternating projection scheme performs explicit projections onto departure and arrival profiles and onto nodal throughput bounds, enabling large-scale structured transport on networks with explicit DA specifications and node-wise capacity limits. This scheme’s linear convergence rate is established in Theorem 5 and confirmed by numerical experiments in Section 6 . The rest of the paper is organized as follows. Section 2 formalizes the problem setup. Section 3 discusses the case where DA constraints are independent, and Section 4 considers the coupled DA setting. In Section 5 , we extend the problem from single-source and single-sink transportation over line graphs to general graphs and present node aggregation methods and a Sinkhorn algorithm tailored to the structure of the cost functionals. Numerical simulations are presented in Section 6 . Finally, Section 7 revisits the scheduling viewpoint, summarizes our theoretical and algorithmic contributions. 2 Problem setup and background We start with a recap of optimal transport, focusing on its extension from bi-marginal to multi-marginal formulations, marginal- and coupling-wise relaxations, and the incorporation of physical constraints. We then specialize to network-based optimal transport, which will serve as the reference point for the temporally flexible formulations in Sections 3 and 4 . 2.1 Multi-marginal optimal transport Multi-marginal optimal transport (MMOT) generalizes the classical optimal transport framework to settings with more than two marginals, and seeks a joint distribution that minimizes a high-dimensional cost while matching given marginals. Key challenges include establishing the existence and uniqueness of solutions for general transport costs. See, for instance, [ 10 , 29 , 37 ] . Given compactly supported non-negative measures \mu^{0},\mu^{1},\dots,\mu^{{\mathcal{T}}} on spaces \mathbb{R}^{n} and a continuous cost function c(x_{0},x_{1},\dots,x_{\mathcal{T}}) , the Monge formulation of MMOT seeks transport maps T_{\ell}:\mathbb{R}^{n}\to\mathbb{R}^{n} for all \ell=1,\dots,{\mathcal{T}} that minimize \displaystyle\int_{\mathbb{R}^{n}}c\big(x_{0},T_{1}(x_{0}),\dots,T_{\mathcal{T}}(x_{0})\big)\,d\mu^{0}(x_{0}), subject to T_{\ell}{}_{\sharp}\mu^{0}=\mu^{\ell} for \ell=1,\dots,{\mathcal{T}} . As usual, the push-forward notation T_{\ell}{}_{\sharp}\mu^{0}=\mu^{\ell} means that for any Borel set S\subset\mathbb{R}^{n} , \mu^{0}\big(T_{\ell}^{-1}(S)\big)=\mu^{\ell}(S) . As in the bi-marginal case, a Monge solution may fail to exist. The Kantorovich formulation of MMOT replaces transport maps by couplings and minimizes \displaystyle\langle c,\pi\rangle:=\int_{\mathbb{R}^{n}\times\dots\times\mathbb{R}^{n}}c(x_{0},\dots,x_{\mathcal{T}})\,d\pi(x_{0},\dots,x_{\mathcal{T}}), (3) over the set of admissible couplings \displaystyle\Pi(\mu^{0},\dots,\mu^{\mathcal{T}})=\Big\{\pi\;\Big|\;P_{\ell}(\pi)=\mu^{\ell},\ \ell=0,1,\dots,{\mathcal{T}}\Big\}, (4) and P_{\ell}(\pi) denotes the projection of \pi onto its \ell -th marginal, i.e., \displaystyle P_{\ell}(\pi):=\int_{\mathbb{R}^{n}\times\dots\times\mathbb{R}^{n}}d\pi(x_{0},\dots,x_{\ell-1},x_{\ell},x_{\ell+1},\dots,x_{{\mathcal{T}}}), where the iterated integral is taken over all variables x_{k} with k\neq\ell . 2.2 Conditions for uniqueness of the solution We next recall classical conditions that guarantee the uniqueness of the optimal coupling in the bi-marginal setting, and then their multi-marginal analogue. Definition 1 ( Monge condition [ 39 ] ) . A cost function c:\mathbb{R}^{2}\to\mathbb{R} is said to satisfy the Monge condition 1 1 1 Also, the Spence–Mirrlees condition in economics [ 10 , 41 ] if, for real variables x,y\in\mathbb{R} , its cross difference \Delta_{(x,x^{\prime})}^{(y,y^{\prime})}(c):=c(x,y)+c(x^{\prime},y^{\prime})-c(x,y^{\prime})-c(x^{\prime},y) satisfies \Delta_{(x,x^{\prime})}^{(y,y^{\prime})}(c)\leq 0 for all x^{\prime}\geq x and y^{\prime}\geq y . If c(x,y) is quasi-antitone, in the sense that \Delta_{(x,x^{\prime})}^{(y,y^{\prime})}(c)\leq 0 , or quasi-monotone, in the sense that \Delta_{(x,x^{\prime})}^{(y,y^{\prime})}(c)\geq 0 , then the minimizer of the transport problem with cost c is unique, see [ 5 ] and [ 39 , Theorem 3.1.2] . In matching theory, the cross-difference condition expresses that, for given matching pairs (x,y) and (x^{\prime},y^{\prime}) , swapping partners to (x,y^{\prime}) and (x^{\prime},y) cannot reduce the total cost. This rules out profitable swaps and leads to an optimal and stable matching. The link between cross differences and second derivatives is made precise through a Taylor expansion argument, as discussed in [ 5 , 7 , 10 ] and extended to higher dimensions in [ 36 ] . Definition 2 ( Twist condition [ 47 ] ) . Let c(x,y)\in C^{1} . The cost c is said to satisfy the twist condition if, for each fixed x , the map y\mapsto\nabla_{x}c(x,y) is injective, and for each fixed y , the map x\mapsto\nabla_{y}c(x,y) is injective. Equivalently, for all distinct pairs y\neq y^{\prime} and x\neq x^{\prime} , one has D_{x}c(x,y)\neq D_{x}c(x,y^{\prime}) and D_{y}c(x,y)\neq D_{y}c(x^{\prime},y) . In other words, the gradient \nabla_{x}c(x,y) uniquely determines y and \nabla_{y}c(x,y) uniquely determines x . This implies that optimal couplings are induced by transport maps and are therefore unique. The twist condition is thus a convenient sufficient criterion for the uniqueness of the optimal transport plan. In the multi-marginal setting, an analogous structure is obtained by imposing a Monge-type condition on all two-marginal projections of the cost. Definition 3 ( Generalized Monge condition [ 39 ] ) . Consider a cost functional c:\mathbb{R}^{n}\to\mathbb{R} of the form c(x_{1},\dots,x_{n}) , where (x_{1},\dots,x_{n}) lie in the support of a measure on {\mathcal{X}}^{n} with {\mathcal{X}}\subset\mathbb{R} . The cost c is said to satisfy the generalized Monge condition if, for any pair of indices 1\leq i0 . We assume that one unit of mass is dispatched from v_{0} and must reach v_{{\mathcal{T}}} , so that in the static setting, transport takes place along the single path {\mathbf{p}} and reduces to a shortest-path problem. We consider a departure-arrival over a line graph, in which departures from v_{0} , crossings at the intermediate nodes v_{1},\dots,v_{{\mathcal{T}}-1} , and arrivals at v_{{\mathcal{T}}} are described by time profiles subject to departure–arrival specifications and nodal capacity bounds. The mass flow is governed by departure and arrival rate constraints. The departure rate \mu^{0}(t) describes the mass density over time at which mass leaves the source node v_{0} , so that \int_{t}^{t+dt}\mu^{0}(\tau)\,d\tau is the amount departing in the interval [t,t+dt] . Similarly, the arrival rate \mu^{\mathcal{T}}(t) describes the mass density over time at which mass reaches the sink node v_{\mathcal{T}} , with \mu^{\mathcal{T}}(t)\,dt the amount arriving in [t,t+dt] . In addition to these boundary specifications, the flow is subject to rate bounds at each intermediate node along the path, \sigma^{i}(t)\leq r(v_{i}),\qquad i=1,\dots,{\mathcal{T}}-1, where \sigma^{i}(t) denotes the instantaneous rate of mass crossing node v_{i} . These constraints ensure that the throughput at each intermediate node does not exceed the prescribed flux limit, reflecting physical or logistical capacity. An illustration is given in Fig. 1 . Figure 1: Mass flow along the line graph {\mathbf{p}}=\{v_{0},v_{1},\dots,v_{{\mathcal{T}}-1},v_{\mathcal{T}}\} . Each particle departs from v_{0} according to the departure rate \mu^{0} , travels sequentially through intermediate nodes v_{1},v_{2},\dots,v_{{\mathcal{T}}-1} abides flow-rate constraints at each node, and arrives at the sink v_{\mathcal{T}} according to the arrival rate \mu^{\mathcal{T}} . Independent DA constraints refer to the case where the departure distribution \mu^{0}(t) and the arrival distribution \mu^{\mathcal{T}}(t) are prescribed separately, without specifying how individual departures are paired with arrivals. Our first step is to formulate the scheduling problem on a single intermediate node. This will serve as the basic building block for the multi-node line graph. We consider a single toll located at v_{1} , which imposes a flow-rate constraint \sigma^{1}(t)\leq r with threshold r>0 . The times at which mass departs from v_{0} , crosses v_{1} , and arrives at v_{2} are denoted by t_{0} , t_{1} , and t_{2} , respectively, and the cost of transporting mass along the two segments is modeled by \displaystyle c(t_{0},t_{1},t_{2})=\frac{w(v_{0},v_{1})}{t_{1}-t_{0}}+\frac{w(v_{1},v_{2})}{t_{2}-t_{1}}. (5) The first term measures the transit cost from v_{0} to v_{1} over the time interval t_{1}-t_{0} , and the second term the cost from v_{1} to v_{\mathcal{T}} over t_{2}-t_{1} . By optimizing this cost under the DA and capacity constraints, we obtain a temporally feasible transport plan that respects both spatial and temporal structure, as formalized below. Problem 1 . (Independent DA with single intermediate node) Given probability measures \mu^{0}(t_{0}) and \mu^{\mathcal{T}}(t_{2}) , along with a flow-rate bound r>0 , determine a probability measure \pi(t_{0},t_{1},t_{2}) on \mathcal{M}_{+}([0,t_{f}]^{3}) that minimizes \displaystyle\iiint_{t_{0},t_{1},t_{2}}c(t_{0},t_{1},t_{2})\,\pi(dt_{0},dt_{1},dt_{2}), (6a) subject to the departure and arrival constraints \displaystyle\iint_{t_{1},t_{2}}\pi(dt_{0},dt_{1},dt_{2})=\mu^{0}(t_{0}), (6b) \displaystyle\iint_{t_{0},t_{1}}\pi(dt_{0},dt_{1},dt_{2})=\mu^{\mathcal{T}}(t_{2}), (6c) and the flow-rate constraint \displaystyle\iint_{t_{0},t_{2}}\pi(dt_{0},dt_{1},dt_{2}):=\sigma^{1}(dt_{1})\leq rdt_{1}. (6d) In what follows, we first characterize when a feasible schedule exists (in terms of an ordering relation between \mu^{0} and \mu^{\mathcal{T}} ), then establish the existence of minimizers for suitable bounds r , and finally prove uniqueness of the optimal coupling by exploiting the Monge and generalized Monge structures introduced in Section 2 . 3.1 Feasibility We first characterize when a pair of independent DA profiles is compatible with a minimum travel time. Lemma 1 ( Feasibility of independent DA ). With fixed minimum travel time \Delta>0 , a pair (\mu^{0},\mu^{{\mathcal{T}}}) on [0,t_{f}] with \int_{0}^{t_{f}}\mu^{0}(dt_{0})=\int_{0}^{t_{f}}\mu^{{\mathcal{T}}}(dt_{{\mathcal{T}}})=1 is feasible if and only if \mu^{0} is dominated by the \Delta -shift of \mu^{{\mathcal{T}}} in first-order (stochastic) order [ 42 , Chapter 1] , that is, F_{0}(t)\ \geq\ F_{{\mathcal{T}}}(t+\Delta)\quad\text{for all }\;\;t\in[0,t_{f}], where F_{0}(t)=\int_{0}^{t}\mu^{0}(ds) and F_{{\mathcal{T}}}(t)=\int_{0}^{t}\mu^{{\mathcal{T}}}(d\tau) . Equivalently, for every bounded increasing test function \phi\colon\mathbb{R}\to\mathbb{R} , we have \int_{0}^{t_{f}}\phi(t)\,\mu^{0}(dt)\ \leq\ \int_{0}^{t_{f}}\phi(t-\Delta)\,\mu^{{\mathcal{T}}}(dt), with \phi(t-\Delta) understood as \phi(0) when t<\Delta [ 42 , Eq. 1.A.7] . In particular, we have 2 2 2 We write \supp(\cdot) for the support of a measure. \displaystyle\begin{aligned} \inf\supp(\mu^{{\mathcal{T}}})\ &\geq\ \inf\supp(\mu^{0})+\Delta,\\ \sup\supp(\mu^{{\mathcal{T}}})\ &\geq\ \sup\supp(\mu^{0})+\Delta.\end{aligned} Proof. For any feasible coupling with t_{{\mathcal{T}}}-t_{0}\geq\Delta almost surely, the event inclusion \{t_{{\mathcal{T}}}\leq t+\Delta\}\subseteq\{t_{0}\leq t\} holds for every t . Taking probabilities gives F_{{\mathcal{T}}}(t+\Delta)\leq F_{0}(t) for all t . Assume F_{0}(t)\geq F_{{\mathcal{T}}}(t+\Delta) for all t . Define the left-continuous generalized inverses F_{0}^{-1}(u)=\inf\{t\mid F_{0}(t)\geq u\} , and F_{{\mathcal{T}}}^{-1}(u)=\inf\{t\mid F_{{\mathcal{T}}}(t)\geq u\} . Then F_{{\mathcal{T}}}^{-1}(u)\ \geq\ F_{0}^{-1}(u)+\Delta for all u\in(0,1) . Define \pi as the image of the Lebesgue measure on (0,1) under the map u\ \mapsto\ \big(F_{0}^{-1}(u),\,F_{{\mathcal{T}}}^{-1}(u)\big) . By construction, the first marginal of \pi has CDF F_{0} and the second marginal has CDF F_{{\mathcal{T}}} . The pointwise inequality above gives t_{{\mathcal{T}}}\geq t_{0}+\Delta for \pi -almost every pair, hence \pi is feasible. The support bounds follow by evaluating F_{0}(t)\geq F_{{\mathcal{T}}}(t+\Delta) at t=\inf\supp(\mu^{{\mathcal{T}}})-\Delta and at t=\sup\supp(\mu^{0})-\Delta . ∎ The condition F_{0}(t)\geq F_{{\mathcal{T}}}(t+\Delta) is related to order-type comparisons between distributions (see, e.g., [ 27 , 42 ] ), but unlike in martingale optimal transport [ 2 ] we do not impose any martingale or mean-preserving constraint here. We only use it as a simple feasibility check for the DA pair. 3.2 Existence and uniqueness for single intermediate node Before analyzing uniqueness, we first establish the existence of a minimizer for Problem 1 . Proposition 1 ( Existence of solution ). For sufficiently large r , Problem 1 admits a minimizing solution \pi . Proof. The space of admissible measures \pi , namely \displaystyle\begin{aligned} &\Pi=\bigg\{\pi\in\mathcal{M}_{+}\big([0,t_{f}]^{3}\big)\Big|\;\iint_{t_{1},t_{2}}\!\!\!\!\!\!\pi=\mu^{0}(t_{0}),\ \iint_{t_{0},t_{1}}\!\!\!\!\!\!\pi=\mu^{\mathcal{T}}(t_{2}),\iint_{t_{0},t_{2}}\!\!\!\!\!\!\pi:=\sigma^{1}(t_{1})\leq r\,dt_{1}\bigg\},\end{aligned} (7) is tight and closed for narrow convergence. Hence it is weakly compact. Since the cost ( 6a ) is lower semicontinuous, the direct method gives existence of a minimizer once we know that \Pi is non-empty. We now show that \Pi is non-empty when r is large enough by an explicit construction. By Lemma 1 , the minimum travel time condition is equivalent to \displaystyle F_{{\mathcal{T}}}^{-1}(u)\geq F_{0}^{-1}(u)+\Delta\qquad\text{for all }u\in(0,1). (8) Fix \varepsilon\in(0,\Delta) and take sufficient large r so that \varepsilon+1/r<\Delta . Let u\sim\mathrm{Unif}(0,1) and s\sim\mathrm{Unif}(0,1/r) be independent, and define t_{0}=F_{0}^{-1}(u) , t_{2}=F_{{\mathcal{T}}}^{-1}(u) , and t_{1}=t_{0}+\varepsilon+s . Let \tilde{\pi} be the law of (t_{0},t_{1},t_{2}) . Then \tilde{\pi} has t_{0} - and t_{2} -marginals \mu^{0} and \mu^{{\mathcal{T}}} . Moreover, ( 8 ) and s\leq 1/r imply that t_{1}-t_{0}\geq\varepsilon and t_{2}-t_{1}\geq\Delta-\varepsilon-\frac{1}{r}>0 , so both traveling times are positive. The condition \varepsilon+1/r<\Delta means \epsilon plus the maximal delay 1/r still fits inside the available travel-time budget \Delta . Here, t_{1} is the crossing time at intermediate node. The constant \varepsilon is a fixed transit delay after departure, before any mass can reach the node. The extra waiting time s , sampled uniformly on an interval of length 1/r , spreads each departure cohort over a window of width 1/r so that the flow respects the capacity bound r . Finally, conditional on t_{0} , the variable t_{1} is uniform on an interval of length 1/r . Hence, for any Borel set S\subset[0,t_{f}] , we have \mathbb{P}(t_{1}\in S\mid t_{0})\leq r\,|S| since a uniform law on an interval of length 1/r has density r . Taking expectations yields to \sigma^{1}(S)=\mathbb{P}(t_{1}\in S)\leq r\,|S| , which is equivalent to \sigma^{1}\leq r\,dt_{1} . Therefore, there always exists a \tilde{\pi} so that \tilde{\pi}\in\Pi , and \Pi is non-empty. ∎ We are now in a position to establish the uniqueness of the optimizer for Problem 1 . For simplicity, we omit the superscript and adopt the notation \sigma^{1}\equiv\sigma for the remainder of this section. Lemma 2 ( Monotonicity ). Consider the cost function c_{t_{0},t_{1}}:=\frac{w(v_{0},v_{1})}{t_{1}-t_{0}}, where (t_{0},t_{1})\in\mathcal{M}_{+}\big([0,t_{f}]^{2}\big) , and let \mu^{0} and \sigma be measures supported on [0,t_{f}] . Assume that \sigma(t)\,dt is absolutely continuous with respect to the Lebesgue measure. Then, the minimizer of the Kantorovich problem \min_{\pi}\int_{t_{0}}\int_{t_{1}}c_{t_{0},t_{1}}\,\pi(dt_{0},dt_{1}), where \pi represents a coupling of the marginals \mu^{0}(dt_{0}) and \sigma(t_{1})\,dt_{1} , is unique and supported on the graph of a non-increasing function T^{\mathcal{D}}(t_{1}) . Proof. We first observe that for any two pairs (t_{1},t^{\prime}_{1}) and (t_{0},t^{\prime}_{0}) satisfying t_{f}>t_{1}>t^{\prime}_{1}>t_{0}>t^{\prime}_{0}>0 , it holds that \displaystyle\frac{w(v_{0},v_{1})}{t_{1}-t_{0}}+\frac{w(v_{0},v_{1})}{t^{\prime}_{1}-t^{\prime}_{0}}>\frac{w(v_{0},v_{1})}{t^{\prime}_{1}-t_{0}}+\frac{w(v_{0},v_{1})}{t_{1}-t^{\prime}_{0}}. The ordering in this inequality characterizes c_{t_{0},t_{1}} as being quasi-monotone, in the terminology of [ 5 ] , see also [ 39 , Section 3.1] . It follows from [ 46 , Theorem 2.18 and Remark 2.19] that the optimal coupling \pi exists and is given by the monotone rearrangement of \mu^{0} and \sigma . That is, for a suitable function T^{\mathcal{D}}(t_{1}) , the optimal transport plan satisfies \int_{0}^{T^{\mathcal{D}}(t_{1})}\mu^{0}(dt_{0})=\int_{0}^{t_{1}}\sigma(s)\,ds . Since T^{\mathcal{D}}(t_{1})t_{1} , so that T^{\mathcal{A}}(t_{1}) is non-increasing. With the monotonicity of the push-forward maps T^{\mathcal{D}}(t_{1}) and T^{\mathcal{A}}(t_{1}) established, we now present the following uniqueness result. Theorem 1 ( Uniqueness ). Under the assumptions of Problem 1 , the minimizer is unique. Moreover, there exist functions T^{\mathcal{D}}(t_{1}) and T^{\mathcal{A}}(t_{1}) that are monotonically non-increasing such that \pi=\big(T^{\mathcal{D}},{\rm Id,T^{\mathcal{A}}}\big)_{\sharp}\sigma , where {\rm Id}(t_{1})=t_{1} is the identity map, and \sigma(t_{1})\,dt_{1} is an absolutely continuous measure on [0,t_{f}] satisfying \sigma(t_{1})\leq r . Proof. Let \pi be a minimizer as established in Proposition 1 , and define \pi_{t_{0},t_{1}}:=\int_{t_{2}}\pi , \pi_{t_{1},t_{2}}:=\int_{t_{0}}\pi , and \sigma:=\iint_{t_{0},t_{2}}\pi . Since the objective function satisfies \displaystyle\iiint_{t_{0},t_{1},t_{2}}\!\!\!\!\!\!\!\!c\,\pi=\iint_{t_{0},t_{1}}\!\!\!\!\!c_{t_{0},t_{1}}\pi_{t_{0},t_{1}}+\iint_{t_{1},t_{2}}\!\!\!\!\!\!\!c_{t_{1},t_{2}}\pi_{t_{1},t_{2}}, it follows that both \pi_{t_{0},t_{1}} and \pi_{t_{1},t_{2}} must be minimizers of their respective problems. Otherwise, there would exist alternative couplings \hat{\pi}_{t_{0},t_{1}} and \hat{\pi}_{t_{1},t_{2}} achieving strictly lower costs \displaystyle\iint_{t_{0},t_{1}}c_{t_{0},t_{1}}\hat{\pi}_{t_{0},t_{1}}<\iint_{t_{0},t_{1}}c_{t_{0},t_{1}}\pi_{t_{0},t_{1}},\ \iint_{t_{1},t_{2}}c_{t_{1},t_{2}}\hat{\pi}_{t_{1},t_{2}}<\iint_{t_{1},t_{2}}c_{t_{1},t_{2}}\pi_{t_{1},t_{2}}. Since both couplings share the same marginal on the t_{1} -axis, we have \displaystyle\int_{t_{0}}\hat{\pi}_{t_{0},t_{1}}(dt_{0},dt_{1})=\int_{t_{2}}\hat{\pi}_{t_{1},t_{2}}(dt_{1},dt_{2})=\sigma(t_{1})\,dt_{1}. By the gluing lemma [ 47 , page 11] , there exists a coupling \hat{\pi} on \mathcal{M}_{+}([0,t_{f}]^{3}) that preserves these marginals while achieving a strictly lower cost, contradicting optimality. Thus, both \pi_{t_{0},t_{1}} and \pi_{t_{1},t_{2}} must be optimal. Next, we show that the relaxed marginal \sigma is unique, which establishes the desired result via Lemma 2 . Suppose there exist two distinct minimizers, \pi^{a} and \pi^{b} . Each induces a density \sigma^{a}(t_{1}) and \sigma^{b}(t_{1}) , respectively, on the t_{1} -axis, along with corresponding transport maps (T^{\mathcal{D},a},T^{\mathcal{A},a}) and (T^{\mathcal{D},b},T^{\mathcal{A},b}) . Since both \sigma^{a}(t_{1}) and \sigma^{b}(t_{1}) satisfy the constraint \sigma(t_{1})\leq r , their convex combination \bar{\sigma}=\frac{1}{2}\sigma^{a}+\frac{1}{2}\sigma^{b} also remains feasible. Similarly, the convex combination \bar{\pi}=\frac{1}{2}\pi^{a}+\frac{1}{2}\pi^{b} defines an optimal coupling. However, the bi-marginal coupling \displaystyle\bar{\pi}_{xt}=(T^{\mathcal{D},a},{\rm Id})_{\sharp}\tfrac{1}{2}\sigma^{a}+(T^{\mathcal{D},b},{\rm Id})_{\sharp}\tfrac{1}{2}\sigma^{b} fails to be supported on the graph of a function, which implies that there exists a cheaper coupling with strictly lower cost, obtained by monotone rearrangement of \bar{\pi}_{xt} . Since \bar{\pi}_{xt} satisfies the marginal constraints, meaning T^{\mathcal{D},a}_{\sharp}\sigma^{a}+T^{\mathcal{D},b}_{\sharp}\sigma^{b}=\mu^{0} , the only way for \bar{\pi}_{xt} to be supported on the graph of a function is if T^{\mathcal{D}} is unique, i.e., T^{\mathcal{D}}=T^{\mathcal{D},a}=T^{\mathcal{D},b} . A similar argument applies to \bar{\pi}_{yt} , ensuring that T^{\mathcal{A}} is also unique. If this were not the case, a more efficient coupling could be constructed through monotone rearrangement, contradicting optimality, and thus completes our proof. ∎ 3.3 Generation to multi-node line graph We are now in a position to extend Problem 1 to a line graph with n intermediate vertices. Consider a single path \mathbf{p} defined as \mathbf{p}=\{v_{0},v_{1},\dots,v_{{\mathcal{T}}-1},v_{\mathcal{T}}\}, and adopt the convention v_{\mathcal{T}}:=v_{n+1} , the corresponding cost function is defined as \displaystyle c^{(\mathbf{p})}(t_{0},t_{1},\dots,t_{{\mathcal{T}}-1},t_{\mathcal{T}}):=\sum_{\ell=1}^{{\mathcal{T}}}\frac{w(v_{\ell-1},v_{\ell})}{t^{\ell}-t^{\ell-1}}, (9) with w(v_{\ell-1},v_{\ell}) representing the weight associated with the edge connecting v_{\ell-1} and v_{\ell} . Problem \mathbf{1}^{\prime} ( Independent DA on line graph ). Given probability distributions \mu^{0}(t_{0}) and \mu^{\mathcal{T}}(t_{\mathcal{T}}) , along with suitable flow-rate bounds r_{1},r_{2},\dots,r_{{\mathcal{T}}-1}>0 , determine a probability measure \pi(t_{0},\dots,t_{\mathcal{T}}) on \mathcal{M}_{+}\big([0,t_{f}]^{n+2}\big) that minimizes \displaystyle\int_{t_{0},t_{1},\dots,t_{{\mathcal{T}}-1},t_{\mathcal{T}}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!c^{(\mathbf{p})}(t_{0},t_{1},\dots,t_{{\mathcal{T}}-1},t_{\mathcal{T}})\,\pi(dt_{0},dt_{1},\dots,dt_{{\mathcal{T}}-1},dt_{\mathcal{T}}), (10a) subject to the departure and arrival constraint: \displaystyle\int_{t_{1},\dots,t_{{\mathcal{T}}-1},t_{\mathcal{T}}}\!\!\!\!\!\!\!\!\!\!\!\pi(dt_{0},dt_{1},\dots,dt_{{\mathcal{T}}-1},dt_{\mathcal{T}})=\mu^{0}(t_{0}), (10b) \displaystyle\int_{t_{0},t_{1},\dots,t_{{\mathcal{T}}-1}}\!\!\!\!\!\!\!\!\!\!\!\pi(dt_{0},dt_{1},\dots,dt_{{\mathcal{T}}-1},dt_{\mathcal{T}})=\mu^{\mathcal{T}}(t_{\mathcal{T}}), (10c) and the flow-rate constraint: \displaystyle\int_{t_{0},\dots,t_{\mathcal{T}}/\{t_{\ell}\}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\pi(dt_{0},dt_{1},\dots,dt_{{\mathcal{T}}-1},dt_{\mathcal{T}})\leq r_{\ell}\,dt_{\ell},\;\ell=1,\dots,{\mathcal{T}}-1. (10d) The set of admissible measures for Problem 1 ′ reads \Pi:=\big\{\pi\;\big|\;\pi\mbox{ satisfies }\eqref{eq:ind-arrival},\eqref{eq:ind-depart},\mbox{ and }\eqref{eq:ind-bound}\big\} . To establish the non-emptiness of \Pi and therefore existence of a feasible \pi\in\Pi , consider the ordered sequence of crossing distributions \sigma^{\ell}(dt) at each intermediate node v_{\ell} . These distributions must satisfy the feasibility condition in Lemma 1 . Moreover, each crossing distribution is normalized such that \int_{0}^{t_{f}}\sigma^{\ell}(dt)=1 for all \ell=1,\dots,{\mathcal{T}}-1 . To establish the uniqueness of the optimizer \pi , we first recall a multi-marginal generalization of the Monge problem (Definition 1 ) in the one-dimensional setting. Specifically, we introduce the generalized Monge condition [ 39 , Page 24] , which provides a structural criterion for the existence of an optimal transport plan in the form of a Monge map. This condition applies to the MMOT problems where the cost function c(x_{1},x_{2},\dots,x_{n}) with x_{i}\in\mathbb{R} for all i=1,2,\dots,n . Theorem 2 ( Uniqueness ). Problem 1 ′ admits unique minimizer when feasible. Proof. The uniqueness of the optimizer follows if the cost function c(t_{0},t_{1},\dots,t_{\mathcal{T}}) satisfies the generalized Monge condition in Definition 3 . For any pair i0 , determine a probability measure \pi(t_{0},t_{1},t_{2}) on \mathcal{M}_{+}([0,t_{f}]^{3}) that minimizes \displaystyle\int_{t_{0},t_{1},t_{2}}\Bigg(\frac{w(v_{0},v_{1})}{t_{1}-t_{0}}+\frac{w(v_{1},v_{2})}{t_{2}-t_{1}}\Bigg)\pi(dt_{0},dt_{1},dt_{2}) (11a) subject to the coupled DA distribution \displaystyle\int_{t_{1}}\pi(dt_{0},dt_{1},dt_{2})=\mu^{0,2}(dt_{0},dt_{2}), (11b) and flow-rate constraint \int_{t_{0},t_{\mathcal{T}}}\pi(dt_{0},dt_{1},dt_{2})\leq rdt_{1} . The generalized form of Problem 2 is illustrated in Fig. 3 . Given the joint probability measure governing departure and arrival times, the objective is to determine the optimal crossing times for all particles at each intermediate node. This formulation aligns with the framework of unequal-dimensional OT [ 10 , 11 , 12 ] , where the two-dimensional coupled DA constraint is mapped to a one-dimensional probability measure characterizing the crossing times at intermediate vertices. Figure 3: Diagram of the coupled DA constraint over a line graph with source node v_{0} and sink node v_{\mathcal{T}} , and connected through intermediate nodes v_{1},\dots,v_{{\mathcal{T}}-1} . The coupled DA \pi(\mu^{0},\mu^{\mathcal{T}}) encodes the joint probability of departure time t_{0} and arrival time t_{\mathcal{T}} . At each intermediate node v_{\ell} , the transport process is characterized by a crossing-time distribution, determining when mass moves from one node to the next. The existence of the problem thus follows directly. Theorem 3 ( Existence ). For sufficiently large flow-rate bound r , Problem 2 admits a minimizing solution \pi . Proof. The space of admissible measures \pi in Problem 2 reads \displaystyle\Pi=\Big\{ \displaystyle\pi\in\mathcal{M}_{+}\big([0,t_{f}]^{3}\big)\Big|\int_{t_{1}}\pi=\mu^{0,2}(dt_{0},dt_{2}),\ \iint_{t_{0},t_{2}}\pi:=\sigma^{1}(t_{1})\leq r,dt_{1}\Big\} is non-empty. It is compact in the weak topology as it is tight and closed for the narrow convergence. As its cost function is lower semi-continuous, we have the existence of a minimizer. ∎ 4.2 Unequal-dimensional OT for uniqueness Before further analyzing the properties of Problem 2 , we formally introduce unequal-dimensional OT, where the optimal transportation plan extends to probability measures with different dimensional supports, i.e., T:\mathbb{R}^{n}\to\mathbb{R}^{m}, with m\neq n. Previous works [ 10 , 11 , 12 ] have investigated the existence, uniqueness, and smoothness of the optimal map in this setting. To establish the uniqueness of the optimal transport map in the unequal-dimensional setting, we introduce three key concepts that characterize the structure of optimal solutions. The non-degeneracy condition ensures that the cost function is sufficiently regular to yield meaningful transport maps, preventing degenerate solutions. Definition 5 ( Non-degeneracy condition [ 12 ] ). A cost function c(x,y) satisfies the non-degeneracy condition if \text{rank}\left(D^{2}_{xy}c(x,y)\right)=\min\{m,n\} , where n and m denote the dimensions of x and y , respectively. We need conditions that characterize transport plans concentrated on deterministic mappings. Definition 6 ( Pure matching [ 10 ] ). A stable matching is said to be pure if the transport plan T is concentrated on the graph of a function T:\mathbb{R}^{n}\to\mathbb{R}^{m} . This implies that almost all agents of type x are matched exclusively with a single agent of type y=T(x) . A weaker form of the twist condition is also proposed for the unequal-dimensional case, ensuring injectivity from the higher-dimensional space to the lower one without full bijectivity. Definition 7 ( x -twist condition [ 12 ] ). The x -twist condition states that, for fixed y\in\mathbb{R}^{m} , the gradient of the cost function w.r.t. x\in\mathbb{R}^{n} ( n>m ), \nabla_{x}c(x,y) , is injective in x , i.e., y\mapsto\nabla_{x}c(x,y) is injective for fixed y . We are now in a position to establish the uniqueness of the transport plan, which maps the coupled DA constraint to a unique crossing time. Proposition 2 ( Purity and uniqueness ). If the cost function c(t_{0},t_{1},t_{2}) satisfies both the non-degeneracy and twist condition, then the minimizer of Problem 2 is unique. Moreover, there exist unique functions T such that \pi=({\rm Id},T)_{\sharp}\mu^{0,{\mathcal{T}}} , where {\rm Id}_{\sharp}\mu^{0,{\mathcal{T}}}=\mu^{0,{\mathcal{T}}} is the identity map, and T_{\sharp}\mu^{0,{\mathcal{T}}}=\sigma , with \sigma(t_{1}) an absolutely continuous measure on [0,t_{f}] with \sigma(t_{1})\leq r . Proof. We begin by verifying the non-degeneracy condition of the cost functional ( 11a ) in Problem 2 , and introduce the notation t_{da} for departure–arrival time pair t_{da}:=(t_{0},t_{2}) . The second-order mixed partial derivative matrix of the cost function is given by \displaystyle\nabla_{t_{da}t_{1}}c(t_{da},t_{1})=\begin{bmatrix}\partial^{2}c/\partial t_{0}\partial t_{1}\\[5.78172pt] \partial^{2}c/\partial t_{2}\partial t_{1}\end{bmatrix}=2\begin{bmatrix}w(v_{0},v_{1})(t_{1}-t_{0})^{-3}\\[5.78172pt] w(v_{1},v_{2})(t_{2}-t_{1})^{-3}\end{bmatrix}. Since this matrix has rank 1, the non-degeneracy condition is satisfied. Next, we establish that the x -twist condition holds. The gradient \nabla_{t_{da}}c(t_{da},t_{1}) is \displaystyle\nabla_{x}c(x,y)=\begin{bmatrix}\partial c/\partial t_{0}\\[5.78172pt] \partial c/\partial t_{2}\end{bmatrix}=\begin{bmatrix}-w(v_{0},v_{1})(t_{1}-t_{0})^{-2}\\[5.78172pt] \phantom{-}w(v_{1},v_{2})(t_{2}-t_{1})^{-2}\end{bmatrix}. For any t_{0}0 at the intermediate nodes, determine a probability measure \pi(t_{0},\dots,t_{{\mathcal{T}}-1},t_{\mathcal{T}}) on \mathcal{M}_{+}([0,t_{f}]^{n+2}) that minimizes \displaystyle\int_{t_{0},\dots,t_{n},t_{\mathcal{T}}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!c^{(\mathbf{p})}(t_{0},\dots,t_{\mathcal{T}})\,\pi(dt_{0},\dots,dt_{\mathcal{T}}), (12a) where c^{(\mathbf{p})} is the path cost ( 9 ), for t_{0}0 at every intermediate node v_{\ell} . We want to determine \pi^{({\mathbf{p}})}\in{\mathcal{M}}_{+}([0,t_{f}]^{n_{\mathbf{p}}}) for all {\mathbf{p}}\in{\mathcal{P}}({\mathcal{V}}^{-},{\mathcal{V}}^{+}) that minimizes \displaystyle\sum_{{\mathbf{p}}\in{\mathcal{P}}({\mathcal{V}}^{-},{\mathcal{V}}^{+})}\!\!\!\!\!\!\!\!\big\langle c^{({\mathbf{p}})},\pi^{({\mathbf{p}})}\big\rangle:=\!\!\!\!\!\!\!\!\sum_{{\mathbf{p}}\in{\mathcal{P}}({\mathcal{V}}^{-},{\mathcal{V}}^{+})}\int c^{({\mathbf{p}})}\,d\pi^{({\mathbf{p}})}, subject to the departure and arrival marginals \displaystyle\sum_{{\mathbf{p}}\in{\mathcal{P}}(v^{-}_{i})}P_{v^{-}_{i}}\big(\pi^{({\mathbf{p}})}\big)=\mu^{0}(t_{0},v^{-}_{i}),\quad v^{-}_{i}\in{\mathcal{V}}^{-} \displaystyle\sum_{{\mathbf{p}}\in{\mathcal{P}}(v^{+}_{j})}P_{v^{+}_{j}}\big(\pi^{({\mathbf{p}})}\big)=\mu^{\mathcal{T}}(t_{\mathcal{T}},v^{+}_{j})\quad v^{+}_{j}\in{\mathcal{V}}^{+}, and the flow rate capacity constraints \sum_{{\mathbf{p}}\in{\mathcal{P}}(v_{\ell})}P_{v_{\ell}}\big(\pi^{({\mathbf{p}})}\big)\;\leq\;r(t_{\ell},v_{\ell})\,dt_{\ell},\quad\mbox{ for }v_{\ell}\in{\mathcal{V}}, (13) where P_{v}:\mathcal{M}_{+}\big([0,t_{f}]^{n_{\mathbf{p}}}\big)\to\mathcal{M}_{+}([0,t_{f}]) denotes the projection onto the marginal associated with node v . A motivation for this formulation is that given an initial and final destination, there are typically a limited number of effective paths. However, for a single path with n nodes, the size of the corresponding transportation map \pi^{({\mathbf{p}})} grows exponentially as the number of temporal marginals at each node increases. To address this challenge, we develop methods based on multimarginal optimal transport. In Section 5.1 , we review multi-marginal entropic regularization and its Sinkhorn implementation. In Section 5.2 , we adapt this framework to a path-wise Sinkhorn algorithm tailored to DA-constrained transport on networks. 5.1 Multi-marginal Sinkhorn algorithm, recap For the MMOT problem, the discretized formulation with objective functional in ( 3 ) and admissible set ( 4 ) yields a large-scale linear program. In the multi-marginal setting, the computational cost typically grows exponentially with the number of marginals, so direct solvers quickly become impractical. The situation improves substantially when the cost has a graphical structure, for instance, when it decomposes into pairwise terms, c(x_{0},\dots,x_{\mathcal{T}})=c(x_{0},x_{1})+c(x_{1},x_{2})+\dotsb+c(x_{{\mathcal{T}}-1},x_{\mathcal{T}}). In such cases, entropic regularization combined with Sinkhorn-type scaling has become a standard tool for large-scale MMOT. Recent work shows that tensor factorization can further accelerate these methods by sharing structure across marginals and removing redundant projections within each iteration, see e.g. [ 19 , 24 , 25 ] for details and applications. By adding an entropic penalty to the original problem, the regularized version can be solved using an alternating minimization scheme [ 38 ] . The key idea of entropic regularized OT, is to introduce the entropic penalty term of \pi\in\mathbb{R}_{+}^{n_{0}\times\cdots\times n_{\mathcal{T}}} defined as \displaystyle D(\pi):=-\sum_{i_{0},\dots,i_{\mathcal{T}}}\pi_{i_{0},\dots,i_{\mathcal{T}}}\Big(\log\pi_{i_{0},\dots,i_{\mathcal{T}}}-1\Big), (14) with the convention 0\log(0)=0 . With a regularization parameter \epsilon to penalize the entropic term, the entropic regularization problem can be written as \displaystyle\pi_{\epsilon}^{\star}:=\argmin_{\pi\in\Pi(\mu^{0},\mu^{1},\dots,\mu^{\mathcal{T}})}\ \langle c,\pi\rangle-\epsilon D(\pi). (15) The unique solution \pi^{\star} of ( 15 ) converges to the optimal solution with maximal entropy within the set of all optimal solutions \pi\in\Pi , see [ 38 , Proposition 4.1] . To obtain an iterative updating scheme for finding the optimizer of \pi^{\star}_{\epsilon} , we derive the Lagrangian \displaystyle{\mathcal{L}}(\pi,\lambda^{0,\dots,{\mathcal{T}}})=\langle c,\pi\rangle-\epsilon D(\pi)+\sum_{\ell=0}^{{\mathcal{T}}}\lambda^{\ell}\left(P_{\ell}(\pi)-\mu^{\ell}\right), where, for each \ell , the marginal \mu^{\ell}\in\mathbb{R}_{+}^{n_{\ell}} and Lagrange dual variable \lambda^{\ell}\in\mathbb{R}^{n_{\ell}} for the discretized marginal constraint P_{\ell}(\pi)\in\mathbb{R}_{+}^{n_{\ell}} . Then, by taking the first-order optimality condition, we have \displaystyle\partial{\mathcal{L}}(\pi,\lambda^{0},\lambda^{1},\dots,\lambda^{\mathcal{T}})/\partial\pi=0, \displaystyle\partial{\mathcal{L}}(\pi,\lambda^{0},\lambda^{1},\dots,\lambda^{\mathcal{T}})/\partial\lambda^{\ell}=0, which gives that the optimizer \pi has a closed-form expression \pi_{i_{0},\dots,i_{\mathcal{T}}}=\exp(-c_{i_{0},\dots,i_{\mathcal{T}}}/\epsilon)\cdot\prod_{\ell=0}^{{\mathcal{T}}}\exp(-\lambda_{i_{\ell}}^{\ell}/\epsilon). By introducing the notation {\mathbf{K}}:=\exp(-c/\epsilon) and {\mathbf{u}}_{\ell}:=\exp(-\lambda_{\ell}/\epsilon) , the optimizer can be written in the more compact form 3 3 3 In the language of Schrödinger bridge problem, where only the entropic term is considered, taking the limit \epsilon\to+\infty reduces the problem to maximum likelihood estimation. In this setting, the reference measure {\mathbf{K}} acts as the prior, while the solution \pi corresponds to the posterior. \displaystyle\pi={\mathbf{K}}\odot\left({\mathbf{u}}_{0}\otimes{\mathbf{u}}_{1}\dots\otimes{\mathbf{u}}_{\mathcal{T}}\right) (16) with \odot the element-wise product and \otimes as the outer product. The dual variables \lambda_{0},\lambda_{1},\dots,\lambda_{\mathcal{T}} have to satisfy the marginal constraints, which follow after we derive the dual by substituting ( 16 ) into the Lagrangian \displaystyle\argmax_{\lambda^{0},\lambda^{1},\dots,\lambda^{\mathcal{T}}}-\epsilon{\mathbf{K}}\odot\left({\mathbf{u}}_{0}\otimes{\mathbf{u}}_{1}\dots\otimes{\mathbf{u}}_{\mathcal{T}}\right)+\sum_{i=0}^{\ell}\langle{\mathbf{u}}_{\ell},\mu^{\ell}\rangle. The updating strategy thus initializes {\mathbf{u}}_{0}={\mathbbm{1}}_{n_{0}}\in\mathbb{R}_{+}^{n_{0}} , and then for \ell=0:{\mathcal{T}} , we iteratively compute {\mathbf{u}}_{\ell}\longleftarrow\mu^{\ell}\oslash P_{\ell}(\pi) (17) until convergence, where \oslash denotes element-wise division. The above updating strategy is known as the Sinkhorn algorithm [ 14 , 38 , 43 ] , which also can be viewed as matrix scaling, by iteratively modifying {\mathbf{u}}_{0},\dots,{\mathbf{u}}_{\mathcal{T}} to satisfy the marginal constraint. In addition, for the relaxed marginal, i.e., P_{\ell}(\pi)\leq\mu^{\ell} , the updates are {\mathbf{u}}_{\ell}\longleftarrow\max\Big\{\mu^{\ell}\oslash P_{\ell}(\pi),\;\mathbf{1}\Big\}. This approach is analogous to the standard Sinkhorn method, and thus inherits a linear convergence rate [ 26 ] . 5.2 Path-wise Sinkhorn algorithm We next derive a Sinkhorn-type scaling scheme for the path-wise formulation in Problem 3 . Each admissible path {\mathbf{p}} carries its own coupling \pi^{({\mathbf{p}})} over the crossing times of the nodes it visits, while the source and sink marginals and interior-node capacities couple across paths through aggregated projections. Entropic regularization yields a multiplicative structure and simple alternating matrix rescaling, in the spirit of the multi-marginal case, with the difference that each interior node shares one multiplier wherever it appears. In practice it is often unnecessary to work with the full all-path formulation. Instead, one may restrict attention to a prescribed family of admissible paths and enlarge it only when needed, in the spirit of column generation for large-scale linear programs [ 21 , 35 ] . In network flow models with path variables, such enrichment is typically guided by a shortest-path-type pricing subproblem under dual weights [ 20 , 34 ] . For a discrete path plan \pi^{({\mathbf{p}})}\in\mathbb{R}_{+}^{n_{0}\times\cdots\times n_{n_{\mathbf{p}}}\times n_{{\mathcal{T}}}} , we consider the path-wise entropy D(\pi^{({\mathbf{p}})}) defined in ( 14 ), and add it to the cost functional in Problem 3 , yielding its entropically regularized formulation. By introducing dual variables \alpha_{v^{-}}(t_{0}) , \beta_{v^{+}}(t_{{\mathcal{T}}}) , and \gamma_{v}(t_{\ell})\geq 0 corresponding to the source node, sink node, and flow rate constraints, respectively, the Lagrangian can be written as \displaystyle\mathcal{L}(\{\pi^{({\mathbf{p}})}\}, \displaystyle\alpha,\beta,\gamma)=\sum_{{\mathbf{p}}}\Big\langle c^{({\mathbf{p}})}+\varepsilon\big(\log\pi^{({\mathbf{p}})}-1\big),\,\pi^{({\mathbf{p}})}\Big\rangle\hskip-0.4pt-\sum_{v^{-}\in{\mathcal{V}}^{-}}\Big\langle\alpha_{v^{-}},\!\!\!\!\sum_{{\mathbf{p}}\in{\mathcal{P}}(v^{-})}P_{v^{-}}\big(\pi^{({\mathbf{p}})}\big)-\mu^{0}(\cdot,v^{-})\Big\rangle \displaystyle-\sum_{v^{+}\in{\mathcal{V}}^{+}}\Big\langle\beta_{v^{+}},\!\!\!\!\sum_{{\mathbf{p}}\in{\mathcal{P}}(v^{+})}P_{v^{+}}\big(\pi^{({\mathbf{p}})}\big)-\mu^{{\mathcal{T}}}(\cdot,v^{+})\Big\rangle-\sum_{v\in{\mathcal{V}}}\Big\langle\gamma_{v},\!\!\!\!\sum_{{\mathbf{p}}\in{\mathcal{P}}(v)}P_{v}\big(\pi^{({\mathbf{p}})}\big)-r(\cdot,v)\Big\rangle, where d\mathbf{t} denotes integration over d\mathbf{t}:=(t_{0},\{t_{\ell}:\ v_{\ell}\in{\mathbf{p}}\},t_{{\mathcal{T}}}) and P_{0} , P_{{\mathcal{T}}} , P_{\ell} are the marginal operators extracting the t_{0} , t_{{\mathcal{T}}} , t_{\ell} marginals of \pi^{({\mathbf{p}})} . The First-order optimality condition of \mathcal{L} with respect to \pi^{({\mathbf{p}})} gives \displaystyle 0=c^{({\mathbf{p}})}+\varepsilon\log\pi^{({\mathbf{p}})}\!-\!\alpha_{v^{-}}(t_{0})\!-\!\!\sum_{v_{\ell}\in{\mathbf{p}}}\gamma_{\ell}(t_{\ell})\!-\!\beta_{v^{+}}(t_{{\mathcal{T}}}). Hence, the path-wise optimizer admits a closed-form solution in the form \displaystyle\pi^{({\mathbf{p}})}(t_{0},\{t_{\ell}\},t_{{\mathcal{T}}})=\exp\!\left(\frac{\alpha_{v^{-}({\mathbf{p}})}(t_{0})+\sum_{v_{\ell}\in{\mathbf{p}}}\gamma_{\ell}(t_{\ell})+\beta_{v^{+}({\mathbf{p}})}(t_{{\mathcal{T}}})-c^{({\mathbf{p}})}}{\varepsilon}\right). Next, define the Gibbs kernel and multiplicative scalings {\mathbf{K}}^{({\mathbf{p}})}(t_{0},\{t_{\ell}\},t_{{\mathcal{T}}}):=\exp\!\big(-c^{({\mathbf{p}})}(t_{0},\{t_{\ell}\},t_{{\mathcal{T}}})/\varepsilon\big) , together with \displaystyle{\mathbf{u}}_{v^{-}}\!\!:=\exp\!\big(\frac{\alpha_{v^{-}}}{\varepsilon}\big),{\mathbf{w}}_{v}:=\exp\!\big(\frac{\gamma_{v}}{\varepsilon}\big),\mbox{ and }{\mathbf{v}}_{v^{+}}:=\exp\!\big(\frac{\beta_{v^{+}}}{\varepsilon}\big). Then the path-wise plan may be factorized as (cf. [ 19 ] ) \pi^{({\mathbf{p}})}={\mathbf{K}}^{({\mathbf{p}})}\;{\mathbf{u}}_{v^{-}}(t_{0})\;\Big(\prod_{v\in{\mathbf{p}}}{\mathbf{w}}_{v}(t)\Big)\;{\mathbf{v}}_{v^{+}}(t_{{\mathcal{T}}}). (18) Fix a path {\mathbf{p}} , and define the path-wise flux profiles as partial integrals of the Gibbs kernel with all other factors, holding one variable and integrating over the rest, so that \displaystyle A^{({\mathbf{p}})}_{v^{-}}(t_{0}):=\int_{\{t_{\ell}\},t_{\mathcal{T}}}\!\!\!\!\!\!\!\!\!\!{\mathbf{K}}^{({\mathbf{p}})}\Big(\prod_{v_{\ell}\in{\mathbf{p}}}{\mathbf{w}}_{v_{\ell}}(t_{\ell})\Big){\mathbf{v}}_{v^{+}}(t_{{\mathcal{T}}}), \displaystyle A^{({\mathbf{p}})}_{v^{+}}(t_{{\mathcal{T}}}):=\int_{t_{0},\{t_{\ell}\}}\!\!\!\!\!\!\!\!\!\!{\mathbf{K}}^{({\mathbf{p}})}{\mathbf{u}}_{v^{-}}(t_{0})\Big(\prod_{v_{\ell}\in{\mathbf{p}}}{\mathbf{w}}_{v_{\ell}}(t_{\ell})\Big), (19) \displaystyle A^{({\mathbf{p}})}_{v}(t_{\ell}):=\int_{t_{0},\{t_{\ell^{\prime}\neq\ell}\},t_{{\mathcal{T}}}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\mathbf{K}}^{({\mathbf{p}})}{\mathbf{u}}_{v^{-}}(t_{0}){\mathbf{v}}_{v^{+}}(t_{{\mathcal{T}}})\!\!\!\!\prod_{v_{\ell^{\prime}}\in{\mathbf{p}},\ \ell^{\prime}\neq\ell}\!\!\!\!\!\!\!{\mathbf{w}}_{v_{\ell^{\prime}}}(t_{\ell^{\prime}}). The model marginals are obtained by summing these flux profiles over paths incident to each node and multiplying by the local scaling as \displaystyle m_{v^{-}}(t_{0}) \displaystyle:=\sum_{{\mathbf{p}}\in{\mathcal{P}}(v^{-})}{\mathbf{u}}_{v^{-}}(t_{0})\,A^{({\mathbf{p}})}_{v^{-}}(t_{0}), \displaystyle m_{v^{+}}(t_{{\mathcal{T}}}) \displaystyle:=\sum_{{\mathbf{p}}\in{\mathcal{P}}(v^{+})}{\mathbf{v}}_{v^{+}}(t_{{\mathcal{T}}})\,A^{({\mathbf{p}})}_{v^{+}}(t_{{\mathcal{T}}}), (20) \displaystyle m_{v}(t) \displaystyle:=\sum_{{\mathbf{p}}\in{\mathcal{P}}(v)}{\mathbf{w}}_{v}(t)\,A^{({\mathbf{p}})}_{v}(t),\qquad v\in{\mathcal{V}}. The corresponding path-wise Sinkhorn scheme can be summarized as in Algorithm 1 . Algorithm 1 Path-wise Sinkhorn with nodal capacities 1: Initialize {\mathbf{u}}_{v^{-}}(t_{0})\!=\!\mathbf{1} , {\mathbf{v}}_{v^{+}}(t_{\mathcal{T}})\!=\!\mathbf{1} , {\mathbf{w}}_{v}(t)\!=\!\mathbf{1} 2: while not converged do 3: Compute flux profile along each path {\mathbf{p}} as in ( 5.2 ). 4: Aggregate marginals at nodes ( 5.2 ), and compute independent DA projections {\mathbf{u}}_{v^{-}}\leftarrow\frac{\mu^{0}(\cdot,v^{-})}{m_{v^{-}}}\ \mbox{ and }\ {\mathbf{v}}_{v^{+}}\leftarrow\frac{\mu^{\mathcal{T}}(\cdot,v^{+})}{m_{v^{+}}}. 5: Compute capacity projection at node v , i.e., {\mathbf{w}}_{v}\leftarrow\min\!\Big\{r_{v}\oslash m_{v},\ \mathbf{1}\Big\}\qquad\text{for each }v\in{\mathcal{V}}. 6: end while 7: Compute plan \pi^{({\mathbf{p}})} for path {\mathbf{p}} as in ( 18 ). Theorem 5 ( Linear convergence ). Algorithm 1 converges to the unique optimal plan at a linear rate. Proof. The entropic formulation is strictly convex in \{\pi^{({\mathbf{p}})}\} , hence the optimizer is unique and strong duality holds. Each multiplicative update in Algorithm 1 enforces one set of marginals or capacity constraints in closed-form, which is the exact maximizer of the dual over that coordinate block. The algorithm is therefore exact block coordinate ascent [ 31 ] on a smooth concave function. Standard results for such schemes give monotone ascent and a global linear rate [ 31 , Theorem 2.1] . ∎ Remark 2 ( Stopping criteria on Algorithm 1 ). For the stopping condition of Algorithm 1 , we monitor marginal violations and capacity violations, i.e., E_{0}=\sum_{i}\|m^{0}_{i}-\mu^{0}(\cdot,v^{-}_{i})\|_{1} , E_{{\mathcal{T}}}=\sum_{j}\|m^{{\mathcal{T}}}_{j}-\mu^{{\mathcal{T}}}(\cdot,v^{+}_{j})\|_{1} , and V=\sum_{\ell}\|(m_{\ell}-r_{\ell})_{+}\|_{1} . Algorithm 1 terminates when E_{0},E_{{\mathcal{T}}},V\leq\tau , with \tau being the precision tolerance. Remark 3 ( Coupled DA ). For the coupled DA case, where the boundary marginal is prescribed jointly in (t_{0},t_{\mathcal{T}}) , the update in Algorithm 1 is modified as follows. Define m^{0,\mathcal{T}}(t_{0},t_{\mathcal{T}}):=\sum_{{\mathbf{p}}}\int\pi^{({\mathbf{p}})}(t_{0},\{t_{\ell}\},t_{\mathcal{T}})\,d\{t_{\ell}\}, and set the boundary ratio \Lambda(t_{0},t_{\mathcal{T}}):=\mu^{0,\mathcal{T}}(t_{0},t_{\mathcal{T}})\oslash m^{0,\mathcal{T}}(t_{0},t_{\mathcal{T}}) . The direct projection step is then applied path-wise via \pi^{({\mathbf{p}})}\;\leftarrow\;\Lambda\odot\pi^{({\mathbf{p}})} for all {\mathbf{p}} , while the interior capacity projections remain unchanged. Similar computations of projections in multimarginal problems with joint marginals constraints were also considered in [ 23 , 25 ] . 6 Numerical examples We now illustrate the two DA regimes and the path-wise formulation on simple test cases. The focus is on how schedules adapt to DA specifications and nodal capacity limits, rather than on numerical performance. Section 6.1 considers independent DA constraints on a line graph. Section 6.2 turns to coupled DA constraints on the same geometry. Section 6.3 then studies transport on a small path-specified network, while Section 6.4 reports the convergence of the path-wise Sinkhorn solver. 6.1 Independent DA constraints on line graph First, we consider the independent DA setting on a single path. The boundary time marginals at the source v_{0} and sink v_{\mathcal{T}} are fixed Gaussian mixtures. The crossing-time marginal at the interior node v_{1} is discretized on a uniform grid and is subject to a per-time-slice capacity. As in Fig. 4 , we use the discretization size n_{t}=100 and a capacity r=2/100 . The optimization enforces the three marginal constraints together with the capacity bound. Figure 4: Independent DA on line graph with single intermediate node. The three one-dimensional time profiles are placed on v_{0} , v_{1} , and v_{\mathcal{T}} . Blue shows the departure density at v_{0} . Green shows the crossing-time density at v_{1} . Red shows the arrival density at v_{\mathcal{T}} . The dotted line at v_{1} marks the per-time-slice capacity c=2 . Light gray guides indicate the aggregated couplings along (v_{0},v_{1}) and (v_{1},v_{\mathcal{T}}) . The plot highlights scheduling: mass is metered through v_{1} to respect capacity, and node-wise marginals satisfy conservation. The panel in Fig. 5 depicts the endpoint coupling between v_{0} and v_{\mathcal{T}} as a smooth surface over (t_{0},t_{\mathcal{T}}) . The blue and red boundary ridges reproduce the prescribed departure and arrival time marginals at v_{0} and v_{\mathcal{T}} . The green curve along the far edge encodes the crossing-time marginal at the interior node v_{1} . Dominant triplets (t_{0},t_{1},t_{\mathcal{T}}) are shown as colored markers, with color indicating the crossing time t_{1} . In one dimension with a flux limit, the separable-in-time objective satisfies a generalized Monge condition, so optimal couplings through t_{1} concentrate on the graph of a monotone map. The support therefore collapses to a single smooth strand rather than a sheet, and slices align with a function graph–consistent with monotone rearrangement and uniqueness of the optimizer. Figure 5: Endpoint coupling and triplet structure for case in Fig. 4 . The surface shows coupling over (t_{0},t_{\mathcal{T}}) with blue and red boundary ridges equal to the source and sink marginals. The green curve along the far edge plots the crossing-time marginal at v_{1} . Colored markers indicate dominant triplets (t_{0},t_{1},t_{\mathcal{T}}) (color = t_{1} ). The support collapses to a single smooth strand, in agreement with the monotone-map structure and uniqueness in one-dimensional flux-limited setting. Next, we extend the independent DA setting to a multistage path with five interior crossings. The joint coupling is supported on tuples (t_{0},t_{1},t_{2},t_{3},t_{4},t_{5},t_{6}) with t_{0}