Decentralized multi-agent approach based on A* algorithm for on-demand transport problem

Abstract

The on-demand transport (ODT) systems have developed worldwide as they have significant social, environmental, and economic benefits. Even with those benefits, it’s still important to gain popular acceptance. The acceptance key is the reactivity of the system in providing fast and reliable solutions whilst respecting vehicles’ and clients’ constraints. This paper presents a decentralized multi-agent approach to model and solve the ODT problem in a static road network. The agents interact with each other using the A* algorithm to find an optimal solution for each transport demand. The optimal solution is expressed by the fastest trajectory taken by the cheapest vehicles. We utilize factual data from a Lebanese city to do experiments evaluating the proposed approach.

Keywords

A* algorithm on-demand transport decentralized approach multi-agent system

1. Introduction

On-demand transport (ODT) is a passenger transport service characterized by flexible routing and scheduling of vehicles operating in shared-ride mode between departure and arrival places according to passengers’ needs. ODT systems have emerged recently in numerous cities globally due to their economic, environmental, and social benefits to individuals and communities [32,34]. For instance, they propose an inexpensive solution compared to taxis since they simultaneously serve multiple transport demands by the same vehicle. That leads to reduce road congestion, road accidents, and pollution (such as greenhouse gas emissions) [5]. In addition, they can serve places not covered by classic public transport.

ODT problem is among the most fundamental and extensively studied problems [9,20]. The challenge is to find a collection of trajectories to transport a set of geographically spread clients, each during a specified window of time. The biggest difficulty of the ODT problem is to provide fast and reliable solutions that take into account the constraints of clients and vehicles.

Multi-agent systems [37] are valuable and promising in modeling and solving distributed complex systems such as ODT systems [4,7,17,33]. The computing load and the search space are distributed on several autonomous agents operating in an environment and interacting with one another. Considering a multi-agent point of view, we can imagine new measures and ways to provide solutions that are not envisaged by centralized approaches. The fundamental challenge, however, lies in developing a decentralized agent-based approach to address the ODT problem.

We present an approach based on multi-agent systems and the A* algorithm to model and solve the ODT problem in a fixed-speed road network.

A client formulates a transport demand. The transport demand contains the number of passengers, the departure and arrival places, and the time windows related to these places. The agents interact with each other based on a decentralized A* algorithm to find the optimal solution. This solution is expressed by the fastest trajectory taken by the cheapest vehicles. It respects the constraints of the client (departure time, arrival time, etc.) and the vehicles (schedule time, empty spaces, etc.) and it optimizes the total travelled time and cost.

Motivated by the advantages of decentralization, our contributions are the following: First, we present a significant extension to the agent-based coordination strategy to extend the approach proposed in [14]. The extension is based on decentralizing the coordination between agents. Second, we implement a prototype to validate the efficacy of the offered approach. We evaluate the approach by instances created from actual data for a Lebanese city. The contribution is important for two reasons: (i) the exponential complexity of the problem is reduced to be polynomial and (ii) a novel coordination strategy based on A* algorithm is introduced and can be applied to several other similar problems.

This is how the paper is organized: related works are presented in Section 2. Section 3 explains the data structure of the ODT system component. The multi-agent approach of the ODT problem is described in Section 4. The agents’ interaction strategy is presented in Section 5. Section 6 outlines the Vehicle agent’s work. In Section 7, we manifest the results of the experiments. The paper is finally concluded in Section 8, which also discusses viewpoints for future work.

2. Related work

Many methods have been used to resolve the on-demand transport problem (so called, dial-a-ride problem: DARP in the literature). The reader can refer to [9] for an up to 2007 survey of the models and algorithms developed for the DARP and to [20] for a recent one that presents the research on the problem since 2007.

As DARP is NP-hard [19], the solution power of the exact methods is limited to small-size problems [2,3,25,30]. For instance, [15] uses branch-and-price-and-cut algorithms to solve the basic DARP. Instances up to 8 vehicles and 96 requests are solved in 898.8 seconds. Furthermore, the branch-and-cut method is used to solve the realistic DARP. The algorithm was able to solve an instance composed of 22 requests in 4 hours [27].

This limitation encourages the decomposition of the problem into simpler subproblems and/or the development of heuristics [23,36].

Therefore, meta-heuristic methods are also used to provide solutions for real-world size problems. For example, in [8] the authors use the genetic algorithm to solve the problem of demand responsive transport (DRT). It is a flexible approach that dynamically treats transport demands. It seeks to optimize the quality of service by minimizing the number of deviations and travel time, and respecting the time windows of each passenger. Furthermore, evolutionary algorithms are used to solve a multiple objective dial-a-ride problem [16]. The objective is to minimize the total distance travelled by vehicles to serve all requests, the drivers’ wages difference, and the total number of empty seats. The taboo search method has also been used to solve the heterogeneous vehicle routing problem [11,24]. In [26], the authors propose a model based on the simulated annealing algorithm to solve the DARP. This model considers time window constraints and aims to minimize the cost of operation represented by the total travelled distance. It also maximizes customer satisfaction by minimizing customer waiting time and travel time on board of the vehicle. The experiments results showed that 66% of taxis and 19% of travelled distance are reduced in the proposed model compared with the classic taxi. Moreover, the ant colony algorithm solves the problem of vehicle trips with stochastic dynamic travel time [13].

All the above-cited works are traditional approaches that consider centralized dispatcher architecture. However, to reduce the complexity of the problem and distribute the computing load and the search space, the multi-agent systems have been used to resolve the on-demand transport problem.

For instance, the authors in [22] propose a distributed multi-layer planning model based on multi-agent systems to solve the demand-responsive transportation (DRT) problem. The model is centralized, but the authors use the A-globe agent as a platform to provide a distributed environment.

The authors in [6] develop a method based on vehicle negotiation for the problem of ODT. Its goal in a changing environment is to address a lack of service in some areas and an over-concentration of vehicles in others.

