Numerical Approach of Network Problems in Optimal Mass Transportation

Affiliation(s)

Laboratory of Mathematics of Decision and Numerical Analysis (LMDAN), FASEG, University of Cheikh Anta Diop, Dakar, Senegal.

Unité Mixte Internationale, UMMISCO, Institut de Recherche pour le Développement, Bondy, France.

Laboratory of Mathematics of Decision and Numerical Analysis (LMDAN), FASEG, University of Cheikh Anta Diop, Dakar, Senegal.

Unité Mixte Internationale, UMMISCO, Institut de Recherche pour le Développement, Bondy, France.

ABSTRACT

In this paper, we focus on the theoretical and numerical aspects of network problems. For an illustration, we consider the urban traffic problems. And our effort is concentrated on the numerical questions to locate the optimal network in a given domain (for example a town). Mainly, our aim is to find the network so as the distance between the population position and the network is minimized. Another problem that we are interested is to give an numerical approach of the Monge and Kantorovitch problems. In the literature, many formulations (see for example [1-4]) have not yet practical applications which deal with the permutation of points. Let us mention interesting numerical works due to E. Oudet begun since at least in 2002. He used genetic algorithms to identify optimal network (see [5]). In this paper we introduce a new reformulation of the problem by introducing permutations . And some examples, based on realistic scenarios, are solved.

In this paper, we focus on the theoretical and numerical aspects of network problems. For an illustration, we consider the urban traffic problems. And our effort is concentrated on the numerical questions to locate the optimal network in a given domain (for example a town). Mainly, our aim is to find the network so as the distance between the population position and the network is minimized. Another problem that we are interested is to give an numerical approach of the Monge and Kantorovitch problems. In the literature, many formulations (see for example [1-4]) have not yet practical applications which deal with the permutation of points. Let us mention interesting numerical works due to E. Oudet begun since at least in 2002. He used genetic algorithms to identify optimal network (see [5]). In this paper we introduce a new reformulation of the problem by introducing permutations . And some examples, based on realistic scenarios, are solved.

KEYWORDS

Optimal Mass Transportation; Network; Urban Traffic; Monge-Kantorovich Problem; Global Optimization

Optimal Mass Transportation; Network; Urban Traffic; Monge-Kantorovich Problem; Global Optimization

Cite this paper

L. Ndiaye, B. Ndiaye, P. Mendy and D. Seck, "Numerical Approach of Network Problems in Optimal Mass Transportation,"*Applied Mathematics*, Vol. 3 No. 5, 2012, pp. 457-466. doi: 10.4236/am.2012.35069.

L. Ndiaye, B. Ndiaye, P. Mendy and D. Seck, "Numerical Approach of Network Problems in Optimal Mass Transportation,"

References

[1] A. Figalli, “Optimal Transportation and Action-Minimizing Measures,” Ph.D. Thesis, Scuola Normale Superiore, Pisa, 2007.

[2] G. Buttazzo, E. Oudet and E. Stepanov, “Optimal Transportation Problems with Free Dirichlet Regions,” Progress in Non-Linear Differential Equations, Vol. 51, 2002, pp. 41-65.

[3] G. Buttazzo, A. Pratelli, S. Solimini and E. Stepanov, “Optimal Urbain Networks via Mass Transportation,” Lecture Notes in Mathematics, Vol. 1961, 2009, pp. 75103.

[4] G. Buttazzo, “Three Optimization Problems in Mass Transportation Theory,” Nonsmooth Mechanics and Analysis, Vol. 12, 2006, pp. 13-23.

[5] E. Oudet, “Some Results in Shape Optimization and Optimization,” 2002. http://www-ljk.imag.fr/membres/Edouard.Oudet/index.php?page=cv/node2

[6] L. Ambrosio, “Mathematical Aspects of Evolving Interfaces,” Lectures Notes in Mathematics, Vol. 1812, 2003, pp. 1-52.

[7] L. Ambrosio and P. Tilli, “Select Topics on ‘Analysis on Metric Espaces’,” Appunti dei Corsi Tenuti da Docenti delle Scuola, Scuola Normale superiore, Pisa, 2000.

[8] L. Caffarelli, M. Feldman and R. J. McCann, “Constructing Optimal Maps for Monge’s Transport Problem as a Limit of Strictly Convex Costs,” Journal of the American Mathematical Society, Vol. 15, No. 1, 2002, pp. 1-26. doi:10.1090/S0894-0347-01-00376-9

