A Balanced Traffic Routing Using the Bio-inspired Traversing and Marking Metaheuristics

1.png

Figure 1. The evolution of both populations

2.png

Figure 2. The four subpopulations classes

To find a path between the source and the destination, it is required to have a meeting between an individual from the BPA subpopulation and an individual from the RPB subpopulation, as well as a meeting point of one RPA individual with another from BPB, that is a path between the destination and the source. (Table 1) summarizes all of the possible situations.

Table 1. Possible meetings between individuals from the four subpopulations

	BPA	BPB	RPA	RPB
BPA	chai_.png	chai_.png	chai_.png	dui_gou_.png
BPB	chai_.png	chai_.png	dui_gou_.png	chai_.png
RPA	chai_.png	dui_gou_.png	chai_.png	chai_.png
RPB	dui_gou_.png	chai_.png	chai_.png	chai_.png

The green sign represents "a solution is found" and the red sign represents "a meeting situation to be ignored".

Any individual from the BPA or RPB subpopulation may meet other individual from the RPB or BPA respectively, thus a source-destination route is found. To have a destination-source route, a crossroad must be found between a BPB or RPA individual and another RPA or BPB individual respectively.

The advantage of this approach is to find paths between source and destination and the opposite direction.

2.2 The algorithm

The principles that manage the evolution and control of the two populations are as follows:

2.2.1 Reproduction of the individuals

An individual must reproduce if it meets more than one unmarked adjacent street; it creates new individuals in these adjacent streets. As of the moment, when these individuals (offspring) are born, the genealogical table is updated, and the “offspring” individual inherits the population characteristics from its parent (color, destination … etc.).

However, if the individual encounters only one adjacent street, it continues its way without any reproduction.

2.2.2 The process of killing individuals

To limit massive population reproduction, any individual considered as unnecessary must be removed. This may be summarized as follows:

• After any reproduction, the “parents” must disappear;
• Another individual from the same population has already marked the adjacent street.
• Any individual in a dead end is blocked.

2.2.3 The marking

Each street in the network has two marking information, one regarding individuals that move from source to destination and the others that move in the opposite direction (Figure 3). These two marking methods act as a communication media between individuals, thus as a means of developing new solutions.

3.png

Figure 3. Marking streets scheme

The first individual marks the street, its fingerprint (individual ID) is saved in an appropriate table.

2.2.4 Competition of individuals

During exploration, individuals may encounter footprints of other individuals in the adjacent streets, this individual is considered blocked if and only if all the adjacent streets are marked; hence we come up with three possible situations:

•  If the marking belongs to this individual, then it will be automatically removed;
•  If its marking belongs to an individual of the same subpopulation, then this individual must be killed;
•  Finally, if the marking belongs to the adjacent street of an individual from another competing population, then this consists of a new solution that should be saved.

2.2.5 Composing a path

An individual’s path is a group of crossed from the starting point to the meeting point of another individual. The fusion of the two segments is the route between the source (starting point of the first individual) and the destination (starting point of the second individual).

To compose an itinerary of an individual, the algorithm uses a genealogical table (Figure 4) that groups all identifiers of the individuals created with their parents.

The search for the roots of a given individual using a recursive function from the smallest child to the largest father.

4.png

Figure 4. The search for the root in the genealogical table

The root of individual 9 is: 9 - 7 - 5 - 3 - 1

If the identifier of the child individual equals the parent’s identifier, then the search is completed and the root of that individual is then found.

An individual’s route vertices check the adjacent streets of its location, if there is a street that is already marked by that individual or its parent; that street is retained and becomes the new position; and the process continues up to the starting point.

The following organizational chart (Figure 5) explains the principle of composition of a given individual’s path based on the genealogical table and adjacent streets:

5.png

Figure 5. Organization chart of an individual’s path search

This Organization chart represents a recursive function, which makes it possible to create a path for any individual, and the fusion between the two paths of two individuals makes up the itinerary between the starting point and the ending point.

2.2.6 Enhancement of the solution

The first meetings between two concurrent subpopulations (BPA—RPB or RPB—BPA) give optimal paths in relation to the number of edges between the starting and ending point. Each route that is found is seen as the shortest path in the non-weighted graph (the point of all edges equals 1).

The exploitation of the routes of the individuals encountered (that provided the solution) reveals that there are individuals (from the same subpopulation) that are blocked and then eliminated. The paths of these individuals constitute other potential solutions (as shown in Figure 6).

The paths between the starting vertex and the meeting point from the previous figure are listed in Table 2.

The exploitation of the paths of the two individuals gave us several possible paths (some of them are rejected because they are circuits); the fusion between two paths of the two individuals we met gives us a route between the starting and the ending vertex (as shown in Table 3).

6.png

Figure 6. Itinerary “1–5–8” is the shortest path compared to the number of edges, and the paths of blocked individuals (with red heads in the figure) may lead to other feasible solutions

Table 2. List of roads found

Table 3. The fusion between the paths found constitutes several realizable routes

nan_wa_.jpg		nu_wa_.png
1	777777777777777777.png	1
2		2
3		3
4		4
5

Let:

• N: is the number of paths found by the 1st individual.
• M: is the number of paths found by 2nd individual.

The total number of routes is equal to N x M.

2.2.7 Sequential or alternating research

The method of finding solutions is very important, either in the quality of the solution or in the speed of the responses. Therefore, the algorithm proposes two techniques of search and which are:

• Sequential search: the algorithm searches first for routes between the source and destination, as it ends and the results are obtained. It searches for routes between the destination and the source. To determine the direction of the search (source—destination or destination—source), it is sufficient to create appropriate subpopulations for each direction during initialization.
• Alternate research: all subpopulations participate in this research. Individuals in two directions move alternately (one iteration for source—destination and the other for destination—source). The competition between individuals on the streets may cause saturation or blockages. This critical situation is affected by time and quality of the solutions and also the progress of the algorithm. To unblock this situation; if the algorithm which determines a subpopulation is stable (there are no new births or individuals eliminated) for a specified number of iterations, it must eliminate this subpopulation to give other individuals a chance in the opposite direction.

2.3 Pseudo code

Initialisation();

While (!all_population_is_empty OR !params.SolutionFound)

{

for(inti = 0 ; i< 5 ; i++)   {

params.Type = i;

params = Discover(&params);

  }

}

Function Discover(void *p)

{

thisGeneration = GetGeneration(params->Type);

for (inti = 0 ; i< (int) thisGeneration.size() ; i++) {

thisPeroffspring = thisGeneration[i];

    Neighbors =  GetNeighbors(thisPeroffspring->Road);

    For (int j = 0 ; j < (int) Neighbors.size() ; j++)

        {

        thisRoad = Neighbors[j];

if ((thisPeroffspring->MyDirection&& graph[thisRoad].MyMarked == -1) ||

        (!thisPeroffspring->MyDirection&& graph[thisRoad].ItsMarked == -1))

              { AddNewPeroffspring();      }

        else {

        if (graph[thisRoad].MyMarked != -1 && graph[thisRoad].ItsMarked != -1)

              {

if (Same_Population(graph[thisRoad].MyMarked,

graph[thisRoad].ItsMarked)

                    {thisPeroffspring->Kill = true;}

else {

GenereSolution() ;

                      } } } } }

The goal of this article is to optimize routes for vehicles in the urban road networks of an Algerian city. Shortest path algorithms in the literature rely on mathematical modeling such road networks which come to be a difficult task. We therefore attempted in this work to use a metaheuristic that is inspired by the behaviors of landmark animals where each animal (an individual) marks the street it traverses with its footprint, so that this individual reproduces, die and inherit from their parent in a given population from source to destination.

The meeting of two individuals from two different populations; constitutes an optimal route between the source and the destination and the exploitation of these optimal routes may lead to other possible paths.

The algorithm uses two vertices techniques:

• The sequential method: it has succeeded in finding all the solutions without any failure, but it is slow compared to the alternately method.
• The alternately method is faster, sensitive to saturation and less optimal compared to the sequential method.

This algorithm comes up with an optimal (“shortest”) route as well as some possible paths between source and destination in an oriented graph. Further work may emphasize on solving problems of “multi-objective” shortest path.