高度道路交通システムにおける情報伝送、ユーザ体
験および持続性の研究
メタデータ

言語: English
出版者:
公開日: 2019-06-25
キーワード (Ja):
キーワード (En):作成者: チョウ, ジョウ ホウ
メールアドレス:所属:

URL

https://doi.org/10.15118/00009911

Transmission Performance,
User Experience, System Sustainability
in Urban Intelligent Transportation
SystemChaofeng Zhang
Department of Information and Electronic Engineering
Muroran Institute of Technology

This dissertation is submitted for the degree ofDoctor of Philosophy of Computer Science and Engineering

March 2019

Declaration

I hereby declare that this thesis is my own work and effort and that it has not been submitted
anywhere for any award. Wherever contributions of others are involved, every effort ismade to indicate this clearly, with due reference to the literature, and acknowledgement ofcollaborative research and discussions.
Chaofeng Zhang
March 2019Acknowledgements

Firstly, I would like to express my sincere gratitude to my advisor Prof. Mianxiong Dongand Prof. Kaoru Ota for the continuous support of my Ph.D study and related research, fortheir patience, motivation, and immense knowledge. Their guidance helped me in all thetime of research and writing of this thesis. I could not have imagined having a better advisor
and mentor for my Ph.D study.
Besides my advisor, I would like to thank the rest of my thesis committee: Prof.Jay
Kishigami, and Prof. Kazuhiko Sato, for their insightful comments and encouragement, butalso for the hard question which incented me to widen my research from various perspectives.
My sincere thanks also goes to Prof. Ota Kaoru, and Prof. He Li, who provides very
valuable advice for my daily research as well as spiritual encouragement. Without they
precious support it would not be possible to conduct this research.
I would like to acknowledge the financial, academic and technical support of the MuroranInstitute of Technology, Japan. The Department of Information and Electronic Engineering
has provided the support and equipment I have needed to produce and complete my thesis. I would also like to acknowledge the financial support and warm regards from China
Scholarship Council as well as Embassy of China, Japan, which has been with me for three
years.
Last but not the least, I would like to thank the lab members: Mr. Liangzhi Li, Miss.
Wuyuzhaola, Mr. Jianwen Xu and Miss. Caijuan Chen, for technical support and spiritualencouragement throughout this research and my life in general. I hope all the team members
can get the degree they desired.
Chaofeng Zhang
March 2019Abstract

ITS (Intelligent transportation system) is a modern way of urban transportation management.
By improving road throughput, managing traffic, and enhancing human mobility, it can
improve the service performance of urban transport networks in a holistic way. Ultimately,
through better traffic management, congestion can be slowed and traffic safety improved.
The large-scale deployment of ITS is very meaningful, which can greatly affect all aspects ofurban life. The traditional means of traffic management can not deal with real time traffic
management very well. The advanced ITS, in keeping with the times, is the integration of asmuch IoT as possible (Internet of Things) equipment, for the human to provide new service
experience.
Recently, the spectrum band beyond 60GHz has attracted attentions with the growthof traffic demand. Previous studies assumed that these bands are not suitable for vehiclecommunications due to the short range and high rate of blockage. However, it also means
there is no existing service or regulation designed for these bands, which makes this area
free to apply. One purpose of this study is to construct an applicable map of 0.1-1 THz
supported autonomous vehicle system through the study of channel capacity, autonomous
relaying and self-driving. For sending a large volume of data, the vehicles keep a gigabit
level link through line of sight channels, which share information about traffic condition andcaptured videos for further processing. The full use of this research can significantly improve
the performance of autonomous driving. A brief overview of possible waveforms followedby specific channel characteristics in 0.1-1 THz band is discussed and an autonomous relay
system for the gigabit road communication is presented. At last, we describe how the highrate short-range communication helps complement extra data to support the advanced new
self-driving technologies.
To improve the user experience, taxi sharing service aims to share the taxi resource
efficiently between passengers with specific relevant plans. However, due to the lack ofsocial interactions, it is hard to improve user experience without considering passengers’
inner connections. To overcome this problem, we propose a cloud-based taxi-sharing system,
which provides real-time taxi sharing services both considering the practical travel needs and
QoS in the journey. The purpose of this service is to minimize the travel cost through sharing

viii
calculated schemes reasonably and quickly and improve the sharing experience as much as
possible. We model the citywide level map into blocks and indexed, in order to search forthe potential paths of ride-sharing dynamically and intelligently. Meaning while, we explore
the paths among communities to find suitable companions as well. Finally, synthesizing thesuggestions of edge exploration on road network and social network, we design a heuristic
algorithm called SONETS to achieve the designing goal and make a real deployment. As
well as the establishment of the mobile application and online service, we also conduct alarge-scale simulation to evaluate the performance with others. The result shows that the
proposed solution could make the whole taxi-sharing system less calculation complexity,
higher sharing QoS, and most of all, keeping the minimum cost of travel cost within 1.16%
increment than distance optimal algorithms.
To keep the sustaibility of urban ITS, we also investigate the maintenance of city-wide
sharing pedelecs, which apply battery-powered motor to assist pedaling and significantly
extend the riding coverage. The large scale deployment of pedelecs, however, requires acareful design of maintainance system to replace the batteries of pedelecs regularly, which
can be very costly. This study develops an optimal path planning scheme for replenishment
trucks based on big data analytic and prediction. To the best of our knowledge, we are the firstto use the systematic methodology of Analysis/Modeling/Test to advance the bike prediction
process using the captured datasets, and conduct the hybrid prediction process learns internal
connections between different dataset dimension as well as optimize the overall maintenanceefficiency.

Table of contents
List of figures

xiii

List of abbreviations

xv

1

Introduction
1.1 Background and Motivation . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1 Transmission Performance of Spectrum Availability in Urban ITS .
1.1.2 User Experience using Taxi Sharing in Urban ITS . . . . . . . . . .
1.1.3 System sustainability about E-bike sharing in urban ITS . . . . . .
1.2 Purpose of This Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Originalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Main Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
1
2
2
3
4
6
7
9

2

Fundamentals and Related Work
2.1 Terahertz Band for Self-Driving ITS . . . . . . . . . . . . . . . . . . . . .
2.1.1 Terahertz Communication Model . . . . . . . . . . . . . . . . . .
2.1.2 Terahertz Autonomous Relay . . . . . . . . . . . . . . . . . . . .
2.1.3 Terahertz Autonomous Driving . . . . . . . . . . . . . . . . . . .
2.2 Taxi Sharing for Social Improvement . . . . . . . . . . . . . . . . . . . . .
2.2.1 Urban Taxi Sharing . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 Social Network . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 E-bike Sharing for Green ITS transportation . . . . . . . . . . . . . . . . .
2.3.1 Traffic Flow Prediction . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Traffic Maintenance Service Optimization . . . . . . . . . . . . . .

11
11
11
12
12
14
14
14
16
16
16

3

Breaking the Blockage for Big Data Transmission
3.1 Communication Model . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Impulse radio waveform . . . . . . . . . . . . . . . . . . . . . . .

19
20
20

x

Table of contents
3.1.2 Channel Capacity . . . . . . . . . . . . . . . . . . . . . . . . . . .
Terahertz Autonomous Relay . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 ATLR Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2 Autonomous Multiple Relaying . . . . . . . . . . . . . . . . . . .
Enhanced Autonomous Driving . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . .
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20
23
23
25
25
25
27

4

Social Taxi Sharing
4.1 Sharing Service Design . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 System Demand . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.2 System Structure . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Map Processing for Cities and Users . . . . . . . . . . . . . . . . . . . . .
4.2.1 Map Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2 Index of Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.3 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.4 Sharing Social Communities . . . . . . . . . . . . . . . . . . . .
4.2.5 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Social Network based Scheduling . . . . . . . . . . . . . . . . . . . . . .
4.3.1 Bidirectional Taxi Searching Algorithm . . . . . . . . . . . . . . .
4.3.2 Temporary Passenger Detection and Adding Algorithm . . . . . . .
4.3.3 Social Network based Heuristic Algorithm . . . . . . . . . . . . .
4.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29
30
31
31
33
33
36
38
41
46
46
47
49
52
55
64

5

Battery Maintenance of Pedelec Sharing System
5.1 System Model and Overview . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1 Impacts of Urban Data on Station Usage . . . . . . . . . . . . . . .
5.1.2 Structure of Scheme . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Hybrid Prediction Model . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1 Local Predictor . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.2 Global Predictor . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.3 Inflection Predictor . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.4 Prediction Integrator . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Pedelec Maintenance Optimization Algorithm . . . . . . . . . . . . . . . .
5.3.1 Less Incompatible Maintenance Map . . . . . . . . . . . . . . . .
5.3.2 Reduced Dynamic Replenishment Optimization Problem . . . . . .

65
67
67
68
70
70
71
73
77
79
80
81

3.2

3.3
3.4

Table of contents
5.3.3 Intelligent Maintenance Optimization Algorithm . . . . . . . . . .
Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.1 Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.2 Accuracy of Predictor . . . . . . . . . . . . . . . . . . . . . . . .
5.4.3 Results Comparisons of IMOA . . . . . . . . . . . . . . . . . . . .
5.4.4 IMOA using Different Bikes . . . . . . . . . . . . . . . . . . . . .
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82
84
84
85
87
89
91

Conclusion and Future Work
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.1 Next-generation vehicle networking technology using Thz . . . . .
6.1.2 User-oriented taxi sharing service using social network . . . . . . .
6.1.3 Efficiency-oriented maintenance service using AI prediction . . . .
6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

93
93
93
94
94
94

5.4

5.5
6

xi

References

97List of figures
1.1
1.2
1.3

Pedelec’s share system, structure and battery maintenance . . . . . . . . . .
No line of sight data sharing through terahertz vehicle networks . . . . . .
Social network community structure applied in taxi sharing service . . . . .

3
4
6

2.1
2.2

Supplement of NLOS (no line of sight) traffic information . . . . . . . . .
Number of bikes and stations . . . . . . . . . . . . . . . . . . . . . . . . .

13
15

3.1
3.2
3.3
3.4

The Hann pulse waveform for four values in THz Band . . . . . . . . . . .
Capacity for three different power spectral densities . . . . . . . . . . . . .
An example of autonomous terahertz level relay algorithm (ATLR) . . . . .
Precision comparison in autonomous driving . . . . . . . . . . . . . . . . .

21
22
24
27

4.1 Structure of the social network based taxi sharing service . . . . . . . . . .
4.2 Muroran map divided into blocks . . . . . . . . . . . . . . . . . . . . . . .
4.3 Muroran map contains extended blocks . . . . . . . . . . . . . . . . . . .
4.4 One cover contains several blocks . . . . . . . . . . . . . . . . . . . . . .
4.5 Formulate the blocks by index . . . . . . . . . . . . . . . . . . . . . . . .
4.6 The index of a block . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.7 Routes begin from original point to each passenger’s destination . . . . . .
4.8 Structure of the social network community . . . . . . . . . . . . . . . . . .
4.9 A tree structure of social network . . . . . . . . . . . . . . . . . . . . . . .
4.10 Find the high betweenness edge . . . . . . . . . . . . . . . . . . . . . . .
4.11 Move them and recalculate the shortest path . . . . . . . . . . . . . . . . .
4.12 Separate the community . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.13 Searching for the nearby taxis from start point . . . . . . . . . . . . . . . .
4.14 Searching for the nearby taxis from start side and destination side . . . . .
4.15 Searching for the taxi through block intersection . . . . . . . . . . . . . . .
4.16 An example that adding new passenger to the exiting travel plan . . . . . .
4.17 Double path searching on the real map and social network map . . . . . . .

32
34
35
36
38
39
40
42
42
44
45
45
48
48
50
51
53

xiv

List of figures
4.18 Screen shots of an experiment in designed application (A) . . . . . . . . .
4.19 Screen shots of an experiment in designed application (B) . . . . . . . . . .
4.20 Different measurements changed by number of taxis . . . . . . . . . . . .
4.21 Different measurements changed by different time window . . . . . . . . .
4.22 Saved cost (economic benefit) Comparison . . . . . . . . . . . . . . . . . .
4.23 (Saved cost / Actual cost) Expense Efficiency Comparison . . . . . . . . .
4.24 Average number of riders . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.25 Performance about close community members . . . . . . . . . . . . . . . .

56
57
58
58
61
61
62
63

5.1 Preliminaries for bike sharing records (A) . . . . . . . . . . . . . . . . . .
5.2 Preliminaries for bike sharing records (B) . . . . . . . . . . . . . . . . . .
5.3 The framework of the pedelec maintenance system . . . . . . . . . . . . .
5.4 An example of BSRC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 Structure for prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6 An example of sudden change interval and decision making tree . . . . . .
5.7 An example of less incompatible maintenance map . . . . . . . . . . . . .
5.8 Local predictor using citywide big data . . . . . . . . . . . . . . . . . . . .
5.9 Comparison of different prediction model . . . . . . . . . . . . . . . . . .
5.10 Performance of four strategies by different settings . . . . . . . . . . . . .
5.11 Performance of battery replacing demand . . . . . . . . . . . . . . . . . .

66
67
69
74
75
78
80
86
86
88
90

List of abbreviations
Acronyms / Abbreviations
2D

Two-Dimensional space

3C

Computing, Communication and Control

3D

Three-Dimensional space

ACO Ant Colony Optimization
ANN Artificial Neural Networks
ATLR Autonomous Relay Algorithm
BSRC Bicycling Sharing Radar Cross ModelCO

Cost-Optimized Algorithm

CPS

Cyber-Physical System

DSRC Dedicated Short Range CommunicationsDTN Delay-tolerant networking
GA

Genetic Algorithm

GBit Gigabit
GPS

Global Positioning System

HD

High-Definition

IFFT Inverse Fast Fourier Transform
IMOA Intelligence Sharing Bike Maintenance Optimization Algorithm

xvi

List of abbreviations

IoV

Internet of Vehicles

IR

Impulse RadioITSIntelligent Transportation System

LiDAR Light Detection and Ranging
LOS Line of Sight
MAC Media Access Control
mmWave millimetre Wave
NLOS No Line of Sight
NYC The City of New YorkPC

Personal Computer

Pedelec Pedal electric cycle
POMDPs Partially Observale Markov Decision Processes
PSBL Intelligent Transportation System
QoE

Quality of Experience

QoS

Quality of Service

RCP Raised-Cosine Pulse
SONETS Social Network based Heuristic AlgorithmThzTerahertz

TSP

Traveling Salesman Problem

UAV Unmanned Aerial Vehicle
V2V Vehicle to Vehicle

Chapter 1
Introduction
1.1

Background and Motivation

ITS (Intelligent transportation system) is a modern way of urban management, mainly contains advanced information technology, communication technology, sensing technology,
control technology and computer technology. By improving road throughput, managing traffic, and enhancing human mobility, it can improve the service performance of urban transport
networks in a holistic way. Ultimately, through better traffic management, congestion canbe slowed and traffic safety improved. The new generation of mobile devices also brings a
better way of user interaction, from the user’s point of view to enhance the overall service
experience.
Its large-scale application is very meaningful, and it can greatly affect all aspects of urban
life. First, it can reduce the growing traffic jams. Traffic jams can cause some problems,
including environmental pollution,Increased energy consumption and the feasibility of ascheduled plan. Second, it can reduce the probability of traffic accidents by driving assistancesystems. Because about three-fourths of traffic accidents are caused by human error. Finally,
it reduces the transport burden on each line, thus maximizing the overall throughput of thetransport network
The traditional means of traffic management can not deal with the above problems very
well. Simple restrictions on travel will bring great inconvenience to people, and building newroads is time-consuming and laborious. And some traffic aids, such as cameras, GPS (Global
Positioning System) and microwave detectors, they play a very limited role.
ITS, in keeping with the times, is the integration of as much IoT as possible (Internet ofThings) equipment, for the human to provide new service experience. For example, by the
analysis and induction of vehicle trajectory, we can optimize the driving path. Through the
tracking, identification and density analysis of vehicles, we can analyze and extract special

2Introduction

road conditions. The addition of artificial intelligence provides new technical support for
automatic driving and traffic signal recognition.

1.1.1

Transmission Performance of Spectrum Availability in Urban ITS

The fast growing demand for vehicle communications has raised the importance of spectrum
availability, which is used for data creation, sharing, and consumption. With this trend, each
mobile cell has to keep 10-GBit transmission rate around the year of 2020 [31]. Some alreadywell designed and researched communication systems applied in 60GHz may be theoreticallycompatible with more than 0.1-THz bandwidth. However, it is difficult to establish a stableand efficient link due to the greater attenuation in vehicle communications. A couple ofresearch groups all around the world have started to investigate the abundant spectrum
resource to be operated beyond 300-GHz, the so-called THz communication systems [11].
With the advanced physical layer solution realized in the future, the new spectral bands can beutilized on Internet of Vehicles (IoV) [21], which lays the foundation for the challenges dueto the explosive growth of autonomous vehicles’ data transmission, sharing and consumption.

1.1.2

User Experience using Taxi Sharing in Urban ITS

New styles of public resource management emerge due to the development of smart devices,which significantly enhance the quality of citizens’ life. Online taxi sharing is one potential
solution for public transportation, which aims to solve the problem of limited taxi resourcein citywide. The main advantage of this service is that it relieves the pressure on thetransportation and improves the quality of user experience [59]. In an online taxi sharing
service, the system provides more sharing opportunities and gives out better routes throughthe interactions of the smart device’s interface. Since the service is provided in real time andthe sharing is also a green transportation style, this taxi sharing management problem has
already generated much interesting in both academy and industry in recent years [2].
Some general studies have already put forward achievements in this service: mobile-cloudarchitecture based taxi-sharing system makes it feasible to satisfy the request of consumers
with minimum increase of travel distance, where a dynamic spatiotemporal index based taxi
routing algorithm is used to find the solution[43] [16], where exists a coordination problem
between car capacity, precedence and user constraints. Generally, traffic congestion andenvironmental concerns are the main advantages that inspire consumers to use taxi sharing
services [8]. However, some potential problems still prevent people from experiencing theservices if we ignore passengers’ special needs [54]. For example, many countries haveto set priority seat and the non-smoking area in urban transportation to fulfill passengers’3

1.1 Background and Motivation

particular needs; The difference in the opposite sex and the strangeness of passengers makethe oppressive atmosphere much like a bus ride. Moreover, if considering the coordination
between consumers, the differences of departure time and destination are the reasons why
most of the sharing agreements cannot be satisfied. The waste of waiting time and thedivision of trip costs make the sharing arrangement hard to establish.

1.1.3

System sustainability about E-bike sharing in urban ITS

Bike-share has recently become a rising trend worldwide as the last-mile solution in cities
from the bus/subway station to home[53]. In a bike-sharing system, riders can use theirsmartphones to locate and use a shared bike available in the nearby. When finish riding,riders can either return the bikes to a bike station or merely leave bikes on the roadside until
the next rider.

(a) Pedelec is stored at the roadside stations(b) One pedelec contains the components of thebattery, console, controller, and motor(c) The maintenance truck stops at the roadsideto provide battery exchange service(d) The installation and removal of the battery
are less than 10 seconds

Fig. 1.1 Pedelec’s share system, structure and battery maintenance
An issue of the legacy bikes is that people can quickly get tired, especially in windy
weather or on steep roads, making the service coverage of sharing bikes limited to about 2km.
Pedelec is a new type of e-bike to solve this issue. The pedelec applies a battery-powered
motor to assist the pedaling as in Fig. 1.1 and accordingly saves the energy of riders. Whenthe pedalling speed is above a reasonable speed (e.g., 25 kilometres per hour), indicating a

4Introduction

Fig. 1.2 No line of sight data sharing through terahertz vehicle networks
smooth and pleasant ride, the pedelec bike cuts off the electric power to save its energy. As aresult, pedelec can extend the ride range to 5km and completely replace vehicles as the last
mile solution.

1.2

Purpose of This Study

The purpose of this study is to improve the transmission performance, user experience andsystem sustainability in urban intelligent transportation systems.
To improve the transmission performance, we construct an applicable map of 0.1-1 THz
supported autonomous vehicle system through the study of channel capacity, autonomous
relaying and self-driving. Fig.1.2 is an example of data sharing scenario through terahertz
band. For sending a large volume of data, the vehicles keep a gigabit level link throughline of sight channels, which share information about traffic condition and captured videos
for further processing. If we can overcome the fading issues, the full use of this research
can significantly improve the performance of autonomous driving. At first, the motivations
from the existing technologies applied in autonomous vehicles need be fully discussed andthen a brief overview of possible waveforms should be investigated followed by specificchannel characteristics in 0.1-1 THz band. Discussions about the platform and throughput indeveloping technology and demonstrator are also given. An autonomous relay system forthe gigabit road communication will be presented next and we also need to describe how thehigh-rate short-range communication helps complement extra data to support the advanced
new self-driving technologies, where all the above problems should be fully discussed.

1.2 Purpose of This Study

5

To improve the user experience, we develop a new social network based taxi sharing
system. Although some constraints dismiss consumers’ idea of sharing, people still frequently
share their trip with whom are in their social connections [13]. As social network is partly
based on real-world relationships (family, colleague), passengers are more likely to trust
the companions if the relationship is based on the social network rather than some purely
online services (second life, online games, etc.) [6]. The connections among them are
more reliable than complete strangers. Therefore, in this thesis, we analyze to discover
one of the various properties in social networks, the community structure. When looking
for suitable travel companions on the map, the social community structure could provide
suggestions about potential passengers in close communities. The proposed method to build
the social communities is clustering. However, the difference with previous studies is thatthe connections of vertexes in one community are dense, while the interactions between
communities are much sparse [46][6]. In Fig.1.3, it shows an example of a social network
community structure after the analysis. This partitioning method for social networks has
efficient meaning to detect the communities. For instances, the communities being mined may
share the same social groups in the real world, or some common interests and backgrounds;
Research areas often separate communities in schools, and in e-mail based communication
networks are often separated by different companies; Since taxi sharing is an opportunitythat all passengers sit in a small space, the companions in the same or close communities
are more reliable than strangers. It is more likely to improve the interactions between eachother, and most of all, to make the social connections tiger, which could naturally improve
the QoS (quality of services) during the journey as well as other intangible benefits [29]. In aword, identifying the communities in local social networks can help the system discovery
and understand the properties of passengers, and further improve the ride-sharing experiencethrough throughout arrangement.
To improve the system sustainability, we investigate the E-bike sharing system calledpedelec sharing. However, a key challenge of pedelecs is how to manage their batteries.
In specific, a fully charged battery in the pedelec provides power within 8 hours [38],and therefore, one pedelec may need to have its battery replaced for three times a day
when continually used to provide 24-hour service [44]. To keep the service of pedelecs,
replenishment trucks are driven across the bike sharing stations to change the batteries ofpedelec. Note that the efficiency of replenishment is not only key to the service quality of theentire pedelec system, but also determines the maintenance cost. This gives rise to the path
planning issue of replenishment trucks. The issue is a challenging task because that withdifferent locations and surrounding environments of bike sharing stations, pedelecs stored

6

Introduction

Fig. 1.3 Social network community structure applied in taxi sharing service
have very different battery usage, and within one station, pedelecs’s battery usage can also
be quite heterogeneous due to the wide service coverage and different riding history.

1.3

Originalities

To apply Thz transmssion in V2V (vehicle to vehicle) network, previous studies assumed thatthese bands are not suitable for vehicle communications due to the short range and high rateof blockage. However, it also means there is no existing service or regulation designed forthese bands, which makes this area free to apply. Therefore, in this study, we draw a potential
map of terahertz vehicle transmission for autonomous vehicles to break the blockage of shortrange and unstable links. Firstly, we give a brief overview of possible waveforms followed by
the specific channel at 0.1-1 THz. Then, we propose an autonomous relay algorithm called
ATLR for the gigabit level communication in the high-speed road environment. Finally, we
discuss how the gigabit links help relieve interference problem and provide extra data to
support various instructions in autonomous vehicles.
To apply social network into taxi sharing, the service we developed aims to share the taxi
resource efficiently between passengers with specific relevant plans. However, due to the lackof social interactions, it is hard to improve user experience without considering passengers’1.4 Main Contribution

7

inner connections. In this study, we introduce the social network community detection
method into the allocation of online taxi sharing service. We propose an optimization
scheme integrates social interaction to improve the sharing efficiency and user experience,by handling the trade-off between cost and social interaction. Then, we state and solve
the sharing arrangement problem by computing a three-step algorithm called SONETS
which includes community detection, bidirectional taxi searching, and social network basedheuristic algorithm, in order to satisfy overwhelming requests with limited taxi resource inrush hour. A real-world based mobile application and simulation are conducted, using local
social network accounts. The results show that our service can fit well with the economic
demand and improve the QoS (quality of service), to achieve cost efficiency, fairness, andhumanized designing.
To discuss the system suitability, at last, we investigate the maintenance of city-wide
sharing pedelecs, which apply battery-powered motor to assist pedaling and significantly
extend the riding coverage. The large scale deployment of pedelecs, however, requires acareful design of maintainance system to replace the batteries of pedelecs regularly, which
can be very costly. This study investigates the issue by developing an offline solution in
two steps. First, an optimal and efficient hybrid predictive prediction model, combining
the future usage increment from local predictor, global predictor and inflection predictor, isdeveloped to improve the prediction accuracy. The developed approach can predict the usage
demand in every 48 hours on a scale of millions of pedelecs. Second, based on the result of
big data analytics developed, an optimal path planning scheme for the replenishment trucks
is developed. As compared to other schemes, our IMOA can save 40% of cost. To verify our
proposal, extensive real-data driven simulations are performed which show that the accuracyof the prediction process is high enough then each traditional method and IMOA solves themaintenance problem efficiently.

1.4

Main Contribution

The main contribution are discussed as following:
1. Impulse waveforms are discussed in this paper due to the fine multipath and fading
environments. It enables precise ranging and data transmission using IEEE 802.15.4a.
These features are indispensable for autonomous system, which makes the motivation
for us.
2. Relay algorithm helps to improve the quality of real-time multi-hop links, by using embedded sensors to monitor the whole candidate space. It handles the channel

8Introduction
condition and road presentation accurately, and leverages the relative position efficiently. After the position adjustment of autonomous vehicles, the terahertz channel
can approach optimized performance.
3. Road simulation is conducted, with the scenario that our sports car cannot detect thetruck which is changing lane in the front. A decision of left-handed rotation from theautonomous driving system may put our car into a dilemma due to the lack of roadinformation.
4. Social network relationship is introduced into the taxi resource management when
limited taxi resource meets with the rush hour. The community structure of a social
network is taken into consideration when scheduling socially connected passengers in
one taxi.
5. Optimization problem is formulated and calculated using our proposed 3-step process,including community detection, real map taxi searching and social network basedheuristic algorithm called SONETS. It searches for an optimized solution to make acost efficiency, fairness, and humanized service designing.
6. Smart device application called ’Social Network Taxi Sharing’ is designed andapplied in the real environment. Furthermore, the large-scale simulation is deployedbased in citywide, using real user information and cartographic information.
7. Big data based prediction is used to develop an efficient offline prediction scheme
based on big data analytics. We use local predictor to analyze the characteristics of thestation itself, global predictor to analyze global correlations, and inflection predictor todeal with unexpected situations. An prediction integrator is used at last to improve theprediction accuracy.
8. Optimal path planning algorithm is developed here. Based on the predicted results,
we can analyse the degree of correlation between stations in real time. After making astation correlation map, a new pedelec maintenance algorithm is developed.
9. Evaluation and verification is conducted here. We select NYC’s shared bicycle
data and city-relevant big data for real simulation experiments. After comparison ofprediction accuracy, real-time average power and overall service quantity, it is provedthat our solution is superior to most benchmark algorithms.

1.5 Organization

1.5

9

Organization

This dissertation is organized in the following: Chapter 2 discusses the fundamental problems
and studies about ITS, including communication issues, cost issues and efficiency issues.
Chapter 3 discusses how to solve the performance issue in urban ITS, where the nextgeneration vehicle networking technology using Thz is conducted here. Chapter 4 proposes areal time and real environment solution to meet with the experience issue in urban car sharing
services, where the user-oriented taxi sharing service using social network is consideredin this study. Chapter 5 introduces the efficiency-oriented maintenance service using AI
prediction, to show a comprehensive solution how to deal with the sustainability issues withthe development of urban ITS. Finally, Chapter 6 is related to conclusion and future work.

Chapter 2
Fundamentals and Related Work
This chapter describes some fundamentals and related works that will be used in this study.
The chapter introduces the fundamental studies about the urban ITS system, concluding terahertz supported self-driving system, urban taxi sharing system and green ITS transportation,
respectively.

2.1

Terahertz Band for Self-Driving ITS

2.1.1

Terahertz Communication Model

Terahertz band communication is envisioned as a key wireless technology to satisfy thedemand of data collection in autonomous vehicles, by alleviating the spectrum scarcity andcapacity limitations of widely used 4G or future 5G networks. Meanwhile, it motivatesthe potential of existing applications in vehicle technologies. The THz band is generally
considered as the spectral band that spans the frequencies between 0.1 and 10 THz. Frequency
regions below and above this band have been fully investigated: Spectral band below 0.1 THz(known as the microwave) is not available to support gigabit level links [65] while the spectral
band beyond 10 THz has too many constraints to realize a feasible optical approach formobile wireless communications. Therefore, the THz band is still one of the least explored
frequency bands for communication. There are many challenges in the realization of efficientand practical THz band communication networks, which is related to the development ofinnovative solutions in the different layers. The solutions overcome the challenges in mmWave systems can also be utilized in terahertz band, which bring enough bandwidth forgigabit level transmission. Impulse waveforms are discussed in this paper due to the finemultipath and fading environments. It enables precise ranging and data transmission using

12

Fundamentals and Related WorkIEEE 802.15.4a. These features are indispensable for autonomous system, which makes the
motivation for us.

2.1.2

Terahertz Autonomous Relay

Autonomous relaying technologies can be discussed to solve the capacity and feasibility
problem mentioned above, but there are still several disadvantages for the real application.
First, the range of terahertz band is relatively shorter than existing wireless technologies
such as Wi-Fi and 4G technologies. The attenuation of transmission distance is muchhigher than longer waves and the antenna array is also not completely developed. Next, theobstacles can easily block terahertz waves, which is similar with mm-Wave. Furthermore,
the molecular absorption such as water vapor molecules can affect the channel performance
more significantly [3]. To overcome the disadvantage mentioned above, vehicle relays canbe applied to form Ad hoc networks or delay tolerant networks (DTN) among autonomousvehicles. These networks can bypass the obstacles such as barriers or constructions andextend the communication links to other vehicles which are out of the shorter terahertz
communication range. The autonomous vehicles are more suitable than man-driven vehicles
since the minor position adjustment can be made to achieve better multi-hop performance.
Here, we propose an autonomous terahertz relay (ATLR) algorithm to determine the relaying
position. This algorithm helps to improve the quality of real-time multi-hop links, by using
embedded sensors to monitor the whole candidate space. It handles the channel condition
and road presentation accurately, and leverages the relative position efficiently. After the
position adjustment of autonomous vehicles, the terahertz channel can approach optimized
performance.

2.1.3

Terahertz Autonomous Driving

Autonomous driving in up-to-date studies mainly focuses on ’correctness’, such as assuming
driving operations are prescribed in advance as functions of time or state of the system, which
can never be proven that autonomous vehicles are superior to human drivers [36]. Althoughpredictive controls such as decision trees, partially observable Markov decision processes(POMDPs), and methods based on multi-policy decision-making are fully discussed, the lackof fully collected data prevents these control systems from the real deployment. For example,
Line of sight (LOS) image data, self-positioning coordinates collected by one vehicle’s
sensors sometimes are inaccurate and needed further calibration. Instead, with the constanthigh-speed channels, the autonomous control system can make the decision depending on
added invisible information, calibrated cooperative positioning and traffic condition of the2.1 Terahertz Band for Self-Driving ITS

13Fig. 2.1 Supplement of NLOS (no line of sight) traffic information for autonomous decisionmaking system
whole city. Fig.2.1 is an example of autonomous driving supported by additional traffic
information. Because of the huge truck ahead, our sports car cannot detect the truck which ischanging lane in the front. A decision of left-handed rotation from the autonomous driving
system may put our car into a dilemma due to the lack of road information.
Nowadays, image recognition is important for human-like driving systems, but researchers only use the RGB data collected by individual sensors. Terahertz band cansatisfy the requirement of constant high-rate video data transmission. This mean provides
the dead zone image data or even computation capability through cloud service linked RSUs
(Road-Side Unit) [32]. Traffic information is captured by the onboard sensors or othervehicles. With the added data provided by other vehicles, we conduct and discuss the impact
of terahertz band for autonomous driving systems.

14

Fundamentals and Related Work

2.2

Taxi Sharing for Social Improvement

2.2.1

Urban Taxi Sharing

Taxi sharing comes into notice by researchers in the field of city resource management,
especially for the environment concerning. Most of the studies are concentrated on how
to save cost for passengers or improve the revenue for drivers, by endeavoring on thecoordination of travel plans. For example, Huang analyzes the Shanghai and Hunan pricelinkage mechanisms for taxi services [26]. By advocating the efficient fuel usage of taxis,
they find it useful for local governments to reduce the financial burden, which leads to thecleaner environment. They also consider one main problem in taxi sharing is how to build areasonable schedule to save fare and time. Another innovative taxi sharing service in Chen’s
study [6] is that the system searches for passengers whose destinations are close enough inorder to reduce the number of activated taxis. They implement a dynamic taxi-sharing systemcalled Intelligent Transportation Systems (ITS), which decreases the total number of activatedtaxis efficiently and leads to the saving of fuel. Besides, Chen proposes a recommendation
mechanism for taxi-sharing [10], which has the feature of lower taxi reaction time and cost.
A non-cooperative game theory is used in that paper for selecting taxis in the same area, andfinally, the solution is completed by the Nash equilibrium. Especially, considering both theprofit of driver and quality of experience (QoE) for passengers, Zhang propose a QoS-aware
taxi-sharing system with appealing the above two challenges [62]. By monitoring theserequirements and dynamically adapting the schedules, they design a heuristic algorithm
under acceptable delay, and it satisfies the needs of a large number of taxis. However, theseworks all assume passengers are willing to share all the time and have no extra demand fortheir companion, which is the lack of personalized customization. It may prevent the real
deployment.

2.2.2

Social Network

Social Network relationship is introduced to improve the quality of taxi services. However,since social network is a weak relationship network, quantizing the abstract social network
connection is hard. By researching different structure of social networks, Zhang concludes
a novel model to describe the relationship strength between the different account of social
network [61]. They find that it will be little impact on the information interaction if ignoring
weak connections in social networks. On the opposite, the strong connections will create astrong influence on the dissemination of information, which brings more social interaction.
Instead, if we could find communities on the map, the members sit together will be much

2.3 E-bike Sharing for Green ITS transportation

15

Fig. 2.2 Number of bikes and stations in NYC bike sharing is increasing year by year
easier to achieve the pleasant journey. Never than less, in real life, many social network
communities are created by geographically closed people. For recommending social network
friends who are geographically close, [60] propose a three-step statistical recommendation
approach to create a GPS-enabled cyber-physical social network. Based on the experiment
data of real-life data, they clear the advantage of merging GPS data and social network.
The results show their novel method can bring extra social benefit in daily life using the
GPS-based cyber-physical social network. Therefore, if we apply the social network flexibly
in daily life, it could benefit the normal human social activities in an all-around way.
In a word, most of the above taxi sharing methods try to reduce travel cost and increase
drives’ benefit. However, none of them considers the passengers’ inner needs. Finding
an optimal tradeoff between cost and social benefit for passengers could increase the QoE
significantly. Different from the works above, we start this taxi sharing problem by road
network and social network processing, where we try to allocate passengers to improve theuser experience when traveling.

16

2.3

Fundamentals and Related WorkE-bike Sharing for Green ITS transportation

There are two main problems should be solved during our study, one is the traffic flow
prediction, and another is the bike maintenance service optimization. The traffic flow
prediction should enormously combine the big citywide data as much as possible, to fit wellwith the characters of a city and improve the prediction accuracy. Then, based on the reliablepredictive results, the system could analyze the inner connection between the outputs andmake a more efficient pedelec service system.

2.3.1

Traffic Flow Prediction

Traffic Analyzing and Prediction solves the traffic problem from new sights. Pan [51]detects and describes the sudden change of traffic using human mobility and social media.
Accidents, celebrations, disasters and the citywide events could result in a significant changeof traffic flows, and they detect these unusual changes based on drivers’ routing behaviors.
They develop a system that identifies the anomalies of driver’s routing behaviors basedon their regular patterns and representative terms on social media. Hoang [23] proposesa new planning method to describe the traffic flows in different regions. They use thecommon citywide big data, including human mobility, weather reports, and road networks.
three different categories of movement patterns are decomposed and analyzed by the system,
including periodic patterns, changes, instantaneous changes. Then, they use Gaussian Markov
Random Fields to exploit spatial-temporal dependence among different regions. Kong [33]propose a new estimation and prediction for traffic congestions using car trajectories. Theyuse a fuzzy comprehensive evaluation method to leverage the real traffic flow patterns. An
article swarm optimization algorithm is used to analyze this patterns and covert the inflection
state to congestion situations, and their claim the proposed method is accuracy, instantaneity,and stability. These methods are highly dependent on real-time data, which is similar to thispaper. However, their useful and customized predictions could not efficiently convert into
ordinary citizens’ cognitive services, which will be discussed deeper in this paper.

2.3.2

Traffic Maintenance Service Optimization

Maintenance Service Optimization is how to make the flexible use of sensed data andcollected information to improve the QoE. Torres [53] aims to improve the sustainability
and livability for the city and present a participatory sensing system called Becity to takethe advantages of the collective knowledge of transportation cyclists, to improve the QoEof cycling. By combining the city usage information, cycling associations and government

2.3 E-bike Sharing for Green ITS transportation

17

entities, the system provides bike routes with the shortest and accessible route, which is better
than Google Maps. To maintenance the damaged bikes and reduce costs, Yao [58] proposesa hybrid bike allocation schedule to balance the system load effectively. The bike-sharing
system in Washington D.C. is estimated, and their load-unbalance status could be reduced
since the proposed system could significantly cut down the percentage of the bikes need toreplace. Caggiani [5] discuss a multi-objective model to assist cyclists to keep lower travel
cost, air pollution, and road safety. The new optimization model uses geolocated real-time
data, which considering traffic congestions and flows, to select an optimal path and avoid air
pollution or more safety. Then, they set up the graphics interface to guide users follow thecurrent optimized path, and finally, result in the improvement of the cycling experience.
From these works we can find that, it is necessary to combine with real-time usage
information and other geographical information together, to improve the efficiency andquality of urban traffic services. Instead of using recently uploaded information to ’adjust’the original schedule and ’adopt’ new changes, our work aims to ’predict’ the future trend andmake a countermeasure at the beginning, which is more efficient and less risky comparing
with the ’problems occur then to be fixed’ model.

Chapter 3
Breaking the Blockage for Big Data
Transmission: Gigabit Road
Communication in Autonomous Vehicles
This chapter describes discusses how to solve the performance issue in urban ITS, where thenext-generation vehicle networking technology using Thz is conducted here.
The purpose of this paper is to construct an applicable map of 0.1-1 THz supported
autonomous vehicle system through the study of channel capacity, autonomous relaying andself-driving. For sending a large volume of data, the vehicles keep a gigabit level link throughline of sight channels, which share information about traffic condition and captured videos
for further processing. We believe the full use of this research can significantly improve
the performance of autonomous driving. The remaining part of this paper is organized asfollows:
In Chapter 3.1, we give a brief overview of possible waveforms followed by specificchannel characteristics in 0.1-1 THz band. Discussions about the platform and throughput indeveloping technology and demonstrator are also given. An autonomous relay system for the
gigabit road communication is presented in Chapter 3.2. In Chapter 3.3, we describe how thehigh-rate short-range communication helps complement extra data to support the advanced
new self-driving technologies. Chapter 3.4 provides conclusions and an outlook to future
research required in this area.

20

Breaking the Blockage for Big Data Transmission

3.1

Communication Model

3.1.1

Impulse radio waveform

A few number of waveforms are considered for terahertz band communication as the key
wireless technology to satisfy the constantly changing attenuation on the road. Impulse radio(IR) waveform is one of the suitable waveforms for vehicle communication, which takes
the advantage of detecting traffic condition and certain resistance with NLOS transmission[12]. The short pulse can reduce the interference of other radio frequency systems, when thegalloping vehicles have to cross by several static or mobile communication systems. In shortrange, the NLOS signal is obtained due to the relatively strong penetration of road obstacles.
The distortion and spurious signal detection is also reduced due to the multipath propagation.
In a word, the impulse radio waveform is suitable for terahertz band communications either
from capacity aspect or attenuation aspect.
Generally, carrierless waveforms such as IFFT pulse are used to realize vehicle positioning
technology or other traffic detecting technologies. Carrier waveforms such as raised-cosine
pulse (RCP) shape are used for data transmission. The basic shape is p(t) = h(t)cos(2π f t),
when h(t) could be Rectangular, Gaussian, Hann or Hamming pulse. In order to calculate thecapacity of this channel model, we analyze the frequency domain for this pulse first. Fig. 3.1
is the PSD (Power Spectral Density) of Hann pulse waveform using four different settings.
The frequency of the carrier wave fc is set as 0.3, 0.6, and 1 THz. The PSD of this pulse is
W ( f ) = Tp [1]sinc2πTp
1 − (2 f Tp )2(3.1)

where the duration Tp of pulse is 0.1 ns. From the figure we can observe that the available
bandwidth increases with the frequency of carrier wave. It is noticed that with the increaseof frequency, the width of the main lobe is also increasing. It broadens the analytical bandand frequency resolution becomes worse. Therefore, Higher frequencies are suitable for lessinterference communication environments.

3.1.2

Channel Capacity

After the spectral analysis, we discuss the possible throughput of our proposed terahertz
model. Generally, the total pass loss model A( f , d) includes the sum of spreading loss andmolecular absorption [28]. The noise includes system noise created by the electronic devices,antenna noise created by the Omni-antenna and molecular absorption noise depending on
different humidity and air quality. For simply discussing the potential, we consider an21

3.1 Communication Model0fc=0.3 Thz, T=Tp/30
fc=0.3 Thz, T=Tp/60
fc=0.6 Thz, T=Tp/30
fc=1 Thz, T=Tp/30-10

PSD [db/Ghz]

-20
-30
-40
-50
-60
-70
-80
0

2

4

6
Frequency (Hz)

8

10

12
10

11

Fig. 3.1 The Hann pulse waveform for four values in THz Bandomni-antenna situation. Notice that the main challenge and decisive factor to improve thelink performance is still the real deployment of directional antennas.
The capacity can be calculated by the sum of each sub-bands’ capacity, noted as ∆ f . In
each sub-band, we consider the PSD of each transmission wave and the noise are locally flat,
therefore the channel capacity isC(d) = ∑ ∆ f log2[1 +iS( fi )]A( fi , d)N( fi , d)(3.2)

where d is the distance between Rx and Tx, S is the PSD function, A is the total pass loss
function and N is the noise function. The capacity mainly depends on the distance and the
SNR ( Signal to Noise Ratio). The attenuation can be independently solved by relaying
technology we introduced later. Meanwhile, the path loss and system noise increase withthe frequency, and we can choose different pulses to achieve suitable PSD to improve thecapacity.
In Fig.3.2, it shows the capacity as a function decreases with the distance. Generally, themolecular absorption noise becomes extremely high at several specific narrow bandwidth[3], which divides the whole THz band into 4 windows (0.38-0.44, 0.45-0.52, 0.62-0.72,
0.77-0.92 THz). In this figure, we set the transmission window with 0.62-0.79 THz, 170
GHz wide. Three common power allocation pulses are proposed here, rectangular-RCP,
Hann-RCP, and Gaussian RCP. Rectangular-RCP is a flat pulse and cannot resist the pathloss and noise efficiently. The Hann-RCP mentioned above performs better in short range

22

Breaking the Blockage for Big Data Transmission

1016
Rectangular-RCP
Hann-RCP
Gaussian-RCP

Capacity [bit/s]

1015

1014

1013

1012

1011

1010
10-3

10-2

10-1

100

101

102

Distance (m)Fig. 3.2 Capacity as a function of the distance for three different power spectral densities

3.2 Terahertz Autonomous Relay

23

than Gaussian-RCP. The Gaussian-RCP is not as sensitive as the others when the distanceincreases. Other pulses such as Sinc-RCP and carrierless IFFT pulse also have specificapplicable systems of terahertz vehicle communications.

3.2

Terahertz Autonomous Relay

Similar to the study result in recent paper [3], we observe the propagation of THz level signal
at 1 and 10 meter decreases by 80 dBm and 110 dBm, respectively. THz communcation
systems are proposed to achieve a 100 m link with directional antennas and shorter than 10 mlink with omnidirectional antenna [34]. In order to extend the available transmission distanceand enhance the resistance of environmental change, our proposed autonomous terahertz
level relay (ATLR) becomes a suitable solution for vehicles. Since there is no universal
standard for such short range communications, Tx can use the whole band to enhance thespatial reuse, which keeps a large volume of throughput in each interval. Besides, throughrelaying, it changes the lower penetration of NLOS communications into more stable LOS
links. Moreover, it provides moderate length links which have the same distance with Wi-Fi
but the bit rate is higher by 5-6 orders.

3.2.1

ATLR Algorithm

However, terahertz transmitters and receivers have to suffer the constantly changing of
propagation and noise when traveling on the road, which makes the relay point hard to select.
Therefore, we propose an autonomous terahertz level relay (ATLR) algorithm to find the best
relay position. The main idea of the optimization strategy is to detect the channel qualityof each position in 2D representation and find the optimized point. In this scenario, we
divide the whole space into very small blocks and detect the channel quality in each of them.
However, under complicated traffic conditions and a l 2 plane area for detection (l is thedefined side length of the plane for an independent relaying scenario), it is impossible for therelays to collect all the information from every space block. Our algorithm calculates the
optimized relay point with relatively less movement when considering the advice of possible
automatic driving routes.
Fig. 3.3 is an example of our proposed ATLR algorithm. Car A and B are autonomousvehicles with the mentioned support of 3D image detection system. Their autonomous
systems advise them to advance following the blue line. A candidate relay Car R is by theside and has the similar self-driving route (noted as the red line). The car B sends a request
to relay R, then R uses the mentioned carrierless IR pulses to detect nearby cars. Notice that

