# Modeling On-demand Transit Transportation System Using an Agent-Based Approach

Olfa Chebbi, Jouhaina Chaouachi

► To cite this version:

Olfa Chebbi, Jouhaina Chaouachi. Modeling On-demand Transit Transportation System Using an Agent-Based Approach. 14th Computer Information Systems and Industrial Management (CISIM), Sep 2015, Warsaw, Poland. pp.316-326, 10.1007/978-3-319-24369-6_26. hal-01444475

HAL Id: hal-01444475

https://inria.hal.science/hal-01444475v1

Submitted on 24 Jan 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 CC BY 4.0 - Attribution - International License
Modeling on-demand Transit Transportation
System using an Agent-based Approach

Olfa Chebbi¹ and Jouhaina Chaouachi²

¹ Institut Supérieur de Gestion de Tunis
Université de Tunis

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

² Institut des Hautes Etudes Commerciales de Carthage
Université de Carthage

IHEC Carthage Présidence-2016 Tunis, Tunisie

**Abstract.** We consider the real-time routing of driverless vehicles in an on-demand transit transportation system with time window. Because fast dispatching decisions are required, decentralized decisions system are generally used in these contexts. For that purpose, we introduce a new multi agent-based simulation model where intelligent vehicle agents determine their specific routes and which transportation requests to serve. They interact with passengers, who strive for minimum waiting time. Our approach offers several advantages: it is fast, make it easy for vehicles to determine their specific routes and needs little information for vehicles. We propose also a specific algorithm for the independent vehicles'agent in order to determine their specific routes. Preliminaries computational tests of our multi-agent model and our developed algorithm prove that our approach is very promising.

**Keywords:** On-demand Transit Transportation System; Public Transportation; Simulation; Multi-agent systems

# 1 Introduction

## 1.1 Simulation context

Transportation tools are in general very complex systems that are intertwined with technology. They consist mainly of several decisions that involves different entities such as vehicles, passengers, etc. These systems are generally also the subjects of several decisions and different policies that affect their operational behavior and level of service. Decisions makers related to these complex systems are often faced with the dilemma of exploring the different effect of their long lasting strategic decisions without to actually implement them. That is why, policies makers, scientists and analysts would use distinctive approaches to understand the system under study. These approaches include benchmarking, historical analysis [12], computational modeling and **simulation**[4]. Indeed, these approaches are very useful in order to find effective policies for managing complex transportation systems.
Simulation program is mainly developed to imitate and shows the operation of a specific system over and how it evolves. In the literature, there exists different simulation approaches. We could note for instance discrete event simulation, dynamic system, etc. However, there exists one specific simulation approach that has the ability to study complex systems at the level of individual behavior. This approach is named the agent-based modeling and simulation (ABMS).

## 1.2 Background of the paper

On the other hand, due to the huge advance in computers, robotic, communication, control, location, information, sensors, and artificial intelligence, we have observed a growth in the development of intelligent transportation systems (ITS). ITS is generally a term used to define complex systems to improve transportation and drivers experience. Examples and applications of ITS include the in-vehicle eCall [5], collision avoidance systems, dynamic traffic light sequence, Personal Rapid Transit (PRT), etc.

A specific focus could be given to the PRT system. PRT have emerged as a very effective and intelligent transportation system. PRT is a concept a personalized urban mass transit system. PRT can be seen as the combination of individualized passengers transportation tool and mass public transit transportation mean. In fact, PRT use small electric driverless vehicles that could take from one to six passengers. PRT have been introduced to many urban contexts such as the Heathrow airport London UK, Morgan town West Virginia USA, Masdar City Abu Dhabi UAE, etc. PRT is seen as an efficient and sustainable transportation tool which has the ability to bring a new insight to the way that people are moved in cities. However, PRT literature is at its infancy.

## 1.3 Related literature