To model the DRT, the authors in [1] propose a multi-paradigm approach. Combinatorial auctions are used as a centralized strategy and distributed hybrid multi-layer planning as a multi-agent approach. The first conducts a global search to find the best solution, while the last addresses actual issues to improve the reliability of the system.

In [38], the authors put forward a centralized multi-agent model to resolve the problem of ODT. A Client agent, an Interface agent and a Vehicle agent interact to encounter the solution. The environment is represented in a spatio-temporal manner in order to avoid broadcasting the transport demand to each Vehicle agent.

In [21], the authors use the multi-objective simulated annealing algorithm and propose a multi-agent system for the static dial-a-ride problem. The goal is to ensure the quality of the service while reducing travel time.

In [31], the authors use the agent-based platform NetLogo to compare three types of transport systems: bus, classic taxi and shared taxi. The compared criteria are service performance, cost, carbon emissions and total distance travelled.

The authors of [14] present an agent-based approach using A* algorithm to solve the problem of on-demand transport. However, this approach has two weak points: 1) the planning algorithm is centralized and 2) its effectiveness has not been proven.

All cited works that solve the problem by an agent-based system, have a central coordinator that makes decisions and finds solutions. [10] presents an approach following fully decentralized decision-making to solve the ODT problem. Two parallel multi-agent coordination processes are provided: The first one makes a decentralized decision based on the insertion-heuristic algorithm. The second coordination improves the quality of the solution achieved by the first coordination by using combinatorial auctions. To evaluate the approach, the authors use data for taxis operating in the city of Saint-Étienne and show that it outperforms a decentralized greedy approach.

In this paper, we extend the approach proposed in [14] and decentralize the multi-agent model to solve the ODT problem.

The work on a decentralized approach is motivated by the limitations of centralized approaches. Therefore, we are using the multi-agent system to extend the approach proposed in [14] and decentralize the planning algorithm and the search space. In addition, real experiments are made to test the new approach.

3. Data structure of ODT system components

The ODT system is composed of the following essential elements: the infrastructure, the transport demand, the vehicle, and the trajectory. In the following, we present the data structure of the four elements. Then, we define the problem of ODT and its objective.

Infrastructure of the city: it defines the city’s road network and it has fixed travel speeds. It is represented by a graph $G = (P, R)$ comprised by a set of nodes $P = {p_{1}, \dots, p_{n}}$ designating the places in the city, and a set of links $R = {r_{1}, \dots, r_{n}}$ identifying the roads. Every road $r_{i} = p_{i} \overset{(t_{i}, d_{i})}{\to} p_{j}$ connects two places $p_{i}$ and $p_{j}$ . The time of crossing $r_{i}$ is represented by $t_{i}$ and the distance between $p_{i}$ and $p_{j}$ is represented by $d_{i}$ . Figure 1 represents a sample of the infrastructure.

Fig. 1.

Infrastructure example.

Transport demand: the client’s transport demand is outlined by: $\begin{array}{l} D = ((dep, t_{dep}) \overset{n_{passengers}}{\to} (arr, t_{arr}), n_{vehicles}) \end{array}$ where

$dep$ and $arr$ are the departure and the arrival places,

$t_{dep}$ is the earliest time of departure,

$t_{arr}$ is the latest time of arrival,

$n_{passengers}$ is the number of passengers to be transported,

$n_{vehicles}$ indicates the greatest vehicles’ number switching to transport passengers.

Three examples of transport demand are provided below:

$d_{1} = ((e, 8 h) \overset{2}{\to} (f, 9 h), 2)$ . In this transport demand, two passengers want to be transported from places e to f. They want to leave e at $8 h$ and must arrive at f before $9 h$ . They only want to be transported by two vehicles.

$d_{2} = ((c, 14 h) \overset{1}{\to} (f, 15 h 00), 2)$ ,

$d_{3} = ((e, 6 h) \overset{3}{\to} (c, 7 h 15), 1)$ .

Vehicle: is presented by (name, capacity, cost, garage, planning table) where:

name: represents the vehicle’s name,

capacity: represents the number of passengers’ seats,

cost: refers to the cost of using the vehicle per kilometer,

garage: is the location where the vehicle is parked each day,

planning table: represents the vehicle occupation per day. This table helps to know at every moment the vehicle’s location (it can be a road or a place) and the number of passengers on board. A line in the table is described by $(t, place, | passengers |)}$ where:

t represents the time,

$place$ indicates the location of the vehicle at moment t,

$| passengers |$ refers to the number of passengers on board at time t.

Table 1

Vehicle $v_{1}$ planning table

t	place	\|passengers\|
$0 h$	a	0
$8 h$	a	2
$8 h 30$	b	3
$8 h 45$	f	0
$9 h$	b	0
$9 h 30$	a	0

( $v_{1}$ , 4, 0.5 €, a, Table 1 ) is an example of a vehicle. The vehicle $v_{1}$ has four seats. It costs 0.5 € per kilometer and it is parked every day at $(a)$ .

From the planning Table 1, we can deduce that $v_{1}$ is in the garage a at time $0 h$ . There are 2 passengers on board at $8 h$ . At $8 h 20$ , $v_{1}$ is on the road $a \to b$ and it has 2 passengers. At $8 h 45$ , the vehicle drops off the passenger on f and follows the path $f \to b \to a$ back to the garage.

Trajectory: a trajectory is defined by: $\begin{array}{l} ((dep, t_{dep}) \overset{v_{1}}{\to} \dots (x_{i}, t_{x_{i}}) \overset{v_{i}}{\to} \dots (arr, t_{arr}))) \end{array}$ where:

$(path = dep \to \dots x_{i} \dots \to arr)$ is the places and roads crossed to get from the departure place $dep$ to the arrival place $arr$ ,

$t_{dep}$ represents the time of departing from $dep$ ,

$t_{x_{i}}$ represents the time to start traversing the road $x_{i} \overset{(t_{i}, d_{i})}{\to} x_{i + 1}$ ,

