American Institute of Mathematical Sciences

Advanced
June  2013, 8(2): 591-624. doi: 10.3934/nhm.2013.8.591

On the ramified optimal allocation problem

Qinglan Xia 1, and  Shaofeng Xu 2,

1. 

Department of Mathematics, University of California at Davis, Davis, CA 95616, United States
2. 

Department of Economics, University of California at Davis, Davis, CA 95616, United States

Received  August 2011 Revised  October 2012 Published  May 2013

This paper proposes an optimal allocation problem with ramified transport technologies in a spatial economy. Ramified transportation is used to model network-like branching structures attributed to the economies of scale in group transportation. A social planner aims at finding an optimal allocation plan and an associated optimal allocation path to minimize the overall cost of transporting commodity from factories to households. This problem differentiates itself from existing ramified transport literature in that the distribution of production among factories is not fixed but endogenously determined as observed in many allocation practices. It is shown that due to the transport economies of scale, each optimal allocation plan corresponds equivalently to an optimal assignment map from households to factories. This optimal assignment map provides a natural partition of both households and allocation paths. We develop methods of marginal transportation analysis and projectional analysis to study the properties of optimal assignment maps. These properties are then related to the search for an optimal assignment map in the context of state matrix.
Keywords: transport economies of scale, optimal transport path, branching structure, Ramified transportation, state matrix., assignment map, allocation problem.
Mathematics Subject Classification: Primary: 91B32, 58E17; Secondary: 49Q20, 90B1.
Citation: Qinglan Xia, Shaofeng Xu. On the ramified optimal allocation problem. Networks and Heterogeneous Media, 2013, 8 (2) : 591-624. doi: 10.3934/nhm.2013.8.591
References:
[1]

M. Bernot, V. Caselles and J.-M. Morel, Traffic plans, Publicacions Matematiques, 49 (2005), 417-451. doi: 10.5565/PUBLMAT_49205_09.

[2]

M. Bernot, V. Caselles and J.-M. Morel, "Optimal Transportation Networks. Models and Theory," Lecture Notes in Mathematics, Vol. 1955, Springer-Verlag, Berlin, 2009.

[3]

A. Brancolini, G. Buttazzo and F. Santambrogio, Path functions over Wasserstein spaces, Journal of the European Mathematical Society, 8 (2006), 415-434. doi: 10.4171/JEMS/61.

[4]

A. Brancolini and S. Solimini, On the Hölder regularity of the landscape function, Interfaces and Free Boundaries, 13 (2011), 191-222. doi: 10.4171/IFB/254.

[5]

G. Buttazzo and G. Carlier, Optimal spatial pricing strategies with transportation costs, in "Nonlinear Analysis and Optimization II. Optimization," Contemporary Mathematics, 514, Amer. Math. Soc., Providence, RI, (2010), 105-121. doi: 10.1090/conm/514/10102.

[6]

G. Carlier and I. Ekeland, Matching for teams, Economic Theory, 42 (2010), 397-418. doi: 10.1007/s00199-008-0415-z.

[7]

P.-A. Chiappori, R. McCann and L. Nesheim, Hedonic price equilibria, stable matching, and optimal transport: Equivalence, topology, and uniqueness, Economic Theory, 42 (2010), 317-354. doi: 10.1007/s00199-009-0455-z.

[8]

G. Devillanova and S. Solimini, On the dimension of an irrigable measure, Rend. Semin. Mat. Univ. Padova, 117 (2007), 1-49.

[9]

I. Ekeland, Existence, uniqueness and efficiency of equilibrium in hedonic markets with multidimensional types, Economic Theory, 42 (2010), 275-315. doi: 10.1007/s00199-008-0427-8.

[10]

A. Figalli, Y.-H. Kim and R. McCann, When is multidimensional screening a convex program?, Journal of Economic Theory, 146 (2011), 454-478. doi: 10.1016/j.jet.2010.11.006.

[11]

E. N. Gilbert, Minimum cost communication networks, Bell System Technical Journal, 46 (1967), 2209-2227.

[12]

L. Kantorovitch, On the translocation of masses, C. R. (Doklady) Acad. Sci. URSS (N.S.), 37 (1942), 199-201.

[13]

F. Maddalena, S. Solimini and J.-M. Morel, A variational model of irrigation patterns, Interfaces and Free Boundaries, 5 (2003), 391-415. doi: 10.4171/IFB/85.

[14]