For managerial aspects, there exists a few studies that tackled the PRT system. One could note network design [13], station locations [14], fleet size [8], the waiting time for passengers [6], [3] and energy consumption [10], [9]. As for simulation, many simulation approaches have been developed to simulate PRT system [1]. **However, these models does not tackle battery issues for the PRT electric vehicles.** Batteries for PRT represents an important feature as they provide energy supplies for the system and need to be periodically charged in specific locations. Simulation model that developed battery issues for PRT was developed by Mueller and Sgouridis [11]. **However, they used discrete event simulation approach to model the PRT system.** According to us, ABMS requires a specific attention in the PRT literature due to its huge ability to simulate the PRT'vehicles behavior. In fact as the PRT vehicles are driverless, agent based simulation represents the perfect tool to model efficiently how the PRT vehicles are operated in this system.
**1.4 Contributions Of the paper**

Starting from the statements that the PRT system deserves a more decentralized
management approach and the related simulation literature to PRT have been
focused on discrete event simulation, we:

1. Define a Multi Agent simulation model for simulating PRT systems.

2. Suggest a decentralized management strategy to solve the problem of managing driverless vehicles in PRT systems.

3. Validate our model on data sets generated following a field study in the case study of Corby in the United Kingdom.

**1.5 Outlines of the paper**

The structure of this paper is as follows. In Section 2, we present briefly the PRT system. In Section 3, we present our problem definition. Section 4 explains the model-driven development process for simulating PRT system. In Section 5, we present results and analysis of our simulation model. Finally, Section 6 concludes and gives directions for future research.

**2 The Personal Rapid Transit System**

Personal rapid transit (PRT) is an automated transit system in which small vehicles move to transport small number of passengers on demand to their desired destinations. Transportation service in PRT is done by means of non-transfer, nonstop and on its own right-of-way. PRT vehicles (also called pods) run on exclusive small tracks also called guideways.

The guideways are designed as elevated facilities above the ground, for pur-
pose of eliminating at-grade crossings or interferences with other transportation
modes.

A PRT system offers a taxi-like transportation service. In fact in PRT, users
are served only on demand. There isn't any predetermined schedule for PRT as
by other conventional mass transportation system such as bus or train. More
specifically, the transportation service is done as follow: at PRT station, a pas-
senger or a group of passengers first select the desired PRT destination station.
Then, the control system dispatch a specific PRT vehicle to the station to take
the passenger of the group of passengers to their desired destination. Transporta-
tion service in PRT is done without any intermediate stops. In fact, PRT stations
are placed offline. This feature allows PRT vehicles to embark/disembark passen-
gers on auxiliary guideways without interfering with the vehicles movements on
the main line. Consequently, PRT vehicles could move without any unnecessary
stops at intermediate stations.

Due to the latest advances in technology and robotics, PRT vehicles are
electric and are under computer control. Therefore, PRT vehicles don't need a
human driver. The size of a PRT vehicle can accommodate one to six passengers
in general. PRT systems was developed in several real world applications recently,
including in Korea, Sweden, London and United Arab Emirates.
## 2.1 Related PRT Literature

In recent decades, different microsimulators have been developed to model the behavior of individuals and automated vehicles. One could note the PRT International (USA)<fnref n="3" />, RUF International (Denmark)<fnref n="4" /> TrakEdit: PRT Simulator from Taxi 2000 (USA)<fnref n="5" />, Mueller and Sgouridis PRT simulator in 2011 [11], etc. More details about PRT simulators are given in [1].

However, what is missing in the literature is a powerful agent based simulator that could take into account different characteristics of the PRT systems in terms of battery management, dispatching decisions and route choice. Mainly, the main difference that battery vehicles bring is the additional movement for the vehicles to charge their battery in the specific charging locations. One should note also that routing and dispatching decisions for PRT vehicles follows strictly central control system decisions. These decisions concern specifically the empty vehicle management (EVM). EVM is a specific control function that has big influence on the routing and dispatching of empty PRT movement. In fact, the empty vehicles flows in station need to be balanced between inbound and outbound flows. Using agent based simulation approach has the possibility to offer a more decentralized control option for PRT system and therefore, bring new insight into PRT management options.

# 3 Problem definition of Distance Minimization and Waiting Time of PRT with multi-agent system

In this section, we present the formal problem definition to be treated in this work.

