# A Multi-agent System Model for the Personal Rapid Transit System

Ezzeddine Fatnassi, Hadhami Kaabi

► To cite this version:

Ezzeddine Fatnassi, Hadhami Kaabi. A Multi-agent System Model for the Personal Rapid Transit System. 16th IFIP International Conference on Computer Information Systems and Industrial Management (CISIM), Jun 2017, Bialystok, Poland. pp.492-501, 10.1007/978-3-319-59105-6_42 hal-01656211

HAL Id: hal-01656211

https://inria.hal.science/hal-01656211

Submitted on 5 Dec 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A multi-agent system model for the Personal Rapid Transit system

Ezzeddine Fatnassi¹ and Hadhami Kaabi¹

Institut Supérieur de Gestion de Tunis
Tunis University

41, Rue de la Liberté - Bouchoucha - 2000 Bardo, Tunisie

**Abstract.** This research concerns a routing and dispatching problem in the context of the on-demand Personal Rapid Transit transportation system. The objective of the problem is to efficiently optimize the total empty movement related to the vehicles as well as the waiting time of passengers in a dynamic settings. To achieve this, a multi-agent model is developed to manage efficiently the Personal Rapid Transit system. The proposed model involves three types of agent as well as the implementation of an efficient decentralized management strategy in order to handle demand of the passengers. Tests are made on a realistic use-case and results reveal the viability of the proposed model and strategy.

**Keywords:** Multi-agent system modeling; On demand transportation system; Public Transportation; Simulation

## 1 Introduction

Personal Rapid transit (PRT) is an on-demand urban transit transportation system. It is generally organized in a fully connected network' shape that covers some parts of a large urban area, or a multi-terminal airport. The network is composed by a set of PRT'stations and dedicated guideways.

The system is fully automated. In fact, the PRT uses a set of driverless electric vehicles (i.e. system controlled) that move along a set of dedicated elevated guideways. This feature allows the separation of the PRT traffic from the conventional urban traffic. PRT vehicles could carry an individual passenger or a small group of individuals up to 6 persons. PRT offers a personalized transportation service as the users of such a system determine on their own the departure time, the departure and the destination of their trip freely. The control system determines based on the current demand the vehicle that should satisfies the demand of users as well as its route and movements within the PRT' network.

The PRT control system needs also to determine the set of empty moves of vehicles within the system. In fact, as the demand from a PRT station does not equal to the demand to this specific PRT station, the PRT control system would need to balance the flow of empty available vehicles in order to meet perfectly the demand of its users while minimizing their waiting time as well as the total energy consumption of the system. This problem is known in the literature by
the empty vehicle redistribution problem. The reader should refer to [12] for
more details about this problem.

In the literature, many algorithms have been developed for the empty vehicle management of PRT' vehicles which focused mainly on the optimal reallocation of the empty vehicles within the system. In fact, this strategy could significantly reduce the waiting time of passengers within the PRT system by increasing the set of empty vehicles displacement. Generally, reallocation algorithms to manage empty moves of PRT vehicles are based on the available historical data related to the incoming of passengers as well as the estimation and prediction of future demands. These approaches use a form of a centralized data base containing past demand and historical data. Due to the central repository, these algorithms are implemented in a centralized manner which they mainly refer to the empty vehicle reallocation. Consequently, these algorithms are hard to be developed in a distributed decentralized way.

Based on this context, implementing simulation tools could be useful in order
to analyze and implement effective empty vehicles strategies for PRT system. In
fact, simulation could be seen as an abstraction of a complex system in order to
study its behavior. In the literature, there exists several simulation approaches
such as discrete event simulation, dynamic system and agent-based simulation
approach (ABS).

Recently, an increasing interest on using multi-agent systems for innovation transportation applications have been proposed in the literature. In fact, Multi agent systems is a very convenient way to model complex urban transportation system composed of a large number of homogenous and heterogeneous individuals interacting within each other and with their environment. Generally, in this kind of system vehicles are modeled as an autonomous agents which aim to find a sequence of moves in order to optimize their operational cost. However, there are only few works in the literature that proposed efficient algorithms for computing approximate solutions in order to optimize transportation system.