$t_{arr}$ represents the time of arrival to $arr$ ,

$v_{i}$ symbolizes a vehicle that transports passengers on the road $x_{i} \overset{(t_{i}, d_{i})}{\to} x_{i + 1}$ .

Suppose $time (traj) = \sum_{i = 1}^{n - 1} time (x_{i} \to x_{i + 1}) = \sum_{i = 1}^{n - 1} t_{i}$ , the time needed to cross the trajectory roads and $cost (traj) = \sum_{i = 1}^{n - 1} cost (v_{i}) * distance (x_{i} \to x_{i + 1}) = \sum_{i = 1}^{n - 1} cost (v_{i}) * d_{i}$ , the cost to cross the trajectory roads, where $x_{1} = dep$ and $x_{n} = arr$ .

On-demand transport problem: let $G = (P, R)$ be an infrastructure and $V = {v_{1}, \dots, v_{n}}$ a collection of vehicles. ODT problem is represented by a client’s transport demand $D = ((dep, t_{dep}) \overset{n_{passengers}}{\to} (arr, t_{arr}), n_{vehicles})$ .

A trajectory $traj$ defined by $\begin{matrix} traj = ((dep, t_{dep}^{'}) \overset{v_{1}}{\to} \dots (x_{i}, t_{i}) \overset{v_{i}}{\to} \dots (arr, t_{arr}^{'}))) \end{matrix}$ is a valid solution of D iff:

$t_{dep}^{'} ⩾ t_{dep}$ and $t_{arr}^{'} ⩽ t_{arr}$ ,

$t_{i + 1} > t_{i}$ where $i \in [1 \dots n - 1]$ ,

$\forall v_{i} \in traj$ , $freeP {(v_{i})}_{[t_{i}, t_{i + 1}]} ⩾ n_{passengers}$ where $freeP {(v_{i})}_{[t_{i}, t_{i} + 1]}$ represents the number of available places of vehicle $v_{i}$ during $[t_{i}, t_{i + 1}]$ ,

$n_{vehChanging} ⩽ n_{vehicles}$ where $n_{vehChanging}$ is the number of vehicles changing.

The example of ODT system is described by the infrastructure defined in Fig. 1 and three vehicles ${v_{1}, v_{2}, v_{3}}$ . Table 2 illustrates the trajectories ${traj}_{1}$ , ${traj}_{2}$ , and ${traj}_{3}$ to respond successively to demands $d_{1}$ , $d_{2}$ , and $d_{3}$ .

Table 2

Trajectories

Demand	Trajectory
$d_{1}$	$(e, 8 h) \overset{v_{2}}{\to} (f, 8 h 20)$
$d_{2}$	$(c, 14 h 05) \overset{v_{2}}{\to} (b, 14 h 35) \overset{v_{1}}{\to} (f, 14 h 50)$
$d_{3}$	$(e, 6 h) \overset{v_{3}}{\to} (f, 6 h 20) \overset{v_{3}}{\to} (b, 6 h 35) \overset{v_{3}}{\to} (c, 7 h 05)$

3.1. Objective of the ODT system

The objective of the ODT system is to find the optimal trajectory satisfying the client’s demand. The optimal trajectory is the fastest trajectory taken by the cheapest vehicles. To this end, we study two optimization criteria: time and cost. Let $Traj = {{traj}_{1}, \dots, {traj}_{n}}$ be the set of trajectories satisfying a demand D.

${traj}_{i} \in Traj$ is timely optimal iff: $\forall {traj}_{j} \in Traj ∖ {traj}_{i}$ , $time ({traj}_{i}) ⩽ time ({traj}_{j})$ . So, ${traj}_{i}$ is the fastest trajectory.

${traj}_{i} \in Traj$ is costly optimal iff: $\forall {traj}_{j} \in Traj ∖ {traj}_{i}$ , $cost ({traj}_{i}) ⩽ cost ({traj}_{j})$ . So, ${traj}_{i}$ is the cheapest trajectory.

Thus, a trajectory is a solution for a demand D, if it satisfies D and if it is optimal.

4. Multi-agent modeling of the ODT problem

The multi-agent systems distribute processing, calculation, and decision-making across numerous agents, with consideration of the distributed nature of the problem. This helps to solve the complexity of transport problems caused by the exponential growth of the search area because of the huge number of vehicles, demands, etc. This also leads to providing a satisfactory solution at an acceptable time for clients’ demands. In the following, we present the ODT problem as a decentralized multi-agent problem.

4.1. General architecture

The architecture of the decentralized multi-agent system is depicted in Fig. 2. The dialogue space is shown in the center of the figure. The agents’ interactions take place on their own information (i.e. the planning tables of the vehicles), the system’s infrastructure, the vehicles and the trajectories to be adopted in order to serve the transport demands.

Fig. 2.

Multi-agent architecture for on-demand transport problem.

4.2. Type of agents

The multi-agent architecture distinguishes between four agents:

Client agent: is an interface between the ODT system and the clients. He transmits the transport demand to the system, and receives-if it exists- the optimal trajectory.

Pathfinder agent: is in charge of determining the quickest path between the demand’s departing and arriving places.

Road agent: a Road agent $A r_{i}$ is associated to every road $r_{i} = x_{i} \overset{(t_{i}, d_{i})}{\to} x_{i + 1}$ of a trajectory. It asks each Vehicle agent the cost of crossing its road. The Road agents collaborate to determine the optimal trajectory.

Vehicle agent: a Vehicle agent $A v_{j}$ is associated with every vehicle of the system. It responds to a Road agent if it is possible to transport passengers along the road.

The following sections explain how agents collaborate and work together to solve the ODT problem.

4.3. Interaction between agents to treat a transport demand

This section provides the main idea of the interaction. The different agents interact with each other referring to a decentralized A* algorithm to find the optimal trajectory for a transport demand.