Within the PRT transportation system network $N$, passengers arrive at stations and ask the PRT system in order to request to carry them from their specific departure PRT station origin to a specific PRT destination station. $N$ is composed by a set of $M$ stations and one depot station. Passengers arrive in each station following a poisson process of rate $\lambda$. Transportation requests should be done immediately and served as soon as possible. No rejection is allowed. PRT system satisfy the transportation requests using a set of electric PRT vehicles. The vehicles are supposed to have a limited battery capacity denoted by $B$. We consider also to have a specific cost matrix that defines the cost of moving between each couple of stations. All vehicles are supposed to be initially located at the depot. Vehicles charging operations are supposed to be done only in the depot. In this paper, the vehicles are supposed to be autonomous. A dispatching decisions refer to assigning a vehicle to a specific transportation request. The dispatch decisions in a PRT system must be decided quickly and as soon as the passenger requests are received. This ensures a reduced waiting time for passengers and therefore a high quality of service. However, the decision of dispatching a

<footnote n="3">³ www.prtnz.com</footnote>

<footnote n="4">⁴ http://www.ruf.dk/</footnote>

<footnote n="5">⁵ http://www.taxi2000.com/</footnote>
vehicle to a specific transportation request requires all the current PRT'network
data. That is why the dispatching decisions should be made while evaluating all
the possible dispatching alternatives in order to optimize the vehicle behavior
and the overall system performance.

The information of the coming of the passengers is known gradually as the PRT system serves its passengers. This is the most crucial point in assigning vehicles to transportation requests because the limited battery capacity don't allow the vehicles to serve all the transportation requests. Therefore, a limit is imposed on the PRT vehicles while traveling a route to serve passengers.

**3.1 Objectives**

The following two objectives have to be achieved in regard to the problem context
formulated above.

1. On the one hand, a minimization of travel and transportation costs has to be faced. This objective can be subdivided into the sub-objectives of minimizing travel distances and minimizing the number of vehicles in use. Concerning travel distance, this objective could be reached by minimizing the total empty movement for PRT vehicles as the distance of satisfying transportation request is considered as a fixed cost. Whereas the evaluation of the needed number of PRT pods could be more complicated as it is pre-defined and related to the strategic level of decisions of PRT system. However, one should note that saving in the exact number of used vehicles in a pre-optimization step could offer a high flexibility to the system. In fact, as we could save in the exact number of used vehicles, the system could enhance its customer service as more free vehicles would be available.

2. On the other hand, a maximization of customer satisfaction has to be addressed by the minimization of the total waiting time of passengers. The focus in this contribution is, besides the minimization of travel cost, on the maximization of customer satisfaction by the minimization of the total waiting time of passengers.

4 The proposed simulation model

In the following subsections, we will first describe the used simulation software.
Then, we describe the developed PRT simulation model.

**4.1 The used simulation software**

Different simulation software was evaluated in order to develop our multi agent
simulation model for the PRT system. Among evaluated software we could note
Entreprise dynamics<sup>6</sup>, Jadex<sup>7</sup>, etc. Our decision was made in favor of the Any-

<footnote n="6">⁶ Source: http://www.incontrolsim.com/enterprise-dynamics/enterprise-dynamics.html</footnote>

<footnote n="7">⁷ Source: http://www.activecomponents.org/bin/view/AC+Tool+Guide/09+Simulation+Control</footnote>
logic software<fnref n="8" />. The Anylogic is a java based simulation software. It offers the advantages of combining three major simulation methodologies: Discrete event simulation; System Dynamic and Agent based simulation. The Anylogic offers modular and hierarchical modeling of complex models. The Anylogic provides also different tools such as diverse library which helps users to better build their models. This software offers also the possibility to work with action chart, state chart and a huge number of statistics tools. This makes possible for any developed simulation model to evaluate their output using the different built-in statistical tools.

## 4.2 Agent based simulation for modeling trips in PRT system

To have a specific simulation model that allows us to model all the designs of a single trips, we choose agent based modeling using the Anylogic simulation software. Intuitively, the PRT vehicles are the only agents that need to be represented in our model. However, we used in our model two types of agents:

1. PRT vehicles are the agents representing the fleet of vehicles in the PRT system. The number of these agents is determined by the strategic decisions related to PRT system.

2. Passengers represent the specified users of the PRT system.

