Computing Optimal Trajectories for Optimal Transport in Nonuniform Environments

In this work, we solve a discrete optimal transport problem in a nonuniform environment. To solve the optimal transport problem, we build the cost matrix and then use classical solvers for discrete optimal transport. The challenge is to form the cost matrix, which requires finding the optimal path between two points, and for this task we formulate and solve the associated Euler-Lagrange equations. A main contribution of ours is to provide verifiable sufficient conditions of optimality of the solution of the Euler-Lagrange equation and to propose new algorithms to to check optimality a-posteriori, thus validating the (exact) computation of the cost matrix. We illustrate our results and performance of the algorithms on several numerical examples in 2 and 3 dimensions.