Let $D = ((dep, t_{dep}) \overset{n_{passengers}}{\to} (arr, t_{arr}), n_{vehicles})$ be a transport demand. The Fig. 3 illustrates the life cycle of D from its debut as a demand until the optimal trajectory is discovered. Additionally, how each sort of agent affects the state of the life cycle. According to Fig. 3, the life cycle starts with a demand issued by a client. The Pathfinder agent receives the demand from the Client agent. The Pathfinder agent is looking for the fastest path1

¹
Finding the fastest path on a weighted graph is solved by a number of classical graph search algorithms. This paper does not cover the study of these algorithms. Readers who are interested can refer to well-known examples: Dijkstra’s algorithm [12] and A* [18].

in the infrastructure connecting the departure place

dep

with the arrival place

arr

. Then it sends this path to the Road agents associated with the path roads. These Road agents coordinate with the Vehicle agents of the ODT system to find the optimal trajectory for D. This coordination is based on the decentralized A* algorithm. Each Road agent

A r_{i}

asks the Vehicle agents about the cost to traverse its road

r_{i} = x_{i} \to x_{i + 1}

. This action presents a portion of the graph shown in Fig. 4.

A r_{i}

asseses the reached nodes

x_{i + 1}

. Then, using a heuristic, it allocates the role to another Road agent. This operation is repeated either until the objective node

arr

is reached and the optimal trajectory is found, or until the operation fails.

Fig. 3.

Demand life cycle.

Fig. 4.

Decentralized A*.

The details of how the Road and the Vehicle agents coordinate to find the optimal trajectory for a transport demand are explained below.

5. Agents’ coordination strategy by adapting A*

The fastest path found by the Pathfinder agent is composed of a set of roads to cross. These roads are associated with Road agents that coordinate with the Vehicle agents to find the optimal trajectory. In other words, they coordinate to find vehicles with minimum cost that can transport passengers on the roads of the fastest path. In [14], the coordination process is based on the classic A* algorithm, where there is a central agent that controls the coordination process between the Vehicle agents. In our approach, the coordination process is based on a decentralized A* algorithm, and it comprises two stages: the initialization and the planning stage. The initialization stage aims to compute an admissible heuristic for the planning stage (i.e., a decentralized A* heuristic). The planning stage seeks to find the optimal trajectory. These two stages are explained in the next two subsections.

5.1. Initialization stage

The purpose of the initialization stage is to calculate an admissible heuristic for the decentralized A* algorithm. To be admissible, the heuristic must represent the lowest cost of achieving the objective from any node on the graph.2

²
Note that the minimum number of vehicle changing required by the client is not considered in the heuristic calculation.

For such purpose, each Road agent

A r_{i}

inquires from every Vehicle agent

A v_{j}

the cost to execute the road

r_{i} = (x_{i} \to x_{i + 1})

from a time

t_{x_{i}}

A r_{i}

stores the execution cost of every

A v_{j}

in a vector

C_{i} = [c_{i}^{1}, \dots, c_{i}^{m}]

. The character “-” means that a Vehicle agent cannot execute

r_{i}

. Every Road agent calculates min

C_{i} = c_{i}^{j}

that represents the minimum cost to traverse the road.

Afterward, $A r_{n}$ associated with the road $r_{n} = (x_{n} \to x_{arr})$ , initializes the heuristic $h_{n} = min (C_{n})$ . Then, It sends this value to $A r_{n - 1}$ that assigns to $h_{n - 1}$ the value $min (C_{n - 1}) + h_{n}$ and so forth till the value $h_{2}$ is calculated.

Let $H = {h_{2}, \dots, h_{n}}$ be the heuristic of the decentralized A* algorithm.

5.2. Planning stage

In the planning stage, Road agents coordinate with the Vehicle agents to determine the optimal trajectory. The coordination strategy is based on the decentralized A* algorithm. This algorithm is modeled by a tree distributed across the Road agents. Every Road agent is in charge of developing one level of the tree. For the algorithm’s correct functionality, a token shared between Road agents exists. The role of the token is to define the next Road agent who will explore the distributed tree. In other words, the token is used to define the Road agent $A r_{i}$ that has the unexplored node having the minimum value of a function f applied to the nodes $x_{i + 1}$ . The token is represented by a vector $F = {f_{1}, \dots, f_{n}}$ having as a dimension the number of roads in the path. Every entry $f_{i}$ in the vector is associated with a Road agent $A r_{i}$ . $f_{i}$ has the lowest value of the function f applied to unexplored nodes $x_{i + 1}$ ( $f_{i} = min f (x_{i + 1})$ ).

The Road agents update the token in the manner described below.

After defining the vector F representing the token, $A r_{1}$ asks every Vehicle agent $A v_{j}$ the execution cost of $r_{1}$ at time $t_{dep}$ . Then, $A r_{1}$ develops $x_{1}$ and computes the value of f applied to each reached node $x_{2}$ (values $f (x_{2})$ ). Afterward, it assigns the value $f_{1}$ to its place in the token vector F. The first stage of the graph illustrated in Fig. 4 is completed. The node $x_{2}$ that minimizes f is chosen to be developed.

Later, $A r_{1}$ transmits the token to $A r_{2}$ and notifies it with the node $x_{2}$ to explore. $A r_{1}$ has thus completed the first planning stage.

Suppose an agent $A r_{i}$ is informed to develop a node $x_{i}$ at the l-th planning stage. $A r_{i}$ contacts the Vehicle agents asking for the cost to traverse the road from the arrival instant at $x_{i}$ . In parallel, $A r_{i}$ contacts the Vehicle agents that will transport the passengers to $x_{i}$ to inform them of their responsibilities. With this information, the Vehicle agents are aware of the necessary engagements to possess a valid path. In Fig. 4, during the exploration of $x_{3}$ (circled), $A r_{3}$ contacts $A v_{j}$ and $A v_{1}$ and informs them that they are reserved to execute $r_{1}$ and $r_{2}$ respectively during specific time intervals.