[9] L. C. Evans and W. Gangbo, “Differential Equations Methods for the Monge-Kantorovich Mass Transfer Problem,” Memoirs of the American Mathematical Society, Vol. 137, No. 653, 1999, pp. 1-66.

[10] A. Pratelli, “Existence of Optimal Transport Maps and Regularity of the Transport Density in Masse Transportation Problems,” Ph.D. Thesis, Scuola Normale Superiore, Pisa, 2003. http://cvgmt.sns.it/

[11] C. Villani, “Topics in Optimal Transportation,” Graduate Studies in Mathematics, Vol. 58, 2003.

[12] C. Villani, “Optimal Transport, Old and New,” Springer, Berlin, 2008.

[13] V. N. Sudakov, “Geometric Problems in the Theory of Infinite Dimensional Distributions,” Proceedings of the Steklov Institute of Mathematics, Vol. 141, 1976, pp. 1178.

[14] Y. Brenier, “Optimal Transportation and Applications,” Extended Monge-Kantorovich Theory,” Lecture Notes in Mathematics, Vol. 1813, 2003, pp. 91-121.

[15] G. Carlier, C. Jimenez and F. Santambrogio, “Optimal Transportation with Traffic Congestion and Wardrop Equilibria,” CVGMT Prepint, 2006. http://cvgmt.sns.it

[16] G. Buttazzo, C. Jimenez and E. Oudet, “An Optimization Problem for Mass Transportation with Congested Dynamics,” SIAM Journal on Control and Optimization, Vol. 48, No. 3, 2009.

[17] F. Santambrogio, “Variational Problems in Transport Theory with Mass Concentration,” Ph.D. Thesis, Scuola Normale Superiore, 2006.

[18] A. Brancolini and G. Buttazzo, “Optimal Networks for Mass Transportation Problems,” Preprint Diparttimento di Matematica Universit di Pisa, Pisa, 2003.

[19] G. Buttazzo and E. Stepanov, “Optimal Transportation Networks as Free Dirichlet Regions for the Monge-Kantorovich Problem,” Annali della Scuola Normale Superiore di Pisa—Classe di Scienze, Vol. 2, No. 4, 2003, pp. 631-678.

[20] C. B. Djiba, “Optimal Assignment of Routes to a Terminal for an Urban Transport Network,” Master of Research Engineering Sciences, Cheikh Anta Diop University, ESP Dakar, 2008.

[21] Dakar Dem Dikk, Full Traffic 2008-2009, File InputOutput, 2008. http://www.demdikk.com

[22] INRO Consultants Inc., “EMME User’s Manual,” 2007.

[23] A. W?chter and L. T. Biegler, “Line Search Filter Methods for Nonlinear Programming: Motivation and Global Convergence,” SIAM Journal on Optimization, Vol. 16, No. 1, 2005, pp. 1-31. doi:10.1137/S1052623403426556

[24] A. W?chter and L. T. Biegler, “On the Implementation of a Primal-Dual Interior Point Filter Line Search Algorithm for Large-Scale Nonlinear Programming,” Mathematical Programming, Vol. 106, No. 1, 2006, pp. 25-57. doi:10.1007/s10107-004-0559-y

[25] R. Fourer, D. M. Gay and B. W. Kernighan, “AMPL: A Modeling Language For Mathematical Programming,” Thomson Publishing Company, Danvers, 1993.

[1] A. Figalli, “Optimal Transportation and Action-Minimizing Measures,” Ph.D. Thesis, Scuola Normale Superiore, Pisa, 2007.

[2] G. Buttazzo, E. Oudet and E. Stepanov, “Optimal Transportation Problems with Free Dirichlet Regions,” Progress in Non-Linear Differential Equations, Vol. 51, 2002, pp. 41-65.

[3] G. Buttazzo, A. Pratelli, S. Solimini and E. Stepanov, “Optimal Urbain Networks via Mass Transportation,” Lecture Notes in Mathematics, Vol. 1961, 2009, pp. 75103.

[4] G. Buttazzo, “Three Optimization Problems in Mass Transportation Theory,” Nonsmooth Mechanics and Analysis, Vol. 12, 2006, pp. 13-23.

