# Optimal Fleet Sizing of Personal Rapid Transit System

Olfa Chebbi, Jouhaina Chaouachi

► To cite this version:

Olfa Chebbi, Jouhaina Chaouachi. Optimal Fleet Sizing of Personal Rapid Transit System. 14th Computer Information Systems and Industrial Management (CISIM), Sep 2015, Warsaw, Poland. pp.327-338, 10.1007/978-3-319-24369-6_27. hal-01444476

HAL Id: hal-01444476

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

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 Attribution 4.0 International License
# Optimal fleet sizing of Personal Rapid Transit system

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.** In this paper, we address the problem of determining the optimal fleet size for Personal Rapid Transit system(PRT). In our problem, we consider electric battery and distance constraints which are found in real world application of the PRT system. To tackle this problem, we propose two valid mathematical formulations that are able to find optimal fleet size. Extensive computational experiments show that the edge based formulation performs impressively well, in terms of solution quality and computational time in comparison to the node based formulation.

**Keywords:** Personal Rapid Transit, Public Transportation, Fleet-sizing, Vehicle Routing Problem

# 1 Introduction

## 1.1 Background

Private vehicles automobile are highly successful as a private transportation tool around the world. In fact, private vehicles provide their users with a nearly unlimited mobility option. Those who own and operate a vehicle could go almost anywhere. Private vehicles offer the advantage of offering an on-demand transportation service 24 hours a day between any origins and destinations in a predefined urban area. However, the increase in the use of private automobile has brought many environmental and social disadvantages. Among these, we could consider congestion, deaths and injuries, air pollution, increasing rate of carbon emissions and the continuing need for more roads, etc. Private vehicles are also responsible for a high percentage of the world's energy and oil usage. This results on a high pressure on the world petrol reserve and in an increase in the oil 'prices. We should note also that public transportation tools in cities such as buses and trains are losing ridership for many years. In fact, those public transportation tools offer a non-flexible transportation option where users need to adapt their transportation needs to a fixed non flexible schedule and routes. The latter results on small use' rate of public transportation tool. That is why
an increasing attention was focused on providing a viable public transportation system to urban areas that could replace private vehicles. Much attention in the United States and the European Union is being focused on the development of Personal Rapid Transit (PRT) systems. PRT is a class of automated fixed-guideway transit systems. Transportation service in PRT is provided by a set of small electric driverless vehicles (see Figure 1). PRT vehicles (also called pods) could take from one to six passengers. PRT' vehicles offers a set of auto-like characteristics (comfort, privacy, speed, etc). These features make PRT a viable alternative to the use of private automobile while being a public transportation system. PRT vehicles runs on a dedicated network of private guideways with stations positioned off the mainline. PRT' networks involves many guideways and closely spaced PRT' stations. This involves easy access of passengers to the PRT vehicles. Various descriptions and definitions of PRT are provided in the literature. Nowadays, there is general unanimity among PRT experts that there are five key characteristics that defines any PRT systems [1]:

1. On-demand, origin-to-destination service: transportation service in PRT is done on demand directly from an origin station to a destination station without any intermediate stops This is done through the specific topology of the PRT network that include offline stations which permit this feature.

2. Small, fully automated vehicles: PRT vehicles are driverless and small. As no driver is needed for a PRT system, a reduced operational cost in comparison with traditional transportation service is obtained.

3. Small, exclusive-use guideways: As the PRT vehicles are small, a use of small guideway is possible. This engenders a small construction costs for a PRT network. Network of PRT is exclusive to the PRT pods. This helps to relieve congestion on the roads.

4. Off-line stations: This feature is one of the unique characteristics of PRT. In fact, stations are located on the sideline. It permits vehicles that don't need to stop at a specific station to by pass-it towards its destination. This results on a short transportation time.

5. A network of fully connected guideways: The network of PRT is fully connected. This feature allow any vehicles to go from any station to any another stations.

The PRT transportation mode has been first introduced in 1953. Nowadays there is different real implementation of PRT around the world. We could note the Heathrow Airport PRT, London UK, the Morgantown PRT, West Virginia, US or the Masdar City PRT, Abu Dhabi, UAE. Unfortunately, the transportation literature related to PRT is at early stages. Special focus was put on the feasibility of PRT system and only recently there were focus on strategic and operational issues related to PRT [2]; [3].

<footnote n="3">³ source:http://www.vincentabry.com/wp-content/uploads/2011/09/Personal-Rapid-Transit.jpg</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1: An Example of PRT Vehicle ³</figcaption></figure>

## 1.2 Objectives of The paper

This paper focuses on a specific related problem to the strategic level of decisions. More specifically, we aim to treat the problem of fleet sizing of a PRT system under battery constraints. The fleet sizing is a really important problem for PRT. In fact, if the fleet size for PRT is large enough, small waiting time for passengers could be reached as passengers will always find empty vehicles available at stations. This engenders a high operational level for such an intelligent system. However, for real case and for rush hours, the fleet size of PRT is mainly subject to different constraints such as financial constraints which don't allow having a perfect zero waiting time for passengers. More specifically, in practice, for high peak demand, the fleet size is subject to financial constraints and will not be so large that all passengers can have zero waiting time. In fact, driverless PRT vehicles are expensive. The investment of purchasing PRT vehicles contributes mainly to the total investment of building PRT system. We could note for instance that purchasing' vehicles contributes on about 10% of the total investment of a PRT system [5].

That is why, optimizing of the fleet size of a PRT system is of a high importance for any PRT system. To the best of our knowledge, this problem was treated only by Li Jie [6]. However, their work doesn't consider battery constraints of PRT vehicles. Battery constraints involve that vehicles would be unavailable for serving passengers as they needs to periodically charge their battery. This could result on a pressure on the fleet of PRT vehicles in order to offers a high level of operational service.

To do so, we study in this paper a relative routing problem related to PRT in order to give decision related to the PRT' fleet size. We aim at our problem by minimizing the total number of used vehicles while respecting the battery capacity of the PRT vehicles.

To the best of our knowledge, there is no significant contribution in the literature to address the above PRT presented problem. In this paper to tackle
the considered problem, we propose as a first step two valid mathematical for-
mulations for solving our problem. Studying the performance of different valid
mathematical formulations for our problem is of a high interest in order to
perceive the general structure of the problem under study. The proposed for-
mulations differs in term of defining the decisions variables. The proposed two
valid mathematical formulations are numerically shown to be efficient to address
small instances size for the treated problem.

**1.3 Motivation of the Paper and Related Literature**

Comparing valid mathematical formulations is of a high interest while studying
new problems as the one treated in this paper. In fact as Demir and Isleyen state
[7], "*although mathematical programming formulation is not efficient solution
method due to the NP-hard structure of routing and combinatorial problems,
it is considered as a first step prior to developing an effective heuristics and
useful to understand the structure of the problem*" [7]. That is why scientists
should be aware of the relative efficiency of routing models through studying the
performance of valid mathematical formulations.

In the literature, several papers proposed to compare mathematical formu-
lation for various problems. Kara [8] studied to compare two mathematical for-
mulations for distance constrained vehicle routing problem (DCVRP). Fatnassi
et al. [9] proposed to compare two valid mathematical formulations for the PRT
case to minimize total traveled distance. Blazewichz et al. [10] proposed to study
mathematical models for single-machine, parallel-machine and job shop schedul-
ing problems. Focus on mathematical models for scheduling problems. Pan [11]
proposed to compare mathematical formulations for both job-shop and flow-shop
scheduling problems. Keha et al. [12] provided a comparison of various mixed
integer linear programming (MILP) formulations for single machine scheduling
problems. Other works on comparison between mathematical formulations for
combinatorial problems include the works of Pan and Chen [13], Unlu and Mason
[14],etc.

As presented above various survey papers have appeared on mathematical
programming formulations for scheduling problems over the years. But in our
search, only two papers focused on mathematical formulations for routing prob-
lems. The exceptions are the papers presented by Kara [8] and Fatnassi et al.
[9]. They developed an integer linear programming model for DCVRP in order
to minimize the total traveled distance.

In this paper, literatures related to routing problems are investigated in order
to look for similarities between the proposed problem related to PRT and other
works in the literature. By assuming the objective function is to reduce the fleet
size of PRT vehicles, computational efficiency of the proposed two mathematical
formulations models is compared and analyzed.

**1.4 Contributions of The paper**

The contributions of this paper are several:
1. We propose a relative problem to the strategic level of decision for PRT system to reduce and minimize the use of PRT vehicles.

2. We propose two valid mathematical formulations to tackle our proposed problem.

3. We compare the efficiency of our two formulations in term of solution quality and computational effort through various analysis and statistical test.

## 1.5 Outline of The paper

The remainder of this paper is organized as follows: in Section 2, problem definition of minimizing fleet size of PRT and notation of models are presented. In Section 3, a valid road based formulation is proposed. Sections 4 and 5 describe the two mathematical formulations for the proposed problem. In Section 6, computational results of models compared. Finally the conclusions of study are drawn in section 7.

# 2 Problem definition

In this section, we present the problem definition as presented in [3],[15].
Let us consider a network of PRT N that contains

- a set of stations $S = \{s_1, s_2, ..., s_M\}$ of cardinality $M$.

- one depot $D$.

- We suppose also that the network $N$ ensures connectivity constraints. This is possible by having enough guideways that make possible to reach any PRT station from any another one.

- We suppose also that a set of electric battery powered vehicles ensure the transportation service within the PRT network.

- Each vehicle have a limited electric battery capacity $B$.

In this paper, we treat the problem of fleet sizing in a static deterministic context. For that purpose, we suppose to have a deterministic list of trips (calendar or schedule) $T = \{1, 2, ..., n\}$ has to be performed. Each trip $i \in T$ is characterized by :

- $Dt_i$: the departure time of trip $i$.

- $Ds_i \in S$: the departure station of trip $i$.

- $At_i$: the arrival time of trip $i$.

- $As_i \in S$: the arrival station of trip $i$.

We suppose that the transportation service is done under the following assumptions:

- An unlimited number of PRT vehicles are available in the depot to guarantee all the trips. The exact number of vehicles needed will be the objective of our problem.

- The charging Operation of the batteries could be done only in the depot.
- The consumed energy for a vehicle from the depot visiting some stations in $N$ and returning to the depot, must never exceed $B$

- We relax time needed to load and unload passengers at PRT stations.

- We suppose that the transportation move between any couple of stations is done following the shortest path. The cost of the shortest path between any pairs of stations is defined by the cost matrix $sp$. The shortest paths between all stations could be determined by using the Floyd Warshall algorithm [16].

The objective of our problem is to assign the trips to vehicles in order to reduce the number of used PRT vehicles. For that purpose, three linear programming formulations are presented based on specific network representation.

Let $G = (V, E)$ be a graph, with $V$ the set of nodes and $E$ the set of the arcs. Each trip $i$ is represented by a node, in addition of two dummy nodes $s$ and $t$, thus $V = T \cup \{s, t\}$. $V^* = V \setminus \{s, t\}$. The set of the arcs $E$ is defined as follows.

- If $i, j \in T$ such that $At_i + Sp_{(As_i, Ds_j)} \le Dt_j$ then we add an arc $(i, j)$ with cost $c_{ij}$, representing the required electric energy to move from arrival station $As_i$ of trip $i$ to depart station $Ds_j$ of trip $j$ in addition to the required electric energy to move from depart station $Ds_j$ to the arrival station $As_j$ of trip $j$.

- for each node $i$ we add an arc $(s, i)$ and the cost of this arc is $c_{si}$, representing the consumed electric energy to reach the arrival station $As_i$ of trip $i$ from the depot while passing through its departure station $Ds_i$.

- for each node $i$ we add an arc $(i, t)$ with cost $c_{it}$, representing the electric energy used to move from the arrival station $As_i$ of trip $i$ to the depot.

From this graph representation, we can see that our problem is similar to the asymmetric distance-constrained vehicle routing problem (ADCVRP). The distance-constrained vehicle routing problem is a variant of the vehicle routing problem (VRP) in which each route is assigned some maximum length or time constraint [17]. Here, this constraint is represented by the maximum distance that the battery capacity $B$ allows each vehicle to run. The problem is asymmetric because the graph $G$ is directed. In fact, the cost of arc $(i, j)$ is generally different than that of arc $(j, i)$. We can also note the low sparsity rate of the graph $G$, and this could be considered as the main difference between our PRT problem and the basic ADCVRP. In fact, for nodes $i, j \in V^*$, if the arc $(i, j)$ exists, the opposite arc $(j, i)$ does not exist. This problem is proven to be NP-hard [3]. As [18] state, the ADCVRP has not been studied as comprehensively as other versions of the VRP, such as the constrained VRP or the VRP with time windows. To the best of our knowledge, only two papers have studied to minimize the total distance traveled by vehicles for this problem [19],[18]. In this work, we present a novelty as we study to minimize the total number of used vehicles.

## 3 Road Based formulation

In this section, we propose a road-based formulation to the PRT routing problem. The following indices variables and notations are introduced:
$$x_{ij} = \begin{cases} 1 & \text{if node } j \text{ is visited after node } i \\ 0 & \text{Otherwise} \end{cases}$$

- $c_{ij}$ is the cost need to go from node $i$ to node $j$.

- $\delta^+(i)$ is the set of edges that have $i$ as a root.

- $\delta^-(i)$ is the set of edges that have $i$ as a sink.

- $V^* = V \setminus \{s, t\}$.

For each $(l, k) \in E$ the following notations and definitions are given:

- $Road_{ab}$ represent a subsequence of connected edges in $G$ starting from node $a$ to reach node $b$. More specifically, $Road_{ab}$ is a sequence of selected edges from the graph $G$ that connect the node $a$ to node $b$.

- $InfR$ is the set of all infeasible Roads in $G$. $InfR$ represents all the roads in $G$ where the total consumed energy exceed the battery capacity of PRT vehicles $B$.

The PRT model is written as follows:

$$\text{Minimize} \quad \sum_{(s,i) \in E} x_{si} \qquad (1)$$

$$\sum_{j \in \delta^+(i)} x_{ij} = 1 \qquad \forall i \in V^* \qquad (2)$$

$$\sum_{j \in \delta^-(i)} x_{ji} = 1 \qquad \forall i \in V^* \qquad (3)$$

$$\sum_{(i,j) \in Road_{ab}} x_{ij} \leq |Road_{ab}| - 1 \quad \forall Road_{ab} \in InfR \qquad (4)$$

$$x_{ij} \in \{0, 1\} \qquad \forall (i, j) \in E \qquad (5)$$

In this model, constraints (2),(3) are assignment constraints. They ensure that the degree of each node is equal to 1. Constraints (4) ensure that there exist no unfeasible roads in the final obtained solution. In fact, they eliminate any unfeasible roads by setting constraints on the cardinality of its related decisions variables. Unfortunately, there are an exponential number of constraints in (4) since the number of unfeasible roads is exponential. Therefore, we should employ reformulations and specific solution methods to be able to solve the problem in a reasonable time.

## 4 MTZ-based formulation

In this section a mixed integer programming formulation, which is based on the classical work of Miller, Tucker, and Zemlin (MTZ) (1960)[20] in the context of the Asymmetric Traveling Salesman Problem (ATSP), is presented. This is a valid mathematical formulation that was presented in [3],[15] for the case of energy minimization in the case of PRT. To that aim the following decision variables and notations are introduced.
- $z_i$ is the consumed electric energy by the vehicle that reaches the depart station $Ds_i$ of trip $i \in V^*$. This decision variable ($z_i$) is introduced to indicate the amount of the remaining electric energy for the vehicle arriving at $Ds_i$, in order to check the possibility of performing another trip before returning back to the depot.

- $a_i = c_{si}$ for $i \in V^*$.

- $b_i = B - c_{it}$ for $i \in V^*$.

Hence, the minimum electric energy assuring all the trips is the optimal value of the following programming model:

$$ \text{Minimize} \quad \sum_{(s,i) \in E} x_{si} \qquad (6) $$

Equations 2,3.

$$ z_i + c_{ij} \le z_j + (b_i - a_j + c_{ij})(1 - x_{ij}) \quad \forall (i, j) \in E^* \qquad (7) $$

$$ a_i \le z_i \le b_i \quad \forall i \in V^* \qquad (8) $$

$$ x_{ij} \in \{0,1\} \quad \forall (v_i, v_j) \in E^* \qquad (9) $$

$$ z_i \ge 0 \quad \forall i \in V^* \qquad (10) $$

The objective (6) is to minimize the number of used vehicles.

Constraints (7) are an MTZ constraints. They involve that the electric energy, for the vehicle visiting $Ds_j$ immediately after $As_i$ ($x_{ij} = 1$), satisfies $z_i + c_{ij} \le z_j$ for $i, j \in T$. Clearly, for the other case $x_{ij} = 0$, the inequalities $z_i + c_{ij} \le z_j + (b_i - a_j + c_{ij})$ holds since $z_i - b_i \le 0 \le z_j - a_j$ ($i, j \in T$).

Constraints (8) present bounds on the electric energy needed to perform the trip $i$. They ensure that the electric energy consumed by the selected roads don't exceed the battery capacity. Finally, Constraints (9) indicates that $x_{ij}$ are binaries variables and (10) $z_i$ are real positive variables.

# 5 Flow-based Formulation

In this section, we present a flow-based mathematical formulation (FB) for our problem. This formulation was presented in [8] for the Asymmetric Distance Constrained Vehicle Routing Problem (ADCVRP). We first introduce the following integer variable:

$z_{ij}$ = the electric energy used to travel from the depot to trip $j$ as $i$ is the predecessor of $j$.

$$ \text{Minimize} \quad \sum_{(s,i) \in E} x_{si} \qquad (11) $$
Equations 2,3.

$$ \sum_{(i,j) \in E'} z_{ij} - \sum_{(i,j) \in E'} z_{ji} - \sum_{j \in V^*} c_{ij} x_{ij} = 0 \quad \forall i \in T \quad (12) $$

$$ z_{ij} \leq (B - c_{jt})x_{ij} \quad \forall (i, j) \in E \quad (13) $$

$$ z_{ij} \geq (c_{ij} + c_{si})x_{ij} \quad \forall i \neq \{s, t\}, \forall (i, j) \in E^* \quad (14) $$

$$ z_{si} = c_{si}x_{si} \quad \forall i \in E^* \quad (15) $$

The objective (11) is to minimize the total number of used vehicles to cover all the trips.

Constraints (12) ensure that the energy consumed $z_{ij}$ from any node $i$ to any node $j$ in a route is equal to the energy consumed between the depot to the node $j$ in addition the electric energy consumed from node $j$ to node $i$. Constraints (13) are battery constraints. In fact, they guarantee that the amount of electric energy a vehicle consumes to reach trip node $j$ from the depot is less than its battery capacity minus the cost of returning to the depot.

In addition, according to constraints (14), the total electric energy consumed used to reach node $j$ from the depot is greater than, or at least equal to, the direct link between the depot and node $j$. Finally, constraints (15) provide the initial values for $z_{si}$, which should be equal to the electric energy consumed while moving from the depot to trip node $i$.

# 6 Computational Results

We compared these two mathematical formulations in terms of GAP in %, CPU time and number of variables. For comparison, test problems' generator from the literature developed by Mrad and Hidri [3] and Mrad et al. [15] is used to generate 190 instances. The size of the problem instances varies from 10 to 100 in a multiple of 5. We generated randomly for each class'size 10 instances. The two models were coded in C++ and CPLEX 12.2. Test problems are run on PC with an Intel i3 CPU 2.53 GHz processor and 3 GB of RAM. Cplex parameter were modified in such a way that the runs are terminated after 100 seconds. This is made in order to test the efficiency of the two mathematical formulations.

We used two performance measures to assert the efficiency of our two tested mathematical formulations. These measures include:

- GAP = $(\frac{SOL-LB}{LB}) \times 100$, where $LB$ is the maximum of the linear relaxation of the two mathematical formulations presented in this paper (MTZ and FB).

- CPU time is the time in seconds needed to find the obtained results.

Comparisons of these performance measurements are presented in Table 1.

In Table 1, for each instance size, the average value among the 10 instances is given in terms of gap and solution time. The last row of this table provides a global average assessment over all the instance sizes. Table 1 presents also
<table><caption>Table 1: Results for the Flow-based formulation and the MTZ Formulation</caption><thead><tr><th rowspan="2">Size</th><th rowspan="2">Number of variables</th><th colspan="2">MTZ Formulation</th><th colspan="2">Flow-based Formulation</th></tr><tr><th>GAP %</th><th>Time(sec)</th><th>GAP %</th><th>Time(sec)</th></tr></thead><tbody><tr><td>10</td><td>41.80</td><td>0.00</td><td>0.32</td><td>0.00</td><td>0.24</td></tr><tr><td>15</td><td>80.40</td><td>10.85</td><td>0.39</td><td>10.85</td><td>0.23</td></tr><tr><td>20</td><td>131.20</td><td>11.59</td><td>2.33</td><td>11.59</td><td>0.84</td></tr><tr><td>25</td><td>197.80</td><td>11.21</td><td>30.45</td><td>11.21</td><td>1.36</td></tr><tr><td>30</td><td>271.00</td><td>14.85</td><td>82.99</td><td>8.32</td><td>24.04</td></tr><tr><td>35</td><td>356.50</td><td>19.46</td><td>103.76</td><td>14.21</td><td>44.88</td></tr><tr><td>40</td><td>455.80</td><td>19.41</td><td>109.47</td><td>11.69</td><td>49.06</td></tr><tr><td>45</td><td>556.20</td><td>22.14</td><td>105.94</td><td>12.44</td><td>84.35</td></tr><tr><td>50</td><td>684.00</td><td>23.98</td><td>104.31</td><td>12.51</td><td>86.55</td></tr><tr><td>55</td><td>812.70</td><td>25.76</td><td>105.25</td><td>13.56</td><td>90.29</td></tr><tr><td>60</td><td>976.80</td><td>28.50</td><td>105.48</td><td>12.38</td><td>93.87</td></tr><tr><td>65</td><td>1124.60</td><td>32.44</td><td>105.12</td><td>13.35</td><td>91.17</td></tr><tr><td>70</td><td>1290.70</td><td>35.92</td><td>103.13</td><td>11.43</td><td>92.88</td></tr><tr><td>75</td><td>1480.20</td><td>38.30</td><td>102.18</td><td>14.33</td><td>99.71</td></tr><tr><td>80</td><td>1656.30</td><td>38.25</td><td>101.33</td><td>11.03</td><td>86.04</td></tr><tr><td>85</td><td>1870.70</td><td>43.66</td><td>101.68</td><td>13.86</td><td>100.45</td></tr><tr><td>90</td><td>2116.40</td><td>43.45</td><td>101.45</td><td>12.98</td><td>93.12</td></tr><tr><td>95</td><td>2345.90</td><td>41.61</td><td>102.04</td><td>17.83</td><td>100.86</td></tr><tr><td>100</td><td>2546.80</td><td>41.75</td><td>101.50</td><td>18.26</td><td>100.64</td></tr></tbody><tfoot><tr><td>Average</td><td>999.78</td><td>26.48</td><td>82.59</td><td><strong>12.20</strong></td><td><strong>65.29</strong></td></tr></tfoot></table>

<table><caption>Table 2: Results of the comparison between the two formulations based on the Wilcoxon matched-pairs signed-rank statistical test</caption><tr><td>P value</td><td>&lt; 0.0001</td></tr><tr><td>Significantly different? (P &lt; 0.05)</td><td>Yes</td></tr><tr><td>One- or two-tailed P value?</td><td>Two-tailed</td></tr><tr><td>Sum of positive, negative ranks</td><td>0.0, -8515</td></tr><tr><td>Sum of signed ranks (W)</td><td>-8515</td></tr></table>

information about the size of the generated graph expressed as the number of variables.

All the instances were not solved to optimality using the two mathematical formulations. The MTZ formulation found the optimal solution 41 times, and the FB formulation found the optimal solution 80 times out of 190 instances. We should note also that mathematical formulations can not obtain optimal solution as the size of the problem increase. This latter proves that our problem is relatively hard to solve.

Statistical analysis using the Wilcoxon matched pairs signed rank test in term of solution quality is provided in Table 2. More details about this statistical test could be obtained from [21].

In terms of objective function, FB formulation is superior to the MTZ formulation. This was confirmed by statistical analysis provided in Table 2. Table
1 shows that for small size instances, the two formulations can find optimal solutions. Mathematical formulations cannot obtain optimum solution as the problems size increases in the limited time (100 seconds) due to the increasing number of variable. For the MTZ formulation, the use of decisions variables related to the nodes rather than the edges (as in the FB formulation) have contributed on the decrease number of constraints and the relatively bad quality solutions of this formulation in comparison to the FB. This is the reason of differences in the performance between the two formulations. We could note that the CPU time grows exponentially as the size of the problem increases. The second performance criterion is CPU times. As seen in the Table 1, Model FF is the best in terms of CPU time. In fact in term of CPU time, there occurs significant difference between the FB and the other MTZ models especially in medium-large sized problems due to the specific structure of the decisions variables related to the FB formulation. We should note that as we put a maximum limit of 100 seconds for both the mathematical formulations, the computing time seems rather constant between a problem size of 40 and 100. This is due to the fact that the mathematical formulation for instances great or equal to 40 trips don't find optimal solutions. In fact, the two mathematical formulations reach the maximum time limit of 100 seconds and exit with the best feasible solution. This confirms that our considered problem is hard to solve especially for medium and large size instance. Therefore, specific adapted heuristics could be developed to tackle large size instances of our problem.

A final conclusion obtained from our study and contrary to the case of min-
imization of total traveled distance for PRT [9], FB performs better than the
MTZ formulation for the case of the minimization of the fleet size.

7 Conclusion

This paper proposes to study a related routing problem to optimize the fleet size for a PRT system. The proposed problem considers the battery constraints related to PRT which is a major operational issue for such a system. Two mathematical formulations are proposed to tackle this problem in order to provide valid fleet sizing for PRT system. Our formulations are applied on different sized test problems. For the proposed routing problem, good quality solutions are obtained. We remarked also that as the size of the problem increase the computation time increases exponentially. This work provides a good reference in order to analyze the cost-effectiveness of the PRT system. Our formulations also help us to determine an approximate fleet size of PRT system.

References

1. Carnegie, J.A., Hoffman, P.S.: Viability of personal rapid transit in new jersey.
Technical report (2007)

2. Lees-Miller, J.D.: Minimising average passenger waiting time in personal rapid transit systems. Annals of Operations Research (2013) 1–20
3. Mrad, M., Hidri, L.: Optimal consumed electric energy while sequencing vehicle trips in a personal rapid transit transportation system. Computers & Industrial Engineering **79** (2015) 1–9

4. Hax, A., Candea, D.: Production and inventory management, 1984

5. Rahimi-Vahed, A., Crainic, T.G., Gendreau, M., Rei, W.: Fleet-sizing for multi-depot and periodic vehicle routing problems using a modular heuristic algorithm. Computers & Operations Research **53** (2015) 9–23

6. 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: Intelligent Transportation Systems (ITSC), 2010 13th International IEEE Conference on, IEEE (2010) 301–305

7. Demir, Y., Kürşat İşleyen, S.: Evaluation of mathematical models for flexible job-shop scheduling problems. Applied Mathematical Modelling **37**(3) (2013) 977–988

8. Kara, I.: Two indexed polonymyal size formulationsfor vehicle routing problems. Technical Report. BaskentUniversity, Ankara/Turkey (2008)

9. Fatnassi, E., Chebbi, O., Siala, J.C.: Comparison of two mathematical formulations for the offline routing of personal rapid transit system vehicles. In: The International Conference on Methods and Models in Automation and Robotics. (2014)

10. Blazewicz, J., Dror, M., Weglarz, J.: Mathematical programming formulations for machine scheduling: a survey. European Journal of Operational Research **51**(3) (1991) 283–300

11. Pan, C.H.: A study of integer programming formulations for scheduling problems. International Journal of Systems Science **28**(1) (1997) 33–41

12. Keha, A.B., Khowala, K., Fowler, J.W.: Mixed integer programming formulations for single machine scheduling problems. Computers & Industrial Engineering **56**(1) (2009) 357–367

13. Pan, J.C.H., Chen, J.S.: Mixed binary integer programming formulations for the reentrant job shop scheduling problem. Computers & Operations Research **32**(5) (2005) 1197–1212

14. Unlu, Y., Mason, S.J.: Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems. Computers & Industrial Engineering **58**(4) (2010) 785–800

15. Mrad, M., Chebbi, O., Labidi, M., Louly, M.: Synchronous routing for personal rapid transit pods. J. Applied Mathematics **2014** (2014)

16. Floyd, R.W.: Algorithm 97: shortest path. Communications of the ACM **5**(6) (1962) 345

17. Toth, P., Vigo, D.: The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (2002)

18. Almoustafa, S., Hanafi, S., Mladenovi, N.: New exact method for large asymmetric distance-constrained vehicle routing problem. European Journal of Operational Research (2012)

19. Laporte, G., Nobert, Y., Taillefer, S.: A branch-and-bound algorithm for the asymmetrical distance-constrained vehicle routing problem. Mathematical Modelling **9**(12) (1987) 857 – 868

20. Miller, C.E., Tucker, A.W., Zemlin, R.A.: Integer programming formulation of traveling salesman problems. J. ACM **7**(4) (October 1960) 326–329

21. Wilcoxon, F., Wilcox, R.A.: Some rapid approximate statistical procedures. Lederele Laboratories (1964)