24

Breaking the Blockage for Big Data Transmission

A

B

O

O’

Fig. 3.3 An example of autonomous terahertz level relay algorithm (ATLR). Car A and B is
the sender and receiver. Pink car tends to find an optimized position using ATLR for relaying
A and Bthe conventional RSS method or the state of the art LiDAR (Light Detection and Ranging)
sensors can also be embedded on an autonomous car for positioning. With the awareness ofsurroundings’ relative distances, relay R moves to the temporal optimal position O1 as Round
1, which calculated by ATLR (the position noted as O in the figure). When moving to thesuggested position, R detects the quality of the channel in each space block and stores in achannel quality matrix Q. After holding at the temporal optimal position, ATLR recalculates
the optimal position as O2 (noted as O′ in the figure) based on the relay quality value Qn,mwe defined. This value is stored in the channel quality matrix Q, where we haveQn,m = (T xn,m − Rxa1 ,a2 ) ∗ (T xn,m − Rxb1 ,b2 ) ∗ Ln,m(3.3)

where T xn,m is the signal quality of the transmitting antenna and Rxi, j presents the receiving
antenna. We use Ln,m to indicate recommendation rate of the route calculated by autonomous
driving system. It depends on the traffic condition dynamically updated by the road understanding system, which the risk areas are eliminated. This setting can also avoid other nearby
vehicular communication systems reasonably. When moving to O2 , ATLR recovers Qn,m andcalculates O3 at the end of Round 2. After k rounds, the relay vehicle fine-tunes itself to thestable position Ok . Since the relay can only monitor channel quality blocks passed by, themoving distance of each round is monotonically decreasing, which finally stops in a specific3.3 Enhanced Autonomous Driving

25

block. Through the process above, car A and B keep the stable and ideal terahertz channel
through relay R.

3.2.2

Autonomous Multiple Relaying

Under the condition of certain dense traffic, there may be more than one candidate relay
available in this scenario. The multiple relays are introduced here to further extend the limited
range between car A and B. Firstly, through position sensors, the ATLR system estimates theneeded number of relays to establish multiple hopping. Similar to our previous study [27], we
propose a multi-deviation transmission protocol to improve the channel quality aggressively.
The basic idea is that by setting common id as a priority (such as MAC address, user id, etc.),
the ATLR produces a map with suggested position O0,i for the first priority Relay Ri . The
relay Ri firstly moves to its optimal position O0,i then a single relay {R j |id(R j ) < id(Ri )}starts to collect the channel information when moving to its O1, j . Then relay Ri moves to its
optimal position O1,i and finishes the first round. Notice that this process can be applied tomore than one relay, which can avoid priority or collision problems. A thoughtful setting of
the priority in a specific scenario can even improve the efficiency of the whole system.

3.3

Enhanced Autonomous Driving

Autonomous driving has become a hot topic in recent years. Many amazing achievements
and applications have emerged. However, these researchers mostly focus on the correctness
defined by human beings. Some pioneers consider the autonomous driving system should
perform better than human driving in an all-round way, which requires more remarkable
perceptibility and reaction in emergency situation. However, even if the autonomous system
can nearly understand the visual information as well as human beings, it can never surpass
human being’s perception. One of the advantages of vehicle network is the information
sharing ability. Conventional vehicles share information and traffic condition through DTN or
RSUs [35], which only provide size limited message transmission. The application of vehicle
terahertz band communication will bring new opportunities to the autonomous system, to see
what human drivers can never see and to learn what human can never learn.

3.3.1

Performance Evaluation

Next, we conduct the simulations in a scenario of autonomous vehicle networks. The
scenario contains a 6 six lane expressway, where 3 lanes in each side. The width of eachroad is 3.5 m and the total length for observation is 200 m, where 12 RSUs (Road-Side

26

Breaking the Blockage for Big Data TransmissionUnit) are established at the road side. These RSUs contain the equipment of various vehiclecommunication systems and imaging sensors, providing 3D imaging and HD videos forautonomous vehicles nearby. The antennas of mmWave system and THz system are bothconsidered as omni-directional antennas. If one transmitter sends information to the receiverof another autonomous vehicle, the receiver cannot collect others’ information using thesame frequency channel. If the channel collision happens, vehicles with higher priorities canestablish the link. The problem of priority can be solved by many ways, such as importanceof data, vehicle types, etc.
In Fig. 3.4, it shows the simulation results of average number of links using different
wireless communication systems. One link represents two or more connected autonomous vehicles. All the vehicles obey the rules of the road and minimize the dangers of driving. Threebasic transmission modes are tested here, gigabit communication, mmWave communication,
DSRC intelligent transportation systems (ITS). The Gigabit communication (noted as T Hz in
the figure) can approach 2.5 Gbit/s in real deployment within 10 meters while mmWave cankeep 0.1-1 Git/s using different approaches. IEEE 802.11p based DSRC has the rate of 3-27
Mb/s with the communication range of 30 meters. RSUs are used in both mmWave and THz
to provide additional road information in case of no vehicle’s part, noted as RSU&mmWave
and RSU+ respectively. Since conventional communication technologies such as DSRC canremain stable links only for images, we consider the captured HD video data can only be
used by mmWaves and THz technologies. AT LR+ represents the links established by threevehicles, where one is the relay that builds bridge using different channels.
With the increase of autonomous vehicles, the average number of links is growing.
However, the slops of all the communication systems decrease due to the interference ofother links. The DSRC keeps keeps stable standard due to the relatively long communication
range, where the collision problem is obvious. The number in THz system is larger than than
the number in mmWave due to the purer communication environment in short range. It is
more flexible to establish reliable links in high density. Never than less, by the supporting of
RSUs, there are more information shared in the air to improve the driving decision system.
The AT LR+ is used to establish multihop links, and more links are established due to thehigher density. It collects more information from different vehicles to improve the accuracyof road condition recognition system.
Currently, higher frequency transmission systems such as Thz bandwidth may be notfully developed to deal with complicated traffic conditions. However, the advantages ofhigher transmission rate and attenuation help create more efficient transmission environment
in short distance. Therefore, a hybrid transmission system using various communication
formats to handle various situations is one of the future tend. It minimizes the interference

27

3.4 Conclusion
40
THz
ATLR+
DSRC
mmWaveRSU+
RSU&mmWave

Average number of links

35
30
25
20
15
10
5
0
20

40

60

80

100

120

140

160

180

200

Number of autonomous vehicles
Fig. 3.4 Precision comparison in autonomous driving through different technologies
from different channels. A hybrid approach may adapt more single or multihop links
to heterogenous networks, which provides more flexible options for autonomous vehiclecommunication.

3.4

Conclusion

In this paper, we study the impact of terahertz band towards vehicle networks. THz bandcommunication relieves the spectrum scarcity and capacity restriction of the existing communication systems. In short range, the THz link can be considered as a transmission window
with almost 1 THz, which supports the growing real-time data transmission. Moreover, wedevelop an autonomous terahertz relay algorithm called ATLR which gives the advice of ideal
relaying position to bypass obstacles and avoids stronger NLOS fading. Finally, we apply
this algorithm in autonomous vehicle network. It helps create more flexible communication
environment and provide more traffic information to nearby autonomous vehicles.

28

Breaking the Blockage for Big Data Transmission

Actually, not limited to autonomous vehicles on the road, terahertz band can be widely
applied to all mobile nano-cell networks, such as delivery drones or UAVs (Unmanned Aerial
Vehicle). Different kind of ’vehicles’ has very different ability to adapt communication
environments. These ’vehicles’ support the exploration of missing details, which helps
human beings and human made machines understand the known world more smartly.

Chapter 4
Social Taxi Sharing: A Cyber-PhysicalApproach for Efficient Urban
Transportation Service
This chapter describes a real time and real environment solution to meet with the experienceissue in urban car sharing services, where the user-oriented taxi sharing service using social
network is considered in this study.
In this chapter, we propose a cloud-based taxi-sharing system, which provides real-time
taxi sharing services both considering the practical travel needs and QoS in the journey. The
purpose of this service is to minimize the travel cost through sharing calculated schemes
reasonably and quickly and improve the sharing experience as much as possible. We model
the citywide level map into blocks and indexed, in order to search for the potential pathsof ride-sharing dynamically and intelligently. Meaning while, we explore the paths amongcommunities to find suitable companions as well. Finally, as well as the establishment of themobile application and online service, we also conduct a large-scale simulation to evaluate
the performance with others. The result shows that the proposed solution could make thewhole taxi-sharing system less calculation complexity, higher sharing QoS, and most ofall, keeping the minimum cost of travel cost within 1.16% increment than distance optimalalgorithms.
The main contributions are summarized as: social network relationship is introduced
into the taxi resource management when limited taxi resource meets with the rush hour. The
community structure of a social network is taken into consideration when scheduling sociallyconnected passengers in one taxi; An optimization problem is formulated and calculatedusing our proposed 3-step process, including community detection, real map taxi searchingand social network based heuristic algorithm called SONETS. It searches for an optimized

30

Social Taxi Sharing

solution to make a cost efficiency, fairness, and humanized service designing; New smart
device application called ’Social Network Taxi Sharing’ is designed and applied in the realenvironment. Furthermore, the large-scale simulation is deployed based in citywide, using
real user information and cartographic information.
The remainder of this paper is organized as follows: in chapter 4.1, we detail the proposedarchitecture of online taxi sharing service. In chapter 4.2 and 4.3, we work on the taxi
allocation problem and develop the optimization algorithm called SONETS. Performance
evaluation is presented in chapter 4.4, and the conclusion is in chapter 4.5.

4.1

Sharing Service Design

This section presents the motivation and structure of the proposed taxi sharing oriented CPS.
Cyber-Physical System (noted as CPS) is essentially a multi-dimensional intelligent technology system. Our work is based on big data, on-line network services, and massive computing.
Through core intelligent vehicular sensing, traffic analysis, schedule optimization, and route
coordination, the proposed CPS will be used for service computing, communications, andcontrol (3C), in order to achieve in-depth integration of the network space (social network,
online service) and physical space (real map, taxi service), which changes the lifestyle andimprove the life quantity. Due to the rapid development of ’cyber’, every person may carry
one or more smart devices for online services, and forms various networks, e.g., social
networks, communication networks, location-based online social networks, etc. Then, we
consider the situation that is sharing potential passengers all have strong or weak social
network connections with each other. They have smart devices which access the Internet andare willing to reach their destinations by sharing a taxi [47]. The sharing system provides
the taxis and sharing arrangement service by working on the coordination of different travelplans, and social network infects between passengers.
Next, we discuss the feasibility of this scenario. There is a period in every day that
potential consumers suddenly need many taxis which we call it taxi-needed peak time: For
example, at lunch or closing time, a mass of potential users in the same social communityof company are waiting at the front door of an office building for taxis. Usually, sharing
taxis by street hailing is a commonly solution in such a taxi resource-limited situation [25],but still need to wait for taxi’s arriving; Actually, these potential passengers may share thesame community if they share similar activities or work at the same place, and the innerconnections are strong enough as well. With the trusted relationships, they are willing toshare the same taxi if they have similar paths [57]; Other potential passengers such as students

4.1 Sharing Service Design31

are willing to share because they are a group of people who are sensitive to the cost anddesire more social interactions [18], and most of, they live in the same camp.
Our new social network based taxi service is proposed for the above scenario. Throughthe coordination of time, taxi and cost, it is designed to schedule potential passengers whom
others may be interested, through which we consider the social network relationships. The
social network is an online service for establishing or reflecting the social relation of people
who have similar interest and activities [54], and location-based networks could even show
the real daily travel needs in a city. Similar social features are the reasons why they connect
to each other, as well as establishing a big social community. It helps us find the persons
who may share the same lifestyle and give out recommendations to other consumers [41].
Therefore, a social network connection is a beneficial recommend status for choosing theright sharing group. For example, graduating from the same school is a reference factor thatmakes the system tend to arrange them in the same groups, which can help satisfy or evencheer up them easily during the same trip [30].

4.1.1

System Demand

For replying to the above concerns, we design a framework of the proposed system withdemands below:
1. Users can update their taxi sharing travel plan with a mobile device through an interactive user interface.
2. All taxis are monitored by the system so that all potential passengers are in the same
queue and experience same standardized service.
3. A solution about the detail information of the routes and passengers is provided foreach taxi, which takes current passengers’ travel plan and social connections into
consideration.

4.1.2

System Structure

Fig.4.1, it represents the architecture of our proposed social network optimized taxi service.
This architecture contains three parts: user part, operation part, and data part. User partcontains potential passengers who desire for taxi sharing and all taxi resources. Operation
part schedules the detail operations in the user layer. The data part provides all necessary
data asked by operation part.

32

Social Taxi Sharing

Potential
Consumers

Smart
Environment

Arrangement
Confirm

User Travel
Plan Data

Notification
ModuleSocial Network
Data Base

Taxi
Resource

Schedule
SystemTaxi Resource
Arrangement
Cloud

Fig. 4.1 Structure of the social network based taxi sharing service
Taxis Resource: One taxi driver uploads their idle time and location. Then, the system
considers it as taxi resource at one specific starting point.
User Interface:The module includes all the necessary sharing plan information sentby the potential passengers. When users planned their trip and needed a taxi, they submit
their plans to via the user interface. Before real departure time, all the untimely information submitted by potential passengers are stored in this module, and be updated into theglobal request queue dynamically. When the time comes, it will be sent to the Schedule
System Module. Generally, it contains four functions: account management, personal data
management, result informing and social network data authorization.
Taxi Resource Arrangement: This module is to monitor all taxi resource and informthe sharing arrangement system.
Schedule System Module: This module works out the schedule of the entire arrangementof every taxi. This module calculates the solution about how to allocated potential consumers
in different taxis. We use a social network based algorithm (SONETS) to complete thepassenger allocation. The input of the processing is based on the data of the travel planin User Travel Plan Data and Social Network Data Base. Finally, it sends the allocation
schedule to the Arrangement Confirm Module for notification.
Arrangement Confirm Module: It pushes arrangement results from the Schedule System module to users. The pushed information includes the distance of the whole trip, adjusted
departure time(one taxi one departure time), number of passengers in a taxi and cost. After all
the informed users in one taxi confirmed the arrangement, the driver considers this schedule
is established. If not, we consider the consumers give up their chances, and delete from thequeue. The other request is sent back to Schedule System module for a new solution.

4.2 Map Processing for Cities and Users

33

Social Network Relationship Database: This module stores user social relationshipwhich based on the social network (e.g., Facebook, Twist and YouTube). Data mining andnetwork analysis are processed by the cloud dynamically, and the users are classified into
community settings. This community definition will be used as the standard whether thetwo potential consumers’ interrelation is tight enough. We consider the tougher the social
interrelation is, the more significant chance they should sit together.
Notification Module: It pushes confirmed results from sharing arrangement module tothe specific consumer. The difference with Arrangement Confirm module is that it combines
the specific travel information from both sides, which contains the travel information about thecurrent positions of taxis and passengers. It enhances the recognition for people. Notice thata reminder function is also embedded in the application to guarantee consumers’ attendance.
Taxi Resource Arrangement module: There are two primary functions for this module,
embedded with a driver-oriented interface. One is to monitor all the taxis in citywide andinform the Sharing Arrangement Module the available taxi resource. Another is to push detail
information of the accomplished travel plan to drivers, including destination, the drop-off
place of each passenger, identity information, departure time, etc. Notice that this moduleconnects to the taxi company, where the taxi service data can be further reused for meaningful
data analysis.

4.2

Map Processing for Cities and Users

In this section, before giving out a practical system model, we firstly pre-process the city mapthat divided by blocks and makes all the travel requests in indexes for different blocks. Then,
we propose a system model in order to describe the travel plans numerically and calculate
the cost on the city map. Finally, we discuss how to search for suitable travel companions on
the social network map.

4.2.1

Map Planning

For each passenger, their start and destination points updated to the system may not be thefinal positions picked or dropped, since most of the taxi drivers could only choose a near drop
off point on the road [25]. Therefore, we assume that all the passengers in one block could
be dropped off at the edge of a real-world block. For a taxi, if it can cross by the edge of one
block, we consider it can drop off all the passengers whose destinations are included in thisblock. The similar idea is proposed by [10] early, which used in passenger recommendation
in local areas.

34

Social Taxi Sharing

Fig. 4.2 Muroran map divided into blocks
Step-1 Map Division: Fig.4.2 is a map of Muroran which has been divided into many
blocks using map street data. The main purpose of this step is to divide passengers’ travel
plan geographically. We select three types of roads as our edges, highway, trunk road, andminor road. Every block is a closed polygon that consists of several roads and vertexes.
Since Muroran City is a port city that faces the Pacific and has mountains behind, there aremany mountain roads which couldn’t cross each other and form blocks. Therefore, it needs
extra manual work to form new blocks, which presents new destination areas. For eachpassenger, his destination is only contained by one block in this map. One block contains acollection of passengers who share the same edges. If one taxi crosses by the edge of thisblock, the passenger whose start or destination point belongs to this block is considered as agood candidate for sharing, and there is no detour for dropping off or picking up. Notice that
if two parallel roads are too close to each other (within 5m), the first one forms a block, andanother one will be ignored during the block division processing.
Step-2 Block Extension: This step is to meet passengers’ habit of getting on and getting
off. On the outside of a block, there may be several users nearby and next to block, where
dropping off them at the same edge is the best choice. Besides, the road has a fixed widthwith two sides for parking. Therefore, it is practical to extend boundaries for each block to
expand the scope of potential passengers. Fig.4.3 is an example of how these blocks extend
and cover each other. Each new block contains the collection of original block members
and other users who are close enough. The edge is extended by 1.5m for minor road, 2m

4.2 Map Processing for Cities and Users

35

Fig. 4.3 Muroran map contains extended blocks
for others, based on the road infrastructure information. We select the center of a polygon
and push the border parallel to the outside for 1.5m/2m to form a closed new polygon. By
processing the map, blocks are divided by roads, and contain common users in both that are’close enough’. The ’close enough’ means the node is outside of the specific block before theextension and included by this block after the extension process. Notice that, the different
colors in the figures are to distinguish the status before and after the extension (in blue andred respectively), and make a clear vision since it will be hard to recognize when map zoomout.
Step-3 Taxi Patrol Cover: The purpose of this step is to provide a rough passenger
dataset in taxi’s patrol path. From the start point to the destination, one taxi shall crossby many blocks. The users belong to these blocks are appropriate for sharing candidates
geographically, because it takes fewer detours and time for dropping off. Therefore, we
define a "cover" here to indicate the taxi’s patrolling area, which helps select the set ofsuitable passengers geographically. As in Fig.4.4, The arrow indicates the direction of thetaxi. Generally, one taxi crosses by several blocks. Each block contains a set of potential
passengers (noted as the circles), and each set is a subset of all potential passengers collected36

Social Taxi Sharing

Fig. 4.4 One cover contains several blocks which refers to sets of potential consumers
by the corresponding path. In other words, when we establish a path, it generates a union set
combined with several subsets, which contains passengers indexed by each block.
Significance: Through the method of map planning, we narrow down the searching
scope for available passengers geographically and improve the calculation speed. It reduces
to a sub-problem from the whole user data set, where we develop a heuristic algorithm tofind the solution in the next section.

4.2.2

Index of Blocks

After the block division process, each block can hold an index which describes the basic
feature of this block and active nodes in it (taxis, passengers, destinations, etc.). The purposeof the index is to reduce the calculation complexity and speed up the route searching process.
As shown in Fig.4.5a, in each block, one node is chosen as the anchor node for this block,which is the geometric center for the polygon. Notice that other center node selection method
like the central intersection also can be taken into consideration. Due to the length limitationand incomplete map information, we use an anchor node instead to make the description

4.2 Map Processing for Cities and Users

37

easy to understand. Then we can calculate the distance, travel time, and fastest path between
blocks on the map through various methods.
To make a practical system, we use the travel time as an important indicator for travel
planning, since it can be dynamically updated by the online service and has the statisticalsignificance to reflect the traffic condition in a specific period (as we know, traffic flows on
the morning rush hour is totally higher than wee hours). It can be estimated through average
travel time by different taxis, which updated by each taxi after each contract is finished.
Besides, the travel time between blocks can be used to filter out those blocks that taxis cannot
reach in time within O(w) computation time, where w is the total number of blocks. For
example, in Fig.4.5b, the matrix C represents the statistical result of travel information ineach block, and each symbol Bi j indicates a directed travel information (e.g. travel time) fromi to j. It is possible that Bi j and B ji have a big difference, which depends on the directionof the overall traffic flow in the citywide (or different period). The advantage of this matrix
is that the travel time and distance are independent of the real-time path-finding algorithm,
which increases the fault tolerance and lateral compatibility for other up to date navigation
systems.
As shown in Fig.4.6, the travel information of each block Bi contains three parts: atravel distance based block list B j .d ji ; a travel time based block list B j .t ji ; a taxi arriving
list Taxim : ti . The travel distance B j .d ji indicates the actual travel distance from arbitrary
block B j to block Bi in its index and they are ordered by ascending. The travel time B j .t ji
is also ordered by ascending based on the travel time from other blocks. The taxi arriving
list Taxim : ti is a list that indicates the planned arriving time by scheduling system or otherstand-by taxis, and this list is in ascending sort as well (taxi stops at the original block Bi isconsidered as 0). The spatial distance (travel distance) and temporal distance (travel time)
can be directly inputted from the block relation matrix C. The designing goal of these lists isused to search for the potential combination of travel plans. For instance, if one passenger
wants to search for taxis in nearby blocks within 10 minutes, the system can filter thosetaxis in blocks that B j .t ji > 600 s. The system will update these lists periodically after new
information is uploaded by each taxi. Notice that the extension of blocks will not create theoverlapped problem in remote blocks (start from different blocks) because the real arriving
time is estimated from the actual start point and uploaded based on the real road path.
The taxis list Taxim : ti contains the taxi ID that scheduled to arrive in the future, andthe ID is acceptable to be listed in both nearby blocks it crosses over. The actual arriving
time is tagged with a stamp ti , and sorted in ascending order. These timestamps are updated
immediately after a single schedule is established, and they will be moved at once when
the taxi passed by. Meaning while, if a new schedule is confirmed (whether it is the new38

Social Taxi Sharing
𝑩𝒊

𝑩𝒌

𝑩𝒊

(a) Indexed block map

Block ID
0

𝐵1

𝐵2

𝐵3

𝐵4

……

𝐵𝑛

𝐵1

0

𝐵12

𝐵13

𝐵14

……

𝐵1𝑛

𝐵2

𝐵21

0

𝐵23

𝐵24

……

𝐵2𝑛

𝐵3

𝐵31

𝐵32

0

𝐵34

……

𝐵3𝑛

𝐵4

𝐵41

𝐵42

𝐵43

0

……

𝐵4𝑛

……

……

……

……

……

0

……

𝐵𝑛

𝐵𝑛1

𝐵𝑛2

𝐵𝑛3

𝐵𝑛4

……

0

(b) Directed travel information matrix

Fig. 4.5 Formulate the blocks by index and calculate the travel information between themtrip combination or individual plan), the newly created timestamps will be inserted to eachblock in the right order. In the real taxi sharing service, it is impossible that the taxis update
continuously the GPS coordinators all the time to show the precise in-and-out time in eachblock. However, it can keep updating with a series of discrete GPS nodes, and the nodes
appear in the right block are indexed in these blocks.

4.2.3

System Model

We consider there is a status set N of users {1, 2, . . . , imax } of potential users who are willingto share a taxi. A set status M with taxis {1, 2, . . . , jmax } are waiting at the blocks. Then,

39

4.2 Map Processing for Cities and Users……

……

Fig. 4.6 The index of a block that contains the list of taxis and travel information from otherblocks.
we consider the taxi sharing peak time is a specific period divided by time slots, noted as
T = {1, 2, . . . ,tmax }.
Time Frame: Since taxi sharing peak time often appears in a specific period in daily life,
similar to [48], we consider this fixed period with same length slots. For a fixed length period,
the system creates dynamic queues both for candidate consumers and taxis. Scheduled
passengers and taxis will be offloaded from the queues.
Destination: For arbitrary user i ∈ N, we define an array Xi = (longitude, latitude) toindicate the travel plan of user i. Zi is the distance between the destination and start point.
We define
Zi = D(|Xi − Oi |)(4.1)
which denotes the distance function of the direct path by a taxi from starting point to thedestination. The result can be solved by inputting vertexes and edges from the open street
map data and applying with common shortest path algorithms. Notice that Oi indicates thecoordinate of starting point and Zi ∈ [Z0 , Zmax ].
Cost: For arbitrary taxi j ∈ M, the total payment C′j in a taxi is formulated as,
C′j = P0 + (Z ′j − Z0 ) · P1

(4.2)

where P0 is the starting fare and P1 is the cost per mile. Z ′j means the total distance taxi jmoves. Z0 is the distance of starting a course. Without loss of generality, the proposed system
calculates the cost for each passenger based on the proportion of distance they experienced.
It can reduce the conflicts on cost segmentation[14]. Since passengers still need to endure

40

Social Taxi Sharing

X3

X2
X1
Z1
Z2

Z3
X4
Z4

Fig. 4.7 Routes begin from original point to each passenger’s destination
the waiting time and detour of dropping off [64], the proposed recommendation system needto handle this problem smoothly and flexibly, which we discuss in the next section.
Since the original route is established by the first passenger, who is also at the head of
the queue, it is fair that all the passengers undertake part of the fee from the start point.
Therefore, we define our distance-based cost division method is calculated from the startpoint of the first passenger to the destination of each. Through the sharing, the passengers
behind the queue have the chance to skip the queue and take the taxi. Moreover, it forces
passengers to use the sharing system efficiently. For example, one passenger’s start point isnear first passenger’s destination, and a taxi should remain seats empty for a long time.
Travel cost is referred to the proportion of each passenger’s travel distance. The basic
description is based on Fig. 4.7. Here, for each passengerb

Z j,b = ∑ D(|X j,a − X j,a−1 |), where X0 = O0 , b ≤ a j

(4.3)

a=1

where a j is the number of passengers in taxi j. Obviously, we can infer the actual distanceof taxi j’s path Z ′j . Their respective cost is divided from the total taxi fare C′j , which using
the proportion of their owe riding distance. For the no.b passenger, the cost C j,b can beformulated as
C j,b =

Z j,b
·C′j
aj
∑y=1 Z j,y(4.4)

The basic reason that one passenger wants to share a taxi is the cheaper cost. Our payment
division method should not break the base line of sharing. Therefore, the passenger b’s

4.2 Map Processing for Cities and Users

41

payment C j,b can be stated as,
C j,b ≤ P0 + (D(|X j,b − O j,b |) − Z0 ) · P1

(4.5)

for the b-th passenger in taxi j.
Economic benefit: The system needs a quantifiable concept to measure the economic
benefit. We define a variable EB j to indicate the economic benefit by sharing. Comparing
with taking a taxi alone, we have the economic benefit (EB) for taxi j here isaj

EB j = ∑ (D(|X j,b − O j,b |) − Z0 ) · P1 − (D(|X j,a j − O j,1 |) − Z0 ) · P1 + (a j − 1) · P0

(4.6)

b=1

4.2.4

Sharing Social Communities

After finding the available taxis in nearby blocks, next we discuss how to search for potential
passengers to improve the quality of experience during the journey. Since communities in thesocial network could represent the real social interactions, social groups, and location-based
activities, we collect location-based social network information from these users to establish
an integrated share schedule through a social network map. The distance on the social
network map is an important factor to indicate the relationship strength between different
individuals and communities. This idea has been applied in many fields: relationship ofpaper authors can be effected on the citation network; the possibility of appearing in thesame place shows how often the two people meet with each other.
As shown in Fig.4.8, a general social network can be formulated as a network of communities that there are more inner connections in one community and less global connections
between different communities. For a general social network dataset, there is a weight todescribe how close the pair of vertices is. One vertex can be connected to multiple vertices
through edges, and each edge holds different weight. The traditional method to draw asocial network is that we can start with the edge which has the strongest weight. Then, we
add edges pair by pair in the descending order until the weakest edge. Through the edge
adding process, the network graph shows nested structures in specific areas, which could beconsidered as communities. For each nested structure, it also can be formulated as a tree
structure to emphasize the strength of a relationship. For example, as shown in Fig.4.9, thefirst level represents the first edge that is leading to the vertex classified into this community(in most of the cases, it is the first edge added on the network for this vertex). A slice throughany level of edge would lead to smaller communities or groups. Edges in a higher level

42

Social Taxi Sharing

Fig. 4.8 Structure of the social network community

Lv-④

Lv-③

Lv-②

Lv-①

Lv-〇

Fig. 4.9 A tree structure of social network to show the robustness of each link

4.2 Map Processing for Cities and Users

43

show more important in establishing these communities. This structure is also similar todendrogram in hierarchical clustering.
Community Detecting Model
Based on the above observation, we can discover that some edges (high-level edges) haveplayed an important role in connection and differentiated communities. In another word, apair of vertices belongs to different communities have to pass at least one of these edges toestablish the shortest path. In traditional methods, the system estimates the importance of eachedge during the edge adding process, which could help establish a broader community. On theother hand, these edges are also the key edges to divide vertices into groups. In the view of a
global social network, those edges are the least central edges for each community. Therefore,
instead of adding edges with the most substantial weight to construct communities, weclassify the community members by removing the most ’busy’ edges between communities.
The essential idea is that by removing the most important edge between communities, we
can discover a community that they have only inner paths after the former most "busy" edge
is removed.
In order to find which edge is the most important between communities, we introduce
a concept of betweenness in previous works. Usually, the vertex betweenness is used tomeasure the centrality and influence in social networks. A node with high betweenness plays
a more critical role in the information flow over the social network. This specific betweenness
is estimated by calculating how many shortest path have passed over this vertex. In this paper,
instead, we calculate the betweenness for each edge. If a vertex belongs to one community
and wants to connect with outside vertex, it has to choose one outer group edge to reachthe vertex in other communities. These edges connecting these communities always holdhigher edge betweenness and should be firstly removed in descending order. Fig.4.10 shows
the process of community detection. The community detecting process is summarized asfollows:
1. Find the shortest path for each pair of nodes.
2. For each path, add one count on the edges it passed by. If there exist two shortest paths
with the same length, all the edges covered by these paths will be counted once.
3. Find the edge which holds the highest betweenness and remove it.
4. Calculate the betweenness effected by the above removing.
5. Repeat the process until vertices in one community cannot contact with outside.
6. Store one less member group as a community and repeat from step 1 until all thecommunities are found.

44

Social Taxi Sharing

Fig. 4.10 Find the high betweenness edge (red edge is high betweenness, yellow edge ismedium, blue is lowest)
The computation complexity is O(mn2 ), m is the number of edges and n is vertices. If wewant to reduce the computation complexity, one potential solution is to calculate the overall
betweenness once and remove them in descending order. However, by our pre-testing, thesame betweenness from middle-level edges could profoundly affect the precise classificationof vertices, but it is still a way for quick classification. Therefore, in a general way, many
paths will be cut off due to the removing process, and they transfer to the next edge nearby.
This process could guarantee that the removed edge is the current "hot" edge that most of thecommunities rely on.
Besides, we carefully consider the potential passengers may be out of the specific social
network, and make this social network classification model to avoid this problem. We
classify users from a location-based social network (which is more reasonable for users
in one city) into several communities and measure the relationship between communities,
instead of an individual’s relationship. This fuzzy pressing could help the system understandusers’ social priority in communities, and avoid using the unquantifiable social relationshipto indicate the interaction priority in order. Furthermore, different users may belong todifferent social networks and entirely has no connections. When designing the arrangement
algorithm (introduced later), we can consider a three-level priority passenger combination,

4.2 Map Processing for Cities and Users

45

Fig. 4.11 Move them and recalculate the shortest path (red edge is high betweenness, yellow
edge is medium, blue is lowest)

Fig. 4.12 Separate the community if no outside links with other communities (red edge ishigh betweenness, yellow edge is medium, blue is lowest)

46

Social Taxi Sharing

same community, same social network and different network, which covers most of thepeople in a city and solve the mentioned problem perfectly.

4.2.5

Problem Statement

In this study, given a series of taxi sharing request, our design is to find an optimized routewhich concludes social network friends in close communities as many as possible, and makesure the travel cost is also minimized among these friends. In a more formal way: Given a
set of taxis M on the nodes and edges composed map, and a series of sharing request queue
Q in time series, our goal is to design a system that serves this request queue by dispatchingidle taxis in M which could satisfy each request in Q, and combine them to improve the QoS
with minimum travel distance increase.
Here are two objects for the design: find social network companions in the trip; savemoney as many as possible. The first object is our primary object, which is to improve the
QoS on the journey. Since previous works have already developed various algorithms toapproach the maximum economic benefit, it is not difficult to form the maximum economic
problem using a greedy algorithm. The real challenge is to search for the pleasant passengers
in the same taxi with the relatively small time interval. Generally, passengers all wish tostart their trip immediately when they upload their travel plan, and they will abandon thisservice if time ran out. Therefore, our design could not wait for the next request to form along queue with maximum span. Instead, we need to design a solution that could either takecost efficiency, fairness, or people-oriented designing, to improve the QoS of taxi service inan all-around way.

4.3

Social Network based Scheduling

The calculation complexity increases exponentially if we calculate all the combination in thequeue, which is also a knapsack problem. In order to find the optimal solution, we divide thepassenger allocation problem into three steps:(1) Build a planning map for rough sharing recommendation, and develop a bidirectional
taxi searching algorithm to match the path the first passenger demanded.
(2) Discuss a solution that satisfies all the constraints for passengers and taxis.
(3) Develop a social network based algorithm to search for the best solution dynamically
until the end of the whole time frame.

47

4.3 Social Network based Scheduling

4.3.1

Bidirectional Taxi Searching Algorithm

First, after a travel request uploaded, the first thing necessary is to find an available taxi
nearby. For the description, we describe the situation using a block map before the extension.
The extended blocks only expand the potential set of taxis, which would not affect the core
concept of algorithm introduced below. Assume there is a new request q0 updated into thesystem queue Q, and the original start point is Q0 .O, which belongs to the block B0 . Then,
we select the travel time list from the index of B0 , and it lists all the blocks B j ∈ B from thenearest to the farthest. Then we assume the current time is t, and for any block j, we havethe time constraint here,t + t j0 ≤ Q.st.l(4.7)

Q.st.l is the time limitation for departure, which means the time cost for taxis from otherblocks reaching the original should not exceed the user’s time limitation. Therefore, any
block satisfies this equation becomes a candidate block that may provide idle taxis (or partly
empty seat taxis). Since we do have the dynamic travel time list corresponding to eachblock’s index, we can quickly find all the t j0 by the descending order, and stop until one
block is too far away that holds long enough t j0 which cannot satisfy Eq.4.7. Next, we cansearch for the taxis in these blocks as a set of candidate taxis.
Fig.4.13, the original point in block B0 can find other taxis in B2 , B3 , B5 . Then each block
maps out several taxis in it, which contains idle taxis or rushing taxis that is planned to arrive
in a concise time in the future. For those taxis arriving in future, we have
Taxim .t j + t + t j0 ≤ Q.st.l(4.8)

where the total sum of taxi arriving, block moving and current time should not exceed theuser’s waiting limitation.
Generally, the taxis within a limited range should be considered firstly since travel timerefers to the travel distance. However, the unpredictable traffic condition may affect the
precision of real available taxis, and then we use the periodically updated travel time toimprove the error-tolerant rate. More than that, it is impossible to draw all the taxis’ future
tracks nearby to realize ride-sharing, where searching for all the points in tracks within thetravel distance limitation needs higher computation complexity.
After we find the available taxis near the original point, next we discuss the taxis whether
the destination is near to the blocks in its future plan. The same with the previous figure,Fig.4.14 shows a bidirectional taxi searching algorithm, in which we search for the blocks
within travel time by both sides.

48

Social Taxi Sharing

𝑩𝒊
Travel Time List

𝑩𝟑

𝑩𝟓
𝑩𝟐
𝑩𝟏
𝑩𝟏𝟏
𝑩𝟏𝟐
𝑩𝟏𝟑

𝑩𝟑

𝑩𝟓

𝑻𝒂𝒙𝒊𝟏
𝑻𝒂𝒙𝒊𝟑
𝑻𝒂𝒙𝒊𝟓
𝑻𝒂𝒙𝒊𝟕

𝑻𝒂𝒙𝒊𝟐
𝑻𝒂𝒙𝒊𝟒
𝑻𝒂𝒙𝒊𝟔
𝑻𝒂𝒙𝒊𝟖

𝑻𝒂𝒙𝒊𝟗
𝑻𝒂𝒙𝒊𝟏𝟏
𝑻𝒂𝒙𝒊𝟏𝟑

𝑻𝒂𝒙𝒊𝟏𝟎
𝑻𝒂𝒙𝒊𝟏𝟐
𝑻𝒂𝒙𝒊𝟏𝟒

𝑩𝟐
Arriving Time List
𝑻𝒂𝒙𝒊𝟐𝟐
𝑻𝒂𝒙𝒊𝟐𝟑
𝑻𝒂𝒙𝒊𝟐𝟒
𝑻𝒂𝒙𝒊𝟐𝟓
𝑻𝒂𝒙𝒊𝟐𝟔
𝑻𝒂𝒙𝒊𝟐𝟕
𝑻𝒂𝒙𝒊𝟐𝟐𝟖

Time Limitation

Fig. 4.13 Searching for the nearby taxis from start point𝑩𝒊

𝑩𝒋

Travel Time List

𝑩𝟑

𝑩𝟕

𝑩𝟓

𝑩𝟗

𝑩𝟐

𝑩𝟏𝟎

Time Limitation

𝑩𝟏

𝑩𝟔

𝑩𝟏𝟏

𝑩𝟏𝟔

𝑩𝟏𝟐

𝑩𝟏𝟕

𝑩𝟏𝟑

𝑩𝟏𝟖

Fig. 4.14 Searching for the nearby taxis from start side and destination side49

4.3 Social Network based Scheduling

Let us define the original point and destination point as Bi and B j , and other high-lighted
blocks are the nearby blocks that satisfy the time limitation. Therefore, there are twolimitations should be satisfied for the non-empty taxi m passing by the original point Bi anddestination point B j respectively, which aret + txi + Taxim .tx ≤ Q.st.lt + ty j + Taxim .ty ≤ Q.dt.l(4.9)

where the taxi should arrive the original point and destination point within the time limitation
window Q.st.l and Q.dt.l. In this example, the blocks B2 , B3 ,B5 nearby origin, blocks
B7 ,B9 ,B10 nearby destination, are selected as the blocks that contain potential taxis forsharing.
Then, we compare the taxis indexed in these blocks to find the intersection on both sides.
As shown in Fig.4.15, for every picking and dropping, we list the blocks nearby, from thenearest to farthest. Then, we combine these blocks in each picking and dropping slot, tofind the intersection set of taxis from these blocks. For example, the system combines theblock B2 and B7 at the front of each picking&dropping case, to find the intersection by theascending order. If it is empty, we pick one of the next blocks in order to continue thisprocess, until we find more than one taxi in the intersection. Here, when selecting the next
block, we choose the block nearest to one of the current combinations, in order to make surethe increased distance is minimum.
Through this bidirectional taxi sharing algorithm, the overall travel distance may increasea little comparing with the optimal solution, due to the heuristic indexing method. However,since the index has filtered out unsatisfactory travel distance and time limitation, the taxi
searching optimization problem becomes a low computation complexity problem which finds
the intersection in a few numbers of sets. Through the process, about half of the taxis arefiltered out when almost less travel distance is increased due to the real path selection on the
map.

4.3.2

Temporary Passenger Detection and Adding Algorithm

Through the bidirectional taxi searching algorithm, the system can help passengers findsuitable taxis, for a single journey or sharing. The passenger can use an idle taxi nearby
enough to establish a new schedule. However, for the case of sharing, we never discuss theinfluence on the passengers who are already sitting in a taxi.
Here, we use a taxi status matrix M to indicate the current necessary information andtravel plan, where the estimated arriving time is indexed in each block. The main purposeof the system is to satisfy the user request queue Q as many as possible. Therefore, when

50

Social Taxi Sharing
Farthest Block

Nearest Block

𝑩𝒊

𝑩𝟐

𝑩𝟑

𝑩𝟓

𝑩𝒋

𝑩𝟕

𝑩𝟗

𝑩𝟏𝟎

𝑻𝒂𝒙𝒊𝟏

𝑻𝒂𝒙𝒊𝟏
𝑻𝒂𝒙𝒊𝟒
𝑻𝒂𝒙𝒊𝟓

𝑻𝒂𝒙𝒊𝟐
𝑻𝒂𝒙𝒊𝟒
𝑻𝒂𝒙𝒊𝟔
𝑻𝒂𝒙𝒊𝟖

𝑻𝒂𝒙𝒊𝟐𝟐
𝑻𝒂𝒙𝒊𝟐𝟑
𝑻𝒂𝒙𝒊𝟐𝟒

𝑻𝒂𝒙𝒊𝟏𝟖

𝑻𝒂𝒙𝒊𝟑𝟏
𝑻𝒂𝒙𝒊𝟑𝟐
𝑻𝒂𝒙𝒊𝟑𝟓

𝑻𝒂𝒙𝒊𝟑𝟖
𝑻𝒂𝒙𝒊𝟒
𝑻𝒂𝒙𝒊𝟒𝟓
𝑻𝒂𝒙𝒊𝟒𝟖

𝑻𝒂𝒙𝒊𝟒𝟐
𝑻𝒂𝒙𝒊𝟒𝟓
𝑻𝒂𝒙𝒊𝟒𝟒𝑩𝒊∩
No Taxi

𝑩𝒋

𝑩𝒊∩
No Taxi

𝑩𝟕

𝑩𝟐

∩

𝑩𝟕

𝑩𝟐

No Taxi

∩

𝑩𝟗

𝑻𝒂𝒙𝒊𝟒

Fig. 4.15 Searching for the taxi through block intersection
the single schedule for the first user is established, the next things need to be done is tocalculate whether those potential members are suitable for sharing. The new intersection
could be found in the next two ways: new picking and dropping point are inserted in thecurrent schedule; The path of the current schedule is rerecorded at once. After finding one
intersection, we estimate whether the constraints can be satisfied. There are three steps
should be concerned before new riding: The capacity is still enough for the new rider; Timeand economic cost constraint could hold; Since a new set of passengers is gathered, wereorder the path to guarantee the travel distance in minimum.
It is easy to confirm the current capacity status by the system. Then, we discuss the time
constraint that all the current passengers and new riders should satisfy the time limitation.
Fig.4.16 shows an example that the estimation for a new intersection appears. The current
path is from the picking up point Q1 .o to the dropping point Q2 .d, and this taxi passes Q2 .oand Q1 .d as well. Meanwhile, a potential rider n3 is inserted into this schedule (noted as dashline), and we discuss whether the constraints can be satisfied. To achieve the travel distance
optimally, the system suggests the taxi go to Q3 .o firstly after picking up user n = 1 at Q1 .o.
Then, the taxi picks up n2 at last and drop them one by one. Notice that the optimal pathrelies on the real traffic condition, the path for real travel time in optimal may be different
from travel distance in optimal. Therefore, the optimal path should be calculated once more
after the new schedule is established. Without loss of generality, in the beginning, we use theshortest distance to arrange an optimized route since the calculation for multiple paths is asignificant burden for the overall schedule optimization.
Next, we formulate the time constraint for the new ride-sharing schedule. We use
T |Ox .o → Oy .o| to indicate travel time of current path from point Ox .o to point Oy .o, and51

4.3 Social Network based Scheduling

1

2

3

1
1
2

2
1

3

Fig. 4.16 An example that adding new passenger to the exiting travel plantwx is the time wasted at point Ox . Then, the increased pick up time and arriving time tds
and tdd for this taxi noted as,
tds = T |Q1 .o → Q3 .o| + tw3 + T |Q3 .o → Q2 .o| − T |O1 .o → O2 .o|tdd = T |Q1 .o → Q3 .o| + tw3 + T |Q3 .o → Q2 .o| − T |O1 .o → O2 .d|(4.10)(4.11)

Here, we only assume the situation that the taxi stops and is waiting at O3 .o for the newrider. From the equation, we can know the reorder for user n3 may result in the incrementof arriving time for former user n1 and n2 . Thus, for user n2 , the picking and dropping time
limitation should be satisfied as,
t + T |O1 .o → O2 .o| + tds ≤ Q2 .st.l(4.12)

t + T |O1 .o → O2 .d| + tdd ≤ Q2 .dt.l(4.13)

where the increased travel for new rider should not exceed the time limitation. The above
process is to filter out whether the time constraint can be satisfied for a specific new rider andfind the optimal solution. Next, we discuss how to filter out and select the potential candidate
for sharing through social network communities.

52

4.3.3

Social Taxi Sharing

Social Network based Heuristic Algorithm

Require: Set of candidate users under a cover N, idle taxis M ′ , user request queue Q;
Ensure: Optimized Schedule S with picked passengers m;
while q ← 1 , q <= size(M ′ ) do
Establish a path PathQ1 for Q1 ;Find idle taxi Mq′ ;for j ← 1, j <= am − 1 do
Find potential riders Q′ = MatchPath(Q, PathQ j ) ;Recognizing Community Members in Q′ ;MemberExist ← 1;
while level ← 0, MemberExist == 1 do
if f ind(Community(Q′ ) == level) ;Pick up rider set R from ’Q’ in this level ;MemberExist == 1;
end ;end while
Find the optimal schedule with one passenger y in R;
Add passenger y into idle taxi Mq′ ;Establish a path PathQ j after adding one passenger in R;
Delete passenger y in the Q;
end for
Return Travel Plan Sq ;end while
return S ;Algorithm Objective:
By map planning, we divide the whole city map into blocks, and all the useless information can be filtered out efficiently. Given a subproblem that one passenger is scheduled
in a taxi and available for sharing, we know how to add potential riders and minimize thetravel time and cost. In another word, the system can search for the optimized solution in alimited sized subset. However, the overall searching process increases exponentially by the
number of n′ user request in the queue, and the computation complexity is within O(n′am ),where am is the capacity for the specific taxi m. We need to develop an algorithm that solves
this subproblem within several time slots to reply to the dynamic queue [22]. The mainidea of the algorithm proposed here is finding the passengers who have the most significant
influence to save the cost and improve the QoS. At first, we select the user at the head of thequeue to start a new schedule (first come first served). Then, we run a parallel path-finding

53

4.3 Social Network based SchedulingFig. 4.17 Double path searching on the real map and social network map, to find theintersection of close passengers based on social relationship and real travel planalgorithm to search for the potential passenger set near to the original path, through thereal map and social network community map. Finally, we compare all the options from themultiple paths created by the given set of passengers, and select the best one. Following isthe detail explanation of our proposed heuristic algorithm.
Problem Reduction: This problem is to search for the best solution about, where oneof the main purposes is to find the highest economic benefit. For calculating the integrated
economic benefit in one taxi (or one subproblem), we have
EB = ∑ EB j

where

j∈M

(4.14)

By observation, we find saved economic cost EB j is more likely influenced by farther path.
Meanwhile, we try to put passengers in the same community as many as possible, to increase
the service experience of ride sharing. Therefore, in one taxi, it is an alternative selection that
we consider the passengers in the same group first, which may sacrifice part of the economic
benefit. Based on the principle of first come first served, the system picks up a passenger at
the head of the queue, to establish the first path. Then, it takes the potential passengers in thesame community, and passenger save more money would get the priority. Notice that it is a

54Social Taxi Sharing

fuzzy conception about the relationship strength for users in the same community, and it ishard to give a strict standard that QoS of one combination is undoubtedly higher. Instead,
we find the combination with higher economic benefit is much more perversive, which isalso the main purpose of the activity "sharing" itself. Thus, in the same community, we only
consider the member who may save more cost.
The above analysis is for the candidates in one community are more significant than thecapacity in one taxi. Although in location-based social networks, it is possible that membersin the same community appear in the same local area since they have the same social features
and activities. However, in the more general situation as shown in Fig.4.17, the systemstill needs to find potential passengers out of the community to fulfill the capacity and savetravel cost. Therefore, the system searches for passengers in the nearby community (onehop community) for farther path passengers. Then, on the social network map, the systememissions to find close passengers to increase QoS, while the new adding of passengers
shrink the options of the travel path.
Algorithm Description: Based on the above theory, we have the following schedulingsteps for passenger allocation:(1) Input the user request queue Q and select the first user at the head of it to establish apath. (2) Select all potential passengers from the queue, which satisfy the primary constraints,
noted as Q′ . (3) Pick up users who are both in the queue Q′ and the same community of thefirst user. If more than one is selected, pick the passenger could save the money most. Then,reorder the schedule to optimize the travel route. Otherwise, skip to step 4. (4)With the fixedpassengers in one taxi, filter out users in request queue Q′ again. Pick up users who are in
the same community and renew the queue. If no one is satisfied, find passengers within one
hop in a social community map, then pick up the user needs the farthest path on the real map.
Then, renew the schedule to shrink the temporal request queue further Q′ . (5) Repeat thestep 3 and 4 until the capacity of one taxi is fulfilled. If no one could be found in the queue
before fulfilling, stop the process for current taxi and start step 1 using another taxi.
Algorithm I show the pseudo code of this heuristic algorithm. Notice that this algorithm
is generally applied to the situation am ≤ 4. The algorithm may not perform well if thecapacity of the taxi is more than 4, due to the size limitation of community, which makes
fewer users in one community appear in the same time. However, the algorithm considers
the user experiences as the priority, so the user request at the head is fulfilled first and mostof the request will not be ignored. Besides, we also provide ’comfortable’ companions to
reduce the travel cost, which strives to make the journey more pleasant and economical.
Computation Complexity: The algorithm will terminate if possible combinations using
a different number of passengers are investigated. We preset imax as the number of taxis

4.4 Performance Evaluation

55

online, and assume imax >> w and jmax . The constraint examination takes less than O(i2max )to establish Q′ (pick each candidate i ∈ N and estimate the remaining imax − 1 passengers).
The circulation related to capacity am is normally a constant loop while the two options
inside have the complexity of O(imax ) for each of them. Since they belong to the same nested
loop, the overtime complexity is less than O(i2max ).
Dynamic Social Network Based Scheduling
Algorithm 2 is the pseudo-code of a dynamic scheduling algorithm in order to solve theproblem dynamically. In each time slot, as introduced in the part of the framework, we input
the temporary candidate users N ′ and taxis M ′ into the system. Then, we use algorithm 1
to calculate the result in each time slot and algorithm 2 to update new request and traffic
information from the map. The above procedures repeat and terminate until the end of thetime frame tmax .
Dynamic Social Network Based Scheduling Algorithm;
t = 0;
while t ≤ tmax do
Input candidate users info N ′ , available taxis and travel plan info matrix M ′ , current
request queue Q and economic benefit EB;
Q = NewRequest(Q);Run [Qt , Nt , Mt , EBt ] = Algorithm1(N ′ , M ′ , Q, EB)) ;Remove users scheduled in Qt ;t = t + ∆t;
end while
Return Q = Q + Qt ;4.4

Performance Evaluation

First, we made a prototypical application based on the structure and algorithm we proposed
before, which contains mobile devices as a client and a standard PC as a server. The real
implement test run by mobile devices and the large-scale numerical analysis run by the PC
server, which is introduced below.
Application Test: We run the test on our application using mobile devices. In Fig.4.18,
we start from the front of a university and select the destination near the Bokoi railway
station through the interface, which is a famous railway station but no direct path of public
transport medium. Therefore, sharing a taxi is an economical way to reach the destination.
We submit our basic personal data to the system within the available period from 10:50
to 11:10. Then, the system accepts our demand and replies to us with a detailed result of56

Social Taxi Sharing

Fig. 4.18 Screen shots of an experiment in designed application (A)the sharing arrangement. A demonstration video is shown on our website (http://www3.
muroran-it.ac.jp/enes/%7Ecfzhang/researches.html).
Comparison Algorithm: Besides, we simulate the proposed social network based taxi
sharing service using the proposed algorithm (noted as SONETS) described in section 5. We
perform the simulation in the scenario of Muroran City. Besides, we choose the other threealgorithms for comparing whether the proposed system can accomplish the goal. One of thesocial network based scheduling algorithm only taking users in the same community into
consideration,(noted as SONETS-Single,SS). Another is a similar algorithm which considers
nearby communities, (noted as SONETS-Near,SN). The last one is an optimized distancealgorithm that only concerns the distance optimal to achieve better economic benefit (noted
as Cost-Optimized,CO). It runs only the part of economy benefit constraint and without any
concerns about the social community priority. Notice that the CO is a brute-force algorithm
that calculates all the possible path when the first passenger’s plan is established, which is
the optimum algorithm within the complexity time O(i2max ). The calculation time is O(i4max )for the real optimum algorithm to calculate different goals. However, since the first travel
plan has constrained the potential passenger set, this algorithm runs in a relatively small case.
Various standards are also recorded to compare the performance of these algorithms.
Practical Experiment: Firstly, we dig the local friend dataset on Facebook as our potential consumers, who are all students and faculties in Muroran Institute of Technology.

4.4 Performance Evaluation

57

Fig. 4.19 Screen shots of an experiment in designed application (B)The number of our potential users is more than 350 and all of them have a direct or indirect
relationship with the others. We find these users could be divided into communities automatically, which separated based on the different research areas. Due to the size limitation ofsocial network dataset, we extend the experiment by inputting location-based online social
networks from Stanford large network dataset collection. The set of Brightkite location-based
online social network is analyzed here, where more than 214000 edges are considered as
our potential users and match the size of our city. The destinations of these passengers are
distributed on the city map blocks, based on an adjustable request ratio. Notice that the realprobability of a request can be extracted from the trace studies or other online taxi services
from previous works.
We find the peak time empirically for taxi sharing every day is about three hours, whichis considered as the length of the taxi sharing service window for the simulation. During thisperiod our potential consumers wait at each block, which considered as the start point. The
available time window for each request (available slots, requesting time, etc.) is randomly
picked in our simulations, following the uniform distribution with a fixed average length.
Points at the edge of each block are considered as the start and destination for users.
Analysis of SONETS: Next, we test the setting of parameters in our proposed system.
The price of all the taxi cost (e.g., P0 , P1 ) for consumers is based on the price of daytime in
Hokkaido, Japan. We consider the time frame T is two hours. The taxi distance limitation Z0
and Zmax are set as 2 km and 10 km. The lower limit Z0 is the minimum charge distance, and58

Social Taxi Sharing

3.5
Saved Money / Actual Payment
Average Number of Riders
Request Completing Ratio

3

Ratio

2.5

2

1.5

1

0.5
50

100

150
Number of Taxis

200

250

Fig. 4.20 Different measurements changed by number of taxis

1.8
1.6

Ratio

1.4
Saved Money / Actual Payment
Average Number of Riders
Request Completing Ratio

1.2
1
0.8
0.6
0.4
5

10
15
20
Average Request Window (minute)

25

Fig. 4.21 Different measurements changed by different time window

4.4 Performance Evaluation

59

using bicycles or walking is cheaper and flexible for a shorter distance. The superior limit
could almost reach the edge of our city, and use the public transportation system is more
economical when the travel distance is above 10 km. We divide the map into about 10000
blocks, based on the method in Section 4. Then, two parameters need further discussion, theadjustable average time window of each request and the taxi density in the city.
In Fig.4.20, three measurements are discussed here. The first is the ratio of Saved Money/ Actual Payment. As mentioned above, the saved money is calculated by Eq.4.6. The actual
payment is the sum of real travel cost for all passengers. The average number of riders isthe expected number of riders in a taxi. The request completing ratio is the ratio that therequests from users are fully satisfied before time runs out. Many situations may lead to theskip of taxi request, e.g., no taxi nearby, no idle taxis, no bonus for drivers. Here, we conduct
the situation that drivers are willing to serve for these passengers, since more travel distancemeans more revenue, and this is in line with personal will.
The x-axis is the number of taxis in the city, randomly started in blocks. The real conditionis that in usual time more than 50 taxis are in the city, and we set the request ratio as 0.8% ineach block. The ratio of request completing increases with the number of taxis. At first, only
55.07% requests can be responded, due to the lack of idle taxis. However, with the increasein taxis, more and more requests are responded. The ratio of Saved Money / Actual Payment
decreases by the number of taxis. This is because the overflow of use requests provide more
options for taxis to maximize the revenue and choose a relatively longer schedule. However,
the ratio decreases to 61.16% due to the smaller size of the request queue, since the taxis canserve all the requests at once when a new request is updated. The ratio of the average numberof riders decreases due to the increment of taxis. At first, almost all the taxis are occupied bymore than three users, where the system can make more travel plans to maximized the travel
cost and picked up passengers in a close community. Finally, the occupancy rate falls to 1,
which means part of the taxis remain idle.
In Fig.4.21, the same measurements are discussed here. The differences are, we adjust
the average request time window instead of the density of taxis. Generally, it is acceptablethat users wait for taxi coming within 5-25 minutes, which depends on the personal habits.
From the figure, we can observe that the ratio of Saved Money / Actual Payment increases
significantly with the increase of time window. Since longer waiting time means more optionsin the request queue, the system can arrange travel plan more efficiently to save more money
for passengers. Finally, it reaches almost 66.8% if the acceptable waiting time is within
25 minutes. The request completing ratio increases rarely. That is because the number oftaxis can cover most of the request queue, which keeps the ratio at about 90%. The average
number of riders shows that still part of the passengers take participate in the sharing activity

60Social Taxi Sharing(idle taxis are also calculated). The request of a time window within 10 minutes shows thesame result with the longer one, which means all the requests can be well responded before
skipping. The time window of 5 minutes is too short for idle taxis arriving at the rendezvous.
Performance Comparison: Next, we discuss the performance using different algorithms. As mentioned above, the SONETS-Single and SONETS-Near are the algorithms only
consider sharing partners from nearby communities. Notice that, using the location-basedsocial network dataset, we divide the almost 10000 nodes into 200 communities. Then,the last outside links connecting with other communities are recovered, and these specificcommunities are considered as the single hop communities. The community within two hops
which are also considered as ’close’ communities for SONETS. The purpose of comparing
these social network algorithms is that we can analyze how much economic benefit should
be sacrificed to achieve higher QoS trips. It is also a tradeoff between system service capacity (overall taxi capacity) and higher service requirements (sharing wiliness with outsidecommunities).
Fig.4.22 shows the overall saved money within three hours. We set about 200 carson the city map, and the request ratio in each block changes from 0.2% to 1%. Without
question, the distance optimal algorithm approaches the best performance about economic
benefit, and remains at the same standard when the request ratio is higher than 0.4%. It
is because all the taxis have already been fully loaded. The same trend with the distance
optimal algorithm, our proposed SONETS has no significant difference, and approximate to
the above algorithm when request ratio increases. It is because more potential passengers
are in close communities, and optimize the travel plan could get a higher economic benefit.
The SONET-single algorithm only considers potential passengers in the same community.
Therefore, it is difficult to find partners until the request ratio becomes almost impractical.
The left one, SONET-Near algorithm considers almost 1/3 members in the queue, which
could perform the same trend with former algorithms.
Fig.4.23 shows the sharing efficiency, which uses the ratio of Saved Money / Actual
Payment to estimate the necessity of sharing. The same results with the former figure, fouralgorithms increase with the request ratio. The same with a received view, the sharing
efficiency is unsatisfied if the request ratio is low enough. Based on the results, it is no
specific meaning for sharing if the ratio is lower than 0.4%, since another cost such asincreased travel time has not be taken considered yet.
Fig.4.24, it shows the average number of riders in one taxi. At the start, when the request
ratio is low enough, it is difficult to find sharing partners for all the four algorithms. However,when more request appears, the distance optimal algorithm serves as many passengers as
possible, to achieve a higher seat ratio. Our SONETS consider community members first,

61

4.4 Performance Evaluation

107

9
8

Saved Money (yen)7654SONETSSONETS-Single
SONETS-Near
Cost-Optimized

3
2
1
0.2

0.3

0.4
0.5
0.6
0.7
0.8
Request Ratio in Each Block (%)

0.9

1

Fig. 4.22 Saved cost (economic benefit) Comparison

0.8

Saved Money / Actual Payment

0.7
0.6
0.5
0.4
SONETSSONETS-Single
SONETS-Near
Cost-Optimized

0.3
0.2
0.1
0.2

0.3

0.4
0.5
0.6
0.7
0.8
Request Ratio in Each Block (%)

0.9

1

Fig. 4.23 (Saved cost / Actual cost) Expense Efficiency Comparison

62

Social Taxi Sharing

Average Number of Riders

1.7

1.6

1.5
SONETSSONETS-Single
SONETS-Near
Cost-Optimized

1.4

1.3
0.2

0.3

0.4
0.5
0.6
0.7
0.8
Request Ratio in Each Block (%)

0.9

1

Fig. 4.24 Average number of riders
leading to fewer options than distance optimal. However, it still approximates the former one
since other passengers are also picked if the seat is empty. The seat ratio of SONETS-Single
and SONETS-Near is lower due to more strict standard for partners. However, they all get an
acceptable seat ratio when request ratio increases.
Fig.4.25a is the request completing ratio changed by request ratio in each block. At
first, due to the lack of requests, all the algorithms could handle the new request updated
and serve them immediately. Our SONETS performs better in all around ways due to the’first come, first served’ principle, and less utilitarian to pick up community members that
may save less money. The higher density of community members in the queue, the higher
possibility to combines them, which releases the opportunity for other communities for the
next schedule. The distance optimal (notes as a cost-optimized algorithm) trends to consider
highest profit passengers, when lower profit passengers are ignored all the time, leading to
the lower completing ratio. The other two algorithms achieve lower completing ratio sincesome passengers outside the community does not take into consideration, which leaves someempty seats and makes the system not fully loaded.
Fig.4.25b is the statistical result of ’close’ companions considered in the process. Our
proposed SONETS holds the highest record, due to the greater coverage in social network
communities. The same with SONET-near, they reach the bottleneck to explore new community members because of the system capacity. The algorithm only considers the samecommunity also approaches the limitation when the request ratio increases to 0.6%. The

63

4.4 Performance Evaluation

100
SONETSSONETS-Single
SONETS-Near
Cost-Optimized

Request Completing Ratio (%)

98
96
94
92
90
88
86
0.2

0.3

0.4
0.5
0.6
0.7
0.8
Request Ratio in Each Block (%)0.91(a) Request completing ratio changed by request ration
Number of Users in Close Communities

10000
9000
8000
7000
6000
SONETSSONETS-Single
SONETS-Near
Cost-Optimized

5000
4000
3000
2000
1000
0.2

0.3

0.4
0.5
0.6
0.7
0.8
Request Ratio in Each Block (%)0.91(b) Statistical result of ’close’ companions considered using
different algorithms
Number of Users in Different Communities

10000

9000

8000

7000

6000
Same Group Community
One Hop Community
Two Hop Community

5000

4000
0.2

0.3

0.4
0.5
0.6
0.7
0.8
0.9
Requset Occur Ratio in Each Block (%)1(c) Statistical result of ’close’ companions

Fig. 4.25 Performance about close community members

64

Social Taxi Sharing

cost-optimized algorithm remains at the relatively lower standard for picking their samecommunity members, which shows the same result with randomly picking. Never than less,
we also count the number of passengers in different communities in Fig.4.25c, to analyze thecomposing proportion of passengers. At first, due to the lack of request, SONETS could not
find enough members in the same community, and have to explore outside communities toachieve better sharing efficiency. However, with the increase of request ratio, it is possible
to search for potential passengers in the nearest community, and continuous increase withthe request ratio, the same with SONET-Single algorithm. Therefore, when request overflows, our proposed algorithm still try to improve the sharing environments (as well as QoS),
although the system capacity has already become a limitation.
Through the comparison, we show that the cost efficiency, fairness, and people-oriented
designing are the three features of our proposed algorithm. Instead, our passengers only needto sacrifice 1.16% cost to experience more pleasant and reassuring sharing service than usual
carpooling in rush hours, which is acceptable for most users.

4.5

Conclusion

In this paper, we study the problem of taxi resource allocation that optimizing the trade-off
between travel cost and user experience. The new proposed system considers social network
communities which helps improve the quality of the sharing service. Through map planning,
we concentrate on the city blocks’ connection with routs to make an efficient booking service.
After that, the passengers within close communities are recommended by the proposed
SONETS algorithm. In the experiment, we make an application and apply it well in the realenvironment. The results of large-scale simulation also show that our algorithm can provide
cost efficiency, fairness, and humanized solutions for potential users, which leads to a higher
quality of user experience.

Chapter 5
Battery Maintenance of Pedelec Sharing
System: Big Data based Usage Prediction
and Replenishment SchedulingThis chapter describes the efficiency-oriented maintenance service using AI prediction, toshow a comprehensive solution how to deal with the sustainability issues with the development of urban ITS.
This chapter develops an optimal path planning scheme for replenishment trucks basedon big data analytic and prediction. To the best of our knowledge, we are the first to
use the systematic methodology of Analysis/Modeling/Test to advance the bike prediction
process using the captured datasets, and conduct the hybrid prediction process learns internal
connections between different dataset dimension as well as optimize the overall maintenanceefficiency.
Our contributions are three-fold: Big data based prediction: we develop an efficientoffline prediction scheme based on big data analytics. We use local predictor to analyze
the characteristics of the station itself, global predictor to analyze global correlations, andinflection predictor to deal with unexpected situations. An prediction integrator is used atlast to improve the prediction accuracy; Optimal path planning algorithm: based on thepredicted results, we can analyse the degree of correlation between stations in real time.
After making a station correlation map, a new pedelec maintenance algorithm is developed.
It is able to avoid the problem of repeated charging and charge nodes with high demand,
thus improving charging efficiency; Evaluation and verification: we select NYC’s sharedbicycle data and city-relevant big data for real simulation experiments. After comparison ofprediction accuracy, real-time average power and overall service quantity, it is proved that
our solution is superior to most benchmark algorithms.

66

Battery Maintenance of Pedelec Sharing System

The remaining parts of this paper are structured as follows: Chapter 5.1 discusses thepreliminaries of urban big data and then provides a brief overview of our hybrid pedelec
system for prediction and maintenance. Based on the process of the proposed framework,
Chapter 5.2 discusses the local predictor and global predictor that complete the predictions
using temporal and spatial information, respectively. Next, it discusses how the apparent
inflection impacts the prediction of each station, and finally, an integrator is used to combine
these predictive results. In Chapter 5.3, we develop a weight based algorithm to solve thebattery replacing problems of replenishment trucks. Chapter 5.4 conducts a large-scale
simulation to test different methods, and Chapter 5.5 closes the paper with concluding
remarks.
450

600

500

350
300

Number of Bikes

Number of Bikes

Number of Renting
Number of Returning

Number of Renting
Number of Returning

400

250
200
150

400

300

200

100
100

50
0

0
5

15

10

20

25

5

30

(a) Number of bikes changed by date (station
A)

20

25

30

Days in a Month (2017/03)(b) Number of bikes changed by date (station
B)
60

60
Number of Renting
Number of Returning

Number of Renting
Number of Returning

50

Average Number of Bikes

50

Average Number of Bikes

15

10

Days in a Month (2017/03)

40

30

20

40

30

20

10

10

0

0
2

4

6

8

10

12

14

16

18

20

22

24

Hours in a Day (2017/03)(c) Number of bikes changed by hour (station
A)

2

4

6

8

10

12

14

16

18

20

22

24

Hours in a Day (2017/03)(d) Number of bikes changed by hour (station
B)

Fig. 5.1 Preliminaries for bike sharing records. The statistical result ranges from different
hours and days, for analyzing the potential connections between bike usage and local
meteorologies

67

5.1 System Model and Overview

5.1

System Model and Overview

5.1.1

Impacts of Urban Data on Station Usage

450

Degree & Thousand of an Inch & mph

350

Number of Renting

Temperature
Precipitation
Wind Speed

60
Station 3450
Station 523
Station 492
Station 448

400

300
250
200
150
100

50

40

30

20

10

50

0
0

5
15

10

20

25

25

30

(b) Weather condition changed by date(2017/03)(a) Three nearby stations of A
70

2

1000
Temperature
Station 519
Station 523
Station 492
Station 3167

Precipitation
Station 519
Station 523
Station 492
Station 3167

1.5

50
500
40

Number of Renting

Fahrenheit

20

Days in a MonthDays in a Month (2017/03)

60

15

10

30

800

600
1
400

Number of Renting

5

0.5
30

200

20

0
5

10

15

20

25

30

Days in a Month (2017/03)(c) Number of bikes influenced by temperature

0

0
5

10

15

20

25

30

Days in a Month (2017/03)(d) Number of bikes influenced by precipitation

Fig. 5.2 Preliminaries for bike sharing records. The statistical result ranges from different
hours and days, for analyzing the potential connections between bike usage and local
meteorologies
We first study the interplay between the big citywide data and the pattern of bike usage
which shares insights on the developed prediction scheme. Through our preprocessingof urban big data, it is found that the bicycle usage data have strong correlation with thecharacteristics of the station itself and the global influence: the station location determines
whether the station service type is used for asymmetric travel during busy periods (unbalanced
access), central transit station (high throughput) or edge extension node; Weather, large-scale
activities or temporal high throughput stations around the station will also affect the use of
the stations around an area and cause fluctuations in the use of the whole area.

68

Battery Maintenance of Pedelec Sharing System

A bike usage record set X includes time information, station information, customer
information, and other decryption information. For a single record x, the duration time isnoted as tx , which is related to the start time ts,x and end time tr,x . During the renting period,
it forms a trajectory from start station ssx to return station rsx . Then we make statistics tobuild an index for each station, including the usage amount in different hours and dates.
Fig. 5.1a and Fig. 5.1b show the usage amount of starting and returning in station A andB, respectively. Note that station B is a popular station at downtown and keeps the highest
usage record in March 2017. Station A is the second popular station this month. We canobserve that station B is a ’center node’ in the station network and reflects the usage trend of
the whole city, while station A seems to be a functional area that forms unbalanced demandof bikes. Through Fig. 5.1c and Fig. 5.1d, we find out that station A is in the resident area
since the unbalanced usage ratio in the morning and closing time. Meanwhile, station B is a
civic activity area after closing time. Combining with the results, we can see the daily traffic
flows and detect unusual conditions based on the prediction.
Another high relevant data set is the weather condition, which is similar to [51]. In
Fig. 5.2b, it shows the temperature, precipitation and wind speed in March 2017. In Fig. 5.2c
and Fig. 5.2d, the usage amount in 3 days (14th-16th day) is relatively low, as well as thetemperature. Another observation is that the usage is more sensitive to unusual weather (e.g.,rain) since there is nothing to protect cyclists. It may be related to the uncomfortable weather
since the low temperature and high precipitation in these days. Fig. 5.2a is the usage ofnearby stations compared with station A. The usage from stations nearby follows the same
trend of increase and decrease with station A. The stations far away from station A havemore or less opposite trends with it in.
In a word, these temporal datasets profoundly affect the usage amount of each station.
Meanwhile, the spatial datasets such as coordinators and relative locations reflect the specificfeatures in different areas [5]. Therefore, when building the predictive model, we take these
temporal and spatial features into consideration.

5.1.2

Structure of Scheme

Fig. 5.3 shows the structure of proposed pedelec maintenance system, including three
processes: (1) Preliminary Data Processing; (2) Prediction Process; (3) Maintenance Service.
Preliminary Data Processing: The process of preliminary data processing mainly handles with raw data from temporal and spatial datasets. It also provides the baseline of thepredicting outcomes from local predictor and global predictor [50]. The prediction process
distinguishes the inflection situations in which the usage changes more sharply than a regularstandard and finally aggregates the above results, and the final process aims to provide

69

5.1 System Model and Overview
Preliminary Data
Processing
BicycleRecords

Prediction Process
Local
Predictor

Geographic
Information

GlobalPredictor

Smart Service

Map
AnalysisInflection
Predictor

Weather
Infomation

Maintenance Service

Integrator

Route
DesignFig. 5.3 The framework of the pedelec maintenance system. Our work contains three part,
preliminary data processing for raw data, prediction process for usage trend prediction, andmaintenance service for pedelec maintenance tasks
the routes for each maintenance fleet based on the calculation of our sharing maintenanceoptimization algorithm.
Prediction Process: Firstly, it loads the raw big data sets through different resources
and formats them to meet the predictive model [37]. The raw temporal data includes all
bike usage records in recent years, the weather report. The raw spatial data includes station
coordinator and local meteorology.
First, we use two normal predictors: the local predictor and global predictor. The local
predictor uses temporal data sets to predict the rough result as a baseline, which only takes theusage record from itself into consideration and will not be influenced by outside stations. The
global predictor calculates the influence from nearby stations, such as the direction of bikeflows, relative distance, and other spatial correlation. The two predictors are combined at theend of this process, where different predictors play essential roles in very different cases. For
example, usually, the bike records follow the result of a local predictor. When a traffic flow
comes at the closing time, it increases the usage of nearby station significantly. Notice that thereason why we divide the predicting process into two parts is the distinction between temporalfeatures and spatial features. They have no overlap with each other. Besides, the prediction
based on a mass of temporal features is mainly trained by linear regression, in which thecomputation cost is relatively low. The spatial features are less but are complicated enoughfor learning model [19]. With the integration of these two predictors, all the data sets will be
trained more accurately than putting all of them into a single learning model [56]. When theweather of strong storm or low temperature comes, the usage ratio of each station will drop
tremendously for a while. This kind of drop is easy to be detected but hard to be trained as aregular model [55]. Therefore, these individual cases should be picked out and trained byanother predictor. Then, we analyze the sudden drop instances based on the observation anddevelop a classification method that minimizes the variance while keeping most of them as

70Battery Maintenance of Pedelec Sharing System

ordinary cases [42], where a series of thresholds describes the classification method. This
process of inflection detecting and predicting model is triggered when one of these features isbeyond its threshold. As mentioned above, these unusual cases only influence the results fora few hours but change the line sharp significantly. We treat them as another data set of bikeusage records and train them separately. When the inflection predictor detects the inflection,
it provides the calculated deviation before the final aggregating. The independence of thisprocess can emphasize the impact of extreme conditions, which improves the accuracy of thewhole process. The process of predictor aggregating integrates the predictions of preliminary
data and inflection data. This hybrid system predicts the result in future time intervals. For
the sake of understanding, we divide the prediction of future usage into hours, from 1 to 6
hours and one day in the future, respectively. The final prediction stores in a maintenancemonitoring server.
Maintenance Service: In real maintenance works, the schedule depending on real-timedata is not efficient enough since there are relatively long delays before the replenishment
fleet arriving at the target station. Due to the delay, most of the low battery bikes maybe
out of the station, which makes the current data based schedule meaningless [9]. Instead,depending on the prediction of history data, the system follow the pattern of pedelec traffic
flow and outputs the schedule. We propose an algorithm that calculates the optimized routes
for replenishment trucks to exchange empty batteries. The maintenance monitor advises
the administrative department with new updated predictions. The new records are updated
in every time interval, then our system calculates the replenishment schedule dynamically.
When the real-time usage record is very different from the prediction, usually the difference
is more significant than a threshold, we have sufficient reasons that there may be someemergency situation or accident in a specific area. The emergency monitoring server notifies
the administrative department of the city. Meanwhile, our system calculates the escape route
if necessary.

5.2

Hybrid Prediction ModelIn this section, we discuss how the local predictor, global predictor and inflection predictor
work to create predictions results, and finally gather them together using prediction integrator.

5.2.1

Local Predictor

Local predictors are primarily based on the characteristics of station itself to predict future
usage. They are quantitatively analyzed for environmental and land form disturbances. The

5.2 Hybrid Prediction Model

71

local predictor trains the temporal data sets including: 1) the usage record in the past days at
the station; 2) the local meteorology (such as temperature/precipitation/snowfall/wind speed,or certain types of weather like Thunder/Ice Pellets/Blowing Snow); 3) calendar related
information (holiday/weekend and workday); and 4) weather forecast information.
These features have correlation with the bike usage by the observation of our raw
resources. All these features are formulated into numerical matrices, and are used as theoriginal numerical format of National Weather Forecast Office of U.S.A: the data sets
indicating one particular state of a period, such as thunder, ice pellets and even holiday,
are formatted as binary variables, e.g. f oggy = 1 indicates this period is foggy; and othercontinuous data sets, e.g., temperature, precipitation, keep in standard matrices. The windspeed is the average wind speed in miles per hour (mph). The precipitation is the total
precipitation in one day to the nearest hundredth of an inch. PSBL is the percentage ofpossible sunshine, which sensed by dividing the minutes of sunshine by the total possible
minutes; Some data sets related to human-made activities rules, are described by different
binary variables even they belong to the same category. For example, Monday is zero andSaturday is one if the system wants to predict the traffic trend on Saturday.
Based on the input temporal data sets, the prediction on future few hours is computed.
Here, we pick up the data set in the recent few days as the input. Since time is passing, theinput of training sets changes every hour. We predict the recent six hours. For the next twodays, we predict the intervals of each six hours. The reason why we use interval instead ofhour is that the predictions of recent six hours are strongly influenced by the current datawhen the prediction of 7 to 48 hours roughly follows the historical trends.
Next, we discuss the details of linear regression modeling here. At first, as introduced in
Section 3, we convert all the features into numeric documents: boolean values are changed
into (0, 1) to represent the extreme weather (storm/thunder/snow); All of the date informationis changed into timestamps and 1 to 7 to present the weekday. Notice that the alreadypredicted results will not be put into the modeling process again since it may cause theiterative error due to the previous predictions. Also, the numeric weather forecast data set
may change periodically, which affects the bike usage prediction distinctly.

5.2.2

Global Predictor

Not only local needs affect the usage of bikes, but the traffic flows from nearby stations also
impact on the bike demand [51] [49], and a global predictor could predict it. The motivation
for using a global predictor is that there is some connectivities between specific stations.
Usually, a small surge in usage also affects the surrounding stations in the future. We inferindirectly the growth of bike usage based on the surrounding stations.

72

Battery Maintenance of Pedelec Sharing System

According to our statistics, users keep a speed of 10 to 15 km/h by cycling and 86.4% of
the duration time are below 20 minutes (in 2016/04). The service condition of nearby stations
plays an essential role in the prediction of the current station, which should be taken into
consideration. To understand the geographical connections between stations, we develop a
Bicycling Sharing Radar Cross Model (BSRC) to describe the nearby bike usage conditions.
Fig. 5.4a shows the BSRC which represents the bike usage of nearby stations for station 491(coordinator [40.741 -73.983]) in 2017/03. We divide the radar plane into fan shapes, noted
as Q1 , Q2 , Q3 , Q4 , · · · . The number in each fan shape means the number of renting records inthis station. In one fan shape, we divide it into three regions based on the distance ([0, 500],[501, 1000], [1001 ∞] meters). Each region contains the sum of bike usage in the same fan
shape with the specific distance range. The three different kinds of color (green, yellow, red)means the different number of levels ([0,20], [21 40], [41 ∞]). From the figure, we can findthat the bike renting ratio in region 1 of fan shape q1 and q8 is relatively high since there are
public service facilities (hospitals, etc.) within 500 meters. However, region 3 in q8 is small
since most of this region is water area. The Fig. 5.4b shows the BSRC of returning recordin station 491 at the same time. Through this BSRC, the nearby stations can be regarded astraffic flow sensors to support the prediction of the target station.
Following are reasons why we turn associative zone to a BSRC and integrate the spatial
data sets into the definition of regions:
1. It is impossible that we put all stations’ data into the learning system individually. The
server can not afford the cost of computation when facing the ever-increasing usage
demand [15]. At the same time, the time cost also prevents the real deployment ofan online service. The BSRC decreases the number of inputs significantly, and thetraining model can save the time that learns the geographic association by itself. The
only thing we need to adjust is the number of regions m.
2. We use the total usage amount instead of the usage record that flows to the target
station because it cannot reflect the real traffic flows. For instance, bad weather may
cause a lower usage ratio of bikes. On the opposite, the lack of available bikes in peaktime may also cause the decrease of bike usage.
3. Several pairs of stations have no direct path due to the river and highland. Therefore,
these stations may become redundant in the prediction process. However, these stations
still can reflect the popularity of sharing bike system during a specific period.
4. The adjustable number of fan shapes provides the adaptability in different cities.
Different sizes of angles represent the sensitivity of this model from directions, anddifferent lengths of regions show the gradients that influenced by distance.

5.2 Hybrid Prediction Model

73

After aggregating the spatial data into regions, we form the mentioned BSRC into
arrays with the time series. Besides, not only the recent usage record is formed, othernotable features are also considered in the BSRC: 1) weather features in the specific regions,
including wind speed, humanity, temperature, precipitation, snowfall, minutes of sunshine,other unusual weather conditions (Fog/Thunder/Ice pellets/Hail/Glaze or Rime/Blowing Dust
or Sand/Smoke or Haze/Blowing Snow/Tornado). 2) public service facilities, including thoseused for educational (schools, libraries), recreational(hospitals, parks, theaters, stadiums),
and cultural (museums, memorial halls) buildings.
Fig.5.5 shows the structure of input data and ANN for prediction. For the sake ofsimplification, all the datasets are formatted into numbers. The usage number of bicycle start
Startx and return Endx records are counted based on the updating. The Weatherx indicatesthe average temperature among these stations, and each station counts other parametersthat represent states in this fan. For example, Pubx states the number of public service
facilities, which presents the importance of residential activity center for citizens’ daily
activities. As the same, the statistical results from the same fan are input to the full-connected
neutral network group by group, with the order of i divided fan shapes and j distance based
regions. Similar to Section 4.1, we predict the future hours based on the interval of six hours,
respectively. Notice that the format proposed above is just an example in one interval (sixhours), here we input the data within recent one week.
Then, we feed the data set into the 3-layer artificial neural network, which the time costand accuracy are acceptable after adjusting several parameters. The output is the incrementof bicycle usage ∆Usage comparing with the ’current’ number of bicycle usage. Then, we
can predict the usage in future k hours Usaget+k = Usaget + ∆Usage. This value is also
estimated by a threshold to detect the sudden change of bicycle usage in the city, which
discussed later.

5.2.3

Inflection Predictor

An inflection predictor is proposed here to handle these sudden changes. Generally, The
usage record of a station may increase or decrease sharply during a few time intervals dueto the sudden changes of terrible rainfalls. Although we can filter these unusual situations
to make a genetic one, and applies to most situations, they genuinely show the apparent
influence to people’s daily life, and moreover, the reaction in emergency situations.
For instance, the heavy rain and strong breeze can stop most citizens’ bike travel. As aresult, the usage records in some stations keep 0 through one day. These kinds of significant
curve deformation we call them inflection situations, and then we extract these data sets fromthe normal ones by the following steps:

74

Battery Maintenance of Pedelec Sharing System

High Usage
Normal Usage

43.83

32.06

Low Usage

5.90

9.61
37.35

3.67

18.83

67.19

4.70

34.29

48.35

41.61

64.93

54.51

34.33
5.35

75.35

14.09

25.8

6.93

7.83

11.93

66.83

42.54

(a) A shared bike radar cross Model of station 491 (start)
High Usage
Normal Usage

44.1

33

Low Usage

9.58
35.67

3.64

18.80

5.87

65.58

4.74

32.9

47.51

40.6

66.32

55.45

33.22
5.80

73.6

14.67

68.32

6.8

24.87
8.29

12.06
42.25

(b) A shared bike radar cross Model of station 491 (end)Fig. 5.4 An example of BSRC. The red circle is high usage (> 40), yellow is normal usage(20 → 40), and green is low usage (< 20). The distance of regions is classified as 500, 1000
and infinite in meter.

75

5.2 Hybrid Prediction Model
New Updated Dataset
1𝑺𝒕𝒂𝒓𝒕𝟏

𝑬𝒏𝒅𝟏

𝑾𝒆𝒂𝟏

……

𝑷𝒖𝒃𝟏

2

𝑺𝒕𝒂𝒓𝒕𝟐

𝑬𝒏𝒅𝟐

𝑾𝒆𝒂𝟐

……

𝑷𝒖𝒃𝟐

……

……

𝑺𝒕𝒂𝒓𝒕𝒊+𝟏

i+1

……

……

……

𝑬𝒏𝒅𝒊+𝟏

𝑾𝒆𝒂𝒊+𝟏……

𝑷𝒖𝒃𝒊+𝟏

……

……

……

……

……

……

ij-1

𝑺𝒕𝒂𝒓𝒕𝒊𝒋−𝟏

𝑬𝒏𝒅𝒊𝒋−𝟏

𝑾𝒆𝒂𝒊𝒋−𝟏……

𝑷𝒖𝒃𝒊𝒋−𝟏ij𝑺𝒕𝒂𝒓𝒕𝒊𝒋

𝑬𝒏𝒅𝒊𝒋

𝑾𝒆𝒂𝒊𝒋

……

𝑷𝒖𝒃𝒊𝒋

……

𝒄𝟏

𝑷𝒖𝒃𝟏

𝑺𝒕𝒂𝒓𝒕𝒊𝒋 𝑬𝒏𝒅𝒊𝒋 𝑾𝒆𝒂𝒊𝒋……

𝑬𝒏𝒅𝟏 𝑾𝒆𝒂𝟏

𝑷𝒖𝒃𝒊𝒋
𝒄𝒒

……

𝑤1

……

𝑤11

𝑤𝑝𝑞
𝒃𝒒

𝒃𝟏
𝑤′1

𝑤′𝑞
∆Usage (∆𝑈𝑖 )Fig. 5.5 Structure of input data set and a 3-layer artificial neural network for prediction. The
table is an exsample of format for each input samples. The network structure shows theconnection between input of train set, hidden neurons and output of future changes
1. Make the rough selection to separate the inflection dataset S′ from the whole data sets
S : At first, we set a threshold based on common sense to point out the unusual usage
record. In a case of station A, if the number of records in one hour is 200% bigger
or 10% than the average (603 and 30, respectively), we consider these records as theinflection dataset S′ which may infect the usage curve deformation massively.
2. Find the notable sudden change ’ interval’: A sudden change interval for a feature(e.g., temperature) is a continuous numerical interval that the distribution of set S′ inthis feature is higher than the distribution of set S − S′ . For example, if the intervalof temperature is more than 35 degree Celsius until the infinite, it means the usage
distribution of set S′ is higher in this interval and lower than S − S′ in other degrees.
Similar with Fig. 5.6a, We plot the probability distribution of set S′ and the complementary set S − S′ for each feature. Then we can observe the intervals from featuresthat the probability distribution in dataset S′ is greater than S. These intervals are
considered as the distinctive sudden change intervals for describing inflection data

76

Battery Maintenance of Pedelec Sharing System(or the distinctive category for discrete feature). When the feature of one new record
falls into the distinctive interval, we can classify this record to dataset S′ and active theinflection predictor.
3. Assign the distinctive intervals as thresholds. The range of multiple distinctive intervalsof a feature may be suitable for a given data set S′ . However, we still need to find theprecise connections if one feature holds multiple intervals. To find the precise set of
distinctive intervals, we define an environmental fitness Q to form the notable interval
selection problem into a coverage ratio optimization problem, where we haveQ=|y||D(y′ ) − D(y)| |x|·( ′ −)′|D(x ) − D(x)| |S | |S − S′ |(5.1)

where the absolute value signs |S′ | indicates the number of records in S′ . x and y are
the records belong to S and S − S′ . D(x′ ) − D(x) indicates the difference of data squareerror before and after adding a new given set of distinctive intervals. Through thefitness Q, we can search for the notable interval set which covers most of the inflection
records and affects them. This problem can be solved by a genetic algorithm or particle
swarm optimization, which depends on the data scale.
4. Train an inflection predictor with the highest fitness interval set. After finding thehighest fitness interval set, we update the inflection dataset S′ , which could satisfy
all the thresholds (or intervals) and discrete features (e.g., thunder). Then we put thedataset S′ back to local predictor and global predictor train a new hybrid predictivemodel independently, the process is similar to the mentioned predictor.
For training such a model, the input is the updated dataset S′ and other environment
information. Notice that not all the usage records are included in the original defined set since
the original definition is developed to discover the inner connections of the strange usage
phenomenon and general standards for handling inflection and sudden changes. Therefore,
the collection of input data set is the usage records satisfied by the mentioned constraints,
and we use another paralleled process of the former predictor (local and global predictor)
to calculate the results, where we could carefully keep the consistency with the previous
process. To distinguish the difference, we claim as the inflection predictor, and the output
is the increment of bicycle usage ∆Usage, comparing with the defined ’current’ data set.
When the time goes, and newly updated records come to the prediction system, it estimateswhether they fall into the threshold and trigger on the inflection predictor if necessary. The
system separates the records in two sets, S − S′ and S′ , and fed them into regular predictive
precess or inflection predictor, respectively. The purpose of the additional means is that the5.2 Hybrid Prediction Model77

predictive model is a response mechanism that could handle the sudden changes smartly,
including but not limited to the unusual situations like disasters and large-scale activities.
By inputting other environmental information such as weathers, they predict the resultsfrom each predictor. Finally, all the predictive results of ∆Usage are combined in prediction
integrator to general a more precise result.
Based on the equation proposed in page 6, we find the three features of temperature,
perception and wind speed have an apparent difference of distribution using different sets.
However, when processing these unusual situations, based on our results in Section 5.2,
the accuracy is not as high as a usual predictor, where we consider our inflection detection
method could only cover part of the sudden change phenomenon. Still, it could help improve
the accuracy in final result comparing with usual predictor only processing.

5.2.4

Prediction Integrator

The prediction integrator combines the results of three predictors. By observation, we findthat usually, the local predictor plays an essential role if it is serenity. However, the global
predictor affects the prediction significantly when there are large-scale activities nearby. As
mentioned before, lousy weather affects humans’ intention of bike traveling. Therefore, we
use a decision-making tree as the final step of our prediction process. Fig. 5.6b shows anexample of a decision-making tree, and both continuous and discrete features are consideredin this process. To process the continuous features, we use the influence of variance to detect
the partition thresholds. The feature which has the most significant decrease of variancewill be selected as the first ramification point of the proposed discussion-making tree. Then,the process estimates the other features in the next two separated branches and continues
to create branches. Finally, it generates a level limited decision-making tree, where thecharacteristics of the model determine the elastic number of levels. Here, we only find theresults from the three predictors have the relatively high influence on the different leaves,and the features of weather are next.
For a specific leaf i in the decision-making tree, we use a linear regression of bike renting
usage Ni and returning usage Ni′ to combine these prediction results and features, where wehave

Ni =ai,1 · Local + ai,2 · Global + ai,3 · In f lection(5.2)

where ai indicates the different coefficient impacted by predictors and weather features. We
use a simple linear regression to train these coefficients for each leaf Ni . For training these78

Battery Maintenance of Pedelec Sharing System

Probability distribution

𝑺 -𝑺′

𝒙𝟏

𝑺′

𝒙𝟐

𝒙𝟑

𝒙𝟒

(a) An example of finding the sudden change interval x1 → x2 and x3 → x4 (thedash line shows the probability distribution of inflection data set and full line
show the usual dataset)

𝑵2

𝑵4

𝑵3

𝑵5

≥0.028 U≥0.01 U

≥0.015 U<0.015 U
Local

Local

<0.025 U≥0.025 U

𝑵7

𝑵6

Local

<0.04 U

GlobalGlobal𝑵𝟏≥0.04 U|∆U|≥0.05 U|∆U|<0.05 U
Inflection(b) A shared bike radar cross Model of station 491 (end)Fig. 5.6 An example of sudden change interval and decision making treecoefficients, the input is considered as the prediction results from each predictor, and output
is considered as the real increment comparing with current usage. Based on our observation,
the prediction result from local, global act as the similar behaviors and inflection predictors
perform relatively higher coefficient when the weather seems unusual (e.g., the temperature
is high). Other features (Wind-speed) make the prediction a fine-tuning.

5.3 Pedelec Maintenance Optimization Algorithm

79

Above all, the three predictors have no overlap and can predict the bike usage independently. Next is the pseudo code of the overall prediction process. When new usage records
updated by the online service, the system predict the usage in future time intervals immediately using the already trained prediction model. At first, the system estimates whether it isnecessary to trigger on the inflection predictor based on the future environment information(e.g., weather forecast), then put the updated data set U into the predictors. Finally, throughthe trained decision making tree and different coefficients in it, the integrator combines thesepredictive results and emphasizes different increments to meeting with the complicated andfickle traffic environment as the time goes. The Algorithm is :Require: U: updated new bike usage record from the service; tmax : the number of targeted
predictive results based on different time interval; C: thresholds to trigger on the inflection prediction process; In f ot : other environmental information in future time intervalt;Ensure: Predictive result of usage increment ∆Usage;
Array ∆Usage = {0};for t = 1 : tmax do
if In f ot satisfies one of the conditions in C thenInput U to In f lection Predictor and get ∆Ut,3 ;else∆Ut,3 = 0;
end ifInput U to Local Predictor then get ∆Ut,1 ;Input U to Global Predictor then get ∆Ut,2 ;Active Prediction Integrator to combine the results ∆Ut = Integrator(∆Ut,3 + ∆Ut,2 +∆Ut,1 );
end forUpdate the prediction array ∆U using ∆Ut ;5.3

Pedelec Maintenance Optimization Algorithm

The usage of renting and returning, bike storage of each station are predicted through above
process, and we use these predictions to design a feasible optimization algorithm for every
replenishment truck, to exchange the batteries at each station.
We divide our solution into two steps: (1).Construct a less incompatible maintenance map
to offer suitable station-to-station links; (2).Reduce the dynamic replenishment problem into a80Battery Maintenance of Pedelec Sharing System

Compatible①②④

Incompatible

○

③

③

②
①

④

②

③

①
④

②
③

②

①
②

③

④

③
④

④

⑤

Fig. 5.7 An example of less incompatible maintenance map (solid and dashed lines arecompatible and incompatible links between stations. Numbers from 1 to 4 present an feasible
route for one truck.)classical TSP. (3).Develop a heuristic algorithm called intelligence sharing bike maintenanceoptimization algorithm (IMOA) to improve the performance.

5.3.1

Less Incompatible Maintenance Map

As discussed earlier, it will cause the overlapped problem if several trucks go around in thesame area. The bikes may happen to follow the same route with the replenishment truck andserved twice[39] [52].
For such a problem, we set an indicator ri, j to indicate the proportion of returning at
station i from the renting station j. Then we set a threshold r ≤ ri, j to indicate a lessincompatible link from station i to j. As shown in the Fig.Fig, imaginary lines are theincompatible links that are closed to each other and may cause overlapped problems. We use
the average distance of the collected distances of each most extended incompatible station,
noted as l1 . Considering the time cost on the road, and there are more than 400 stations in thecity, our replenishment truck complete more than k maintenance mission within an hour. We
set a maximum range for each mission. Therefore, the trucks can guarantee k missions within
one hour, noted as l2 . Therefore, we can construct a less incompatible maintenance map to
indicate the candidate links (distance ∈ [l1 , l2 ]) from stations to stations that the trucks canfollow. The stations that nearby enough (less than l1 ) are considered as incompatible links
and the stations that far away are considered out of truck’s moving range.

5.3 Pedelec Maintenance Optimization Algorithm81

For instance, Fig. 5.7 shows an example of less incompatible maintenance map, where
the solid line is the feasible links between stations and dashed lines mean the indicator is toohigh for constant maintenance. The numbers indicate the feasible steps of each route andlinked by the stable route. Through it, the system can narrow down the optional range of next
stations and reduce the computation time.

5.3.2

Reduced Dynamic Replenishment Optimization Problem

After making a less incompatible maintenance map, we design routes for trucks that cover
lower battery remaining stations as many as possible. We assume there are w replenishment
trucks from the warehouse and s ∈ G stations are available for bike maintenance. We consider
this warehouse as an origin point, which considered as an additional ’station’ on the map.
Therefore, this problem is reduced into a traveling salesman problem (TSP): Given a map list
D of vertices(stations) and arcs(links) between each pair of cities, find the optimal route thatsatisfies maximized demands D among all the cities.
Different from the classical static TSP problem, the replenishment demand of eachstation is continuously changing [63]. Although the calculated schedule may be the optimal
solution in current period [20], however, as the time goes by, the solution cannot fit with thedemand change in each station. One potential solution is the genetic algorithm, which is abionic optimization algorithm and has the capability of random large-scale search [40]. The
calculation speed is adjustable and comfortable to combine with other algorithms, and issuitable for static TSP problems [17]. However, the feedback in the system is not enough inour dynamic problem. Furthermore, when the demand of each station floats, it often createsa lot of inaction redundant Diego generation and may enter the local value, which makes theefficiency of the system very low.
With the observation above, combining the advantages of ACO (Ant Colony Optimization) and GA [24][7], we propose an intelligent pedelec maintenance optimization algorithm,
which is based on the pheromones on the links left by the former trucks [45], to improve theefficiency of the whole system. This algorithm can make trucks no longer confined to thepheromones when selecting the path, and make the use of existing information and search
new path synchronously. It correctly increases the randomness and diversity of solutions anddramatically enhances the robustness of the basic heuristic algorithm.
To fit this specific problem, we describe the TSP problem again: There is a total numberof n stations in the city, noted as (1, 2, · · · , n ∈ V ). One truck departs from station 1 to start
its tasks, where the probability travels to city i is noted as p1i , and the probability travels
to another city p1 j is independent. No matter how many time it takes at the station i, thetime serving in other cities will be delayed by t1i . For instant, one truck starts at station 1,

82

Battery Maintenance of Pedelec Sharing Systemthen p11 = 0 and t = 0. It costs time ti j for the truck travel from station i to station j, whereti j = vdi j and v is average speed of replenishment trucks. If the task at station i is completed,
the truck travel to another station k with the probability pik . The optimization goal is that
we design a schedule which contains the stations with the highest expected number of lower
battery bikes.
Require: G = (V, A): created incompatible maintenance map contains vertex and arc; w:
number of replenishment fleet; U: prediction results of bike usage; q: set qth best
replenishment schedule;
Ensure: Schedule P;
Set incompatible indicator array σ = IncIn(U);Set travel probability array p = TravelArc(z0 , σ );Pheromone array z = z0 ;for each g = 1; g ≤ Generation; g + +; doPath = {0};Temporary Station Set V ′ = V ;for each i = 1; i ≤ w; i + + do
Pathi = RouteSelection(V ′ , p);
Delete stations in Pathi from V ′ ;end for
Sort Path and Select best qth schedules, Path′ ;Pheromone array z = U pdatePhe(z, Path′ );Travel probability array p = TravelArc(z, σ );end for
P = Path;
1: t = 0;
2: while t ≤ tmax do

Input Updated G = (V, A), w,U;
4:
Pt = AlgorithmII(G, w,U);
5:
t = t + ∆t;
6: end while
return P;
3:

5.3.3

Intelligent Maintenance Optimization Algorithm

Next, we take the demand of each station into consideration. Trucks tend to select a pathwith higher demand, lower distance and higher pheromone provided by former trucks. Our

83

5.3 Pedelec Maintenance Optimization Algorithm

prediction process predicts the demand for replenishment task, and pheromone is the patternthat describes the relativity of one link in a traditional optimized solution.
According to the above concerns, we define the probability that the truck travels toanother station as,

pi j =

βz σ ij ijβz σ ∑ ik ik0,, where i, j, k ∈ V ′(5.3)

where i = j

where zi j indicates the pheromone of the link from station i to station j and set a parameter z0
as an initial value. β is the adjustable parameter and V ′ = {1, 2, · · · , n} −V0 is the candidate
βstations, where V0 is the set of stations served recently. σi j indicates the importance ofstations’ maintenance order, which try to find the station with empty battery bikes as manyβas possible. The importance σi j we define here is,β

σi j =

U · Sr1·
Sb · ti j c ·CS + d · MS

(5.4)

where U, Sr , Sb is the predicted bike storage, renting ratio and returning ratio. CS is thenumber of nearby served stations and MS is the number of nearby marked stations that areplanned to be served. c and d is the adjustable parameter. ti j is the time cost if travels toβstation j. This σi j considers the possibility of dry battery bike storage in current stations, aswell as the spreading of bikes before and after maintenance.
The algorithm allows the trucks to find the optimal path for updating the pheromones,
and tehen this parameter is updated globally, noted aszi j ← (1 − φ ) · zi j + φ · △zi j(5.5)

where φ ∈ [0, 1] and △zi j = Di j which indicates the total number of served bikes at station jusing the journey i to j.
However, before the system converges to global optimal solution, the current solution
may fall into the local minimum, which leads to a stop of iterations. In order to avoid this,
we update the rule of pheromones. At each iteration, only trucks with the best solutions canupdate zi j . We select q trucks with the best q solution, and the definition of pheromones
becomes,mzi j ← (1 − φ ) · zi j + ∑ φ · △zi j,q
q=1

(5.6)

84

Battery Maintenance of Pedelec Sharing System

where the new △zi j,q we define here is, Di j , where i, j ∈ V ′q△zi j,q =0,where i = j(5.7)

where q indicates the qth optimal solution in current system.
When the new updated of prediction results come, firstly, the system modifies theincompatible map and reset the incompatible indicator array σ and travel probability arrayp. Then, set the initiate pheromone array as z0 and enter into the iterations process. The
main steps of iteration in the algorithm are described as the following: (1) We set w trucks
and input the current prediction result. These trucks travel to another station following theless incompatible map and use Eq.5.3 to select the next station. (2) When all the trucks
finished their journeys, the system sorts the qth best solution and uses Eq.5.6 to update thepheromones ∆z on the arcs. (3) Reset all the trucks into the initial state and update the travel
probability p between stations using new pheromones ∆z. (4) Repeat the above steps until
the number of iterations runs out. Finally, the system outputs the optimized route as P.
The above steps are the process in our proposed IMOA algorithm, where Algorithm 2 isthe pseudo code. At first, we input the prediction results and construct a less incompatible
maintenance map. Then, we use Algorithm 2 to train a model and calculate the detailed
schedule for each truck. Finally, our IMOA outputs the routes with specific stations and timestamp for each time interval, using the dynamic variant routing algorithm (pseudocode in
Algorithm 3).

5.4

Simulation

This section verifies the performance of our proposal using simulations. In each simulation,
we apply the proposed pedelec maintenance system in a real-world city map. The settingsof pedelecs and city big data sets are extracted from the open data of governments, then thedata is input to the proposed system.

5.4.1

Settings

We use the open data of bike sharing system ’Citibike’ in NYC for our simulations. ’Citibike’
is a widely used data set that has already been visualized. Besides, the geographic information
and weather information are also well discussed by other studies [4]:85

5.4 Simulation’Pedelec’ and Battery: As mentioned above, Pedelec is a kind of electric bike that is very
useful when riding in hills or strong winds. Since there is a revaluation about the battery
in these e-bikes, we consider three different types of power replenishment system in thesimulations, lead-acid battery (or other conventional battery about 15 Ah), lithium-ion battery(e.g., 24 Ah) and lithium iron phosphate battery (e.g., 48 Ah) [38]. For an adult, he can keep
the speed of 6 km/h without pedaling or keep the speed of 10 to 13 km/h within the range of
100 kilometers under the support of electronic controller [44]. Therefore, we assume one
lithium ion battery can keep working for 6 to 8 hours. When a Pedelec needs maintenance,
the replenishment truck can install a new battery on it instead of the empty battery if stoppingat the station [1]. Since they all use rechargeable batteries, we assume one replenishment
truck can replace all the batteries at the station.
’Citibike’: It is a set of sharing bike records starting with 2013/12 and ending with
2017/04 in the website of Citibike, and we have shown the statistical result of total usage
in Section 3.1. One essential record contains trip duration, start time & stop time, start
station & end station, station locations, start time & end time, coordinator, etc. As counted
in the introduction, there are more than 600 stations. We choose the data for this year(2017/03-2017/05) as our testing data, and the others are considered as training data.
Weather Report and Forecast: We use the data set of National Weather Service Forecast
Office for our study. One essential record in a specific area (e.g., central park) contains
the date, max & min & average temperature, precipitation, snowfall, direction & speed &peak of wind, particular weather (fog, thunder, tornado), etc. The most exciting thing is thatcompared with other traffic flows (such as cars or metro) [23], the activities of bike travelingare more sensitive to the weather condition. In another word, lousy weather inflects our’human sensors’ significantly.
Geography Information: Google API is applied in our study to gather useful geography
information that helps the system understand the geographical correlations between stations.

5.4.2

Accuracy of Predictor

First, we analyze the accuracy of each predictor and discuss how a citywide big dataset
performs for the pedelec maintenance system. Fig. 5.8a and Fig. 5.8b shows the average
probability and error of bike usage at each station. We input 15 days’ data and predict thebike usage in recent two days. The linear regression only method reaches the accuracy of
67.39% within recent 6 hours, where the accuracy is defined as,n

A = 1 − ∑ (U −Ui )/ ∑ Ui
i=1

i

(5.8)

Battery Maintenance of Pedelec Sharing System
1

25

Average Eorror

Prediction Accuracy

86

0.8
0.6
0.4
0.2
0

20
15
10

5
0

1h-6h

Linear regression（LR）

6h-12h12h-24h

LR+Week（WK）

24h-48h

LR+WK+Weather（WE）

1h-6h

Linear regression（LR）(a) Average accuracy in each station

6h-12h12h-24h

LR+Week（WK）

24h-48h

LR+WK+Weather（WE）(b) Averaged error in each station

Fig. 5.8 Local predictor using citywide big data
where U indicates the number of bike usage record. However, the additional week data (notedas 1 to 7) shows no help for the prediction, which means no strong connection with bikeusage. The same with the observation in Section 3, the weather information shows important
influence on the prediction, and it reaches 81.68% within new 6 hours. The average error isdefined as,n

E = ∑ (U −Ui )/n

(5.9)

30

1

Average Eorror

Prediction Accuracy

i=1

0.8

0.6
0.4
0.2

0

20
15
10
5
0

1h-6h

6h-12hInflection Prediction（IP）

12h-24h24h-48h1h-6h6h-12hInflection Prediction（IP）

LR+WK+WE+IP+Integrator(a) Global predictor using citywide big data
(average accuracy in each station)

12h-24h24h-48h

LR+WK+WE+IP+Integrator(b) Global predictor using citywide big data
(averaged error in each station)
30

1

Average Eorror

Prediction Accuracy

25

0.8

0.6
0.4
0.2

25

20
15
10
5
0

0

1h-6h

6h-12hANN

12h-24h

ANN+BSRC

24h-48h(c) Inflection predictor and integrator using
citywide big data (average accuracy in eachstation)1h-6h6h-12hANN

12h-24h24h-48h

ANN+BSRC(d) Inflection predictor and integrator using
citywide big data (averaged error in each station)

Fig. 5.9 Comparison of different prediction model5.4 Simulation87

It shows the prediction result is below 10.200 for all the stations, while linear regression
only method and additional week data can help reach 19.011% and 18.846%, respectively.
Fig. 5.9a and Fig. 5.9b show the prediction result of global predictor. We input 15 days’
data and use an ANN to learn the result. The historical usage data reaches an accuracy of
75.26%, which is better than linear regression only method. Then, we use additional global
information from other stations and form them in the BSRC, and the accuracy of the results
reaches 87.12%. The average error of ANN + BSRC is 7.275 within new 6 hours, which is
the half of ANN only prediction (13.86). Besides, both the average error and accuracy lookwired between 24 hours and 48 hours. We set the number of neurons in a hidden layer arounds = log(2N), where N is the number of neurons in the input layer. To keep it real, we use one
parameter setting that the accuracy in 6-12h is the highest (6-12h is more meaningful for real
deployment). Based on our observation, there is no big difference for the future 6-12, 24 and48 hours as the predictive result for ANN. Besides, it also a powerful piece of evidence that
our system design could avoid accumulated errors from previous predictions. The system
could predict more extended future hours parallelly with the near future, without interferencewith each other, which is also one of the advantages. Fig. 5.9c and Fig. 5.9d show theaccuracy of our inflection predictor and integrator. Since the inflection predictor processes
the sudden change data sets, including about 10% of the total records, The upper and lower
limits of the result are very high, therefore, the accuracy only can reach 55.68% about new
6 hours and the average error is 22.15. However, the prediction integrator successfully
combines the results of the local predictor, global predictor, and inflection predictor, andthe accuracy is 90.11%, 88.2%, 79.69% and 76.58% in recent 48 hours. The average error,
which is a good result that, the prediction with averaged 6.78 error is approached, and keeps
it below 15 within recent two days.

5.4.3

Results Comparisons of IMOA

In the experiment, we apply four maintenance strategies to evaluate our system. One strategy
is the optimal solution that assuming all the future usage records have already been foreseen,
and replenishment trucks ignore distance to travel immediately (noted as Optimal Solution,
OS). IMOA method uses our proposed algorithm and the predicted results. Similar with [? ],the third algorithm uses the standard nearest neighbor procedure (NNP) with highest bikestorage. The fourth one completes replenishment tasks at stations without strategy (randomly
selection, RS).
Fig. 5.10a, it shows the number of charged bikes during a day in 2017/04. For simplicity,
we assume the replenishment trucks exchange all the batteries of bikes at the stations andthen ignored the charge time. All the Pedelecs start with a random state of charge which

88

Battery Maintenance of Pedelec Sharing System
1

9000

Replaced Bikes

7000

Average Battery Capacity Remaining

OS
RS with Predicted Data
NNP with Predicted Data
IMOA with Predicted Data

8000

6000
5000
4000
3000
2000

0.9
0.8
0.7
0.6
0.5

IMOA with Predicted Data
RS with Predicted Data
NNP with Predicted Data
OS

0.4
0.3
0.2

1000
2

4

6

8

10

12

14

16

18

20

22

2

24

4

6

8

10

Hour

(a) Battery replaced bikes changed by the hour
in a day (10 replenishment trucks)

14

16

18

20

22

24

(b) Battery remaining changed by the hour ina day (10 replenishment trucks)
0.9

Average Battery Capacity Remaining

0.9

Average Battery Capacity Remaining

12

Hour

0.85
0.8
0.75
0.7
6 Supply Vehicles
8 Supply Vehicles
10 Supply Vehicles
12 Supply Vehicles
14 Supply Vehicles
16 Supply Vehicles
18 Supply Vehicles
20 Supply Vehicles

0.65
0.6
0.55
0.5
0.45
2

4

6

8

10

12

14

16

18

20

22

24

Hour

(c) Battery remaining changed by number ofreplenishment trucks

0.8

0.7
Lithium Ion Batteries
Lithium Iron Phosphate Battery
Conventional Battery

0.6

0.5

0.4

0.3
2

4

6

8

10

12

14

16

18

20

22

24

Hour

(d) Battery remaining changed by different
batteries

Fig. 5.10 Performance of four strategies by different settings
follows the uniform distribution. We assume that replenishment trucks are working during
the day. The x-axis is the time series and we account every hour. The y-axis is the numberof charged bikes, and 9765 bikes in 612 stations are monitored in that day. Except for thelowest one, we find the other three maintenance strategies can find the optimized route using
their strategies. With the scatting of our replenishment trucks, the peak comes at 6 a.m.
Another reason is the increment of traffic flows, while our IMOA algorithm based strategy
can follow the traffic flows and stop at the stations with more bike storage. The next peakcomes at 5 p.m., which is the closing time for citizens. From the figure, we can observe thatour proposed algorithm outperforms the other two since we take the emission traffic trend of
charged bikes into consideration.
Fig. 5.10b shows the average remaining battery using the same setting. The y-axis is
the change of the average remaining battery among all bikes. Similar to the former figure,
we can observe that our IMOA algorithm can detect the traffic flows smartly. However, the5.4 Simulation89

remaining battery can reflect the active maintenance. Therefore, the slope about remaining
battery is more smooth than the number of charged bikes. Finally, the remaining battery
stays at a moderate level as well as the others.
Fig. 5.10c and Fig. 5.10d are the average remaining battery using different settings. The
former one is the average remaining battery changed by different replenishment trucks. The
number of replenishment trucks is related to the maintenance cost. More replenishment
trucks keep the average remaining battery of all bikes at a higher level. From the figure, we
can say, our algorithm could significantly improve the average battery capacity remaining
when the number of replenishment trucks is rare. Then, the growth trend decreases with theincrease in vehicles, due to over more completable links on the city map. The latter one isabout the different batteries. We assume all the bikes use only one type of batteries. The
lead-acid battery can support average 3 hours while the up to date lithium iron phosphatebattery keeps working for about 12 hours. Therefore, the remaining battery of the lead-acidbattery cannot keep a higher standard since it runs down very quickly. The other two canfinally keep average 76.3% and 88.7% batteries if the replenishment trucks keep working.
The figure also shows the proposed optimization algorithm is indispensable for the old typeof batteries since the demand for the battery change is more prominent. It also shows theadvantage of new batteries, which has the strong robustness and lower maintenance demandin limited replenishment situations.

5.4.4

IMOA using Different Bikes

Next, we discuss the impact of low battery bike, which refers to the quality of user experience
using these electric powered bikes. The primary purpose of the proposed algorithm is tokeep the average remaining battery of all bikes at a high level, to ensure the normal operationof the share-bike system, and eliminate low battery bikes through our maintenance systemsince the power outage in use may lead to shorter travel distance and more human resources
consumption. Therefore, the demand from each station that replacing low battery bike is anecessary evaluation standard in our simulations. Fig. 5.11a shows the number of low battery
bikes using the same setting and algorithms. If the replenishment fleet uses the random
selection method, averaged more than 6000 bikes keep the remaining battery lower than 30%
and the total number of bikes in our system is 9765, which means 62.7% bikes need battery
replacement within two hours. The nearby selection algorithm keeps the remaining battery ata lower standard and reaches the minimum due to the high traffic flow in the morning. Our
proposed IMOA algorithm performs better than the former one due to the better maintenanceschedule, and reach 0 minimum at the start of 8 o’clock. If we carefully analyze the curve of
IMOA, as shown in Fig. 5.11b, we can observe that the different level of remaining battery

90Battery Maintenance of Pedelec Sharing System
5000

7000

Battery 10%
Battery 20%
Battery 30%
Battery 40%
Battery 50%

Number of low battery bikes

Number of low battery bike (30%)

4500
6000
OS
IMOA with Predicted Data
RS with Predicted Data
NNP with Predicted Data

5000

4000

3000

2000

4000
3500
3000
2500
2000
1500
1000

1000

500
0

0
2

4

6

8

10

12

14

16

18

20

22

24

2

4

6

8

10

12

Hour

(a) Number of low battery bikes changed by
the hour (10 replenishment trucks)

16

18

20

22

24

(b) Number of low battery bikes by the hour
(10 replenishment trucks)
4500

Number of replaced low battery bikes (30%)

4500

Number of replaced low battery bikes

14

Hour

Battery 10%
Battery 20%
Battery 30%
Battery 40%
Battery 50%

4000
3500
3000
2500
2000
1500
1000
500
0
2

4

6

8

10

12

14

16

18

20

22

24

Hour

(c) Replaced low battery bikes changed byhour

Conventional Battery
Lithium Iron Phosphate Battery
Lithium Ion Batteries

4000
3500
3000
2500
2000
1500
1000
500

2

4

6

8

10

12

14

16

18

20

22

24

Hour

(d) Replaced low battery bikes (different battery) changed by hourFig. 5.11 Performance of battery replacing demandfollows the same trend. Notice that the number of lower battery bikes (10%, 20%, 30%)
reaches the same point at the 8, 18, 24 o’clock since the replenishment fleet patrols at the ’hotspot’ stations in order to replace more batteries and some bikes in edge stations are ignored.
Fig. 5.11c shows the number of replaced low battery bikes for one day, and we distinguishthe different level of the remaining battery to observe the result. As mentioned above, there
are always demand the replacement of low battery bikes, and this figure shows how many
demands have been satisfied through our IMOA. The higher number means more low battery
bikes are satisfied, which creates the opposite slope with the former figure in most cases. The
number of replaced bikes is also related to the number of trucks, and more trucks remain
the battery ratio at the relatively lower standard. Fig. 5.11d shows the influence of different
battery. Using the same setting as former one (10 trucks and same map information), the leadacid battery bikes reach the 30% line more often than lithium ion and lithium iron phosphateembedded bikes. Through the figure we can say, in most of the case, the new lithium iron

5.5 Conclusion

91

phosphate embedded bikes do not need to worry about the power shortage problem with amedium size of replenishment fleet. It also proves that only a smaller replenishment fleet
is needed to reach the same performance as the normal battery, which greatly reduces thereplenishment cost. In a word, our proposed algorithm performs better than the other classicalsolutions, and the average remaining battery keeps at a relatively higher standard. Besides,
the demand for low battery replacing is also satisfied well, which make the whole prediction
and scheduling system feasible.

5.5

Conclusion

This paper has studied the maintenance of pedelec system based on big data analytics,
which meets the growing maintenance demand of new types. We have first studied the realworld urban data sets from all collect-able dimensions to explore the relations of different
ingredients on the usage of sharing bikes. After that, a new hybrid predictive model todigitize the useful information in various fields and predict the future trend of bike usage has
been developed. Finally, using the prediction outputs, a heuristic algorithm called intelligent
share bike maintenance optimization algorithm (IMOA) has been proposed to solve themaintenance problem for replenishment trucks. Through simulations, we have verified our
proposal from all angles and validate that the accuracy of our prediction model is high enoughand IMOA solves the maintenance problem efficiently.
In the future, we intend to extend our work in two dimensions. First, the proposedsystem is feasible for NYC. However, the different landform and weather condition could
significantly influence the bike usage and changes the inner connections between various
datasets. We plan to develop a universal model to apply in different cites. Second, theefficiency and performance bound of the proposed algorithm have not been thoroughly
investigated. We intend to use more artificial intelligence technologies to improve theperformance of the whole system.

Chapter 6
Conclusion and Future Work
6.1

Conclusion

In this thesis, we investigate the exssting problem in urban ITS and achieve the transmission
performance, user experience, system sustainability in urban intelligent transportation system.

6.1.1

Next-generation vehicle networking technology using Thz

To improve the performance issues, we study the impact of terahertz band towards vehicle
networks. THz band communication relieves the spectrum scarcity and capacity restrictionof the existing communication systems. In short range, the THz link can be considered
as a transmission window with almost 1 THz, which supports the growing real-time datatransmission. Moreover, we develop an autonomous terahertz relay algorithm called ATLR
which gives the advice of ideal relaying position to bypass obstacles and avoids stronger
NLOS fading. Finally, we apply this algorithm in autonomous vehicle network. It helps
create more flexible communication environment and provide more traffic information to
nearby autonomous vehicles. Actually, not limited to autonomous vehicles on the road,terahertz band can be widely applied to all mobile nano-cell networks, such as delivery
drones or UAVs (Unmanned Aerial Vehicle). Different kind of ’vehicles’ has very different
ability to adapt communication environments. These ’vehicles’ support the exploration of
missing details, which helps human beings and human made machines understand the known
world more smartly.

94

6.1.2

Conclusion and Future Work

User-oriented taxi sharing service using social network

To improve the experience issues, we study the problem of taxi resource allocation that
optimizing the trade-off between travel cost and user experience. The new proposed system
considers social network communities which helps improve the quality of the sharing service.
Through map planning, we concentrate on the city blocks’ connection with routs to make anefficient booking service. After that, the passengers within close communities are recommended by the proposed SONETS algorithm. In the experiment, we make an application andapply it well in the real environment. The results of large-scale simulation also show that ouralgorithm can provide cost efficiency, fairness, and humanized solutions for potential users,
which leads to a higher quality of user experience.

6.1.3

Efficiency-oriented maintenance service using AI prediction

To improve the sustainability issues, this paper also studies the maintenance of pedelec
system based on big data analytics, which meets the growing maintenance demand of new
types. We have first studied the real-world urban data sets from all collect-able dimensions
to explore the relations of different ingredients on the usage of sharing bikes. After that, a
new hybrid predictive model to digitize the useful information in various fields and predict
the future trend of bike usage has been developed. Finally, using the prediction outputs, aheuristic algorithm called intelligent share bike maintenance optimization algorithm (IMOA)
has been proposed to solve the maintenance problem for replenishment trucks. Throughsimulations, we have verified our proposal from all angles and validate that the accuracy ofour prediction model is high enough and IMOA solves the maintenance problem efficiently.

6.2

Future WorkIn the future, we intend to extend our work in three dimensions. First, not limited toautonomous vehicles on the road, terahertz band can be widely applied to all mobile nanocell networks, such as delivery drones or UAVs (Unmanned Aerial Vehicle). Different kindof ’vehicles’ has very different ability to adapt communication environments. We plan totransfer our technology to all kinds of vehicles. Next, humanized solutions for potential users,
which leads to a higher quality of user experience, need a more solid measurements to show
a specific factor for detail comparison. Then, we can arrange passengers more precisely. At
last, the proposed system is feasible for NYC. However, the different landform and weather
condition could significantly influence the bike usage and changes the inner connections
between various datasets. We plan to develop a universal model to apply in different cites.

6.2 Future Work95

Meanwhile, the efficiency and performance bound of the proposed algorithm have not beenthoroughly investigated. We intend to use more artificial intelligence technologies to improve
the performance of the whole system.

References[1] Abagnale, C., Cardone, M., Iodice, P., Strano, S., Terzo, M., and Vorraro, G. (2015).
Power requirements and environmental impact of a pedelec. a case study based on real-life
applications. Environmental Impact Assessment Review, 53:1 – 7.
[2] Agatz, N., Erera, A., Savelsbergh, M., and Wang, X. (2012). Optimization for dynamic
ride-sharing: A review. European Journal of Operational Research, 223(2):295 – 303.
[3] Akyildiz, I. F., Jornet, J. M., and Han, C. (2014). Terahertz band: Next frontier for
wireless communications. Physical Communication, 12:16–32.
[4] Almannaa, M. H., Elhenawy, M., Ghanem, A., Ashqar, H. I., and Rakha, H. A. (2017).
Network-wide bike availability clustering using the college admission algorithm: A casestudy of san francisco bay area. In 2017 5th IEEE International Conference on Models
and Technologies for Intelligent Transportation Systems (MT-ITS), pages 580–585.
[5] Caggiani, L., Camporeale, R., and Ottomanelli, M. (2017). A real time multi-objective
cyclists route choice model for a bike-sharing mobile application. In 2017 5th IEEE
International Conference on Models and Technologies for Intelligent Transportation
Systems (MT-ITS), pages 645–650.
[6] Chard, K., Bubendorfer, K., Caton, S., and Rana, O. F. (2012). Social cloud computing: A
vision for socially motivated resource sharing. IEEE Transactions on Services Computing,5(4):551–563.
[7] Chen, D. (2017). Solving a new type of tsp using genetic algorithm. In IECON 2017 43rd Annual Conference of the IEEE Industrial Electronics Society, pages 3333–3339.
[8] Chen, P.-Y., Liu, J.-W., and Chen, W.-T. (2010). A fuel-saving and pollution-reducing
dynamic taxi-sharing protocol in vanets. In Proceedings of the 72nd IEEE VehicularTechnology Conference Fall (VTC 2010-Fall), pages 1–5.
[9] Chen, Q., Liu, M., and Liu, X. (2018). Bike fleet allocation models for repositioning in
bike-sharing systems. IEEE Intelligent Transportation Systems Magazine, 10(1):19–29.
[10] Cheng, T. and Wicks, T. (2014). Event detection using twitter: A spatio-temporalapproach. PLoS ONE, 9(6):e97807.
[11] Chusseau, L., Lampin, J., Bollaert, S., Duvillaret, L., and Mangeney, J. (2005). Thz
active devices and applications: a survey of recent researches. In Microwave Conference,
2005 European, volume 1, pages 4–pp. IEEE.

98

References[12] Cui, X., Gulliver, T. A., Li, J., and Zhang, H. (2016). Vehicle positioning using 5g
millimeter-wave systems. IEEE Access, 4:6964–6973.
[13] Deshpande, P., Kodeswaran, P. A., Banerjee, N., Nanavati, A. A., Chhabra, D., andKapoor, S. (2015). M4m: A model for enabling social network based sharing in theinternet of things. In Proceedings of the 7th International Conference on Communication
Systems and Networks (COMSNETS 2015), pages 1–8.
[14] Dong, M., Liu, X., Qian, Z., Liu, A., and Wang, T. (2015). Qoe-ensured price competition model for emerging mobile networks. Wireless Communications, IEEE, 22(4):50–57.
[15] Dong, M., Ota, K., and Sakai, M. (2013). A novel information dissemination system forvehicle-to-rsu communication networks. In 2013 International Conference on Connected
Vehicles and Expo (ICCVE), pages 918–919.
[16] d’Orey, P. M., Fernandes, R., and Ferreira, M. (2012). Empirical evaluation of a
dynamic and distributed taxi-sharing system. In 2012 15th International IEEE Conferenceon Intelligent Transportation Systems, pages 140–146.
[17] Elloumi, W., Baklouti, N., Abraham, A., and Alimi, A. M. (2013). Hybridization of
fuzzy pso and fuzzy aco applied to tsp. In 13th International Conference on HybridIntelligent Systems (HIS 2013), pages 105–110.
[18] Ezirim, K. and Jain, S. (2015). Taxi-cab cloud architecture to offload data traffic from
cellular networks. In 2015 IEEE 16th International Symposium on A World of Wireless,
Mobile and Multimedia Networks (WoWMoM), pages 1–6.
[19] Fu, Y., Sun, D., Wang, Y., Feng, L., and Zhao, W. (2017). Multi-level load forecasting
system based on power grid planning platform with integrated information. In 2017
Chinese Automation Congress (CAC), pages 933–938.
[20] Gong, D. and Ruan, X. (2004). A hybrid approach of ga and aco for tsp. In Fifth World
Congress on Intelligent Control and Automation (IEEE Cat. No.04EX788), volume 3,
pages 2068–2072 Vol.3.
[21] Guo, L., Dong, M., Ota, K., Li, Q., Ye, T., Wu, J., and Li, J. (2017). A secure mechanism
for big data collection in large scale internet of vehicle. IEEE Internet of Things Journal,
4(2):601–610.
[22] Guo, S., Dong, M., and Guo, M. (2008). Performance analysis of heuristic algorithms
for lifetime-aware directional multicasting in wireless ad hoc networks. In Advanced Information Networking and Applications - Workshops, 2008. AINAW 2008. 22nd International
Conference on, pages 1311–1316.
[23] Hoang, M. X., Zheng, Y., and Singh, A. K. (2016). Fccf: Forecasting citywide crowd
flows based on big data. In Proceedings of the 24th ACM SIGSPATIAL International
Conference on Advances in Geographic Information Systems, GIS ’16, pages 6:1–6:10,
New York, NY, USA. ACM.
[24] Honda, K., Nagata, Y., and Ono, I. (2013). A parallel genetic algorithm with edge
assembly crossover for 100,000-city scale tsps. In 2013 IEEE Congress on Evolutionary
Computation, pages 1278–1285.

References99[25] Hosni, H. E., Farhat, N., Nimer, R., Alawieh, N., Masri, C. E., Saroufim, M., Artail,H., and Naoum-Sawaya, J. (2012). An optimization-based approach for passenger toshared taxi allocation. In Proceedings of the 20th International Conference on Software,
Telecommunications and Computer Networks (SoftCOM 2012), pages 1–7.
[26] Huang, Q. and Yuan, F. (2010). The linkage mechanisms between gas price and the taxi
fare in china. In Management and Service Science (MASS), 2010 International Conferenceon, pages 1–4.
[27] Jia, J. and Zhang, Q. (2013). Rendezvous protocols based on message passing in
cognitive radio networks. IEEE Transactions on Wireless Communications, 12(11):5594–
5606.
[28] Jornet, J. M. and Akyildiz, I. F. (2011). Channel modeling and capacity analysis forelectromagnetic wireless nanonetworks in the terahertz band. IEEE Transactions on
Wireless Communications, 10(10):3211–3221.
[29] Khan, A., Correa, O., Tanin, E., Kulik, L., and Ramamohanarao, K. (2017). Ridesharing is about agreeing on a destination. In Proceedings of the 25th ACM SIGSPATIALInternational Conference on Advances in Geographic Information Systems, page 6. ACM.
[30] Kim, J.-T., Lee, J.-H., Kim, S., and Kim, I. K. (2013). Social contents sharing modeland system based on user location and social network. In Proceedings of the Third
International Conference on Consumer Electronics Berlin (ICCEBerlin 2013), pages
314–318.
[31] Kleine-Ostmann, T. and Nagatsuma, T. (2011). A review on terahertz communications
research. Journal of Infrared, Millimeter, and Terahertz Waves, 32(2):143–171.
[32] Kong, L., Khan, M. K., Wu, F., Chen, G., and Zeng, P. (2017). Millimeter-wave wirelesscommunications for iot-cloud supported autonomous vehicles: Overview, design, andchallenges. IEEE Communications Magazine, 55(1):62–68.
[33] Kong, X., Xu, Z., Shen, G., Wang, J., Yang, Q., and Zhang, B. (2016). Urban traffic congestion estimation and prediction based on floating car trajectory data. Future
Generation Computer Systems, 61:97–107.
[34] Kürner, T. (2012). Towards future thz communications systems. Terahertz Science andTechnology, 5(1):11–17.
[35] Li, H., Ota, K., Dong, M., and Guo, M. (2017a). Mobile crowdsensing in software
defined opportunistic networks. IEEE Communications Magazine, 55(6):140–145.
[36] Li, N., Oyler, D. W., Zhang, M., Yildiz, Y., Kolmanovsky, I., and Girard, A. R.
(2017b). Game theoretic modeling of driver and vehicle interactions for verification andvalidation of autonomous vehicle control systems. IEEE Transactions on Control Systems
Technology, PP(99):1–16.
[37] Li, Y., Gao, J., Lee, P. P. C., Su, L., He, C., He, C., Yang, F., and Fan, W. (2017c).
A weighted crowdsourcing approach for network quality measurement in cellular data
networks. IEEE Transactions on Mobile Computing, 16(2):300–313.

100

References[38] Liu, C. T. and Hsu, R. C. (2015). A fuzzy q-learning based assisted power management
method for comfortable riding of pedelec. In 2015 6th International Conference on
Automation, Robotics and Applications (ICARA), pages 580–585.
[39] Liu, Z., Dong, M., Zhang, B., Ji, Y., and Tanaka, Y. (2016a). Rmv: Real-time multiview video streaming in highway vehicle ad-hoc networks (vanets). In 2016 IEEE Global
Communications Conference (GLOBECOM), pages 1–6.
[40] Liu, Z., Dong, M., Zhang, B., Ji, Y., and Tanaka, Y. (2016b). Rmv: Real-time multiview video streaming in highway vehicle ad-hoc networks (vanets). In 2016 IEEE Global
Communications Conference (GLOBECOM), pages 1–6.
[41] Lomotey, R. K. and Deters, R. (2014). Architectural designs from mobile cloudcomputing to ubiquitous cloud computing - survey. pages 418–425.
[42] Lv, F., Zhu, H., Chang, S., and Dong, M. (2017). Synthesizing vehicle-to-vehiclecommunication trace for vanet research. In 2017 IEEE International Conference on Smart
Computing (SMARTCOMP), pages 1–3.
[43] Ma, S., Zheng, Y., and O., W. (2015). Real-time city-scale taxi ridesharing. IEEE
Transactions on Knowledge and Data Engineering, 27(7):1782–1795.
[44] Minakov, I., Passerone, R., and Rossi, M. (2017). Design and energy optimization ofa multifunctional iot solution for connected bikes. In 2017 Global Internet of Things
Summit (GIoTS), pages 1–6.
[45] Mohammed, M. M. A., He, C., and Armstrong, J. (2017). Performance analysis of acoofdm and dco-ofdm using bit and power loading in frequency selective optical wirelesschannels. In 2017 IEEE 85th Vehicular Technology Conference (VTC Spring), pages 1–5.
[46] Nguyen, A. T., Li, B., Welzl, M., and F., E. (2011). Stir: Spontaneous social peer-topeer streaming. In Proceedings of IEEE Conference on The Computer Communications
Workshops (INFOCOM WKSHPS 2011), pages 816–821.
[47] Ota, K., Dong, M., Chang, S., and Zhu, H. (2014). Mmcd: Max-throughput andmin-delay cooperative downloading for drive-thru internet systems. In Communications(ICC), 2014 IEEE International Conference on, pages 83–87.
[48] Ota, K., Dong, M., Chang, S., and Zhu, H. (2015a). Mmcd: Cooperative downloadingfor highway vanets. Emerging Topics in Computing, IEEE Transactions on, 3(1):34–43.
[49] Ota, K., Dong, M., Chang, S., and Zhu, H. (2015b). Mmcd: Cooperative downloadingfor highway vanets. IEEE Transactions on Emerging Topics in Computing, 3(1):34–43.
[50] Ota, K., Dong, M., Zhu, H., Chang, S., and Shen, X. (2011). Traffic information
prediction in urban vehicular networks: A correlation based approach. In 2011 IEEE
Wireless Communications and Networking Conference, pages 1021–1025.
[51] Pan, B., Zheng, Y., Wilkie, D., and Shahabi, C. (2013). Crowd sensing of traffic
anomalies based on human mobility and social media. In Proceedings of the 21st ACM
SIGSPATIAL International Conference on Advances in Geographic Information Systems,
SIGSPATIAL’13, pages 344–353, New York, NY, USA. ACM.

References

101[52] Paul, F. and Bogenberger, K. (2014). Evaluation-method for a station based urbanpedelec sharing system. Transportation Research Procedia, 4:482 – 493. Sustainable
Mobility in Metropolitan Regions. mobil.TUM 2014. International Scientific Conference
on Mobility and Transport. Conference Proceedings.
[53] Torres, S., Lalanne, F., del Canto, G., Morales, F., Bustos-Jimenez, J., and Reyes, P.
(2015). Becity: sensing and sensibility on urban cycling for smarter cities. In 2015 34th
International Conference of the Chilean Computer Science Society (SCCC), pages 1–4.
[54] Vegni, A. M. and Loscri, V. (2015). A survey on vehicular social networks. IEEE
Communications Surveys Tutorials, PP(99):1–1.
[55] Wang, X., Zhou, Z., Yang, Z., Liu, Y., and Peng, C. (2017). Spatio-temporal analysis andprediction of cellular traffic in metropolis. In 2017 IEEE 25th International Conference
on Network Protocols (ICNP), pages 1–10.
[56] Wang, Y., Du, B., Rong, Q., and Lin, X. (2016). Travel patterns analysis of urban
residents using automated fare collection system. Chinese Journal of Electronics, 25(1):40–
47.
[57] Wu, J., Dong, M., Ota, K., Li, J., and Pei, B. (2014). A fine-grained cross-domain access
control mechanism for social internet of things. In 2014 IEEE 11th Intl Conf on UbiquitousIntelligence and Computing and 2014 IEEE 11th Intl Conf on Autonomic and Trusted
Computing and 2014 IEEE 14th Intl Conf on Scalable Computing and Communications
and Its Associated Workshops, pages 666–671.
[58] Yao, X., Shen, X., Wang, L., and He, T. (2017). Hybrid bicycle allocation for usage
load balancing and lifetime optimization in bike-sharing systems. In 2017 18th IEEE
International Conference on Mobile Data Management (MDM), pages 112–117.
[59] Yu, X. and Fan, C. (2014). Ecological analysis of smart city based on the numericalsimulation technology. In 2014 Fifth International Conference on Intelligent Systems
Design and Engineering Applications, pages 438–441.
[60] Yu, X., Pan, A., Tang, L.-A., Li, Z., and Han, J. (2011). Geo-friends recommendationin gps-based cyber-physical social network. In Advances in Social Networks Analysis andMining (ASONAM), 2011 International Conference on, pages 361–368.
[61] Zhang, S. (2014). Influence of relationship strengths to network structures in social network. In Communications and Information Technologies (ISCIT), 2014 14th International
Symposium on, pages 279–283.
[62] Zhang, S., Ma, Q., Zhang, Y., Liu, K., Zhu, T., and Liu, Y. (2015). Qa-share: Towards
efficient qos-aware dispatching approach for urban taxi-sharing. In Sensing, Communication, and Networking (SECON), 2015 12th Annual IEEE International Conference on,
pages 533–541.
[63] Zheng, Y., Capra, L., Wolfson, O., and Yang, H. (2014). Urban computing: concepts,
methodologies, and applications. ACM Transactions on Intelligent Systems and Technology(TIST), 5(3):38.

102

References[64] Zhou, Z., Dong, M., Ota, K., Shi, R., Liu, Z., and Takuro., S. (2015). Game-theoretic
approach to energy-efficient resource allocation in device-to-device underlay communications. Communications, IET, 9(3):375–385.
[65] Zhou, Z., Ota, K., Dong, M., and Xu, C. (2017). Energy-efficient matching for resource
allocation in d2d enabled cellular networks. IEEE Transactions on Vehicular Technology,
66(6):5256–5268.

Publications
Journals
1. Chaofeng Zhang, Mianxiong Dong, Kaoru Ota, Jian Qiu, Minyi Guo, "Social Taxi
Sharing: A Cyber-Physical Approach for Efficient Urban Transportation Service,"
ACM Transactions on Cyber-Physical Systems (TCPS), In Press.
2. Chaofeng Zhang, Kaoru Ota, Juncheng Jia, Mianxiong Dong, "Breaking the Blockage
for Big Data Transmission: Gigabit Road Communication in Autonomous Vehicles,"IEEE Communications Magazine, vol. 56, no. 6, pp. 152-157, June 2018.
3. Chaofeng Zhang, Mianxiong Dong, Kaoru Ota, Minyi Guo, "Social Network Optimized Taxi Sharing Service for Smart Cities," IEEE IT Professional, vol. 18, no. 4, pp.
34-40, July-Aug. 2016.

Proceeding of International Conference
1. Chaofeng Zhang, Kaoru Ota, Mianxiong Dong, "Cooperative Positioning Optimizationin Mobile Social Networks," in Proceedings of IEEE 84th Vehicular Technology
Conference, 2016.
2. Hidekazu Suzuki, Mianxiong Dong, He Li, Kaoru Ota, Chaofeng Zhang, "Overlay
Optimization for Cost Efficient P2P Streaming Service", Joint 8th International Conference on Soft Computing and Intelligent Systems and 17th International Symposium on
Advanced Intelligent Systems (SCIS & ISIS2016), Sapporo, Hokkaido, Japan, August25-28, 2016.

Under Review
1. Chaofeng Zhang, Mianxiong Dong, Tom H. Luan and Kaoru Ota, "Battery Maintenance of Pedelec Sharing System: Big Data based Usage Prediction and Replenishment
Scheduling," IEEE Transactions on Network Science and Engineering, Minor Revision.