4-17]).

2.2. Network Problems Applied to the Urban Transportation

In the models of optimal design of an urban area we considered that

·  the urban area is a well known regular compact subset of;

·  the density of residents and the density of services are two well known positives measures with equal mass.

The irrigation problem consists to find among all feasible structures (or feasible network) those that minimize the transportation cost

The particular irrigation problem of the average distance consists to find an optimal network for which the average distance for a citizen to reach the mos t nearby point of the network is minimal.

Theorem 1 For every there exists an optimal network for the Optimization problem

where is the Hausdorff measure defined on.

Notice that there are other proposition of functionals to be minimized.

For more details, we refer the interested reader to the several recent papers on the subject (see for instance [1-3, 18,19]).

Our aim is to concentrate our effort on the numerical questions to locate the optimal network in a given domain says for example a town.

3. Approximation and Numerical Simulations

3.1. First Steps for the Formulation of the Discrete Problem

In this subsection, we are going to propose a first approach of discretization. From this, we deduce a generalized formulation but not the own possible formulation.

Let

For the simulation we are going to consider:

·  and;

·  such that;

·  a sequence of points and of balls such that

, with

, and.

and let and. We build an other map switching round cyclically the images of balls. Then satisfies

where and.

Then we have, i.e.

Therefore when, we obtain

(4)

Suppose that the map and the measure are regular, the Equation (4) leads

(5)

Then

is cyclically monotonous and.

At first, in problem () the objective is to find the points which minimize

subject to

In the next section, we show that it is quite possible to give a more general approximation .

3.2. New Reformulation Using Permutations

In the literature, many formulations (see for example [1-4]) have not yet practical applications which deal with the permutation of points. In this paper we introduce a new reformulation of the problem by introducing permutations.

Let us take a permutation defined on such that, we set:

and we solve the two following problems: ()

subject to

and problem ()

subject to

with the norm and

.

This is a theoretical formulation. And our aim is to apply it to a practical urban transport network. As a first step, we decided to work on with a reasonable number of points.

For a scenario in, if we consider points: the number of programs to be solved becomes. We leave the reader to verify that for:

·  m = 3 points we solve 27 programs

·  m = 4 points we solve 256 programs

·  etc.

A scenario involving up to 18 points is used for problem (). Using this scenario with problems () and () requires to solve programs, it is the reason we consider only some of these points for permutations in () and ().

3.3. Numerical Experiments

This section shows how the three models developed in the two previous Sections 3.1 and 3.2 are applied to real data of Dakar Dem Dikk (3D). Recall that 3D (see [20], [21]) is the main public urban transportation company in Dakar. This company manages a fleet of buses with different technical characteristics. Some of the buses can operate only in certain roads in the city center and the others can access in all over the network. Buses are parked overnight at Ouakam and Thiaroye terminals (see Figure 1).

To ensure network coverage, 3D manages its services by using 17 lines, with 11 from Ouakam terminal and 6 from Thiaroye terminal. Each line ensures a certain num-

Figure 1. Urban transportation network of 3D.

ber of routes. At present, the total number of routes in the network is 289. First, the most important 18 sites of the network are identified. Thirty (30) permanent terminuses (terminals) and 810 bus stops are used (see Figure 1, where bus stops are not represented due to their size). The map in Figure 1 is obtained by using the software EMME [22]. Table 1 gives the 18 sites, their latitude and longitude.

The data are based on the scenario of 3D; and the input data needed to use the models are the:

·  total length of the network kilometers;

·  number of points (terminals and bus stops) (see Figure 1);

·  latitude and longitude of points representing the two terminals and bus stops.

The total distance covered by all the buses from terminals to starting points of routes and from end points back to their terminals represents the total length of the network; and we have L = 5902.62 kilometers (for the 18 sites).

The GPS (Global Positioning System) coordinates are calculated with Google map, and then transformed into coordinates on the plane with he formula: degree + (minute/60) + (second/3600). Table 1 gives the coordinates of all points.

The numerical experiments are executed:

·  on a computer: 2 × Intel(R) Core(TM)2 Duo CPU 2.00 GHz, 4.0 Gb of RAM, under UNIX system;

·  and by the software IPOPT (Interior Point OPTimization) 3.9 stable [23,24], running with linear solver ma27.

For the objective function, we have:

with

Finally,

Table 1. Scenario of 3D.

and is added to the value of the objective function.

Constraint gives

.

Urban transportation network of 3D Thus, , i.e.:

And gives

i.e.:

with and.

We simply formulate the problem in AMPL [25] syntax, and solve the problem through the AMPL environment; with a total number of 38 variables for problem. The solution obtained is an optimal one (for each case) wherein the priority is assigned to the minimization of the distance between and. The IPOPT found an optimal point within desired tolerances; and we obtain the following results: the total number of iterations is 16 and for the optimal network we have

. The others obtained solutions, and are given in Table 2 with the GPS coordinates. The points and are represented in the network (see Figure 2).

Permutations make the resolution more complicated but can give better results. The number of sub-problems to solve depends on the number of points in the network. Thus, we choose points in 3D’s network.

Now, let us take the permutation which is the main idea of this work. For problem, such that, we have. Therefore some constraints are similar and we have 9 subproblems to solve. An illustration:

The three unconstrained sub-problems are obtained for with, i.e. in the three permutations (1,1,1), (2,2,2) and (3,3,3).

All sub-problems constraints are reported in Table 3.

Table 2. y1 and ym for optimal network Σopt.

Figure 2. Optimal network of 3D without permutation.

Table 3. All constraints with permutations.

It is sufficient to solve and; since we have, , , , , , , , and.

We only compute the quantities, and. For all sub-problems, the objective function is the same as problem with.

with

,

and

.

Finally,

and is added to the value of the objective function.

From computational results, we have obtained the same value for all 10 sub-problems. Thus, permutations do not influence the distance constraint on the curve of. The optimal value is for all with.

For problem, we consider and the number of possible permutation is. Recall that the number of sub-problems to solve depends on the number of points in the network. Also, we choose points in 3D’s network. Thus, for the considered permutation we have obtained a total of sub-problems to solve, see Table 4.

In order not to overload explanations, we develop only the sub-problem, the rest are left to the reader as an exercise.

In, the sub-problem is obtained for

with vectors and . For the objective function, we have

Table 4. Optimal values of αi with different permutations.

with

,

and

Finally,

and is added to the value of the objective function for all sub-problems

The constraint

gives

i.e.:

For the scenario of problems and, we choose x1 = Ouakam terminal, x2 = Thiaroye terminal and x3 = Leclerc (see Table 5).

We denote by and the optimal value and the optimal solution of sub-problem , respectively.

The results show that the following six sub-problems:, , , , , give the best value . The six solutions are different, i.e.:

with only.

The curve can be described by one of the points; see Figure 3 where

.

The points which define (with coordinates are given in Table 6, with.

The solutions giving the best possible permutations (optimum) are illustrated in Table 6 and include all permutations.

According to the simulations, we determine a set of optimal policy that can describe the optimal network. Finally: after comparison of the simulated models, we can deduce that the model for problem is better. It provides the best curve describing the optimal value, obtained with the permutations introduced in the objective function.

4. Conclusions

In this paper, we describe applications of mass transportation theory and develop how to optimize the curve design of urban network problems. Using the discrete formulations, we give three nonlinear programming problems with continue variables, and have described urban transportation problem of 3D applied to these three models. The results have shown that the optimal network is obtained with permutations including.

In future works, we will study an application in and make a reformulation that solves a unique program,

Figure 3. Optimal network Σopt.

Table 5. The network Σopt with permutations.

Table 6. The optimal solutions with permutations.

5. Acknowledgements

We would like to thank all DSI’s (Division Système d’Information) members of 3D for their time and efforts for providing the data, and discussions related to the meaning of the data.

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. 75- 103.
  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. 1- 178.
  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.

Journal Menu >>