R. McCann and M. Trokhimtchouk, Optimal partition of a large labor force into working pairs, Economic Theory, 42 (2010), 375-395. doi: 10.1007/s00199-008-0420-2.

[15]

G. Monge, Mémoire sur la théorie des déblais et de remblais, Histoire de l'Académie Royale des Sciences de Paris, avec les Mémorires de Mathématique et de Physique pour la même année, (1781), 666-704.

[16]

F. Morgan and R. Bolton, Hexagonal economic regions solve the location problem, American Mathematical Monthly, 109 (2002), 165-172. doi: 10.2307/2695328.

[17]

F. Santambrogio, Optimal channel networks, landscape function and branched transport, Interfaces and Free Boundaries, 9 (2007), 149-169. doi: 10.4171/IFB/160.

[18]

C. Villani, "Topics in Optimal Transportation," Graduate Studies in Mathematics, 58, American Mathematical Society, Providence, RI, 2003.

[19]

C. Villani, "Optimal Transport. Old and New," Grundlehren der mathematischen Wissenschaften, Vol. 338, Springer-Verlag, Berlin, 2009. doi: 10.1007/978-3-540-71050-9.

[20]

Q. Xia, Optimal paths related to transport problems, Communications in Contemporary Mathematics, 5 (2003), 251-279. doi: 10.1142/S021919970300094X.

[21]

Q. Xia, Interior regularity of optimal transport paths, Calculus of Variations and Partial Differential Equations, 20 (2004), 283-299. doi: 10.1007/s00526-003-0237-6.

[22]

Q. Xia, The formation of tree leaf, ESAIM Control, Optimisation and Calculus of Variations, 13 (2007), 359-377. doi: 10.1051/cocv:2007016.

[23]

Q. Xia, The geodesic problem in quasimetric spaces, Journal of Geometric Analysis, 19 (2009), 452-479. doi: 10.1007/s12220-008-9065-4.

[24]

Q. Xia, Boundary regularity of optimal transport paths, Advances in Calculus of Variations, 4 (2011), 153-174. doi: 10.1515/ACV.2010.024.

[25]

Q. Xia, Ramified optimal transportation in geodesic metric spaces, Advances in Calculus of Variations, 4 (2011), 277-307. doi: 10.1515/ACV.2011.002.

[26]

Q. Xia, Numerical simulation of optimal transport paths, in "The Second International Conference on Computer Modeling and Simulation," 1, IEEE, (2010), 521-525. doi: 10.1109/ICCMS.2010.30.

[27]

Q. Xia and A. Vershynina, On the transport dimension of measures, SIAM Journal on Mathematical Analysis, 41 (2010), 2407-2430. doi: 10.1137/090770205.

[28]

Q. Xia and S. Xu, The exchange value embedded in a transport system, Applied Mathematics and Optimization, 62 (2010), 229-252. doi: 10.1007/s00245-010-9102-0.

show all references

References:
[1]

M. Bernot, V. Caselles and J.-M. Morel, Traffic plans, Publicacions Matematiques, 49 (2005), 417-451. doi: 10.5565/PUBLMAT_49205_09.

[2]

M. Bernot, V. Caselles and J.-M. Morel, "Optimal Transportation Networks. Models and Theory," Lecture Notes in Mathematics, Vol. 1955, Springer-Verlag, Berlin, 2009.

[3]

A. Brancolini, G. Buttazzo and F. Santambrogio, Path functions over Wasserstein spaces, Journal of the European Mathematical Society, 8 (2006), 415-434. doi: 10.4171/JEMS/61.

[4]

A. Brancolini and S. Solimini, On the Hölder regularity of the landscape function, Interfaces and Free Boundaries, 13 (2011), 191-222. doi: 10.4171/IFB/254.

[5]

G. Buttazzo and G. Carlier, Optimal spatial pricing strategies with transportation costs, in "Nonlinear Analysis and Optimization II. Optimization," Contemporary Mathematics, 514, Amer. Math. Soc., Providence, RI, (2010), 105-121. doi: 10.1090/conm/514/10102.

[6]

G. Carlier and I. Ekeland, Matching for teams, Economic Theory, 42 (2010), 397-418. doi: 10.1007/s00199-008-0415-z.

[7]

P.-A. Chiappori, R. McCann and L. Nesheim, Hedonic price equilibria, stable matching, and optimal transport: Equivalence, topology, and uniqueness, Economic Theory, 42 (2010), 317-354. doi: 10.1007/s00199-009-0455-z.

[8]

G. Devillanova and S. Solimini, On the dimension of an irrigable measure, Rend. Semin. Mat. Univ. Padova, 117 (2007), 1-49.

