THE MODELLING OF STATE OF THE ART TAXI
OPERATIONS AND DISPATCHING APPROACHES








WU XIAN







NATIONAL UNIVERSITY OF SINGAPORE
2013



THE MODELLING OF STATE OF THE ART TAXI OPERATIONS
AND DISPATCHING APPROACHES
WU XIAN
2013

THE MODELLING OF STATE OF THE ART TAXI
OPERATIONS AND DISPATCHING APPROACHES









WU XIAN
(B. Eng. & M. Eng., Tsinghua University, Beijing, P. R. China)



A THESIS SUBMITTED
FOR THE DEGREE OF DOCTOR OF PHILOSOPHY
DEPARTMENT OF CIVIL & ENVIRONMENTAL ENGINEERING
NATIONAL UNIVERSITY OF SINGAPORE
2013



DECLARATION

I hereby declare that this thesis is my original work and it has been written by me in its
entirety.

I have duly acknowledged all the sources of information which have been used in
the thesis.
This thesis has also not been submitted for any degree in any university previously.



Wu Xian

i

ACKNOWLEDGEMENTS

My sincerest gratitude goes to my supervisor, Associate Professor Lee Der-Horng who
has guided me to the final step of this thesis. His continuous encouragement always
gave me confidence throughout the four-year PhD studies. Besides the research, I also
learned the skills of self-presentation, communication and leadership from him, which
would be valuable treasures for the rest of my career life.
I would also like to thank my module teachers, Prof. Meng Qiang, Dr. Szeto Wai
Yuen, Prof. Chan Weng Tat, Prof. Ong Say Leong, Prof. Fwa Tien Fang, Prof. Chin
Hoong Chor, Prof. Tan Kiang Hwee, Prof. David Chua Kim Huat and Dr. Shen Lijun
for their kindness and commitment.
Thanks also go to my NUS colleagues and friends, including Dr. Cao Jinxin, Dr.
Chen Jianghang, Dr. Wang Tingsong, Dr. Liu Zhiyuan, Dr. Weng Jinxian, Dr. Wang
Xinchang, Dr. Qu Xiaobo, Dr. H.R. Pasindu, Dr. Zhang Jian, Wang Qing, Ma Yaowen,
Yang Jiasheng, Dr. Jin Jiangang, Fu Yingfei, Zhang Yang, Huang Sixuan, Zheng
Yanding, Aditya Nugroh, Dr. Wang Shuaian, Zhang Lei, Sun Lijun, Li Siyu, Qin Han,
He Nanxi, Maggie Sou, Sun Leilei, Lu Zhaoyang, Tan Rui, Ge Dongliang and Zhao
Kangjia for their kindly support and cooperation.
I also want to thank Mr. Foo Chee Kiong, Madam Yap-Chong Wei Leng, and
Madam Theresa Yu-Ng Chin Hoe for their hard working and assistance.

Finally, my deepest gratitude goes to my girlfriend, my parents and my brother, for
their always understanding, support and love.

ii

Table of Contents
Table of Contents ii
Executive Summary vii
List of Tables x
List of Figures xi
List of Abbreviations xiv
List of Symbols xviii
Chapter 1 Introduction 1
1.1 Research Background 1
1.2 The Current Taxi Dispatching System 3
1.2.1 The operator-level taxi dispatching system 3
1.2.2 The market-level taxi dispatching system 5
1.3 Issues in the Current Taxi Dispatching System 6
1.3.1 Issues for the Booking Taxi Service (BTS) 6
1.3.2 Issues for the Non-Booking Taxi Service (NBTS) 7
1.3.3 Issues for the evaluation of dispatching strategies 8
1.4 Research Objectives and Scope of the Thesis 9
1.5 Organization of the Thesis 11
Chapter 2 Literature Review 14
2.1 Literature on Taxi Service Models (TSMs) 14
2.1.1 The mathematical TSM: from the economics point of view 14

iii

2.1.2 The mathematical TSM: from the transportation point of view 17

2.1.3 The micro-simulation based TSM 20
2.2 Literature on the Taxi Dispatching System 23
2.2.1 The centralized dispatching strategy 24
2.2.2 The non-centralized dispatching strategy 25
2.2.3 Other taxi dispatching related research studies 26
2.3 Summary 26
Chapter 3 A Micro-Simulation Based TSM 28
3.1 Background 28
3.2 Software Architecture 30
3.2.1 Limitations of the existing microscopic simulation software 30
3.2.2 The software architecture for the proposed TSM 31
3.3 Model Development 34
3.3.1 The Taxi-Customer Searching Model (TCSM) 34
3.3.2 The Customer Demand Model (CDM) 36
3.3.3 The Dispatching Strategy Model (DSM) 40
3.3.4 The Simulation Network Model (SNM) 45
3.4 Input Data, Parameters and Performance Indicators 49
3.4.1 The customer OD matrix 49
3.4.2 Model parameters 51
3.4.3 Performance Indicators (PIs) 54

iv

3.5 A Simulation Example 55
3.5.1 Simulation results 59
3.5.2 Analysis 63
3.6 Summary 66
Chapter 4 An Improved Dispatching Strategy for the CBK 67
4.1 Background 67
4.2 General Description of the Proposed MA-DS-BC 70

4.2.1 System architecture 70
4.2.2 Dispatching operations 71
4.3 The Collaborative Booking Assignment Process (CBAP) 75
4.3.1 Problem formulation for the CBAP 75
4.3.2 The multi-agent based solution process for CBAP 78
4.4 Simulation Experiments 81
4.4.1 The simulation model 81
4.4.2 Pseudo code for the simulation of CBAP 83
4.4.3 Input data and parameters 84
4.4.4 Simulation results 87
4.4.5 Analysis 89
4.5 Summary 90
Chapter 5 An Integrated Dispatching Strategy considering CBK and ABK 92
5.1 Background 92

v

5.2 The System Architecture of the ABC-DS 94
5.2.1 General system architecture 94
5.2.2 The taxi agent 96
5.2.3 The Advance Booking Chain (ABC) 98
5.3 Dispatching Operations (1) – the Initial Assignment Phase (IAP) 99
5.3.1 Cost Computation Process (CCP) 99
5.3.2 General dispatching operations 104
5.4 Dispatching Operations (2) – the Local Planning Phase (LPP) 107
5.4.1 The move operations 109
5.4.2 Searching strategy for the ABK-LP-Q 111
5.4.3 General dispatching operations 113
5.5 Simulation Experiments 118
5.5.1 The simulation model 118

5.5.2 Input data and parameters 120
5.5.3 Simulation result (1): test of the CCP 122
5.5.4 Simulation result (2): test of the LPP 123
5.5.5 Simulation result (3): sensitivity analysis 124
5.6 Summary 129
Chapter 6 A Game Theory Based Control Strategy for the NBTS 131
6.1 Background 131
6.2 The System Architecture and Problem Formulation 133

vi

6.2.1 System architecture of the LISS 133
6.2.2 Game-theoretical formulation for the TCNP 135
6.3 Solution Procedure for TCNP 140
6.3.1 General operations for both taxi and customer agents 140
6.3.2 Calculation of Customer Utility function: CCU
j
(k) 144
6.3.3 The Select-A-Customer function: SAC
i
(k) 146
6.3.4 The Check For Stop function CFS
i
(k) 151
6.4 Simulation Experiments 152
6.4.1 The simulation model 152
6.4.2 Pseudo code for the simulation of TCNP 152
6.4.3 Input data and parameters 154
6.4.4 Simulation results 155
6.4.5 Analysis 158

6.5 Summary 159
Chapter 7 Conclusions 161
7.1 Conclusions 161
7.2 Future Works 164
Bibliography 168
Appendix 175


vii


Executive Summary

As an important mode of transport, taxis have played an important role in many large
cities worldwide. However, with the increase of both taxi supply and demand, the
imbalance between the two (either in spatial or temporal dimensions) has become an
urgent issue: on one hand, customers have to bear longer waiting time at taxi stands and
on another hand, taxi drivers have to spend longer empty cruising time in the road
network. To respond to this issue, many large cities have adopted taxi dispatching
systems which provide an alternative way for both customers and taxi drivers to find
each other easily. However, there exist a number of practical issues in the operation of
the taxi dispatching systems: firstly, customers’ will of booking taxis is not strong;
secondly, the system can do nothing to those customers who take taxis without booking;
thirdly, in a competitive taxi market where more than one taxi operator exists,
operational efficiency of the entire market as well as individual operators would be
largely affected by the market structure and the organization of taxi dispatching
strategies which give rise to the complexity of the problem. Thus, this thesis aims to
provide solutions or indications to deal with the aforementioned three practical issues.
A micro-simulation based Taxi Service Model (TSM) has been developed and
introduced in this thesis as test bed to evaluate the operational performance of different

dispatching/control strategies. It is enabled by customized simulation environment in

viii

which the dynamic behaviors of taxis and customers, the dispatching/control strategies
and group characteristics of individual taxi operators could be modeled. This model has
been firstly employed to study the booking taxi services in this thesis: on one hand, for
the current booking service, an improved agent-based taxi dispatching approach
considering the impact of booking cancellations has been proposed and tested, the
results of experiments show that the proposed approach may have the potential to
attract more customers to book taxis by reducing the chance of booking cancellations
effectively; on the other hand, for the advance booking service, an improved taxi
dispatching approach handling both current bookings and advance bookings has been
proposed and tested, the results of the experiments show that the proposed approach can
benefit both taxi drivers and customers at certain demand scale levels and certain
advance booking ratios, as well as for certain taxi fleet scales.
For the non-booking taxi service in which customers take taxis by waiting at taxi
stands or hailing on the street, this thesis has proposed a novel control strategy, namely
the Limited Information Sharing Strategy (LISS) to improve the operational efficiency
of the entire taxi fleet, which has also been tested by the aforementioned simulation
model. This strategy has adopted game theory to formulate the problem in which the
utilities of both customers and taxis are specifically defined by considering a number of
theoretical and practical problems/constraints. The negotiation mechanism in LISS has
been specifically selected to ensure that the negotiation process can lead to a Nash
Equilibrium (NE). The experiment results show that the LISS can effectively reduce

ix

customers’ waiting time especially in the CBD area during peak-hours, while keeping
the risk of the taxi side within a certain level.

In all, this thesis has provided a comprehensive study on the dispatching/control
strategies for both individual taxi operators and the entire taxi market, which is
expected to offer persuasive support to decision makers for related taxi policies.


x

List of Tables
Table 2.1: The mathematical TSM: from the transportation point of view 21
Table 2.2: The simulation-based TSMs 23
Table 3.1: The partition of the study area 50
Table 3.2: An example of the customer OD matrix (customers/hr) 50
Table 3.3: Baseline customer OD matrix for Scenario 1 (customers/hr) 56
Table 3.4: Baseline customer OD matrix for Scenario 2 (customers/hr) 56
Table 3.5: Parameters for both simulation scenarios 58
Table 3.6: The evaluation of dispatching strategies for Scenario 1 62
Table 3.7: The evaluation of dispatching strategies for Scenario 2 62
Table 3.8: The comparison between Non-Coop-DS and Coop-DS. 66
Table 4.1: The pseudo code for the simulation process of the CBAP 84
Table 4.2: The customer OD matrix (customers/hr) 85
Table 4.3: The simulation results 87
Table 5.1: The partition of the study area 119
Table 5.2: The customer OD matrix (customers/hr) 120
Table 6.1: The pseudo code of TCNP(t) for simulation 153
Table 6.2: The customer OD matrix (customers/hr) 154



xi


List of Figures
Figure 1.1: Customer waiting time at taxi stands (LTA, 2010) 2
Figure 1.2: Operations of the current operator-level dispatching system 3
Figure 1.3: Operations of the current market-level dispatching system 5
Figure 2.1: Research topics in the taxi service market (Yang et al. 2002) 16
Figure 3.1: The two-tier software architecture for the proposed TSM 33
Figure 3.2: The functional block diagram for the simulation model 34
Figure 3.3: The Customer Demand Model (CDM) 40
Figure 3.4: Three types of the operator-level dispatching strategy 41
Figure 3.5: Swim-lane diagram of the centralized dispatching strategy 42
Figure 3.6: Two types of the market-level dispatching strategy 45
Figure 3.7: Stand-level simulation 47
Figure 3.8: District-level simulation 48
Figure 3.9: Region-level simulation 49
Figure 3.10: The evaluation of dispatching strategies for Scenario 1 60
Figure 3.11: The evaluation of dispatching strategies for Scenario 2 61
Figure 4.1: The non-centralized dispatching system architecture 71
Figure 4.2: Swim-lane diagram of the proposed non-centralized dispatching strategy 72
Figure 4.3: The simulation model for the test of the proposed dispatching strategy 82
Figure 4.4: The Occupancy Rate (OR) 87

xii

Figure 4.5: The Customer Waiting Time (CWT) of all taxi stands 88
Figure 4.6: The Customer Waiting Time (CWT) of taxi stands within the study area 88
Figure 4.7: The Number of Booking Cancellations (BCs) 89
Figure 5.1: The non-centralized dispatching system architecture 95
Figure 5.2: General rules for the decision process of the taxi agent. 97
Figure 5.3: Swim-lane diagram of the IAP 104
Figure 5.4: The move operations. 110

Figure 5.5: Swim-lane diagram of the LPP 114
Figure 5.6: The simulation model for the test of the proposed dispatching strategy. 119
Figure 5.7: The test for the CCP in the simulation 122
Figure 5.8: The test for the LPP in the simulation 123
Figure 5.9: The simulation results (ABK_R=50%). 125
Figure 5.10: The simulation results (ABK_R=25%). 127
Figure 5.11: The simulation results (ABK_R=75%). 128
Figure 6.1: The decentralized control system architecture 134
Figure 6.2: The problem formulation framework 135
Figure 6.3: Swim-lane diagram of the solution procedure of TCNP 141
Figure 6.4: The primary and secondary utilities 146
Figure 6.5: Four cases in the Step 2 of the SAC
i
(k) 149
Figure 6.6: The simulation model for the test of the proposed dispatching strategy. 152
Figure 6.7: The convergence test for the TCNP when t = 1200 sec. 155

xiii

Figure 6.8: The convergence test for the TCNP when t = 3600 sec. 156
Figure 6.9: The convergence test for the TCNP when t = 6000 sec. 156
Figure 6.10: Average Customer Waiting Time (CWT) at all taxi stands 157
Figure 6.11: Average Customer Waiting Time (CWT) at taxi stands in the study area 157
Figure 6.12: The Occupancy Rate (OR) 157


xiv

List of Abbreviations


ABC
Advance Booking Chain
ABC-DS
Advance Booking Chain Dispatching Strategy
ABK
Advance Booking
ABK_R
Advance Booking Ratio
ABK-LP-Q
Advance Booking - Local Planning - Queue
ABK-Q
Advance Booking Queue
API
Application Program Interface
AWT
Anticipated Waiting Time
BC
Booking Cancellation
BQ
Booking Queue
BR
Booking Rate
BTS
Booking Taxi Service
CBAP
Collaborative Booking Assignment Process
CBD
Central Business District
CBK
Current Booking

CBQ
Confirmed Booking Queue
CCP
Cost Computation Process
CCU
Calculation of Customer Utility
CDM
Customer Demand Model

xv

CFS
Check For Stop
CLAP
Collaborative Linear Assignment Problem
Coop-DS
Cooperative Dispatching Strategy
CWQ
Customer Waiting Queue
CWT
Customer Waiting Time
DC
Dispatching Controller
DPD-VRP
Dynamic Pickup and Delivery Vehicle Routing Problem
DPT
Desired Pickup Time
DSM
Dispatching Strategy Model
EDT

Estimated Delivery Time
Free-DS
Free Dispatching Strategy
GPS
Global Positioning System
G-RM-FM-I
Generalized Regret Monitoring with Fading Memory and Inertia
IAP
Initial Assignment Phase
IO
Input/Output
ITS
Intelligent Transportation Systems
IU
In-vehicle Unit
LISS
Limited Information Sharing Strategy
LM
with Local Mediation
LOS
Level of Service
LPP
Local Planning Phase

xvi

MA
Multi-Agent
MA
3


Multi-Agent Assignment Algorithm
MA-DS
Multi-Agent based Dispatching Strategy
MA-DS-BC
Multi-Agent based Dispatching Strategy considering Booking
Cancellations
MCWT
Maximum Customer Waiting Time
NBTS
Non-Booking Taxi Service
NE
Nash Equilibrium
Non-Coop-DS
Non-Cooperative Dispatching Strategy
OD
Origin-Destination
OR
Occupancy Rate
PDPTW
Pickup and Delivery Problem with Time Windows
PI
Performance Indicator
SAC
Select-A-Customer
SAP
Spatial Adaptive Play
Sep-DS
Separate Dispatching Strategy
SNM

Simulation Network Model
SQ
Sequence Queue
TCNP
Taxi-Customer Negotiation Process
TCSM
Taxi-Customer Searching Model
TP
Taxi Pools

xvii

TSM
Taxi Service Model
UBK
Number of Unsuccessful Booking
UML
Unified Modeling Language
VTAP
Vehicle-Target Assignment Problem
WLAN
Wireless Local Area Network
WLU
Wonderful Life Utility

xviii

List of Symbols

t

A point of time
A(t)
the set of all possible decision profiles
A
i
(t)
the set of waiting customers that can be reached by VT
i
(t)
A
-i
(t)
the set of all possible a
-i
(t)
α
the probability of the true mean not lying within the confidence
interval
a(t)
the decision profile of all taxi agents at time t
a
i
(t)
the decision of the taxi agent of VT
i
(t)
a
-i
(t)
the set of decisions of all taxi agents except the one of VT

i
(t)
a
*
(t)
the decision profile in Nash Equilibrium (NE)
ABC
i

the Advance Booking Chain (ABC )of the taxi agent ta
i

ABK*
the ABK that a taxi agent ta
i
just receives from the dispatching center
ABK
i
m

the m
th
ABK in ABC
i

AWT
cb

the Anticipated Waiting Time (AWT) of cb
B

i

the belief of taxi agent ta
i

BQ
i

the i
th
Booking Queue (BQ)
CB
the set of customer bookings

xix

cb
i

the i
th
customer booking in CB
CBK*
the CBK that a taxi agent ta
i
just receives from the dispatching center
1%
CI




(1- α%) confidence interval for the true mean
DC
i

the i
th
Dispatching Controller (DC)
D
i

the desire of taxi agent ta
i

ε
the random error
E
the set of links (road segments)
ET
j
(t)
the set of vacant taxis engaged WC
j
(t)
G
road network
I*
mediated intention of taxi agent
I
i


the intention of taxi agent ta
i

LA
i

the i
th
logical area
rep
N

the number of simulation repetitions
P
j

the preference (probability) of the customer in booking taxis of
operator j
*ABK
p


the pickup location of ABK*
*ABK
p


the delivery location of ABK*
*CBK

p


the pickup location of CBK*
*CBK
p


the delivery location of CBK*
,im
p


the pickup location of ABK
i
m


xx

,im
p


the delivery location of ABK
i
m

ρ
a parameter in the calculation of D

i

S
j

the market share of the operator j
sd
the standard deviation
TA
the set of taxi agents
ta
i

the i
th
taxi agent in TA
(1 /2), 1
rep
N
t



the Student’s t-statistic for the probability of a two-sided error
summing to α with (N
rep
- 1) degrees of freedom
*
DPT
ABK

t

the Desired Pickup Time (DPT) of ABK*
,
DPT
im
t

the Desired Pickup Time (DPT) of ABK
i
m

,
EDT
im
t

the Estimated Delivery Time (EDT) of ABK
i
m

t
j,0

WC
j
(t)’s arrival time at the taxi stand
T
0


the customer’s queuing time at the taxi stand before booking a taxi
T
max

the maximum time the customer can wait at the taxi stand
O
i
T

the number of occupied hours of the i
th
taxi
T
i

the total service hours of the i
th
taxi
V
i
T

the empty cruising hours of the i
th
taxi
TP
i

the i
th

Taxi Pool (TP)
TP
i
*

the set of available taxis (i.e., taxis in free state) in TP
i

TS
the set of all taxi stands

xxi

TS
j

the i
th
taxi stand in TS
TS*
the Tabu set
U
g
(a(t))
the global utility corresponding to a(t)
( ( ))
i
VT
U a t


the utility function of vacant taxi VT
i
(t) with the decision profile a(t)
( ( ))
j
WC
U a t

the utility function of waiting customer WC
j
(t)
V
the set of nodes(junctions)
V
k

the k
th
node in V
VT(t)
the set of vacant taxis at time t
VT
i
(t)
the i
th
vacant taxi in VT(t)
W
i


the waiting time of the i
th
customer
WC(t)
the set of waiting customers at time t
WC
i
(t)
the i
th
waiting customer in WC(t)