The ABS presents the advantage of being able to study various complex
system from the perspective of individual point of view. In the literature, ABS
have been implemented and applied to model many logistics and transportation
systems [13][15]. Consequently, it would be interesting to implement an ABS
based on the context of PRT in order to reduce its empty vehicles movement
and waiting time of passengers.

In the literature, several simulation model and dynamic strategies have been
implemented for the PRT context. One could note [12] where authors studied
to minimize waiting time of passengers. However, these latter works does not
consider battery issues related to the electric PRT vehicles.

One could note also [14]where authors proposed a discrete event simulation approach to model the PRT system. ABS have been proposed within the PRT context in [2] [5] [6]. However, in [2] [5] authors focused on the activities related to vehicles rather than the stations and in [6] authors does not consider battery issues related to PRT vehicles.
Based on these gaps in the literature, we propose in this paper a distributed management algorithm and ABS for PRT systems. The novelty of our approach resides on the fact that we model stations in PRT as an independent actors (i.e. Agents) that are capable of making decisions and ask for empty PRT vehicles. In fact, we give a special focus on implementing a decentralized management algorithm where the set of decisions is distributed on the stations rather than the vehicles. This feature offers several advantages:

- Eliminating the need for a central control system as the decisions are made autonomously by the stations.

- A high flexibility for the PRT system as it would be able to cope with uncertain and unusual demand and traffic condition.

Consequently, the contributions of this paper is threefold:

- We propose an ABS where stations acts as an independent and autonomous actors in the PRT system.

- We propose a decentralized management strategy for minimizing waiting time of passengers and the set of empty moves in the system.

- We test our approach based on a realistic case study of Corby in the United Kingdom.

The structure of this paper is as follows. In Section 2, the problem definition is presented. Section 3 explains the proposed ABS as well as the implemented decentralized strategy. The computational results and analysis of our simulation model are presented in Section 4. Finally, Section 5 concludes and gives directions for future research.

## 2 Problem Definition

In this section, we present the formal problem definition related to PRT. The proposed problem considers to have a PRT network $N$ with a set of finite PRT stations denoted $M$. Groups or individual PRT’users come at the different PRT stations to ask a specific transportation service from their current location to a specific PRT’sation. We suppose that passengers arrives based on a specific poisson process of rate $\lambda$. The transportation requests should be served imme- diately. Rejection of transportation demand is not allowed in the system. The PRT system has a set of electric driverless vehicles that the system would use to satisfy the transportation demand. The PRT’vehicles are constrained by its limited battery capacity $B$. This limited battery capacity would allow the vehi- cle to travel for a limited distance before returning to the charging location to recharge their batteries.

We consider also to have a predefined matrix distance that determine the cost of moving between each pair of stations. The vehicles are initially located at the charging location. The vehicles in the PRT system are driverless that move without any human intervention. Our problem consider to find a set of dispatching decisions in order to satisfy the transportation demand. We should
note that dispatching decisions refer to the assignment of a vehicle to a specific transportation request. As soon as the system receives transportation demand, dispatching decisions need to be made as soon as possible in order to reduce the waiting time of passengers and to increase the efficiency of the system. The dispatching decisions within a PRT system should be made while knowing the current state of the network. That is why effective strategies should be made while evaluating several possibilities in order to optimize the current state of the system.

Our problem is a dynamic one. In fact, the information related to the coming of the transportation requests is known gradually as the PRT system serves its passengers. This characteristic represents an important feature to our problem as the driverless vehicles could not serve all the transportation requests at the same time due to the limited battery capacity and fleet size.

The objective of our problem is to find the set of dispatching decisions related to PRT system that would minimize the total energy consumption and the waiting time of passengers. These two objectives are of a high interest as they would increase the efficiency and the appealing of such a transportation system.

# 3 The simulation model

In this section, we present the proposed ABS model to tackle the proposed problem related to PRT. For this purpose, we present the multi-agent system modeling of PRT. Then, we present the proposed decentralized strategy.