[5] E. Oudet, “Some Results in Shape Optimization and Optimization,” 2002. http://www-ljk.imag.fr/membres/Edouard.Oudet/index.php?page=cv/node2

[6] L. Ambrosio, “Mathematical Aspects of Evolving Interfaces,” Lectures Notes in Mathematics, Vol. 1812, 2003, pp. 1-52.

[7] L. Ambrosio and P. Tilli, “Select Topics on ‘Analysis on Metric Espaces’,” Appunti dei Corsi Tenuti da Docenti delle Scuola, Scuola Normale superiore, Pisa, 2000.

[8] L. Caffarelli, M. Feldman and R. J. McCann, “Constructing Optimal Maps for Monge’s Transport Problem as a Limit of Strictly Convex Costs,” Journal of the American Mathematical Society, Vol. 15, No. 1, 2002, pp. 1-26. doi:10.1090/S0894-0347-01-00376-9

[9] L. C. Evans and W. Gangbo, “Differential Equations Methods for the Monge-Kantorovich Mass Transfer Problem,” Memoirs of the American Mathematical Society, Vol. 137, No. 653, 1999, pp. 1-66.

[10] A. Pratelli, “Existence of Optimal Transport Maps and Regularity of the Transport Density in Masse Transportation Problems,” Ph.D. Thesis, Scuola Normale Superiore, Pisa, 2003. http://cvgmt.sns.it/

[11] C. Villani, “Topics in Optimal Transportation,” Graduate Studies in Mathematics, Vol. 58, 2003.

[12] C. Villani, “Optimal Transport, Old and New,” Springer, Berlin, 2008.

[13] V. N. Sudakov, “Geometric Problems in the Theory of Infinite Dimensional Distributions,” Proceedings of the Steklov Institute of Mathematics, Vol. 141, 1976, pp. 1178.

[14] Y. Brenier, “Optimal Transportation and Applications,” Extended Monge-Kantorovich Theory,” Lecture Notes in Mathematics, Vol. 1813, 2003, pp. 91-121.

[15] G. Carlier, C. Jimenez and F. Santambrogio, “Optimal Transportation with Traffic Congestion and Wardrop Equilibria,” CVGMT Prepint, 2006. http://cvgmt.sns.it

[16] G. Buttazzo, C. Jimenez and E. Oudet, “An Optimization Problem for Mass Transportation with Congested Dynamics,” SIAM Journal on Control and Optimization, Vol. 48, No. 3, 2009.

[17] F. Santambrogio, “Variational Problems in Transport Theory with Mass Concentration,” Ph.D. Thesis, Scuola Normale Superiore, 2006.

[18] A. Brancolini and G. Buttazzo, “Optimal Networks for Mass Transportation Problems,” Preprint Diparttimento di Matematica Universit di Pisa, Pisa, 2003.

[19] G. Buttazzo and E. Stepanov, “Optimal Transportation Networks as Free Dirichlet Regions for the Monge-Kantorovich Problem,” Annali della Scuola Normale Superiore di Pisa—Classe di Scienze, Vol. 2, No. 4, 2003, pp. 631-678.

[20] C. B. Djiba, “Optimal Assignment of Routes to a Terminal for an Urban Transport Network,” Master of Research Engineering Sciences, Cheikh Anta Diop University, ESP Dakar, 2008.

[21] Dakar Dem Dikk, Full Traffic 2008-2009, File InputOutput, 2008. http://www.demdikk.com

[22] INRO Consultants Inc., “EMME User’s Manual,” 2007.

[23] A. W?chter and L. T. Biegler, “Line Search Filter Methods for Nonlinear Programming: Motivation and Global Convergence,” SIAM Journal on Optimization, Vol. 16, No. 1, 2005, pp. 1-31. doi:10.1137/S1052623403426556

[24] A. W?chter and L. T. Biegler, “On the Implementation of a Primal-Dual Interior Point Filter Line Search Algorithm for Large-Scale Nonlinear Programming,” Mathematical Programming, Vol. 106, No. 1, 2006, pp. 25-57. doi:10.1007/s10107-004-0559-y

[25] R. Fourer, D. M. Gay and B. W. Kernighan, “AMPL: A Modeling Language For Mathematical Programming,” Thomson Publishing Company, Danvers, 1993.