A multi-agent approach for on-demand transportation problem in cities

Abstract

On-demand transportation (ODT) systems have proliferated in diverse cities worldwide due to their social, economic and environmental advantages. Despite those advantages, it is vital to get public approval. The approval key is the system’s reactivity in supplying speedy and reliable solutions that consider clients’ and vehicles’ constraints. Those solutions have to reflect actual life conditions to optimize the quality of service. The most regarded challenge in studying the ODT problem in cities is the stochastic time-dependent travel speed that varies due to traffic fluctuations. To deal with an actual ODT problem, a system has to represent the traffic on its scale. Hence, estimating the travel speed at a specific time and affording a solution based on reliable traffic data. Accordingly, the passengers are served better. This work contributes to the study by solving the ODT problem in cities with a massive multi-agent system that considers historical traffic data and unpredictable events disrupting the typical traffic. We evaluate the proposed approach by experiments with instances based on actual data for a city in the north of Lebanon. The results reveal that the quality of service increases when the stochastic time-dependent travel speed is considered. 50% to 100% of affected clients by an unpredictable event are satisfied when this event is considered by the system.

Keywords

On-demand transportation massive multi-agent modeling stochastic time-dependent travel speed historical traffic data self-organization

1. Introduction

On-demand transportation (ODT) is a ride-sharing taxi that addresses several transportation demands to the same vehicle. ODT problem has been widely studied for several years [7,21]. Nowadays, it is still critical because an increase in the population and its mobility leads to an increase in the traffic problem. Recently, ODT systems have proliferated in diverse cities in the world due to their social, economic and environmental advantages [15,30,31]. For instance, they serve areas uncovered by traditional public transport. Moreover, they propose a cheaper solution than taxis because they allow the transportation of several clients per vehicle simultaneously. That contributes to reducing the negative consequences on the environment, especially air and noise pollution, soil consumption, etc. [3]. However, it is essential to get public approval despite those benefits. The approval key is the system’s reactivity in supplying speedy and reliable solutions that consider clients’ and vehicles’ constraints, reflect actual life conditions, and optimize the quality of service.

The most regarded challenge in studying the ODT problem in cities is the stochastic time-dependent travel speed. This later varies according to the traffic situation. Therefore, an ODT system has to evaluate the traffic conditions to foresee any transformations in speed during vehicle circulation and provide reliable results. Multi-agent system [36] has been regarded as an efficient tool for solving ODT problem [2]. However, up to our knowledge, all precedents published research using the multi-agent technology do not consider the stochastic time-dependent travel speed, especially that varies according to unpredictable events [1,12,13,23,37]. In this paper, we use multi-agent system to agentify the ODT problem in cities massively. We propose a historical traffic data-based system that reflects the traffic on its scale and provides accurate travel speeds. It can also anticipate the effect of unpredictable events on the traffic, avoid congested roads by diverting the vehicles, and finally serve the passengers on time.

The main contributions of the paper are as follows: First, a specification model is defined to design and implement a massive multi-agent system that we have applied to ODT problem and traffic representation. Second, the massive multi-agent system considers historical traffic data and unpredictable events disrupting the typical traffic to represent the traffic organization on its scale. Third, a prototype of the proposed approach is designed and implemented to validate its effectiveness. Finally, we generate instances based on real data for a city in the north of Lebanon to evaluate the proposed approach. The contribution is significant for the following reasons: The stochastic time-dependent travel speed is considered while solving the ODT problem in cities. The representation of the traffic organization on its scale enables estimating the travel speed at a specific time and affording a solution based on reliable traffic data. Concepts within the traffic organization framework can be extended and applied to several similar problems, e.g. traffic regulation in urban areas.

In the rest of this paper, we present some previous works solving the Vehicle Routing Problem (VRP) and its variants in Section 2. A description of the elements of the ODT system is provided in Section 3. Section 4 outlines the massive multi-agent approach of the ODT problem. Section 5 manifests the treatment of a new client’s demand. Section 6 presents the treatment of the traffic evolution. The experimentation is presented in Section 7. The last section concludes and discusses the future works.

2. Literature review

Most researches on Vehicle Routing Problem (VRP) and its variants presume fixed travel speeds [5,14]. That is fictitious and conducts to acquire irresponsible and pricey outcomes- the service quality declines and the drivers’ regular working hours increase. Neglecting the variation of travel speeds will lead to scramble the working hours of 50% of the vehicle’s trips [26] and to misevaluating the trajectories duration up to 20% [10]. Accordingly, it is essential to take into consideration the time-dependent travel speed.

Limited papers address the VRP with time-dependent travel speed [6]. For a recent survey about the different models, interested readers can refer to [16].