## 3.1 The multi-agent system modeling of PRT

Generally, coordination in on-demand transportation systems (i.e. PRT) could be in two distinctive forms: i) Centralized in which the central control system tends to improve the performance of the global system by exploring all the different alternatives related to the current situation related to the transportation network by the use of coordination and information sharing. ii) Decentralized in which coordination could be found at an inter-urban zone only, which could causes conflicting practices that need to be managed.

As a result of the high level of transportation service that the PRT aims to offer to its users, PRT could be modeled as a decentralized system in which independent agents could take their own decisions. This feature would ensures a highly reactive system to the upcoming demand of passengers. Consequently, the PRT could be modeled by using multi-agent system modeling approach. Multi-agent system modeling approach consists of a set of different agents interacting with each other's in order to solve a specific problem, compete for a finite set of shared resources (i.e. the PRT vehicles) or coordinating with each other in order to avoid conflicts.

In the literature [1], the term agent defines a software or a hardware based computer system that has specific characteristics such as reactivity and pro-activity, autonomy, and social ability. Multi-agents systems offer the advantage
of being simple to implement and understand [15]. Also when the problem and
the modeled systems is itself distributed, multi-agent system models offer more
flexibility in term of dealing with the different constraints of the simulated sys-
tem.

As complex systems such the PRT are generally a decentralized and dis-
tributed ones with many interactions between its different components, it is
rather difficult to model and analyze each possible interaction at the earlier
design process of a multi-agent model. In fact, multi-agent systems modeling
approach handles this complexity by decomposing the system into smaller and
rather simple autonomous agents. Consequently and based on this feature, there
is no need to define all the possible control reaction and interaction in the sim-
ulated system. Therefore, an autonomous agent in a multi-agent system would
act and update its state according to its own environment and interaction with
the other different agents. Based on this feature, the complexity of the whole
simulated system is reduced [11].

In the literature, PRT is considered as a complex and distributed system [4]. PRT is composed by different interacting actors and a network of complex subsystems that together provide a high level of transportation service. Thus, PRT can be modeled as a network of agents. Agents in PRT would try to maximize their own gain rather than the whole system gain. Each agents would act autonomously by being able to interact with its dynamic environment and taking pro-active and reactive decisions [13]. In this sense, it exists numerous studies that proposed to tackle on-demand transportation systems modeling by the use of a multi-agent system modeling approach.

In [2] [5], authors proposed to model PRT using multi-agents based approach where vehicles act as an independent agents. In [6], authors proposed to use multi-agent simulation approach for the PRT context where stations act as independent agent but without tackling many hard constraints related to PRT such as the limited distance constraints. Other works on PRT includes discrete event simulation [8][9], static energy consumption minimization [7][10], fleet sizing [3], network design [16], and so on. The novelty on our approach is to consider stations as independent agents while taking into account various constraints and limitation related to the PRT vehicles.

## 3.2 The proposed modeling approach

As we proposed to use Multi-agents simulation approach for our PRT system,
one could argue that the driverless vehicles would be used as the only agent types
in our model. However, we used in our model three type of agents: i) Vehicles,
ii) Passengers, iii) Stations.

This different agents would communicate with each other and their own
environment. The passengers agents arrive at specific PRT station and ask to be
transported to another PRT station. Consequently, the passengers agents send
a transportation request to its current departure station. The transportation
request is represented by a triplet: i) Departure station ii) Arrival station iii)
Departure time
This transportation request would be treated by the specific agent that rep-
resents the departure station. In fact, the station agent and based on the trans-
portation demand characteristic would select the best available vehicle agent
available at the departure station based on the total traveled distance and the
available electric battery charge. Consequently, we could consider that the envi-
ronment in our simulated system represents all the information available at the
different nodes of the network.

In the following subsections, the role of each type of agent is explained.

3.3 Vehicle agent

The vehicle agents in our model has four different functions:

- They transport passenger' agents in order to satisfy their transportation requests.

- They interact with the station agents in order to know what passengers request they could satisfy.