After receiving the road’s execution cost, $A r_{i}$ explores $x_{i}$ and calculates the associated values $f (x_{i + 1}$ ). Then, it assigns the value $f_{i}$ within the token in the appropriate place.

$A r i$ contacts the Road agent $A r k$ which will seize the A* tree and analyse the unexplored node reducing f. $A r k$ relates to the lowest value $f_{k}$ of the vector F. $A r i$ notifies $A r k$ that it is its role to explore the node minimizing f and sends for it the token vector F. This stage of planning is repeated till the goal is attained or failure occurs. The last change to A* algorithm is the addition of a trimming factor depending on the number of vehicles $n_{vehicles}$ . Trimming occurs when a node $x_{i}$ is reached with more Vehicle agents than $n_{vehicles}$ . For example, let $n_{vehicles} = 2$ . Two nodes $x 4$ are trimmed due to the fact that they are attained via 3 Vehicle agents, as shown in Fig. 4.3

³
Note that exiting a car $v_{1}$ to take a car $v_{2}$ and then retaking $v_{1}$ is considered three vehicles changes.

Now, we define the distance-plus-cost heuristic function (

f (x_{i})

). This function determines the order in which the decentralized A* algorithm explores the tree’s nodes.

f (x_{i}) = g (x_{i}) + h (x_{i})

$g (x_{i})$ is the cost calculated using A* tree to cross from $dep$ to $x_{i}$ . The cost $c_{i}^{j}$ of executing a road is placed in the middle as shown in the Fig. 4.

$h (x_{i})$ is the heuristic evaluation of the goal’s distance. It is represented as the lowest cost of reaching the $goal$ from $x i$ when the number of vehicles used to transport passengers is set to ∞.

$h (x_{i}) = h_{i}$ where $(h_{i})$ value is derived from the vector H mentioned earlier.

$f (x_{i})$ is placed next $x_{i}$ as showed in Fig. 4.

Note that the decentralized A* tree is distributed among agents. Each of them calculates and memorizes one level of the tree, reducing calculation time.

6. Vehicle agent work

The Vehicle agent is requested by the Road agent to verify its availability to transport passengers during the initialization and planning stages. In the following, we detail the role of the Vehicle agent during the two stages.

6.1. Initialisation stage

During the initialization stage, the Vehicle agent tests if it has free spaces to transport the passengers on a road during a time interval. In the positive case, it responds with the cost and time interval of road execution.

Consider that the Vehicle agent receives the road $x_{i} \overset{t_{i}, d_{i}}{\to} x_{i + 1}$ with $t_{x_{i}}$ the execution starting time and $t_{x_{i + 1}}$ the execution ending time of the road. From its planning table, the Vehicle agent computes the time slot $T s = {t s_{1}, \dots, t s_{m}}$ between $t_{x_{i}}$ and $t_{x_{i + 1}}$ . Let $t s_{i} = [t_{a_{i}}, t_{b_{i}}]$ where $a_{i}$ is the vehicle’s place at time ( $t_{a_{i}}$ ) and $b_{i}$ is its place at time ( $t_{b_{i}}$ ). The Vehicle agent checks for each interval $t s_{i}$ , if the number of free seats is greater than or equal to the number of passengers. If positive, the Vehicle agent calculates the cost of road execution by multiplying the road distance $d_{i}$ by the vehicle cost per Km. Otherwise, it returns with “-”. Thus, the execution of the road by this vehicle is not possible. The computation of a road execution cost during the initialization stage is illustrated in Algorithm 1. The latter is inspired by the algorithm given in [14] that computes the cost of the path roads.

Algorithm 1

Calculating road execution cost during initialisation stage

6.2. Planning stage

During the planning stage, the Vehicle agent tests whether it can arrive at the starting point of the road before the start time and whether it can arrive at its end point before the end time without disturbing the commitments with others Road agents. Consider that a Vehicle agent gets a road $x_{i} \overset{t_{i}, d_{i}}{\to} x_{i + 1}$ with $t_{x_{i}}$ the execution starting time and $t_{x_{i + 1}}$ the execution ending time, and a set of roads R which it is engaged to execute. The Vehicle agent tests the four following conditions:

$t_{a_{1}} + t_{{path}_{(a_{1} \to x_{i})}} ⩾ t_{x_{i}}$

$t_{x_{i}} + t_{{path}_{(x_{i} \to b_{1})}} ⩽ t_{b_{1}}$

$t_{a_{n}} + t_{{path}_{(a_{n} \to x_{i + 1})}} ⩽ t_{x_{i + 1}}$

$t_{x_{i + 1}} + t_{{path}_{(x_{i + 1} \to b_{n})}} ⩽ t_{b_{n}}$

where

t_{s_{1}} = [t_{a_{1}}, t_{b_{1}}]

is the time slot where

t_{x_{i}}

should be inserted and

t_{s_{n}} = [t_{a_{n}}, t_{b_{n}}]

the time slot where

t_{x_{i + 1}}

should be inserted.

Condition (1) ensures that the demand initiates at or before the earliest time to quit, condition (2) affirms the execution of the demand without ignoring the time interval of the next one, condition (3) assures the ending at or before the latest time to arrive to the goal, and condition (4) guarantees the providing of the service by considering the interval of time of the next demand.

7. Experiments

The current section presents experiments that prove the effectiveness of our approach. The following subsections are composed of the experiments platform, experiments settings, and experiments results.

7.1. Experiments platform

Multi-agent simulation toolkit MASON (Multi-Agent Simulation Of Networks) [28] and Monte Carlo method [35] are utilized to build a testing platform and prove the validity of the approach.

Mason can support many agents and has several advanced features such as fast, easily extendable, portable, highly modular, flexible, written in Java, etc. Further features are presented in [29].