These different agents developed in this works are considered as the perceptive entities having the ability to think, take decisions and react according to the current situation of the system. The PRT vehicles mainly achieves four main functions:

1. Passengers' transportation and Request satisfaction,

2. Charging operation,

3. Collecting travel statistics.

The passengers' agents mainly imitate the passengers' behavior. Each PRT vehicle day begins in the depot. The passengers' transportation demands will trigger a series of events and make the vehicle agents' properties and behaviors change. For a single trip, the PRT' passengers customer ask to be transported from their specific station to their destination station. A vehicle agent takes the request and handles it according to the principle of Close first. This means that the empty vehicle available in the station of the passengers will handle the transportation request. If there is more than one empty vehicle in the station of the transportation request, the vehicle agent with the high level of energy in its battery will handle the transportation request. Otherwise, if there isn't any vehicle in the station of the transportation request, the closest empty vehicle to this location will be assigned to serve the specific trip. Details about PRT' vehicle behavior are shown in Algorithm 1. We should note also that if a vehicle agent finished serving a transportation request and there isn't any passengers waiting to be transported a principle of first come first serve is applied to serve transportation requests in others stations in the network.

<footnote n="8">⁸ Source: www.anylogic.com/</footnote>
<caption>**Algorithm 1 Algorithm of a Agent Vehicle()**</caption>

1: **if** CurrentState=Waiting **then**
2:   **for all** Waiting Passengers $P_i$ in this.CurrentStation **do**
3:     **if** this.Batterylevel Allows the vehicle to serve $P_i$ **then**
4:       Assign $P_i$ to Vehicle
5:       Exit FOR
6:     **end if**
7:   **end for**
8: **end if**
9: **if** CurrentState=Waiting **then**
10:   MinDistance=Big-M.
11:   AffectedPassenger=NULL.
12:   **for all** Waiting Passengers $P_i$ in the PRT network **do**
13:     **if** this.Batterylevel Allows the vehicle to serve $P_i$ and $P_i$ isn't in the current station of the vehicle **then**
14:     MinDistance= Distance Between Current Station of Vehicle and the current station of $P_i$
15:   AffectedPassenger=$P_i$
16: **end if**
17: **end for**
18: **if** not (AffectedPassenger == NULL) **then**
19:   Assign $P_i$ to Vehicle
20: **end if**
21: **end if**

After the vehicle agent successfully deals with a transportation request, its level of energy in its battery is updated. The vehicle will begin to check its battery'energy level as soon as it successfully deals with an order. If it found that its level of energy is less or equal to the energy needed to returning to the depot in addition to a specific reserve value, the vehicle will then go back to its depot station to charge its battery. The passengers' agent mainly simulates the behavior of actual PRT users in stations. They also simulate the process of asking for a PRT'vehicle in order to study its behavior.

## 5 Computational Results

In this section, we report the computational results obtained for testing the multi agent simulation model for the PRT system. As for the network configuration, **we used the Corby use case which represents a real PRT network [2]** (see Figure 1). This configuration is based on a multiple depots shape. As we supposed in our works to have a single depot network topology,**we generated 4 different networks while taken into consideration only one depot.**

As for PRT' transportation requests, we used carefully generated scenarios based on the already developed PRT works [7] [6]. More specifically to obtain the different scenarios, traveling requests from any station *i* to station *j* were generated according to a Poisson process with rate $\lambda_{ij} \in [0.789, 17.902]$. These
<figure><img src="image_2.png" /><figcaption>Fig. 1: The Corby network</figcaption></figure>

rates are publicly available and are given the ATS/CityMobil software<fnref n="9" />. For each
tested network, we used 5 different generated scenarios. In our simulation
tests, we supposed to have 200 as a PRT' fleet size. The battery capacity
was taken as 40 minutes [10]. The reserve parameter(Algorithm 1) was supposed
to be equal to be the tenth of the total battery capacity of the PRT vehicles. The
results are shown in Table 1. The estimated wasted energy as well as effective
energy are reported in Table 1. We report also for each scenario the average
waiting time for passengers. Wasted energy denotes the energy used for the
empty movements of vehicles. Waiting Time of passengers denotes the difference
in time between the rise of the demand and the fulfillment of this demand. To
interpret this huge number of results, we conduct correlation analysis. We used
the Multiple Pearson correlation tests to understand the effects of the design
parameters in general. This latter includes the effects of network configuration,
scenarios and their interactions. The effects of some of the studied parameters
are intuitive and have already been reported in the literature.

<footnote n="9">⁹ ATS/CityMobil PRT source: http://www.ultraprt.com/prt/implementation/simulation/</footnote>
<table><caption>Table 1: Computational Results of our Multi-Agent Decentralized Strategy</caption><thead><tr><th>Scenario</th><th>Network Wasted Energy in % Effective Energy in % Average Waiting Time in Seconds</th></tr></thead><tbody><tr><td>1</td><td>D1 20.434 79.566 937.078</td></tr><tr><td>2</td><td>D1 34.943 65.057 700.699</td></tr><tr><td>3</td><td>D1 34.855 65.145 755.855</td></tr><tr><td>4</td><td>D1 35.187 64.813 773.932</td></tr><tr><td>5</td><td>D1 31.645 68.355 578.453</td></tr><tr><td>6</td><td>D2 34.708 65.292 747.547</td></tr><tr><td>7</td><td>D2 38.511 61.489 683.355</td></tr><tr><td>8</td><td>D2 40.369 59.631 754.456</td></tr><tr><td>9</td><td>D2 39.016 60.984 859.082</td></tr><tr><td>10</td><td>D2 39.902 60.098 786.457</td></tr><tr><td>11</td><td>D3 40.438 59.562 280.051</td></tr><tr><td>12</td><td>D3 35.191 64.809 256.676</td></tr><tr><td>13</td><td>D3 35.874 64.126 297.712</td></tr><tr><td>14</td><td>D3 41.846 58.154 403.273</td></tr><tr><td>15</td><td>D3 36.660 63.340 262.621</td></tr><tr><td>16</td><td>D4 37.040 62.960 822.613</td></tr><tr><td>17</td><td>D4 40.949 59.051 780.078</td></tr><tr><td>18</td><td>D4 42.119 57.881 752.612</td></tr><tr><td>19</td><td>D4 35.836 64.164 797.523</td></tr><tr><td>20</td><td>D4 38.879 61.121 748.360</td></tr><tr><td>Average</td><td>36.720 63.280 648.922</td></tr></tbody></table>

In order to determine the design parameters that have the most significant effect on the wasted energy, multiple correlation Pearson tests was performed using GraphPad software<fnref n="10" />. Tables 2, 3 represent the resultant Pearson outcomes for the wasted energy and average waiting time. Values

<table><caption>Table 2: Results of the Correlation tests Related To The Scenario</caption><thead><tr><th>Statistic</th><th>Scenario vs. Wasted Energy</th><th>Scenario vs. Average Waiting Time in Seconds</th></tr></thead><tbody><tr><td>Pearson r</td><td></td><td></td></tr><tr><td>r</td><td>0.5752</td><td>-0.2055</td></tr><tr><td>95% confidence interval</td><td>0.1778 to 0.8113</td><td>-0.5941 to 0.2608</td></tr><tr><td>R square</td><td>0.3308</td><td>0.04225</td></tr><tr><td>P value</td><td></td><td></td></tr><tr><td>P-value (two-tailed)</td><td>0.008</td><td>0.3846</td></tr><tr><td>Significant? (alpha = 0.05)</td><td>Yes</td><td>No</td></tr></tbody></table>

The multiple Pearson tests' results indicate that all main the two-way interactions are significant at a level of significance of 0.05 for the wasted energy. On the other hand, most of waiting time of passengers interactions are not significant. This significance of the two-way interactions for the wasted energy proves that the network topology and the scenario factors are interrelated. This proves the importance of the different strategic decisions on our PRT system. In the other hand, these factors have no real significant impact on the waiting time of passengers. Explaining the effects of the network topology on the wasted energy

<footnote n="10">¹⁰ more details about GraphPad software could be found in http://www.graphpad.com/</footnote>
<table><caption>Table 3: Results of the Correlation tests Related To The Network</caption><thead><tr><th>Statistic</th><th>Network vs. Wasted Energy</th><th>Network vs. Average Waiting Time in Seconds</th></tr></thead><tbody><tr><td>Pearson r</td><td></td><td></td></tr><tr><td>r</td><td>0.5332</td><td>-0.1949</td></tr><tr><td>95% confidence interval</td><td>0.1186 to 0.7895</td><td>-0.5869 to 0.2711</td></tr><tr><td>R square</td><td>0.2843</td><td>0.03798</td></tr><tr><td>P value</td><td></td><td></td></tr><tr><td>P-value (two-tailed)</td><td>0.0155</td><td>0.4103</td></tr><tr><td>Significant? (alpha = 0.05)</td><td>Yes</td><td>No</td></tr></tbody></table>

is simple and straightforward. An increase in the average distance between the depot and the different stations should be directly translated to an increase in the travel distance.

# 6 Conclusion and Future Research Directions

In this paper, we introduced a new Agent based simulation model for modeling PRT system. Based on agent method, this paper describes the PRT dispatching system simulation model using AnyLogic software. In this model the customers' demand can't be estimated ahead. That is why, it was important to consider specific rules for the different agent in order to reduce total traveled distance and waiting time of passengers. Simulation experiment verifies the exactness of this model and concludes that our simulation model by considering vehicles as autonomous agent is a powerful approach to model and optimize the PRT system. Extension to our work includes developing enhanced routing policies for the PRT system based on this model.

# References

1. Anderson, J.E.: Some history of prt simulation programs (2007)

2. Bly, P., Teychenne, P.: Three financial and socio-economic assessments of a personal rapid transit system. In: Proceedings of the tenth international conference on automated people movers. p. 39 (2005)

3. Daszczuk, W.B., Choromański, W., Mieścicki, J., Grabski, W.: Empty vehicles management as a method for reducing passenger waiting time in personal rapid transit networks. IET Intelligent Transport Systems (February 2014), http://digital-library.theiet.org/content/journals/10.1049/iet-its.2013.0084

4. Gilbert, N.: Agent-based social simulation: dealing with complexity. The Complex Systems Network of Excellence 9(25), 1–14 (2004)

5. Kohn, A.: The ecall program: Overview and design considerations (2010)

6. Lees-Miller, J.D.: Minimising average passenger waiting time in personal rapid transit systems. Annals of Operations Research pp. 1–20 (2013)

7. Lees-Miller, J.D., Wilson, R.E.: Sampling for personal rapid transit empty vehicle redistribution. Transportation Research Record: Journal of the Transportation Research Board 2216, 174–181 (2011), http://dx.doi.org/10.3141/2216-19

8. Li, J., Chen, Y.S., Li, H., Andreasson, I., van Zuylen, H.: Optimizing the fleet size of a Personal Rapid Transit system: A case study in port of Rotterdam. In: International Conference on Intelligent Transportation. pp. 301–305 (2010)
9. Mrad, M., Chebbi, O., Labidi, M., Louly, M.: Synchronous routing for personal rapid transit pods. J. Applied Mathematics 2014 (2014), http://dx.doi.org/10.1155/2014/623849

10. Mrad, M., Hidri, L.: Optimal consumed electric energy while sequencing vehicle trips in a personal rapid transit transportation system. Computers & Industrial Engineering 79, 1-9 (2015), http://dx.doi.org/10.1016/j.cie.2014.09.002

11. 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), http://dx.doi.org/10.1002/atr.158

12. Scharpf, F.W.: Games real actors play: Actor-centered institutionalism in policy research, vol. 1997. Westview Press Boulder, CO (1997)

13. Won, J.M., Lee, K.M., Lee, J.S., Karray, F.: Guideway network design of personal rapid transit system: A multiobjective genetic algorithm approach. 2006 Ieee Congress on Evolutionary Computation, Vols 1-6 (2006)

14. Won, J.M., Choe, H., Karray, F.: Optimal design of personal rapid transit. In: Intelligent Transportation Systems Conference. pp. 1489-1494 (Sep 2006), http://dx.doi.org/10.1109/ITSC.2006.1707434