- They interact with the specific charging station agent in order to perform charging operation.

- They gather different statistics in order to evaluate the performance of the whole system.

Every vehicle can be in four principal states: waiting empty, moving empty, moving with passengers, charging state.

3.4 Passenger agent

The passenger agent is composed of a set of passengers or an individual one
with the same departure and destination stations, and whose number does not
exceed the capacity of the PRT vehicle in term of number of passengers (e.g.
six passengers). This agent interacts with the station agent in order to inform
it about its related transportation request. Then, after a vehicle agent pick up
the passenger agent it sends a message to the station agent in order to inform
it about its waiting time which would be needed to gather statistics related to
the system.

3.5 Station agent

In our simulation model, the station agents are the most important ones. In
fact, the dispatching decisions related to the PRT system are implemented as
an integral part of the station agents. Thus, the station agents would receive
all the different passengers arriving at their locations. Each station agent would
evaluate the available transportation requests. Based on the current situation of
the system, the station agent would interact with the vehicles agent available at
its location in order to perform the transportation request. The station agent
would choose from the available empty vehicle the best one able to perform the
transportation request. This decision is based on the traveled distance related to the transportation request as well as the available electric energy in the different vehicles. If no empty vehicles are available, the station agent would communicate with the other station agents in order to ask for a specific number of vehicles. For example, if a station agent has four waiting transportation requests that could not be satisfied by the available vehicle agent in the station, it would ask all the other stations agents to send four different empty PRT vehicles. The different other station agents would evaluate the demand and would accept or reject the demand in empty vehicles. In the case of acceptance a conflict could arise if more than one station would satisfy the need of empty vehicles of a specific station agent. In this case, the station agent asking for empty vehicle would accept only the vehicles coming from the closest distance possible. Finally, we should note that periodically the station agent would evaluate the available empty vehicle agent available at its location. If a vehicle has waited empty for too long, it would be sent to the charging location.

Details about PRT station agents are shown in Algorithm 1. We should note that station agents treat the transportation demand based on the principle of first come first serve in order to minimize the total waiting time.

<caption>**Algorithm 1 Station Agent Algorithm()**</caption>

1: **for all** Waiting Passengers $P_i$ in this.CurrentStation **do**
2:     **for all** Waiting empty vehicles $V_i$ in this.CurrentStation **do**
3:         **if** $V_i$.Batterylevel Allows the vehicle to serve $P_i$ **then**
4:             Assign $P_i$ to Vehicle $V_i$
5:             Exit FOR
6:         **end if**
7:     **end for**
8:     **if** $P_i$ isn't satisfied by an empty vehicles **then**
9:         Ask other station agents to send empty vehicle to satisfy $P_i$
10:        Evaluate the offers in term of empty vehicles from the other station agents and assign the best alternative to $P_i$.
11:    **end if**
12: **end for**
13: Evaluate the number of empty vehicles in the station
14: **if** the number of empty waiting vehicles is less than a certain reserve value **then**
15:    Ask other station agents to send empty vehicle to balance the number of waiting empty vehicles
16: **end if**

Finally, we should note from Algorithm 1 that a proactive behavior is implemented as a part of the general behavior of the station agent. In fact, we propose that each station should have a fixed number of empty vehicle waiting for passengers to come in order to reduce the total waiting time of passengers. Periodically and after serving the different waiting passengers, the station agent would look for the number of empty waiting vehicles in its current location and
ask other station agents to send empty vehicles if the station is at a deficit of empty vehicles (e.g. number of empty vehicles is less than the reserve value).

# 4 Computational Results

The proposed simulation model was written in C++ language with the intention of analyzing the proposed decentralized strategy. The written computer program was written with the intention to predict the service level for the system using several statistics related to the waiting time of passenger, consumed energy, etc.

In this section, we present the computational results related to our multi-agent model for the PRT system. For the testing bed, we choose the one from the literature [9]. The testing bed is based on the Corby real use case which represents a realistic PRT network. The network is composed of 15 stations and 4 depots. As we are treating the case of a single depot topology, we proposed to generate four different networks where each one of them contain only one different depot.

As for the simulated scenarios related to the PRT transportation requests, we used scenarios adapted from the literature [4]. More specifically, the generated scenarios are based on the data available in the ATS/CityMobil software<fnref n="1" />. The ATS/CityMobil presents the rates $λ_{ij}$ of a poisson process for traveling from any station *i* to any other station *j* in the Corby network. We should note that $λ_{ij} \in [0.789, 17.902]$. We used in this paper 5 different scenarios. Also, we supposed that the total number of fleet is equal to 200 vehicles. The reserve value related to the number of empty vehicles that should be present in each station is equal to 2 vehicles. We should note that we supposed that the battery would make the vehicles run for 40 minutes before to be needed to recharge it [4]. Results are presented in Table 1. Table 1 presents the percentage of empty movements as well as the full movement (movement of a vehicles with passengers) of the total movement of vehicles in the system. We also present the mean waiting time of passengers for each scenario in minutes (Min). We should note that the waiting time of a passengers is the difference between the arrival time of the passengers to their arrival station and the time of the fulfillment of their demand.

Results shows the good performance of our decentralized strategy as we found a mean waiting time of 3.847 minutes and a mean empty movement of 47.677 % which means that the vehicles move in 47.677 % empty without taking passengers.

# 5 Conclusions

In this study, a multi-agent system model is proposed for the PRT system. Unlike the majority of the previous studies, a decentralized management strategy with complex relationships between the different agents is proposed. This study

<footnote n="1">¹ ATS/CityMobil PRT source: http://www.ultraprt.com/prt/implementation/simulation/</footnote>
<table><caption>Table 1: Results of the proposed strategy</caption><thead><tr><th>Network</th><th>Scenario</th><th>waiting Time in Min</th><th>Empty Movement in %</th><th>Full Movement in %</th></tr></thead><tbody><tr><td>1</td><td>1</td><td>2.552</td><td>37.634</td><td>62.366</td></tr><tr><td>1</td><td>2</td><td>2.920</td><td>38.725</td><td>61.275</td></tr><tr><td>1</td><td>3</td><td>3.145</td><td>40.158</td><td>59.842</td></tr><tr><td>1</td><td>4</td><td>2.931</td><td>41.787</td><td>58.213</td></tr><tr><td>1</td><td>5</td><td>2.827</td><td>40.840</td><td>59.160</td></tr><tr><td>2</td><td>1</td><td>3.286</td><td>43.977</td><td>56.023</td></tr><tr><td>2</td><td>2</td><td>3.891</td><td>44.474</td><td>55.526</td></tr><tr><td>2</td><td>3</td><td>3.610</td><td>43.713</td><td>56.287</td></tr><tr><td>2</td><td>4</td><td>3.981</td><td>47.605</td><td>52.395</td></tr><tr><td>2</td><td>5</td><td>3.816</td><td>46.748</td><td>53.252</td></tr><tr><td>3</td><td>1</td><td>4.338</td><td>54.576</td><td>45.424</td></tr><tr><td>3</td><td>2</td><td>4.599</td><td>52.304</td><td>47.696</td></tr><tr><td>3</td><td>3</td><td>4.039</td><td>51.145</td><td>48.855</td></tr><tr><td>3</td><td>4</td><td>4.478</td><td>52.770</td><td>47.230</td></tr><tr><td>3</td><td>5</td><td>4.750</td><td>55.088</td><td>44.912</td></tr><tr><td>4</td><td>1</td><td>4.143</td><td>51.331</td><td>48.669</td></tr><tr><td>4</td><td>2</td><td>4.770</td><td>51.513</td><td>48.487</td></tr><tr><td>4</td><td>3</td><td>4.634</td><td>53.284</td><td>46.716</td></tr><tr><td>4</td><td>4</td><td>4.295</td><td>53.729</td><td>46.271</td></tr><tr><td>4</td><td>5</td><td>3.936</td><td>52.134</td><td>47.866</td></tr></tbody><tfoot><tr><td colspan="2">Average</td><td>3.847</td><td>47.677</td><td>52.323</td></tr></tfoot></table>