Four types of agents are generated to be associated with the clients, roads, vehicles and pathfinders. Each agent is defined in MASON as a class that inherits sim.engine.SimState. The time is shown by a schedule: an instance of the class sim.engine.Schedule. Mason schedules each agent to be stepped on at various time in the future and to perform some actions. The four agents have two principal methods (send and receive) to send and receive messages during the coordination strategy.

The monte Carlo method [35], invented in 1947 by Nicholas Metropolis, is a numerical method that generates a random number value using probabilistic techniques. It is used to generate the departing and arriving places of the demand as well as their departing and arriving times.

7.2. Experiments settings

Tripoli is a Lebanese city. It is located in the north. Its area is 2.0248 km2. It has 20.7% of the population of Lebanon which is close to 850,000 people. Tripoli has a municipality, a port, 144 schools, 10 higher education institutions, 11 hospitals, etc. The road network of Tripoli is used as infrastructure in the experiments. 315 roads and 117 locations are utilized. Every road is connected to a road Agent. It has two variables: a distance and a speed limit ranging from 40 to 100 km/h. These parameters come from the municipality of Tripoli. In addition, we choose a famous transport company in Tripoli called Connexion. It has 45 drivers and 30 vehicles dedicated to transport clients to Tripoli’s neighborhoods. The meeting with the general manager provides information on the Tripolitan population such as the number of demands per day, departing and arriving places, and the most popular departure times.

We describe how the transport demands of the passengers are created in the following paragraphs.

First of all, the departure and arrival places are created by applying the Monte Carlo technique to Tripoli places. The regularly demanded places (according to the data that the general Manager presented), have a higher chance (75%) of being selected.

Passengers’ number is randomly selected using the uniform distribution on a set composed of four integers ranging from 1 and 4.

Based on the general manager’s information, the departure time for most demands varies between the following intervals: [07:00, 09:00] and [14:00, 16:00]. The technique of Monte Carlo is used on a collection of hours ranging from 07:00 to 22:00 to generate the departure time of each demand. Peak hours (7:00 to 09:00 and 14:00 to 16:00) have a higher probability (75%) of being selected than other hours. As result, 500 demands are created and saved in an XML file.

Concerning vehicles, each one has a garage place where it is parked every day and a cost per kilometer. All vehicles operate all day long, thus having the same work schedule. However, drivers have different work schedules.

7.3. Experiments results

The experiments are carried out under the following conditions: an Intel core i3 processor, 6 GB of RAM, and the Windows 7 operating system. Three types of experimentation are executed. The first experiment assesses the feasibility of our approach by comparing it to another recent decentralized approach proposed in [10]. The two remaining experiments reveal that our approach results in an acceptable execution time even though the number of demands and vehicles increases.

In the first experiment, we compare our decentralized A*-based approach to a decentralized auction-based one presented in [10]. The latter is compared to a classical centralized approach using a mixed-integer linear program (MILP) solver and supplying adequate quality results. In this experiment, we measure the number of served demands by fixing the number of vehicles to 20 and varying the total number of demands between 0 and 160. Figure 5 illustrates the difference in the number of satisfied demands between the two compared approaches. Our approach provides solutions retaining values of served demands remarkably close to those of the compared approach.

Fig. 5.

Nb. of served demands by two decentralized approaches.

In the second experiment, we measure how many demands the system treats and the execution time by fixing the number of demands and varying the number of vehicles. 5 cases are differentiated: the first one contains 40 demands, the second is formed of 80 demands, including the 40 previous demands, the third is composed of 120 demands, including the 80 previous demands, the fourth involves 160 demands and the last covers 200 demands including all 160 demands. There are now 500 created demands. In each case, the demands are randomly executed seven times. Then, the system compares the achieved results to those of selective demands processing. In this processing, the system prioritizes every demand beginning with the demand that has the fewest roads (in its path), and so on.

Table 3 shows the results of processing demands. For each treatment of demands, we represent the results in three lines. The first line represents the number of vehicles. The second is the average number of served demands executed in random order and the average processing time. The third line is the number of served demands executed with priority and the processing time. For example, (33 D, 2.5 sec) signifies that 10 vehicles in a random order serve 33 of 40 demands in 2.5 seconds.

Table 3

Treatment of demands

Vehicle’s number	10	20	30
Treatment of 40 demands
average of served demands randomly	(33 D, 2.5 sec)	(40 D, 8.6 sec)	(40 D 37 sec)
∣ served demands with priority ∣	(33 D, 2.7 sec)	(40 D, 11.4 sec)	(40 D, 60 sec)
Treatment of 80 demands
average of served demands randomly	(42 D, 2.2 sec)	(70 D, 16 sec)	(80 D, 97 sec)
∣ served demands with priority ∣	(45 D, 3.25 sec)	(71 D, 16.5 sec)	(79 D, 264 sec)
Treatment of 120 demands
average of served demands randomly	(58 D, 3.7 sec)	(88 D, 21.5 sec)	(111 D, 107 sec)
∣ served demands with priority ∣	(62 D, 3.7 sec)	(92 D, 11.6 sec)	(110 D, 82.2 sec)
Treatment of 160 demands
average of served demands randomly	(65 D, 4.22 sec)	(97 D, 20.6 sec)	(128 D, 74 sec)
∣ served demands with priority ∣	(69 D, 4 sec)	(108 D, 13.5 sec)	(131 D, 38.6 sec)
Treatment of 200 demands
vehicles number	10	20	30
average of served demands randomly	(66 D, 4.5 sec)	(104 D, 18 sec)	(137 D, 70 sec)
∣ served demands with priority ∣	(70 D, 3.4 sec)	(115 D, 7.8 sec)	(146 D, 28 sec)

The graphs in Fig. 6 and Fig. 7 represent the results in Table 3. The two graphs in Fig. 6 illustrate the number of served demands according to the number of vehicles. The first denotes the randomly executed demands, and the second represents the selective execution.

The two graphs in Fig. 7 define the execution time of demands according to the number of vehicles. The first depicts the processing of demands randomly. The second shows their treatment selectively. These results reveal that increasing the vehicles’ number, boosts both the execution time and the demands that are served. Furthermore, applying an intelligent prioritization method in the treatment of demands augments the demands that are served and decreases the duration of execution and the vehicles that are used.

Fig. 6.

Number of served demands.

Fig. 7.

Demands execution time.

In the third experiment, we study the number of served demands and the processing time by fixing the vehicles’ number and varying the demands’ number. We determine four cases: the first case includes 10 vehicles, the second contains 15, the third has 20, and the fourth includes 25 vehicles. For each case, the demands are treated by priority. As mentioned before, the system prioritizes every demand beginning with the demands having the fewest roads (in its path). Figure 8 and Fig. 9 depict the result of the third experiment. Figure 8 illustrates the variation in the number of served demands, and Fig. 9 shows the variation in the processing time of given demands.

Fig. 8.

Percentage of served demands.

Fig. 9.

Processing time.

7.4. Analyses

The obtained results manifest:

one vehicle treats a transport demand in 0.9 seconds.

our decentralized approach provides remarkably close results to those obtained by another decentralized one. The quality of service symbolized by the number of demands served by our approach is adjacent to the one of the decentralized approach presented in [10].

the increasing number of demands raises the number of demands that are served as well as the processing time.

the increasing number of vehicles is accompanied by the rise in the number of served demands and the processing time.

even though the increase in the number of demands and vehicles, our decentralized algorithm still serves the demands during an acceptable execution time.

the introduction of an intelligent priority strategy in the execution of demands increases the demands served for more than 66% of cases and reduces the execution time and the number of vehicles used for more than 53% of cases.

our decentralized approach could process and give promising results in an acceptable execution time regardless of the size of the problem.

In the end, we conclude two things: 1) If the processing of demands is done with a certain priority, optimal solutions can emerge; 2) The time of execution and the number of demands that are served depend on several factors: the number of roads in the path of each demand, the order of demands processing, the start time of each demand, the number of available vehicles and the total number of demands to serve.

8. Conclusion and future work

This paper presented a multi-agent approach based on A* algorithm for on-demand transport problem on a road network characterized by time-independent travel speeds. This approach is implemented and evaluated using real-world data from a Lebanese country called Tripoli. To assess the feasibility of the proposed approach, we showed that it offered adjacent results as a decentralized auction-based approach.

Our approach assumes a fixed travel speed. This assumption shows the limitations of real-life conditions: time-dependent travel speed, unpredictable events such as accidents, festivals, etc. In real life, the travel speed is not constant. It varies and depends on the traffic situation. If the time-dependent travel speed is not considered, the time window of clients and vehicles won’t be respected, and the quality of service will decline.

This work should be expanded to solve a real ODT problem by incorporating real-time data about traffic and road network conditions. Likewise, we have to consider how the ODT system remains operational and optimal in real-time, following a change in an ODT component like accidents, work on roads, etc. The transport demand should be expanded to include more requirements such as transporting a group from one location to several locations and vice versa. For instance, transporting a family from their house to particular locations such as university, work, market, school, etc. The ODT system’s global optimality should be studied continuously. In other words, when the system receives a demand, it will answer with an optimized trajectory response and be able to update the previous trajectories and get a system-level optimization. Furthermore, the multi-agent coordination strategy must be extended to increase the simultaneous work of agents.

References

Abdulrab,

Babkin and

Satunin, A hybrid multi-layered approach to demand responsive transport systems modeling, in: 2010 5th International Conference on System of Systems Engineering, IEEE, 2010, pp. 1–6.

Baldacci,

Mingozzi and

Roberti, Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints, European Journal of Operational Research 218(1) (2012), 1–6. doi:10.1016/j.ejor.2011.07.037.

Baldacci,

Toth and

Vigo, Exact algorithms for routing problems under vehicle capacity constraints, Annals of Operations Research 175(1) (2010), 213–245. doi:10.1007/s10479-009-0650-0.

A.L.

Bazzan and

Klügl, A review on agent-based technology for traffic and transportation, The Knowledge Engineering Review 29(3) (2014), 375–403. doi:10.1017/S0269888913000118.

Benintendi,

Merino Gòmez,

De Mare,

Nesticò and

Balsamo, Energy, environment and sustainable development of the belt and road initiative: The Chinese scenario and western contributions, Sustainable Futures 2 (2020), 100009. doi:10.1016/j.sftr.2020.100009.

Bertelle,

Nabaa,

Olivier and

Tranouez, A decentralized approach for the transportation on demand problem, in: From System Complexity to Emergent Properties, Springer, Berlin, Heidelberg, 2009, pp. 281–289. doi:10.1007/978-3-642-02199-2_13.

Boella,

Elkind,

B.T.R.

Savarimuthu,

Dignum and

M.K.

Purvis (eds), PRIMA 2013: Principles and practice of multi-agent systems, in: PRIMA 2013: Principles and Practice of Multi-Agent Systems: 16th International Conference, Dunedin, New Zealand, December 1–6, 2013, Proceedings, Vol. 8291, Springer, 2013.

Carotenuto,

Paradisi and

Storchi, A flexible transport service for passengers, Transportation Research Procedia 3 (2014), 442–451. doi:10.1016/j.trpro.2014.10.025.

J.-F.

Cordeau and

Laporte, The dial-a-ride problem: Models and algorithms, Annals of operations research 153(1) (2007), 29–46. doi:10.1007/s10479-007-0170-8.

10.

Daoud,

Balbo,

Gianessi and

Picard, ORNInA: A decentralized, auction-based multi-agent coordination in ODT systems, AI Communications 34(1) (2021), 37–53. doi:10.3233/AIC-201579.

11.

Detti,

Papalini and

Zabalo, Manrique de Lara. A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare, Omega 70 (2017), 1–14. doi:10.1016/j.omega.2016.08.008.

12.

E.W.

Dijkstra, A note on two problems in connexion with graphs, Numerische mathematik 1(1) (1959), 269–271. doi:10.1007/BF01386390.