Some works contemplate the travel speed modification emanated from predictable events. For example, a model is proposed for vehicles routing and scheduling problem considering the variation in travel speed during different times of the day [22]. This sample shows more evolved results than those conveyed by another one that deals with the same problem with a fixed travel speed. The authors use the FIFO property to guarantee that a vehicle initiating at a time t, will reach its destination at a time $t^{'}$ more diminutive than the arrival time of another that starts from the same point but in $t^{″} > t$ . The authors in [9] advert to the method of Floating Car Data (FCD) to compile historically documented traffic data on a road network in the United Kingdom. The collected data disintegrate one day into 15-time slots to reflect the changes in traffic conditions during the 24 hours. The time slot alters between 30 minutes and 8 hours to encompass peak hours and the nighttime when congestion does not occur. Afterwards, they utilize historical traffic data to create a road timetable that supplies the minimum travel time and the shortest-time trajectory between two places of a road network according to a specific time of a day, a day of a week, and a season of a year. They then reveal that using historical information, road timetables, and time-dependent travel times guide to obtaining outcomes satisfying the clients’ time windows and evading the drivers’ overtime. The authors in [26] construct a model for a goods allocation system employed to schedule a fleet of vehicles in the South West UK. This model assumes time-dependent travel speed based on historical traffic data. They create a road timetable with the same concept as the one operated in [9] to acquire the shortest-time paths between the clients and appoint them to vehicles. This model seeks to reduce the total time required to deliver goods from a depot to a set of clients who foist several restrictions. The experiments indicate a saved amount of 7% ${CO}_{2}$ emissions than the model based on constant speeds. In [10], while planning vehicle routes in urban areas, the authors take into consideration time-dependent travel time. The collection of historical data is made by the FCD method. In addition, the authors employ data mining techniques to analyse and filter data since a massive amount of data are collected by this method. Furthermore, [11] displays the consequence of regarding the travel time on the credibility of vehicles planned routes. Therefore, the experiments ascertain the necessity to assume this factor in the metropolitan areas to enhance the planning of vehicles routes and supply coherent and well-grounded outcomes. The authors in [18] have recently used a tabu search method to solve time-dependent vehicle routing problem (TDVRP). Different paths between a pair of nodes are considered. The shortest-time path according to the time is computed based on road-network information. Also, [34] presents an exact approach based on branch-and-price method to solve the same problem.

Predictable events are insufficient to show the actual traffic conditions. The consideration of unpredictable events is necessary. The authors in [24] show that considering traffic information allows a 12% reduction in the use of a vehicle: 8.4% of the reduction is due to historical information, and 3.6% is due to real-time traffic information. Therefore, some recent researches have considered the change in travel time due to unpredictable events. For example, the authors in [32] discuss the dynamic dial a ride problem (DDARP) by studying the effect of the time-dependent and stochastic travel speeds on vehicles trips. They solve the problem by two types of methods: (1) deterministic methods that treat DDARP by using the average time-dependent travel speeds and (2) stochastic methods that treat stochastic DARP by considering the unpredictable events that may occur in the future. In this approach, the paths of the vehicles do not change due to an unpredictable event, but the time required to cross the shortest-distance path is calculated by bearing in mind the future accidents that may occur. The two methods are compared and proved that considering the historical effect data of the accidents in the paths estimation has a beneficial impact on the quality of the solutions. Authors in [19] weigh each road by an interval travel time (ITT) to give reliable solutions in city logistics. The shifted gamma distribution generates the value of travel times of each road. The lower bound of the intervals is the 5% quantiles and the upper bound is the 95% quantiles. Using the ITT technique, the aggregation of different travel times on each road and data collection to calculate the roads travel time are avoided.

Based on our information, all precedents papers that propose multi-agent systems to model and solve the ODT problem do not consider the stochastic time-dependent travel speed [1,4,12,13,23,28,29,37]. In [27], the authors propose a multi-agent approach to resolve the ODT problem in cities with time-dependent travel speed. Based on the city’s historical traffic data, the travel speed is evaluated at a particular time. Experimental results show that considering travel speed reduces customer dissatisfaction by more than 50%.

To the best of our knowledge, this paper is the first to address the ODT problem using multi-agent technology and considering stochastic time-dependent travel speed and real-life conditions as unpredictable events.

3. The components of ODT system

The essential components in the ODT system are: the road network of the city, the client’s demand, the vehicle and the trajectory. In this section, we describe the representation of each component in the system.

3.1. Stochastic dynamic road network

The road network of the city is characterized by dynamic (time-dependent) and stochastic speeds. It is defined by a graph $G = (P, E)$ consisting of a set of points $P = {p_{1}, \dots, p_{n}}$ denoting the locations in the city, and a set of edges $E = {e_{1}, \dots, e_{m}}$ designating the roads in the city. Each road connects two locations $p_{i}$ , $p_{j}$ and has the following characteristics:

A List of expected traffic situations. This list reflects the typical traffic on the road. We construct this list by adopting the method described in [9] with regard to the road’s historical traffic data.

Table 1 represents an example of this list. A time interval and a traffic situation characterize every row in the table. For example, between 7h00 and 10h00, the traffic situation on the road is dense.

A List of expected traffic situations following unpredictable events. This list reflects the usual impact on the traffic of unpredictable events that may occur on the road such as car accidents. It is used to anticipate future changes in traffic conditions when an unpredictable event occurs on the road. The list is constructed from historical traffic data about the impact of unpredictable events on traffic.

Table 2 represents a simple example of this list. It reflects the impact on the traffic of an accident occurred on the road $r_{1}$ . Every row in the table is described by (time interval, impacted roads, impact time, traffic situation). Suppose the accident occurs at 10h30, the road $r_{1}$ and their contiguous roads $r_{2}$ and $r_{3}$ are affected during 30 min. Their traffic situation is dense.

a real-time traffic situation. It can be calculated using various technologies [17,33,35].

Table 1
List of expected traffic situations

Time interval Traffic situation

$[7 h 00, 10 h 00]$ Dense

$[10 h 00, 14 h 00]$ Low

$[14 h 00, 16 h 00]$ Dense

$[16 h 00, 7 h 00]$ Low

Time interval	Traffic situation
$[7 h 00, 10 h 00]$	Dense
$[10 h 00, 14 h 00]$	Low
$[14 h 00, 16 h 00]$	Dense
$[16 h 00, 7 h 00]$	Low

Table 2

List of expected traffic situations following an accident on road $r_{1}$

Time interval	Impacted roads	Impact time	Traffic situation
$[7 h 00, 10 h 00]$	$r_{1}$ , $r_{2}$ , $r_{3}$	45 min	Saturated
$[10 h 00, 14 h 00]$	$r_{1}$ , $r_{2}$ , $r_{3}$	30 min	Dense
$[14 h 00, 18 h 00]$	$r_{1}$ , $r_{2}$ , $r_{3}$	45 min	Saturated
$[18 h 00, 7 h 00]$	$r_{1}$ , $r_{2}$	20 min	Dense

This is a distributed, dynamic and self-organizing model that depends heavily on historical traffic data. Consistent data collection is essential to accurately reflect traffic, ensure the accuracy of this model and achieve goal. The collection and analysis of traffic data is not part of this work. Those interested can refer to [20,35].

3.2. The client’s demand

The client’s demand is defined by: $\begin{matrix} D = ((origin, t_{origin}) \overset{n_{passengers}}{\to} (dest, t_{dest})) \end{matrix}$

$origin$ and $dest$ are the origin and the destination locations,

$t_{origin}$ is the earliest time to leave the origin,

$t_{dest}$ is the latest time to arrive to the destination,

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

Consider

d_{1} = ((u, 9 h) \overset{3}{\to} (v, 11 h))

an example of a demand.

d_{1}

means three passengers request to depart from u after

9 h

and intend to reach v before

11 h

3.3. Vehicle

Every vehicle is described by (name, capacity, planning table):

name represents the vehicle’s name,

capacity represents the passenger seats’ number in the vehicle,

planning table refers to the occupancy of the vehicle for each day. Every row in the table is represented by $(t, road, | passengers |)$ where:

t is time,

$road$ is the road on which the vehicle is located at time t,

$| passengers |$ is the passengers’ number at time t.

The planning table provides the path of the vehicle and the number of passengers at each time.

This is an example of a vehicle: ( $v_{1}$ , 6, Table 3 ). $v_{1}$ is a vehicle that has 6 seats. The information about $v_{1}$ can be easily derived from Table 3. At time $9 h 00$ , $v_{1}$ is on road $r_{1}$ with no passenger. At $9 h 30$ , the vehicle is on road $r_{2}$ and the number of passengers is 4. At $9 h 40$ , $v_{1}$ is on road $r_{2}$ and the number of passengers is 4. At $10 h 00$ , the vehicle drops off one passenger at a place on road $r_{4}$ and takes roads $r_{2}$ to drops off the passengers and takes roads $r_{3}$ , $r_{5}$ to pick up 3 passengers.

Table 3
Vehicle $v_{1}$ planning table

Time Road $| passengers |$

$9 h 00$ $r_{1}$ 0

$9 h 30$ $r_{2}$ 4

$10 h 00$ $r_{4}$ 3

$10 h 30$ $r_{2}$ 0

$11 h 00$ $r_{3}$ 0

$11 h 30$ $r_{5}$ 3

Time	Road	$\| passengers \|$
$9 h 00$	$r_{1}$	0
$9 h 30$	$r_{2}$	4
$10 h 00$	$r_{4}$	3
$10 h 30$	$r_{2}$	0
$11 h 00$	$r_{3}$	0
$11 h 30$	$r_{5}$	3

3.4. Trajectory

Every trajectory $traj$ is represented by: $\begin{matrix} traj = (r_{origin}, {start}_{1}) \overset{t_{origin}}{\to} \dots (r_{i}, {start}_{i}) \overset{t_{i}}{\to} \dots (r_{dest}, end) \end{matrix}$ where

$path = r_{origin} \to \dots r_{i} \dots \to r_{dest}$ represents the roads relating an origin location to a destination location,

${start}_{i}$ is the starting time. $end$ is the arrival time at the destination,

$t_{i}$ is the time taken to cross a road $r_{i}$ .

4. Massive multi-agent modeling for ODT problem

The ODT problem consists of a large number of elements such as customers, vehicles, roads, traffic situations, etc. Thus, it is modeled as a massive multi-agent problem to represent diverse ODT elements and realize a self-organizing system.

4.1. Types of agents

We distinguish two categories of agents: static agents and dynamic agents.

In the static agent category, there is the Client agent, the Vehicle agent and the Pathfinder agent.

Client agent: it sends the demand of the client to all the vehicles in the system and, if available, gets the best vehicle that can serve it.

Vehicle agent: is associated to every vehicle in the system. Its role is to check if it can transport the passengers of a demand.

Pathfinder agent refers to every Vehicle agent and it offers the trajectories for the Vehicle agent to follow.

We identify as dynamic agent: Road agent and Regulator agent. They are dynamic because they self-organize online by changing their number and their characteristics according to traffic situations.

Road agent: is associated to contiguous roads that have a similar speed limit and traffic situation for a given period of time.

Regulator agent: is associated to contiguous roads that have a similar traffic situation for a given period of time.

Each road is associated to a Road agent and a Regulator agent. These agents rely on historical traffic data of their roads to continuously predict and reflect real traffic.

4.2. General architecture

Figure 1 shows the general architecture of the ODT system. The main agent is the Regulator agent. It interacts with the Road agents, the Pathfinder agents and the contiguous Regulator agents. The ultimate goal of the Road and Regulator agents is to reflect the traffic at its real scale. Thus, the Pathfinder agent provides the Vehicle agent a reliable trajectory with an accurate estimation of the duration of the path.

Fig. 1.

General architecture.

5. Treatment of a client’s demand

This section describes the collaboration between agents to treat a new demand. The Client agent broadcasts each new demand to all Vehicle agents. A Vehicle agent executes the demand if it complies with two constraints: (1) having free seats to transport the passengers between the requested times, and (2) inserting the demand into its planning table without breaking the time slots of its previously accepted demands and the new demand. We address these constraints in the next section.

5.1. The description of constraints

A Vehicle agent checks its availability when a demand $D = ((origin, t_{origin}) \overset{n_{passengers}}{\to} (dest, t_{dest}))$ is requested to manage it. The Vehicle agent refers to its planning table to affirm whether the number of accessible seats between $t_{dep}$ and $t_{arr}$ is greater than or equal to $n_{passengers}$ . Then, it calculates the time intervals $t s_{1} = [t_{a_{1}}, t_{b_{1}}]$ where the demand departure time will be inserted and $t s_{2} = [t_{a_{2}}, t_{b_{2}}]$ where the arrival time will be inserted. Afterwards, it verifies the following four constraints by cooperating with its Pathfinder agent. $\begin{array}{l} (1) & t_{a_{1}} + t_{traj (a_{1} \to origin)} ⩾ t_{origin} \\ (2) & t_{origin} + t_{traj (origin \to b_{1})} ⩽ t_{b_{1}} \\ (3) & t_{a_{2}} + t_{traj (a_{2} \to dest)} ⩽ t_{dest} \\ (4) & t_{dest} + t_{traj (dest \to b_{2})} ⩽ t_{b_{2}} \end{array}$

Constraint (1) assures that the new demand initiates at a time that does not surpass the earliest time to depart, constraint (2) assures that the demand is served without disregarding the time slot of the subsequent demand, constraint (3) asserts that it ends at a time that does not exceed the latest time to reach its destination, and finally, constraint (4) ensures that the service is provided by taking into consideration the time interval for the following order.

5.2. Constraints verification

After checking the number of free seats, each Vehicle agent proceeds to check each of the above constraints. To do this, the Vehicle agent contacts the Pathfinder agent to find the trajectory connecting the two locations in each constraint starting from the departure time of the initial place. The Pathfinder agent suggests the usual path1

¹
How a path becomes a usual path is not discussed in this paper.

that the Vehicle agent prefers depending on the time to get from one place to the other. Then, it contacts the Regulator agents in charge of the roads of the path to calculate the time needed to cross them at a time t.

Based on the List of expected traffic situations of its roads, each contacted Regulator agent calculates the time required to cross its roads segment by applying the algorithm described in [22]. This algorithm respects the FIFO priority. It ensures that a vehicle starting at a time t, will arrive at a time $t^{'}$ smaller than the arrival time of another that starting from the same point but in $t^{″} > t$ .

Then, it sends its part of trajectory containing the computed time to the Pathfinder agent. The latter computes the result of the trajectory from the responses of all the contacted Regulator agents and sends the result to its Vehicle agent. The Vehicle agent checks whether the trajectory matches the currently verified constraint. If it does, the Vehicle agent proceeds to verify the other constraints. If the trajectory does not satisfy the constraint, the Pathfinder suggests two other paths. Then, the same scenario is repeated to estimate each path. Figure 2 shows how agents cooperate in estimating a path.

Fig. 2.

Agents cooperation strategy.

The Vehicle agent informs the Client agent of its availability to execute the demand after verifying all the constraints. If a Vehicle agent does not comply with these constraints, it cannot conform to the demand.

Vehicle agents able to execute the demand calculate two values: the number of vehicles in circulation and their total traveled distance. Then, they negotiate with each other to find the best vehicle to transport the passengers. The best Vehicle agent is the one that minimizes the number of vehicles in circulation. If two Vehicle agents have the same number, the one that minimizes the total traveled distance is the best. The method of negotiation is explained in [28,29].

6. Treatment of the traffic evolution

We distinguish two types of traffic: a dynamic deterministic traffic and a dynamic stochastic traffic. In this section, we explain how the Road and Regulator agents rely on the historical traffic data of their roads to anticipate the real traffic situation. Finally, we explain the merging and the decomposition of the dynamic agents.

6.1. Treatment of the deterministic traffic evolution

Deterministic traffic is the typical traffic of everyday life. Based on the List of expected traffic situations of their roads, Road and Regulator agents self-organize to represent deterministic traffic continuously on its scale. They vary their traffic situation and execute the merging and decomposition operations to assign themselves to a new set of roads depending on the traffic situation.

6.1.1. Determination of dynamic agents and their time intervals

At the initial time $t_{0}$ (the start time of the ODT system) and based on the List of expected traffic situations of each road, a Road agent ${Ar}_{i}$ associates with a set of contiguous roads that have a similar speed limit and a similar traffic situation during a time interval $I_{i} = [t_{0}, t_{i}]$ . The Road Agent ${Ar}_{i}$ has the same traffic situation as its roads during $I_{i}$ . Also, a Regulator agent ${Areg}_{j}$ associates with a set of contiguous roads with similar traffic situation during a time interval $I_{j} = [t_{0}, t_{j}]$ . The Regulator agent ${Areg}_{j}$ has the same expected traffic situation as its roads during $I_{j}$ . We obtain n Road agents and m Regulator agents covering the road network during $I_{i}$ and $I_{j}$ , respectively. The upper bounds $t_{i}$ and $t_{j}$ represent the minimum of the upper bounds of the time intervals that contain $t_{0}$ . These intervals are elements in the List of expected traffic situations of ${Ar}_{i}$ and ${Areg}_{j}$ roads.

6.1.2. Behavior of dynamic agents during their time intervals

During $I_{i}$ , the Road agent ${Ar}_{i}$ constantly compares the expected traffic situation with the real traffic situation of each of its roads. If the two situations are homogeneous, it continues to rely on the List of expected traffic situations to reflect the traffic. The reverse case is discussed in Section 6.2.

During the interval $I_{j}$ , the Regulator agent ${Areg}_{j}$ listens to its Road agents covering its geographical area. If it does not receive any urgent messages from them, it proceeds to reflect the expected situation. The opposite case is dealt with in Section 6.2

6.1.3. Behavior of dynamic agents at the end of their time intervals

At $t_{i}$ = upper bounds of $I_{i}$ and $t_{j}$ = upper bounds of $I_{j}$ , the Road agent and the Regulator agent proceed to determine their new roads, their new traffic situation and their subsequent time intervals $I_{i + 1}$ and $I_{j + 1}$ , respectively.

Using the List of expected traffic situations, each Road agent and each Regulator agent check the traffic situation of their roads at $t_{(i + 1)}$ and $t_{(j + 1)}$ , respectively. The result shows two cases:

The roads have similar traffic situations during a certain period. In this case, the Road agent and the Regulator agent keep the same set of roads but with a new traffic situation during $I_{i + 1}$ and $I_{j + 1}$ , respectively. The Road agent and the Regulator agent send a message to their contiguous Road agents and contiguous Regulator agents, respectively, informing them about the new traffic situation and trigger the merging operation if it is possible.

The roads have different traffic situations. In other words, at least one of the road has a different traffic situation than the others. In this case, the Road agent and the Regulator agent trigger the decomposition operation by creating one or more new Road agents and new Regulator agents, respectively, according to the traffic situation on their roads. Each new agent Road agent and each new Regulator agent define their roads and their traffic situation during $I_{i + 1}$ and $I_{j + 1}$ , respectively. Then, they inform their contiguous ones about the new traffic situation to trigger the merging operation if it is possible.

$I_{i + 1}$ and $I_{j + 1}$ are calculated in the same way as $I_{i}$ and $I_{j}$ .

6.2. Treatment of the stochastic traffic evolution

At a time t, a Road agent notices that the expected traffic situation on a road differs from the real situation. In this case, the Road agent detects the occurence of an unpredictable event on the road. It defines the type, the location and the time of the event. Then, it sends an urgent message with the event parameters to the Regulator agent responsible for the impacted road. Based on these parameters and the List of expected traffic situations following unpredictable events of the road, the Regulator agent creates an urgent list for each impacted road. The urgent list contains the new traffic situations of the road during the time of impact. It replaces its List of expected traffic situations during that time. Each Road agent associated with an impacted road received the corresponding urgent list from the Regulator agent. Table 4 is an example of an urgent list created for the road after an accident.

Table 4
Urgent list

Impact time Traffic situation

$[10 : 30, 10 : 50]$ Saturated

$[10 : 50, 11 : 00]$ Dense

$[11 : 00, 14 : 00]$ Fluid

Impact time	Traffic situation
$[10 : 30, 10 : 50]$	Saturated
$[10 : 50, 11 : 00]$	Dense
$[11 : 00, 14 : 00]$	Fluid

The Road agent and the Regulator agent created based on the urgent list, are referred to as the Urgent Road agent and Urgent Regulator agent, respectively. Each Urgent Regulator agent searches for the Pathfinder agents that are affected by this unpredictable event. These are the agents whose the trajectory of their Vehicle agent will pass through the impacted roads during the impact period. The Urgent Regulator agent re-evaluates these trajectories and sends the new evaluation to the affected Pathfinder agents. The Pathfinder agent, in turn, informs its Vehicle Agent of the new evaluation. If the new evaluation is consistent with the planning table of the Vehicle agent, it continues following the trajectory normally. Otherwise, it decides to divert and asks its Pathfinder agent for a new trajectory. The latter proposes the trajectory that contains no impacted roads or the minimum number of impacted roads. The diversion helps to reduce the negative effect of the event on the trajectory duration.

6.3. Merging and decomposition operations

The dynamic agents self-organize to continuously fit the real traffic. They decompose into several and merge with others contiguous dynamic agents to cover the road network according to the traffic. Therefore, their number varies. For example, during the night at 02:00, there is one Regulator agent. This is not the case during peak hours, when the Regulator agent decomposes to represent the multiple traffic situations.

In the following two subsections, we explain the merging and decomposition operations of dynamic agents. To know how Road agent and Regulator agent apply these operations, please replace the word dynamic agent by Road agent and Regulator agent, respectively.

Fig. 3.

Merging of road agents in a single one.

6.3.1. Merging dynamic agents

At a time $t_{i}$ , a new dynamic agent (created after decomposition or merging operations) or a dynamic agent that has a new traffic situation sends a message with its properties (speed limit and traffic situation) to its contiguous dynamic agents. If a contiguous dynamic agent has similar properties during a time interval $[t_{i}, t_{f} [$ , it responds with a message containing the time interval. After receiving all responses, the dynamic agent merges with those that replied to compose a single dynamic agent during $[t_{i}, t_{c}]$ where $t_{c}$ is the minimum of the upper bounds of all time intervals sent by the dynamic agents.

As illustrated in Fig. 3, a Road agent $r_{1}$ has a low traffic situation at $I_{1} = [t_{{min}_{1}}, t_{{max}_{1}}]$ , and Road agent $r_{2}$ has a low traffic situation at $I_{2} = [t_{{min}_{1}}, t_{{max}_{2}}]$ . In this case, $r_{1}$ and $r_{2}$ merge into a single agent $r_{3}$ with a low traffic situation during the time interval $I_{3} = I_{1} \cap I_{2} = [t_{{min}_{1}}, t_{{max}_{3}}]$ where $t_{{max}_{3}} = min (t_{{max}_{1}}, t_{{max}_{2}})$ .

6.3.2. Decomposition of a dynamic agent

At a time t, a dynamic agent perceives several traffic situations on the roads associated to it. In this case, it decomposes into multiple dynamic agents. Each dynamic agent reassociates with contiguous roads that have the same traffic situation during a common time interval. The time interval is determined as explained in Section 6.1.1. Then, it informs its contiguous dynamic agents about the new traffic situation to trigger the merging operation if possible.

Figure 4 gives an example of Road agents decomposition. The part1 shows a Road agent has two traffic situations (medium and low) on its roads. This contradicts the definition of a Road agent. Therefore, the Road agent decomposes into two Road agents as shown in part 2 and part 3. The Road agent 1 has low traffic and the Road agent 2 has medium traffic.

Fig. 4.

Decomposition of a road agent.

7. Experiments

This section includes experiments based on real instances to validate the proposed approach. These experiments measure:

the number of served demands (clients) considering the traffic situation;

the number of satisfied clients when the system considers unpredictable events;

the number of Road and Regulator agents associated with the dynamic stochastic road network of a city at various times;

the number of contacted agents to evaluate paths.

7.1. Experiments parameters

We used the multi-agent simulation toolkit MASON [25] to develop an experimental platform and validate our approach.

We used the road network of a Lebanese city called Tripoli. We used 214 nodes and 410 roads for the experiments. The road has a distance and a speed limit which varies between 40 and 100 km/h. We also selected a well-known transportation company in Tripoli called Connexion. The interview with the general manager enabled us to identify the needs of the Tripolitan population in order to define the number of daily demands, the origin and destination locations and the most requested departure times.

The List of expected traffic situations and the List of expected traffic situations following unpredictable events for each road are generated based on the city traffic statistics provided by the municipality.

The clients’ demands are generated according to the information provided by the general manager of the transportation company. The origin and destination locations are generated by the application of Monte Carlo method [8] on Tripoli locations. The frequently requested locations have a more elevated probability (75%) of being appointed corresponding to other places. Moreover, the number of passengers is haphazardly chosen by applying the uniform distribution to a set of four integers that range between 1 and 4.

The Monte Carlo method is applied to a set of hours that vary between 7:00 and 22:00. The peak hours that have a higher possibility (75%) to be picked than the others range between the two intervals $[7 : 00, 9 : 00]$ and $[14 : 00, 16 : 00]$ . As results, 500 demands are created.

7.2. Experiments results

We conducted three experiments, which are explained in the following subsections.

7.2.1. Number of unsatisfied clients

In these experiments we generate four accidents, each of which we measure:

the number of demand served during the impact time of the accident;

the number of clients affected by the accident. These are clients who will be dissatisfied if the system does not consider the accident;

the number of satisfied clients among those affected by the accident after the system considers the accident.

We assume that three traffic accidents occurred in Tripoli in one day. The roads are chosen based on Tripoli municipality statistics on the most accident-prone roads. The first accident occurs at 07:30 on a road chosen by applying the Monte Carlo method to the most accident-prone roads between 07:00 and 09:00. The second accident is generated on the same road at 12:30. The road for the third accident generated at 20:30 is chosen among the most prone roads to have accidents between 19:00 and 21:00. We present five scenarios: the first has 100 transportation demands, the second 200, the third 300, the fourth 400, and the fifth 500. The demands of the previous scenario are included in each scenario. Table 5 shows the results obtained for each accident in the five scenarios.

Table 5
Impact of the three accidents on demands

Treatment of 100 clients

Accident No. 1 2 3

Number of served clients during accident 17 2 11

No. of clients affected by the accident 1 0 1

No. of satisfied clients 1 0 1

Treatment of 200 clients

Accident No. 1 2 3

Number of served clients during accident 31 3 23

No. of clients affected by the accident 6 0 2

No. of satisfied clients 5 0 1

Treatment of 300 clients

Accident No. 1 2 3

Number of served clients during accident 52 3 28

No. of clients affected by the accident 9 0 2

No. of satisfied clients 6 0 1

Treatment of 400 clients

Accident No. 1 2 3

Number of served clients during accident 74 5 35

No. of clients affected by the accident 13 1 3

No. of satisfied clients 9 1 2

Treatment of 500 clients

Accident No. 1 2 3

Number of served clients during accident 96 6 51

No. of clients affected by the accident 15 2 4

No. of satisfied clients 11 2 2

Treatment of 100 clients
Accident No.	1	2	3
Number of served clients during accident	17	2	11
No. of clients affected by the accident	1	0	1
No. of satisfied clients	1	0	1

Treatment of 200 clients
Accident No.	1	2	3
Number of served clients during accident	31	3	23
No. of clients affected by the accident	6	0	2
No. of satisfied clients	5	0	1

Treatment of 300 clients
Accident No.	1	2	3
Number of served clients during accident	52	3	28
No. of clients affected by the accident	9	0	2
No. of satisfied clients	6	0	1

Treatment of 400 clients
Accident No.	1	2	3
Number of served clients during accident	74	5	35
No. of clients affected by the accident	13	1	3
No. of satisfied clients	9	1	2

Treatment of 500 clients
Accident No.	1	2	3
Number of served clients during accident	96	6	51
No. of clients affected by the accident	15	2	4
No. of satisfied clients	11	2	2

In this experiment, we find that: (1) the number of dissatisfied clients increases when the number of served clients during the accident period increases; (2) an accident affects between 2% to 39% of the clients; (3) 50% to 100% of the affected clients are satisfied because accidents are considered by the system.

This experiment ascertains that considering unpredictable events is necessary because the predictable ones are insufficient to reflect the actual traffic. In brief, the stochastic time-dependent travel speed should be considered while computing the trajectories durations.

7.2.2. Coverage of Tripoli road network by dynamic agents

In this experiment, we measure the number of Road and Regulator agents associated with Tripoli roads. This number is measured every 30 minutes starting at 7:00 until midnight. We additionally choose a road by applying the uniform distribution to the roads where an accident is most likely to occur. Then, we generate an accident on this road and we measure the change in the number of agents due to this accident. Figure 5 shows the results.

The chart shows that: (1) at midnight,when traffic is fluid, Tripoli, made up of 410 roads, is covered by 14 Road agents and a single Regulator agent; (2) the number of Regulator agents is less than the number of Road agents; (3) the number of agents increases during peak hours between $[7 h 00, 9 h 00]$ and $[14 h 00, 16 h 00]$ and decreases during other time intervals; (4) the number of dynamic agents increases during accidents.

This experiment proves that the dynamic Road and Regulator agents self-organize online by changing their number and their characteristics according to traffic situations. When an unpredictable event appears, the number of dynamic agents increases to reflect accurately the traffic of the roads affected by this event.

Fig. 5.

Number of road and regulator agents associated with the roads of Tripoli during a day and variation of this number following an accident.

7.2.3. Number of contacted dynamic agents

In the approach proposed in [27] where each road is associated with a Road agent, the Pathfinder agent contacts the Road agents to evaluate a path. In our approach, the Pathfinder agent contacts the Regulator agents instead of the Road agent. In this experiment, we measure the number of contacted Road agents in [27] and that of Regulator agents in this approach to evaluate a path. Figure 6 presents the experiment’s results. It shows that the number of contacted Road agents is always greater than that of Regulator agents. Our approach saves more than 60% of the contacted agents.

Fig. 6.

Difference between the number of contacted roads and regulator agents.

In brief, the two last experiments reveal that the ultimate goal of the dynamic agents is to reflect the traffic on its real scale and optimize the communication by minimizing the number of contacted agents.

8. Conclusions

This paper presented an agent-based algorithm for the ODT problem in cities characterized by dynamic and stochastic speeds. The main contribution is the resolution of the problem by a massive multi-agent system that considers historical traffic data and unpredictable events disrupting the typical traffic. The system operates online for continuously represent the traffic organization on its scale and produce reliable results to serve the client on time. Experiments with instances based on real data for a city in the north of Lebanon showed that the quality of service increases when the stochastic time-dependent travel speed is considered. 50% to 100% of clients affected by an unpredictable event are satisfied when this event is considered by the system.

Our approach assumes that each road must have the actual traffic situation and consistent and up-to-date historical traffic data. If a road does not have the actual traffic situation or the historical traffic data does not take into consideration a new sudden event, our approach will be limited in the representation of the traffic. Therefore, the results will not be reliable, and the quality of service will decrease.

This approach may be extended to regulate traffic in a city. In addition, multiple agents can be added: road junction agent, unpredictable event agent, etc. Moreover, a Pathfinder agent that offers the shortest time trajectory is under study. The purpose of the usual path is to respect the desires of the drivers and prevent the vehicles from following the same trajectories. Accordingly, this helps to minimize the possibility of traffic on the roads. As an example, if the Pathfinder agent always offers the shortest path in terms of time, then this path taken by all vehicles will never remain the shortest path.

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.

A.L.

Bazzan and

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

Benintendi,

E.M.

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 decentralised 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.

Braekers,

Ramaekers and

Van Nieuwenhuyse, The vehicle routing problem: State of the art classification and review, Computers & Industrial Engineering 99 (2016), 300–313. doi:10.1016/j.cie.2015.12.007.

Cattaruzza,

Absi,

Feillet and

González-Feliu, Vehicle routing problems for city logistics, EURO Journal on Transportation and Logistics 6(1) (2017), 51–79. doi:10.1007/s13676-014-0074-0.

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.

Eckhardt, Stan Ulam, John von Neumann, and the Monte Carlo method, Los Alamos Science 15(30) (1987), 131–136.

Eglese,

Maden and

Slater, A road timetableTM to aid vehicle routing and scheduling, Computers & Operations Research 33(12) (2006), 3508–3519. doi:10.1016/j.cor.2005.03.029.

10.

Ehmke ,

Fabian,

Meisel and

D.C.

Mattfeld, Floating car based travel times for city logistics, Transportation Research Part C: Emerging Technologies 21(1) (2012), 338–352.

11.

J.F.

Ehmke and

A.M.

Campbell, Customer acceptance mechanisms for home deliveries in metropolitan areas, European Journal of Operational Research 233(1) (2014), 193–207. doi:10.1016/j.ejor.2013.08.028.

12.

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.

13.

El Falou,

Malass,

Itmi,

El Falou and

Cardon, An application of adapted A* decentralized approach for on demand transportation problem, in: 2014 IEEE 26th International Conference on Tools with Artificial Intelligence, IEEE, 2014, pp. 930–936.

14.

Elshaer and

Awad, A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants, Computers & Industrial Engineering 140 (2020), 106242. doi:10.1016/j.cie.2019.106242.

15.

Garaix,

Artigues,

Feillet and

Josselin, Optimization of occupancy rate in dial-a-ride problems via linear fractional column generation, Computers & Operations Research 38(10) (2011), 1435–1442. doi:10.1016/j.cor.2010.12.014.

16.

Gendreau,

Ghiani and

Guerriero, Time-dependent routing problems: A review, Computers & operations research 64 (2015), 189–197. doi:10.1016/j.cor.2015.06.001.

17.

Ghosh,

M.S.

Sabuj,

H.H.

Sonet,

Shatabda and

D.M.

Farid, An adaptive video-based vehicle detection, classification, counting, and speed-measurement system for real-time traffic data collection, in: 2019 IEEE Region 10 Symposium (TENSYMP), IEEE, 2019, pp. 541–546. doi:10.1109/TENSYMP46218.2019.8971196.

18.

Gmira,

Gendreau,

Lodi and

J.-Y.

Potvin, Tabu search for the time-dependent vehicle routing problem with time windows on a road network, European Journal of Operational Research 288(1) (2021), 129–140. doi:10.1016/j.ejor.2020.05.041.

19.

P.-O.

Groß,

M.W.

Ulmer,

J.F.

Ehmke and

D.C.

Mattfeld, Exploiting travel time information for reliable routing in city logistics, Transportation Research Procedia 10 (2015), 652–661. doi:10.1016/j.trpro.2015.09.019.

20.

Gupta,

Hamzin and

Degbelo, A low-cost open hardware system for collecting traffic data using Wi-Fi signal strength, Sensors 18(11) (2018), 3623. doi:10.3390/s18113623.

21.

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.

22.

Ichoua,

Gendreau and

J.-Y.

Potvin, Vehicle dispatching with time-dependent travel times, European Journal of Operational Research 144(2) (2003), 379–396. doi:10.1016/S0377-2217(02)00147-9.

23.

Jin,

Abdulrab and

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

24.

Kim,

M.E.

Lewis and

C.C.

White, Optimal vehicle routing with real-time traffic information, IEEE Transactions on Intelligent Transportation Systems 6(2) (2005), 178–188. doi:10.1109/TITS.2005.848362.

25.

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.

26.

Maden,

Eglese and

Black, Vehicle routing and scheduling with time-varying data: A case study, Journal of the Operational Research Society 61(3) (2010), 515–522. doi:10.1057/jors.2009.116.

27.

Malas,

El Falou,

Itmi and

Cardon, Multi-agent approach for on-demand transport problem in a city, in: 2016 Third International Conference on Electrical, Electronics, Computer Engineering and Their Applications (EECEA), IEEE, 2016, pp. 40–45. doi:10.1109/EECEA.2016.7470763.

28.

Malas,

El Falou and

El Falou, Agents negotiating to meet the on-demand transport problem, in: 2018 International Conference on Computer and Applications (ICCA), IEEE, 2018, pp. 202–209. doi:10.1109/COMAPP.2018.8460396.

29.

Malas,

El Falou,

Itmi and

Cardon, Solving on-demand transport problem through negotiation, in: Proceedings of the Summer Computer Simulation Conference, 2016, pp. 1–7.

30.

S.N.

Parragh,

J.P.

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.

31.

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.

32.

Schilde,

K.F.

Doerner and

R.F.

Hartl, Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem, European Journal of Operational Research 238(1) (2014), 18–30. doi:10.1016/j.ejor.2014.03.005.

33.

Smadi,

Baker and

Birst, Advantages of using innovative traffic data collection technologies, in: Applications of Advanced Technology in Transportation, 2006, pp. 641–646. doi:10.1061/40799(213)102.

34.

H.B.

Ticha,

Absi,

Feillet,

Quilliot and

Van Woensel, The time-dependent vehicle routing problem with time windows and road-network information, Operations Research Forum 2(1) (2021), 1–25.

35.

Wang,

Ouyang,

Meng and

Kong, A traffic data collection and analysis method based on wireless sensor network, EURASIP Journal on Wireless Communications and Networking 2020(1) (2020), 1–8. doi:10.1186/s13638-019-1618-7.

36.

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

37.

Zidi,

Ghedira and

Mesghouni, A multi-agent system based on the multi-objective simulated annealing algorithm for the static dial a ride problem, IFAC Proceedings Volumes 44(1) (2011), 2172–2177. doi:10.3182/20110828-6-IT-1002.02639.

A multi-agent approach for on-demand transportation problem in cities

Abstract

Keywords

1. Introduction

2. Literature review

3. The components of ODT system

3.1. Stochastic dynamic road network

Table 1 List of expected traffic situations Time interval Traffic situation [ 7 h 00 , 10 h 00 ] Dense [ 10 h 00 , 14 h 00 ] Low [ 14 h 00 , 16 h 00 ] Dense [ 16 h 00 , 7 h 00 ] Low

3.3. Vehicle

Table 3 Vehicle v 1 planning table Time Road | passengers | 9 h 00 r 1 0 9 h 30 r 2 4 10 h 00 r 4 3 10 h 30 r 2 0 11 h 00 r 3 0 11 h 30 r 5 3

4. Massive multi-agent modeling for ODT problem

4.1. Types of agents

4.2. General architecture

5.1. The description of constraints

5.2. Constraints verification

1 How a path becomes a usual path is not discussed in this paper.

6.1. Treatment of the deterministic traffic evolution

6.1.1. Determination of dynamic agents and their time intervals

6.1.2. Behavior of dynamic agents during their time intervals

6.1.3. Behavior of dynamic agents at the end of their time intervals

6.2. Treatment of the stochastic traffic evolution

Table 4 Urgent list Impact time Traffic situation [ 10 : 30 , 10 : 50 ] Saturated [ 10 : 50 , 11 : 00 ] Dense [ 11 : 00 , 14 : 00 ] Fluid

6.3.2. Decomposition of a dynamic agent

7.1. Experiments parameters

7.2. Experiments results

7.2.1. Number of unsatisfied clients

References

Table 1
List of expected traffic situations

Time interval Traffic situation

$[7 h 00, 10 h 00]$ Dense

$[10 h 00, 14 h 00]$ Low

$[14 h 00, 16 h 00]$ Dense

$[16 h 00, 7 h 00]$ Low

Table 3
Vehicle $v_{1}$ planning table

Time Road $| passengers |$

$9 h 00$ $r_{1}$ 0

$9 h 30$ $r_{2}$ 4

$10 h 00$ $r_{4}$ 3

$10 h 30$ $r_{2}$ 0

$11 h 00$ $r_{3}$ 0

$11 h 30$ $r_{5}$ 3

¹
How a path becomes a usual path is not discussed in this paper.

Table 4
Urgent list

Impact time Traffic situation

$[10 : 30, 10 : 50]$ Saturated

$[10 : 50, 11 : 00]$ Dense

$[11 : 00, 14 : 00]$ Fluid