differs from the previous studies for PRT in that it considers stations as an autonomous agent as well as battery issues within a multi-agent simulation model. The validity and reliability of the proposed model are evaluated through simulation experiments by using a real world application related to an urban use case from the United Kingdom.

The next step of this study is to integrate the proposed model within a decision support system related to PRT in order to evaluate the best strategy among many others for the system. In future studies, the effect of other external factors on the performance of the different agents could be studied. Finally, the development of learning algorithms for the stations and vehicles agents could be a promising field of study.

## References

1. Avci, M.G., Selim, H.: A multi-agent system model for supply chains with lateral preventive transshipments: Application in a multi-national automotive supply chain. Computers in Industry 82, 28–39 (2016)

2. Chebbi, O., Chaouachi, J.: Modeling on-demand transit transportation system using an agent-based approach. In: Computer Information Systems and Industrial Management, pp. 316–326. Springer (2015)

3. Chebbi, O., Chaouachi, J.: Optimal fleet sizing of personal rapid transit system. In: Computer Information Systems and Industrial Management, pp. 327–338. Springer (2015)

4. Chebbi, O., Chaouachi, J.: Reducing the wasted transportation capacity of personal rapid transit systems: An integrated model and multi-objective optimization
approach. Transportation Research Part E: Logistics and Transportation Review (2015)

5. Chebbi, O., Chaouachi, J.: A decentralized management approach for on-demand transit transportation system. In: Proceedings of the Second International Afro-European Conference for Industrial Advancement AECIA 2015. pp. 175–184. Springer (2016)

6. Daszczuk, W.B., Mieścicki, J., Grabski, W.: Distributed algorithm for empty vehicles management in personal rapid transit (prt) network. Journal of Advanced Transportation (2016)

7. Fatnassi, E., Chebbi, O., Chaouachi, J.: Discrete honeybee mating optimization algorithm for the routing of battery-operated automated guidance electric vehicles in personal rapid transit systems. Swarm and Evolutionary Computation (2015)

8. Fatnassi, E., Chebbi, O., Siala, J.C.: Evaluation of different vehicle management strategies for the personal rapid transit system. In: Modeling, Simulation and Applied Optimization (ICMSAO), 2013 5th International Conference on. pp. 1–5. IEEE (2013)

9. Fatnassi, E., Chebbi, O., Siala, J.C.: Two strategies for real time empty vehicle redistribution for the personal rapid transit system. In: Intelligent Transportation Systems-(ITSC), 2013 16th International IEEE Conference on. pp. 1888–1893. IEEE (2013)

10. Fatnassi, E., Chebbi, O., Siala, J.C.: Comparison of two mathematical formulations for the offline routing of personal rapid transit system vehicles. In: Methods and Models in Automation and Robotics (MMAR), 2014 19th International Conference On. pp. 554–559. IEEE (2014)

11. Jennings, N.R.: On agent-based software engineering. Artificial Intelligence 117(2), 277 – 296 (2000), http://www.sciencedirect.com/science/article/pii/S0004370299001071

12. Lees-Miller, J.D.: Empty vehicle redistribution for personal rapid transit. Ph.D. thesis, Liverpool John Moores University (2011)

13. Moyaux, T., Chaib-Draa, B., D'Amours, S.: Supply chain management and multiagent systems: an overview. In: Multiagent based supply chain management, pp. 1–27. Springer (2006)

14. Mueller, K., Sgouridis, S.P.: Simulation-based analysis of personal rapid transit systems: service and energy performance assessment of the masdar city prt case. Journal of Advanced Transportation 45(4), 252–270 (2011)

15. Wen, G., Zhao, Y., Duan, Z., Yu, W., Chen, G.: Containment of higher-order multi-leader multi-agent systems: a dynamic output approach. IEEE Transactions on Automatic Control 61(4), 1135–1140 (2016)

16. Zheng, H., Peeta, S.: Network design for personal rapid transit under transit-oriented development. Transportation Research Part C: Emerging Technologies 55, 351–362 (2015)