[9]

I. Ekeland, Existence, uniqueness and efficiency of equilibrium in hedonic markets with multidimensional types, Economic Theory, 42 (2010), 275-315. doi: 10.1007/s00199-008-0427-8.

[10]

A. Figalli, Y.-H. Kim and R. McCann, When is multidimensional screening a convex program?, Journal of Economic Theory, 146 (2011), 454-478. doi: 10.1016/j.jet.2010.11.006.

[11]

E. N. Gilbert, Minimum cost communication networks, Bell System Technical Journal, 46 (1967), 2209-2227.

[12]

L. Kantorovitch, On the translocation of masses, C. R. (Doklady) Acad. Sci. URSS (N.S.), 37 (1942), 199-201.

[13]

F. Maddalena, S. Solimini and J.-M. Morel, A variational model of irrigation patterns, Interfaces and Free Boundaries, 5 (2003), 391-415. doi: 10.4171/IFB/85.

[14]

R. McCann and M. Trokhimtchouk, Optimal partition of a large labor force into working pairs, Economic Theory, 42 (2010), 375-395. doi: 10.1007/s00199-008-0420-2.

[15]

G. Monge, Mémoire sur la théorie des déblais et de remblais, Histoire de l'Académie Royale des Sciences de Paris, avec les Mémorires de Mathématique et de Physique pour la même année, (1781), 666-704.

[16]

F. Morgan and R. Bolton, Hexagonal economic regions solve the location problem, American Mathematical Monthly, 109 (2002), 165-172. doi: 10.2307/2695328.

[17]

F. Santambrogio, Optimal channel networks, landscape function and branched transport, Interfaces and Free Boundaries, 9 (2007), 149-169. doi: 10.4171/IFB/160.

[18]

C. Villani, "Topics in Optimal Transportation," Graduate Studies in Mathematics, 58, American Mathematical Society, Providence, RI, 2003.

[19]

C. Villani, "Optimal Transport. Old and New," Grundlehren der mathematischen Wissenschaften, Vol. 338, Springer-Verlag, Berlin, 2009. doi: 10.1007/978-3-540-71050-9.

[20]

Q. Xia, Optimal paths related to transport problems, Communications in Contemporary Mathematics, 5 (2003), 251-279. doi: 10.1142/S021919970300094X.

[21]

Q. Xia, Interior regularity of optimal transport paths, Calculus of Variations and Partial Differential Equations, 20 (2004), 283-299. doi: 10.1007/s00526-003-0237-6.

[22]

Q. Xia, The formation of tree leaf, ESAIM Control, Optimisation and Calculus of Variations, 13 (2007), 359-377. doi: 10.1051/cocv:2007016.

[23]

Q. Xia, The geodesic problem in quasimetric spaces, Journal of Geometric Analysis, 19 (2009), 452-479. doi: 10.1007/s12220-008-9065-4.

[24]

Q. Xia, Boundary regularity of optimal transport paths, Advances in Calculus of Variations, 4 (2011), 153-174. doi: 10.1515/ACV.2010.024.

[25]

Q. Xia, Ramified optimal transportation in geodesic metric spaces, Advances in Calculus of Variations, 4 (2011), 277-307. doi: 10.1515/ACV.2011.002.

[26]

Q. Xia, Numerical simulation of optimal transport paths, in "The Second International Conference on Computer Modeling and Simulation," 1, IEEE, (2010), 521-525. doi: 10.1109/ICCMS.2010.30.

[27]

Q. Xia and A. Vershynina, On the transport dimension of measures, SIAM Journal on Mathematical Analysis, 41 (2010), 2407-2430. doi: 10.1137/090770205.

[28]

Q. Xia and S. Xu, The exchange value embedded in a transport system, Applied Mathematics and Optimization, 62 (2010), 229-252. doi: 10.1007/s00245-010-9102-0.

[1]

David Kinderlehrer, Adrian Tudorascu. Transport via mass transportation. Discrete and Continuous Dynamical Systems - B, 2006, 6 (2) : 311-338. doi: 10.3934/dcdsb.2006.6.311
[2]

Klas Modin. Geometry of matrix decompositions seen through optimal transport and information geometry. Journal of Geometric Mechanics, 2017, 9 (3) : 335-390. doi: 10.3934/jgm.2017014
[3]

John C. Schotland, Vadim A. Markel. Fourier-Laplace structure of the inverse scattering problem for the radiative transport equation. Inverse Problems and Imaging, 2007, 1 (1) : 181-188. doi: 10.3934/ipi.2007.1.181
[4]

