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 & 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.  doi: 10.5565/PUBLMAT_49205_09.  Google Scholar

[2]

M. Bernot, V. Caselles and J.-M. Morel, "Optimal Transportation Networks. Models and Theory,", Lecture Notes in Mathematics, (1955).   Google Scholar

[3]

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

[4]

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

[5]

G. Buttazzo and G. Carlier, Optimal spatial pricing strategies with transportation costs,, in, 514 (2010), 105.  doi: 10.1090/conm/514/10102.  Google Scholar

[6]

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

[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.  doi: 10.1007/s00199-009-0455-z.  Google Scholar

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[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, (1781), 666.   Google Scholar

[16]

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

[17]

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

[18]

C. Villani, "Topics in Optimal Transportation,", Graduate Studies in Mathematics, 58 (2003).   Google Scholar

[19]

C. Villani, "Optimal Transport. Old and New,", Grundlehren der mathematischen Wissenschaften, (2009).  doi: 10.1007/978-3-540-71050-9.  Google Scholar

[20]

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

[21]

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

[22]

Q. Xia, The formation of tree leaf,, ESAIM Control, 13 (2007), 359.  doi: 10.1051/cocv:2007016.  Google Scholar

[23]

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

[24]

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

[25]

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

[26]

Q. Xia, Numerical simulation of optimal transport paths,, in, 1 (2010), 521.  doi: 10.1109/ICCMS.2010.30.  Google Scholar

[27]

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

[28]

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

show all references

References:
[1]

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

[2]

M. Bernot, V. Caselles and J.-M. Morel, "Optimal Transportation Networks. Models and Theory,", Lecture Notes in Mathematics, (1955).   Google Scholar

[3]

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

[4]

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

[5]

G. Buttazzo and G. Carlier, Optimal spatial pricing strategies with transportation costs,, in, 514 (2010), 105.  doi: 10.1090/conm/514/10102.  Google Scholar

[6]

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

[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.  doi: 10.1007/s00199-009-0455-z.  Google Scholar

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[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, (1781), 666.   Google Scholar

[16]

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

[17]

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

[18]

C. Villani, "Topics in Optimal Transportation,", Graduate Studies in Mathematics, 58 (2003).   Google Scholar

[19]

C. Villani, "Optimal Transport. Old and New,", Grundlehren der mathematischen Wissenschaften, (2009).  doi: 10.1007/978-3-540-71050-9.  Google Scholar

[20]

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

[21]

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

[22]

Q. Xia, The formation of tree leaf,, ESAIM Control, 13 (2007), 359.  doi: 10.1051/cocv:2007016.  Google Scholar

[23]

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

[24]

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

[25]

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

[26]

Q. Xia, Numerical simulation of optimal transport paths,, in, 1 (2010), 521.  doi: 10.1109/ICCMS.2010.30.  Google Scholar

[27]

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

[28]

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

[1]

Stefan Doboszczak, Manil T. Mohan, Sivaguru S. Sritharan. Pontryagin maximum principle for the optimal control of linearized compressible navier-stokes equations with state constraints. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020110
[2]

Xiyou Cheng, Zhitao Zhang. Structure of positive solutions to a class of Schrödinger systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020461
[3]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012
[4]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012
[5]

Xin-Guang Yang, Lu Li, Xingjie Yan, Ling Ding. The structure and stability of pullback attractors for 3D Brinkman-Forchheimer equation with delay. Electronic Research Archive, 2020, 28 (4) : 1395-1418. doi: 10.3934/era.2020074
[6]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103
[7]

Guangbin CAI, Yang Zhao, Wanzhen Quan, Xiusheng Zhang. Design of LPV fault-tolerant controller for hypersonic vehicle based on state observer. Journal of Industrial & Management Optimization, 2021, 17 (1) : 447-465. doi: 10.3934/jimo.2019120
[8]

José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, 2021, 20 (1) : 369-388. doi: 10.3934/cpaa.2020271
[9]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251
[10]

Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253
[11]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018
[12]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019
[13]

Sergio Conti, Georg Dolzmann. Optimal laminates in single-slip elastoplasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 1-16. doi: 10.3934/dcdss.2020302
[14]

Haili Yuan, Yijun Hu. Optimal investment for an insurer under liquid reserves. Journal of Industrial & Management Optimization, 2021, 17 (1) : 339-355. doi: 10.3934/jimo.2019114
[15]

Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384
[16]

Kien Trung Nguyen, Vo Nguyen Minh Hieu, Van Huy Pham. Inverse group 1-median problem on trees. Journal of Industrial & Management Optimization, 2021, 17 (1) : 221-232. doi: 10.3934/jimo.2019108
[17]

S. Sadeghi, H. Jafari, S. Nemati. Solving fractional Advection-diffusion equation using Genocchi operational matrix based on Atangana-Baleanu derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020435
[18]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375
[19]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016
[20]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

2019 Impact Factor: 1.053

Tools

Metrics

  • PDF downloads (22)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences