# Optimum Allocation Method of Standby Taxi Vehicles at Taxi Stands

Takashi Tanizaki

► To cite this version:

Takashi Tanizaki. Optimum Allocation Method of Standby Taxi Vehicles at Taxi Stands. 20th Advances in Production Management Systems (APMS), Sep 2013, State College, PA, United States. pp.3-10, 10.1007/978-3-642-41263-9_1 . hal-01451751

HAL Id: hal-01451751

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

Submitted on 1 Feb 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
# Optimum Allocation Method of Standby Taxi Vehicles at Taxi Stands

Takashi Tanizaki

Department of Informatics, Faculty of Engineering,
Kinki University, Hiroshima, Japan
tanizaki@hiro.kindai.ac.jp

**Abstract.** There are two ways for a taxi company to get customers. One is to deliver taxi for a telephone request, and the other is to get customers on street. In previous research we researched rearrangement method of the taxi drivers working hours so as to operate many taxis with many telephone requests for the former method. In this paper, we propose optimum allocation method of standby taxi vehicles at taxi stands for the latter method. In order to minimize the total mileage, fulfilling the taxi demand of all the allocation and maximum number restriction of taxi stands, we formulate this problem as Linear Programming problem. As a result of numerical calculation, there are some improving points to change the number of standby taxi vehicles at taxi stands, and it turned out that total mileage may be reducible by 30%.

**Keywords.** optimum allocation, taxi company, linear programming, service productivity

## 1 Introduction

In Japan, the number of customers who use taxis has been decreasing for about fifteen years. But the number of taxi vehicles (we call taxis in this paper) has been increasing from 2002 by regal revision. As a result, income of a taxi per day decreases [1]. It became very severe to get customer between taxi companies. Then taxi companies introduce various methods to gain more customers, for example, customer membership. Some companies introduce new taxi operation system using GPS and smartphone to shorten taxi waiting time. For 90% of taxi companies, the number of possession taxis is less than 50. Moreover, for 70% of taxi companies, the capital is less than 10 million yen. Therefore it is difficult for many taxi companies to introduce above system because of financial deficit. From above reason, we research improvement method of service productivity to gain more customers by little investment for small taxi companies.

There are two customer acquisition methods for taxi companies in Japan. One is to deliver a taxi for a telephone request, and the other is to get customers on street. For the former method, it is required to deliver a taxi immediately by telephone requests. We researched improvement method of rearranging taxi drivers' working hours so as to work many taxis with many telephone requests [2]. For the latter method, it is required to allocate taxis for a place with many customers who need a taxi. We research
the optimum allocation method of standby taxis at taxi stands to minimize total millage between taxi stands and the place where customer takes a taxi.

In this paper, we analyze present situation of the Taxi Company which we research (we call Company A in this paper), research the optimum allocation method, and apply our method to Company A.

## 2 Subjects of Company A

Company A is typical small taxi company whose business area is less than 30 minutes drive by taxi. Maximum numbers of taxis at each taxi stand, the number of taxis which can be worked in every hour, and the operation records for each place where customer took the taxi in 2011 are as follows.

### 2.1 Maximum numbers of taxis at each taxi stand

Maximum numbers of taxis at each taxi stand are shown in Table1. They are determined by the size of taxi stand, distribution with other taxi companies, etc.

<table><caption>Table 1. Maximum numbers of taxis at each taxi stand</caption><tr><td>Taxi stand</td><td>a</td><td>b</td><td>c</td><td>d</td><td>e</td><td>f</td><td>g</td><td>h</td><td>i</td><td>j</td></tr><tr><td>Maximum numbers</td><td>3</td><td>3</td><td>4</td><td>1</td><td>2</td><td>1</td><td>4</td><td>5</td><td>5</td><td>2</td></tr></table>

### 2.2 Total numbers of taxis which can be worked in each hour

Total numbers of taxis which can be worked in each hour are shown in Table2. There are many taxis in time zone between 7:00 and 1:00 for large number of taxi demand, and few taxis in time zone between 3:00 and 6:00 for small number of taxi demand.

<table><caption>Table 2. Total numbers of taxis in each hour</caption><tr><td>Time zone</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td></tr><tr><td>Total numbers</td><td>21</td><td>16</td><td>11</td><td>7</td><td>5</td><td>5</td><td>5</td><td>16</td><td>21</td><td>21</td><td>21</td><td>21</td></tr></table><table><tr><td>Time zone</td><td>12</td><td>13</td><td>14</td><td>15</td><td>16</td><td>17</td><td>18</td><td>19</td><td>20</td><td>21</td><td>22</td><td>23</td></tr><tr><td>Total numbers</td><td>26</td><td>26</td><td>25</td><td>26</td><td>26</td><td>26</td><td>26</td><td>21</td><td>21</td><td>21</td><td>21</td><td>21</td></tr></table>

### 2.3 The operation records

The operation records for each place where customer took the taxi in 2011 are shown in Table 3. These records are counted on the time when customer took the taxi. Area in Table 3 is a group of the near place of distance. “Deliver” in Table 3 is a call from a customer and picking up a customer at the call place. “Getting” in Table 3 is en-countering and picking up a customer at taxi stand or on street.
There are 50 areas in the operation records of Company A. It is difficult to solve the problem with 50 areas because size of problem is large. Therefore we pick up 26 areas exceeding 1000 equivalent to 0.5% of about 200,000 annual sum totals in "Deliver" or "Getting". The analyzing results of monthly operation record are as follows.

* Many areas of taxi use increase in December because of year-end party.

* Specific area of taxi use increase in March because of graduation ceremony and farewell party.

<table><caption>**Table 3.** The operation records</caption><thead><tr><th>Area</th><th>A1</th><th>A2</th><th>A3</th><th>...</th><th>A48</th><th>A49</th><th>A50</th><th>Total</th></tr></thead><tbody><tr><th>Deliver</th><td>2085</td><td>11476</td><td>4633</td><td>...</td><td>115</td><td>24</td><td>103</td><td>109036</td></tr><tr><th>Getting</th><td>47076</td><td>3935</td><td>10897</td><td>...</td><td>137</td><td>5</td><td>8</td><td>83220</td></tr><tr><th>Total</th><td>49161</td><td>15411</td><td>15530</td><td>...</td><td>252</td><td>29</td><td>111</td><td>192256</td></tr></tbody></table>

From this result, it is better to consider different taxi allocation in March and December from an all year. We analyze also about the operation record in each area according to time zone. The results are as follows.

* In many areas, there is much use of taxi in time zone between 8:00 and 20:00. In this time zone, many people go out and many supermarkets open.

* In A2 area, there is much use of taxi in time zone between 21:00 and 3:00. It seems that there are many bars in A2 area.

* In some areas, there is little use of taxi in time zone between 10:00 and 17:00. In these areas, there is much use of a morning, the evening, and night. Therefore, it seems that the taxi is used at the time of commuting and going home.

As mentioned above, the time zones with much use of taxi are different in areas. Therefore, it is necessary to decide optimum allocation of standby taxis at taxi stands in every hour.

## 3 Formulation

We research the optimum allocation method of standby taxis at taxi stands to minimize total millage between taxi stands and the place where customer takes a taxi (we call it demand place). In this company, it is possible to drive taxi to all demand places from any taxi stands. In order to minimize the total mileage, fulfilling the taxi demand of all the allocation, it is considered how many taxis should be driven to a demand place from a taxi stand (see Fig.1).
<figure><img src="image_2.png" /><figcaption>Fig. 1. from – to table</figcaption></figure>

**3.1 Notation**

The following notations are used to formulate this problem.

i : Taxi stand (i = 1, 2, ..., 10),

j : Demand place (j = 1, 2, ..., 26),

t:Time zone(t = 0, 1, ...,23),

xijt: The number of taxis which move from i to j in time zone t,

cij : Distance from i to j,

Xt : Total number of taxis in time zone t,

T_i : Maximum numbers of taxis at taxi stand i,

Djt : Taxi demand in demand place j in time zone t.

There are many places where customer takes a taxi in demand place. We decide to
make into a representative point the place allocated mostly, as a result of discussion
with Company A. We measure the mileage from a taxi stand to the representative
point of demand place on the map for cij.

**3.2 Formulation**

The objective is to minimize sum total of mileage from taxi stands to demand place
for each time zone. The Problem is formulated as follows:

$$
\text{Minimize} \sum_{i=1}^{10} \sum_{j=1}^{26} c_{ij} x_{ijt} \quad \text{for each } t (t = 0, 1, \dots, 23) \quad (1)
$$

subject to

$$
\sum_{j=1}^{26} x_{ijt} \leq T_i, \qquad (2)
$$
$$ \sum_{i=1}^{10} x_{ijt} \geq D_{jt}, \qquad (3) $$

$$ \sum_{i=1}^{10} \sum_{j=1}^{26} x_{ijt} = X_t, \qquad (4) $$

$$ x_{ij} \geq 0. \qquad (5) $$

Constraint (2) shows that sum total of taxis which stand by at taxi stand i do not exceed the maximum number of taxis at the taxi stand. Constraint (3) shows that sum total of taxis which move to the demand place j fulfills taxi demand of the place. Constraint (4) shows sum total of taxis which move from i to j is equal to total number of taxis in each time zone.

# 4 The application result to Company A

As shown in 2.2, total number of taxis which can be worked changes for every hour. Therefore, it is necessary to decide optimum allocation of standby taxis at taxi stands in every hour. As shown in 2.1, there are maximum numbers of taxis at each taxi stand. First, we solve the problem in 3.2 to decide optimum allocation of standby taxis at taxi stands in each time zone. Secondly, we analyze the influence on taxi operation caused by the maximum number restrictions of standby taxi at each taxi stand. Therefore we solve the problem in 3.2 without maximum number restrictions at each taxi stand, and solve the ideal optimum allocation. Thirdly, we compare two results with present allocation. For these case studies, we use optimization solution software package using the operation records in 2011/1 to 2011/12 from Company A.

## 4.1 Calculation procedure with maximum number restrictions

We solve the optimal solution of the problem in 3.2 under the following conditions.

* T<sub>i</sub> and X<sub>t</sub> are given in Table1 and Table2.

* D<sub>jt</sub> is annual average of the operation records in time zone t. If sum of D<sub>jt</sub> exceeds X<sub>t</sub>, D<sub>jt</sub> is distributed proportionally so that sum of D<sub>jt</sub> may become equal to X<sub>t</sub> (See Table4).

* Since the calculation result becomes the real number, sum total of calculating result at each taxi stand is rounded off (See Table5).
## 4.2 Calculation procedure without maximum number restrictions

We solve the optimal solution of the problem in 3.2 without maximum number restrictions under the following conditions.

* Ti is equal to $\infty$, Xt is given in Table2.

* Djt is annual average of the operation records in time zone t. If sum of Djt exceeds Xt, Djt is distributed proportionally so that sum of Djt may become equal to Xt (See Fig.2).

* Since the calculation result becomes the real number, sum total of calculating result at each taxi stand is rounded off (See Fig.3)

<table><caption>Fig. 2. Determination of D<sub>j</sub></caption><thead><tr><th colspan="5">Monday (6:00) X<sub>t</sub> = 5</th><th colspan="5">Monday(13:00) X<sub>t</sub> = 26</th></tr><tr><th>Demand place</th><th>A1</th><th>A2</th><th>...</th><th>A26</th><th>Total</th><th>A1</th><th>A2</th><th>...</th><th>A26</th><th>Total</th></tr></thead><tbody><tr><td>D<sub>jt</sub></td><td>1.77</td><td>0.48</td><td></td><td>0.44</td><td>7.71</td><td>4.58</td><td>0.52</td><td></td><td>0.19</td><td>22.56</td></tr><tr><td colspan="5">Total>X<sub>t</sub>, then distributed</td><td colspan="5">Total < X<sub>t</sub>, then not change</td></tr><tr><td>D<sub>jt</sub>(Input Data)</td><td>1.15</td><td>0.31</td><td></td><td>0.03</td><td>5.0</td><td>4.58</td><td>0.52</td><td></td><td>0.19</td><td>22.56</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>Fig. 3. Calculation result at each taxi stand by procedure 4.1 & 4.2 (Monday 13:00)</figcaption></figure>

## 4.3 Calculation results

The present allocation of taxis at taxi stands, the calculation result on Monday by procedure 4.1 and 4.2 are shown in Fig.4, Fig.5 and Fig.6. We calculate day by day about one week. We show the result of Monday for example. Sum total of mileage on Monday in expression (1) is shown Table 4. From Table 4, sum total of millage is shorter in order of Procedure 4.2, Procedure 4.1, and present allocation. Therefore solving Linear Programming (we call LP in this paper) problem described in 3.2 is effective method to decide optimum allocation of standby taxis.
From Fig.4 and Fig.5, it is effective for mileage reduction to increase taxi at taxi stand d, f, i and to decrease taxi at taxi stand g, h. Since there is hospital near taxi stand d and supermarket near taxi stand f, there is taxi demand. Although there is a university near taxi stand i, there is no transportation from university to Shinkansen express station, therefore there is taxi demand. From Fig.4 and Fig.6, it is effective for mileage reduction to increase taxi at a, c and to reduce taxi at b, g, h. Since there is railroad station near taxi stand a and bar near taxi stand c, there is much taxi demand.

From Table 4, sum total of millage without restrictions is 62% of the best result in present situation (= Procedure 4.1). The maximum number restrictions of standby taxi at taxi stand a have bad influence on the management of company A.

<figure><img src="image_4.png" /><figcaption>Fig. 4. Present allocation of taxis at taxi stands</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 5. Calculation result on Monday by procedure 4.1</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 6. Calculation result on Monday by procedure 4.2</figcaption></figure>
<table><caption>Table 4. Sum total of millage on Monday</caption><thead><tr><th></th><th>Present allocation</th><th>Procedure 4.1</th><th>Procedure 4.2</th><th></th><th>Present allocation</th><th>Procedure 4.1</th><th>Procedure 4.2</th></tr></thead><tbody><tr><td>0</td><td>30648.4</td><td>18872.6</td><td>3349.0</td><td>12</td><td>35390.5</td><td>28832.3</td><td>14021.5</td></tr><tr><td>1</td><td>2438.5</td><td>1963.3</td><td>1504.7</td><td>13</td><td>22346.3</td><td>18507.0</td><td>10757.1</td></tr><tr><td>2</td><td>1966.7</td><td>1487.0</td><td>1288.0</td><td>14</td><td>17343.0</td><td>14270.8</td><td>10620.5</td></tr><tr><td>3</td><td>1678.9</td><td>1598.1</td><td>1349.8</td><td>15</td><td>20942.2</td><td>16875.8</td><td>11879.4</td></tr><tr><td>4</td><td>2141.4</td><td>664.5</td><td>924.8</td><td>16</td><td>23447.7</td><td>18879.4</td><td>12369.9</td></tr><tr><td>5</td><td>5969.4</td><td>2368.2</td><td>1981.8</td><td>17</td><td>39590.7</td><td>30318.1</td><td>19632.0</td></tr><tr><td>6</td><td>9020.0</td><td>5510.5</td><td>5547.1</td><td>18</td><td>37310.6</td><td>27765.9</td><td>16700.0</td></tr><tr><td>7</td><td>20456.4</td><td>7816.2</td><td>8947.3</td><td>19</td><td>24766.6</td><td>16777.5</td><td>14246.4</td></tr><tr><td>8</td><td>18048.8</td><td>14266.1</td><td>12665.2</td><td>20</td><td>22706.8</td><td>14707.9</td><td>12184.2</td></tr><tr><td>9</td><td>25866.1</td><td>17059.9</td><td>11874.9</td><td>21</td><td>24964.7</td><td>17956.2</td><td>9717.8</td></tr><tr><td>10</td><td>25384.9</td><td>17886.4</td><td>11851.2</td><td>22</td><td>31614.5</td><td>19281.4</td><td>7574.5</td></tr><tr><td>11</td><td>25875.2</td><td>17650.0</td><td>13610.2</td><td>23</td><td>36111.6</td><td>23713.4</td><td>5988.3</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td>Total</td><td>506029.7</td><td>355028.3</td><td>220585.3</td></tr></tbody></table>

# 5 Conclusions

We research the optimum allocation method of standby taxis at taxi stands to minimize total millage between taxi stands and the place where customer takes a taxi. In order to minimize the total mileage, fulfilling the taxi demand of all the allocation and maximum number restriction of taxi stands, we formulate this problem as LP problem. Using the operation records in 2011/1 to 2011/12 from Company A, we analyze present situation of Company A, and apply our method to Company A. As a result of numerical calculation, it turns out that solving LP problem is effective method to minimize the total mileage. There are some improving points to change the number of standby taxis at taxi stands, and it turned out that total mileage may be reducible by 30%.

We will research taxi drivers' working hours so as to work many taxis with many taxi delivery demands and incomes using optimum solution method.

# References

1. Ministry of Land, Infrastructure, Transport, and Tourism, WHITE PAPER ON LAND, INFRASTRUCTURE, TRANSPORT, AND TOURISM IN JAPAN, 2010. (in Japanese)

2. Takashi Tanizaki, Improvement Method of Service Productivity for Taxi Company, Competitive Manufacturing for Innovative Products and Services: Proceedings of the APMS 2012 Conference, Advances in Production Management Systems, Springer (now publishing)