13.

Duan,

Sun,

Sun and

Li, Stochastic time-dependent vehicle routing problem: Mathematical models and ant colony algorithm, Advances in Mechanical Engineering 7(11) (2015), 168781401561863. doi:10.1177/1687814015618631.

14.

El Falou,

Itmi,

El Falou and

Cardon, On demand transport system’s approach as a multi-agent planning problem, in: 2014 International Conference on Advanced Logistics and Transport (ICALT), IEEE, 2014, pp. 53–58.

15.

Gschwind and

Irnich, Effective handling of dynamic time windows and its application to solving the dial-a-ride problem, Transportation Science 49(2) (2015), 335–354. doi:10.1287/trsc.2014.0531.

16.

P.M.

Guerreiro,

P.J.

Cardoso and

H.C.

Fernandes, A comparison of multiple objective algorithms in the context of a dial a ride problem, in: International Conference on Computational Science, Springer, Cham, 2020, pp. 382–396.

17.

Guo,

Robertson and

Y.-H.

Chen-Burger, Using multi-agent platform for pure decentralized business workflows, in: Web Intelligence and Agent Systems: An International Journal, Vol. 6, IOS Press, 2008, pp. 295–311.

18.

P.E.

Hart,

N.J.

Nilsson and

Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE transactions on Systems Science and Cybernetics 4(2) (1968), 100–107. doi:10.1109/TSSC.1968.300136.

19.

Healy and

Moll, A new extension of local search applied to the dial-a-ride problem, European Journal of Operational Research 83(1) (1995), 83–104. doi:10.1016/0377-2217(93)E0292-6.

20.

S.C.

Ho,

W.Y.

Szeto,

Y.-H.

Kuo,

J.M.

Leung,

Petering and

T.W.

Tou, A survey of dial-a-ride problems: Literature review and recent developments, Transportation Research Part B: Methodological 111 (2018), 395–421. doi:10.1016/j.trb.2018.02.001.

21.

Issam,

Kamel,

Mesghouni and

Ghedira, A multi-agent system based on the multi-objective simulated annealing algorithm for the static dial a ride problem, in: IFAC Proceedings Volumes, Vol. 44, 2011, pp. 2172–2177.

22.

Jin,

Abdulrab and

Itmi, A multi-agent based model for urban demand-responsive passenger transport services, in: In2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence), IEEE, 2008, pp. 3668–3675.

23.

A.L.

Kok,

C.M.

Meyer,

Kopfer and

J.M.J.

Schutten, A dynamic programming heuristic for the vehicle routing problem with time windows and European community social legislation, Transportation Science 44(4) (2010), 442–454. doi:10.1287/trsc.1100.0331.

24.

D.S.

Lai,

O.C.

Demirag and

J.M.

Leung, A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph, Transportation Research Part E: Logistics and Transportation Review 86 (2016), 32–52. doi:10.1016/j.tre.2015.12.001.

25.

Laporte,

Toth and

Vigo, Vehicle routing: Historical perspective and recent contributions, EURO Journal on Transportation and Logistics 2(1) (2013), 1–4. doi:10.1007/s13676-013-0020-6.

26.

Lin,

Li,

Qiu and

Xu, Research on optimization of vehicle routing problem for ride-sharing taxi, Procedia-Social and Behavioral Sciences 43 (2012), 494–502. doi:10.1016/j.sbspro.2012.04.122.

27.

Liu,

Luo and

Lim, A branch-and-cut algorithm for a realistic dial-a-ride problem, Transportation Research Part B: Methodological 81 (2015), 267–288. doi:10.1016/j.trb.2015.05.009.

28.

Luke,

Cioffi-Revilla,

Panait,

Sullivan and

Balan, Mason: A multiagent simulation environment, Simulation 81(7) (2005), 517–527. doi:10.1177/0037549705058073.

29.

Luke,

Simon,

Crooks,

Wang,

Wei,

Freelan,

Spagnuolo,

Scarano,

Cordasco and

Cioffi-Revilla, The MASON simulation toolkit: Past, present, and future, in: International Workshop on Multi-Agent Systems and Agent-Based Simulation, Springer, Cham, 2018, pp. 75–86.

30.

Malheiros,

Ramalho,

Passeti,

Bulhòes and

Subramanian, A hybrid algorithm for the multi-depot heterogeneous dial-a-ride problem, Computers & Operations Research 129 (2021), 105196. doi:10.1016/j.cor.2020.105196.

31.

L.A.

Merlin, Comparing automated shared taxis and conventional bus transit for a small city, Journal of Public Transportation 20(2) (2017), 2. doi:10.5038/2375-0901.20.2.2.

32.

S.N.

Parragh,

Pinho de Sousa and

Almada-Lobo, The dial-a-ride problem with split requests and profits, Transportation Science 49(2) (2015), 311–334. doi:10.1287/trsc.2014.0520.

33.

Pilato,

Vitabile,

Vassallo,

Conti and

Sorbello, Web Directories as a knowledge base to build a multi-agent system for information sharing, Web Intelligence and Agent Systems: An International Journal 2(4) (2004), 265–277.

34.

Posada,

Andersson and

C.H.

Häll, The integrated dial-a-ride problem with timetabled fixed route service, Public Transport 9(1) (2017), 217–241. doi:10.1007/s12469-016-0128-9.

35.

R.Y.

Rubinstein and

D.P.

Kroese, Simulation and the Monte Carlo Method, John Wiley & Sons, 2016.

36.

M.M.

Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations research 35(2) (1987), 254–265. doi:10.1287/opre.35.2.254.

37.

Weiss (ed.), Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, MIT Press, Cambridge MA USA, 1999.

38.

Zeddini,

Zargayouna and

Yassine, Space and space-time organization model for the dynamic vrptw, in: 6th Workshop on Agents in Traffic and Transportation, Co-Located with the 8th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2010), Toronto, Canada, 2010, pp. 21–27.