Simone Fiori. Error-based control systems on Riemannian state manifolds: Properties of the principal pushforward map associated to parallel transport. Mathematical Control and Related Fields, 2021, 11 (1) : 143-167. doi: 10.3934/mcrf.2020031
[5]

Qinglan Xia. An application of optimal transport paths to urban transport networks. Conference Publications, 2005, 2005 (Special) : 904-910. doi: 10.3934/proc.2005.2005.904
[6]

Christian Léonard. A survey of the Schrödinger problem and some of its connections with optimal transport. Discrete and Continuous Dynamical Systems, 2014, 34 (4) : 1533-1574. doi: 10.3934/dcds.2014.34.1533
[7]

Brendan Pass. Multi-marginal optimal transport and multi-agent matching problems: Uniqueness and structure of solutions. Discrete and Continuous Dynamical Systems, 2014, 34 (4) : 1623-1639. doi: 10.3934/dcds.2014.34.1623
[8]

Wilfrid Gangbo, Andrzej Świech. Optimal transport and large number of particles. Discrete and Continuous Dynamical Systems, 2014, 34 (4) : 1397-1441. doi: 10.3934/dcds.2014.34.1397
[9]

Thomas Lorenz. Partial differential inclusions of transport type with state constraints. Discrete and Continuous Dynamical Systems - B, 2019, 24 (3) : 1309-1340. doi: 10.3934/dcdsb.2019018
[10]

Ibrahima Faye, Emmanuel Frénod, Diaraf Seck. Two-Scale numerical simulation of sand transport problems. Discrete and Continuous Dynamical Systems - S, 2015, 8 (1) : 151-168. doi: 10.3934/dcdss.2015.8.151
[11]

Stefan Possanner, Claudia Negulescu. Diffusion limit of a generalized matrix Boltzmann equation for spin-polarized transport. Kinetic and Related Models, 2011, 4 (4) : 1159-1191. doi: 10.3934/krm.2011.4.1159
[12]

Robert J. McCann. A glimpse into the differential topology and geometry of optimal transport. Discrete and Continuous Dynamical Systems, 2014, 34 (4) : 1605-1621. doi: 10.3934/dcds.2014.34.1605
[13]

Paul Pegon, Filippo Santambrogio, Davide Piazzoli. Full characterization of optimal transport plans for concave costs. Discrete and Continuous Dynamical Systems, 2015, 35 (12) : 6113-6132. doi: 10.3934/dcds.2015.35.6113
[14]

Julián López-Gómez. On the structure of the permanence region for competing species models with general diffusivities and transport effects. Discrete and Continuous Dynamical Systems, 1996, 2 (4) : 525-542. doi: 10.3934/dcds.1996.2.525
[15]

Louis Caccetta, Ian Loosen, Volker Rehbock. Computational aspects of the optimal transit path problem. Journal of Industrial and Management Optimization, 2008, 4 (1) : 95-105. doi: 10.3934/jimo.2008.4.95
[16]

Youcef Mammeri, Damien Sellier. A surface model of nonlinear, non-steady-state phloem transport. Mathematical Biosciences & Engineering, 2017, 14 (4) : 1055-1069. doi: 10.3934/mbe.2017055
[17]

Xu Yang, François Golse, Zhongyi Huang, Shi Jin. Numerical study of a domain decomposition method for a two-scale linear transport equation. Networks and Heterogeneous Media, 2006, 1 (1) : 143-166. doi: 10.3934/nhm.2006.1.143
[18]

Shi Jin, Xu Yang, Guangwei Yuan. A domain decomposition method for a two-scale transport equation with energy flux conserved at the interface. Kinetic and Related Models, 2008, 1 (1) : 65-84. doi: 10.3934/krm.2008.1.65
[19]

Thomas Blanc, Mihai Bostan, Franck Boyer. Asymptotic analysis of parabolic equations with stiff transport terms by a multi-scale approach. Discrete and Continuous Dynamical Systems, 2017, 37 (9) : 4637-4676. doi: 10.3934/dcds.2017200
[20]

Lorenzo Brasco, Filippo Santambrogio. An equivalent path functional formulation of branched transportation problems. Discrete and Continuous Dynamical Systems, 2011, 29 (3) : 845-871. doi: 10.3934/dcds.2011.29.845

2020 Impact Factor: 1.213

Tools

Metrics

  • PDF downloads (49)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy