The following references do not completely answer the idea of a metric (that satisfies the triangle inequality) as said by the OP they are still useful.
Under network flow, Emami (2018) describes several algorithms that can be used to tackle the geometric transportation problem.
- The exact geometric algorithm
The main contribution of this paper is that, when the ground distance is the $l_1$, $l_2$, or $l_\infty$ norm, the algorithm runs in $\mathcal O(n^{2.5}\log n \log N)$.
The author describes the results by Atkinson and Vaidya (1995) through the weighted Voronoi diagram (WVD). Where this fits into the question is that in such a diagram, the distance between cells can satisfy the standard Euclidean metric.
- The approximate geometric algorithm
In fact, there are two such algorithms proposed by Agarwal et al. (2017).
The first is a randomized $\epsilon$-approximation algorithm that finds the optimal
transportation in $\mathcal O(n^{1+\epsilon})$ expected time whose expected cost is $\mathcal O(\log(1/\epsilon))\mu(\tau^*)$ if the spread of $A \cup B$ is bounded by some polynomial. This algorithm uses randomly-shifted grids to recursively decompose the problem into a set of easier subproblems that are solved by Orlin’s algorithm.
The second algorithm described is a $(1 + \epsilon)$ approximation algorithm
that finds a transportation plan with cost $(1 + \epsilon)\mu(\tau^*)$ in time
$\mathcal O(n^{1.5}\epsilon^{-d}\operatorname{polylog}(U)\operatorname{polylog}(n))$. The algorithm constructs an efficient representation of the pairwise distances between the point sets, and then makes use
of Lee and Sidford’s min-cost flow algorithm on the resulting flow graph.
NB There is a post here on OR.SE that explains the difference between exact and approximate.
Finally, there is an older paper by Lim et al. (2006) that studies a transportation problem with minimum quality commitment (MQC).
The transportation problem with MQC can be classified into two classes: the metric version and the non-metric version. The metric version makes the restriction that the transportation costs satisfy the triangular inequality. In other words, in the metric version, $c_{i,j}$ depends on the distance between the location of carrier $i$ and the location of customer $j$ which forms a metric. The metric version is practical in some real applications. [...] This paper focuses on the non-metric version of the transportation problem with MQC; in terms of the computational complexities [...] The other [heuristic] is a greedy heuristic, whose solution quality depends on the scale of the minimum quantity when the transportation cost forms a distance metric.
It is also proven that the transportation problem with MQC and metric transportation costs in $\sf{NP}$-hard.
References
[1] Emami, P. (2018). Algorithms for the Geometric Transportation
Problem. Available from: https://pemami4911.github.io/cs-dojo/algorithms-geometric-transportation.pdf.
[2] Atkinson, D. S., Vaidya, P. M. (1995) Using geometry to solve the transportation problem in the plane. Algorithmica. 13(5):442–461.
[3] Agarwal, P. K., Fox, K., Panigrahi, D., Varadarajan, K. R., Xiao, A. (2017). Faster algorithms for the geometric transportation problem.
Proceedings of the 33rd International Symposium on Computational
Geometry (SoCG 2017).
[4] Lim, A., Wang, F., Xu, Z. (2006). A Transportation Problem with Minimum Quantity Commitment. Transportation Science. 40(1):117-129.
