Report PW19SS101 PDF

Dissertation on
“Dynamic Taxi Ride Sharing for distributed taxi Network”

Submitted in partial fulfillment of the requirements for the award of degree of
Bachelor of Technology
in
Computer Science & Engineering
Submitted by:
Aishwarya Manjunath 01FB15ECS019
Akshaykanth D L 01FB15ECS031
Anusha Kamath 01FB15ECS048
Under the guidance of
Internal Guide External Guide

Dr. Snehanshu Saha Vaskar Raychoudhury
Professor, Associate Professor,
PES University Miami Univeristy
January – May 2019
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

FACULTY OF ENGINEERING
PES UNIVERSITY
(Established under Karnataka Act No. 16 of 2013)
100ft Ring Road, Bengaluru – 560 085, Karnataka, India

PES UNIVERSITY
(Established under Karnataka Act No. 16 of 2013)

100ft Ring Road, Bengaluru – 560 085, Karnataka, India
FACULTY OF ENGINEERING
CERTIFICATE
This is to certify that the dissertation entitled
‘Title of the project’

is a bonafide work carried out by
Aishwarya Manjunath 01FB15ECS019

Akshaykanth D L 01FB15ECS031
Anusha Kamath 01FB15ECS048
In partial fulfilment for the completion of eighth semester project work in the Program of Study
Bachelor of Technology in Computer Science and Engineering under rules and regulations of PES
University, Bengaluru during the period Jan. 2019 – May. 2019. It is certified that all corrections /
suggestions indicated for internal assessment have been incorporated in the report. The
dissertation has been approved as it satisfies the 8th semester academic requirements in respect
of project work.
Signature Signature Signature

Dr. Snehanshu Saha Dr. Shylaja S S Dr. B K Keshavan
Professor Chairperson Dean of Faculty
External Viva
Name of the Examiners Signature with Date
1. __________________________ __________________________
2. __________________________ __________________________
DECLARATION
We hereby declare that the project entitled “Dynamic Taxi

Ride Sharing for distributed taxi Network” has been carried
out by us under the guidance of Dr.Snehanshu Saha and
submitted in partial fulfillment of the course requirements for
the award of degree of Bachelor of Technology in Computer
Science and Engineering of PES University, Bengaluru
during the academic semester January – May 2019. The matter
embodied in this report has not been submitted to any other
university or institution for the award of any degree.
01FB15ECS019 Aishwarya Manjunath
01FB15ECS031 Akshaykanth D L
01FB15ECS048 Anusha Kamath

ACKNOWLEDGEMENT
The success and final outcome of this project required a lot of guidance and assistance from
many people and I am extremely privileged to have got this all along the completion of my
project. All that I have done is only due to such supervision and assistance and I would not
forget to thank them.
I owe my deep gratitude to our project guide Dr. Snehanshu Saha, Professor - PES University,
who took keen interest on our project work and guided us all along, till the completion of our
project work by providing all the necessary information for developing a good system.
I would not forget to remember Vaskar Raychoudhury, Associate Professor - Miami University
for his encouragement and moreover for his timely support and guidance till the completion of
our project work.
I wish to express my sincere thanks to Dr. Shylaja S S, ChairPerson of Computer Science

Department, for providing me with all the necessary facilities for the research.
I would also like to extend my gratitude to DR. Murthy K N B, Vice Chancellor - PES
University, Prof. Ajoy Kumar, COO - PES University, Prof. Jawahar Doreswamy, Pro
Chancellor – PES University and Dr. M. R. Doreswamy, Chancellor – PES University.
Not to forget the teachers that were always there. Heartfelt thanks to all the teachers who were
part of the journey throughout the 4 years!
I was never alone. There were two pillars who were right by my side at all times. A small
thanks would never suffice, nevertheless I would express my profound gratitude to the two
pillars – my parents.
And lastly a warm thanks to all my friends without whom hard times wouldn’t have been made
easy.
ABSTRACT
Sustainability of local co-operative taxi networks in the face of competition

from corporate behemoths is a problem worthy of investigation. Lack of
infrastructure background support and venture capital demands alternative
strategies for survival.
A viable solution requires novel modelling approach and computational
framework. Such framework needs to be fully distributed and therefore is sub-
optimal. We propose an intra-city taxi service that leverages individual rides and
local network for ride management. This, in turn, demands a bunch of decision
variables and objectives to be optimized. Some of these objectives are conflicting
and therefore the problem requires a multi objective optimization formulation.
We propose to exploit the flexible structure and multi-agent like behaviour
of Ant colony optimization to tackle the diversity of objectives in the ride share
problem. We consider the scenario of ride share only since that is the hardest part
in the taxi business. The implementation is multi-modular and provides an
alternative approach to commonly used centralized taxi network.
We define novel performance metrics and present results to supplement the
modelling approach. Our results show that spatio-temporal diversity is the biggest
road block to wide scale ride sharing. Nonetheless, our solution ensures a very
reasonable acceptance in shared rides. This is one of the few notable outcomes.
Finally, a revenue framework is proposed to analyse nuances of the
operating environment.
Table of Contents
1. Introduction ............................................................................................................................. 10
1.1. Overview ............................................................................................................................. 10
1.2. Scope ............................................................................................................................... 11
1.3. Objective ......................................................................................................................... 11
1.4. Outcomes ......................................................................................................................... 12
2. Research Background .............................................................................................................. 14
2.1. Literature Survey ............................................................................................................. 14
3. Methodology ........................................................................................................................... 21
3.1. Proposed Approach .......................................................................................................... 21
3.2. High Level System Architecture ....................................................................................... 28
4. Environment Requirements ...................................................................................................... 32
4.1. Hardware Requirements ................................................................................................... 32
4.2. Software Requirements .................................................................................................... 32
4.3. Data Requirements ........................................................................................................... 33
5. Results ..................................................................................................................................... 34
5.1 Verification of Here API: ....................................................................................................... 34
5.2 Temporal Analysis of the dataset: .......................................................................................... 36
5.4 Queue Model ......................................................................................................................... 55
5.5 Queue length distribution ....................................................................................................... 56
5.6 Pareto Front Analysis ............................................................................................................. 59
6. Conclusions ............................................................................................................................. 63
7. Future Work ............................................................................................................................ 64
8. References ............................................................................................................................... 65
Dynamic Taxi Ride Sharing for distributed taxi Network
Definitions, Acronyms and Abbreviations
The mathematical model comprising of objective functions and constraints include:
7
PESU CSE Confidential Jan –May 2019
Table 2: Variables and their Meanings
8
Figures Table:
Figure 3.2.1: High Level Architecture of Taxi System----------------------------------------------28
Figure 4.3.1: Request Points in Chicago Dataset ------------------------------------------------- 333
Figure 5.1.1: Route shown by Google API - 1 ---------------------------------------------------- 344
Figure 5.1.2: : Route shown by HERE API - 1 --------------------------------------------------- 344
Figure 5.1.3: : Route shown by Google API - 1I ----------------------------------------------- 3535
Figure 5.1.4: : Route shown by HERE API - 1I -------------------------------------------------- 355
Figure 5.2.1: Distribution of passenger requests on weekdays during a week in february -- 366
Figure 5.2.2: Distribution of passenger requests on weekend during a week in July --------- 366
Figure 5.2.3: Distribution of passenger requests on weekdays during a week in July ------- 377
Figure 5.3.1: Distribution of passenger requests on Sunday, December 11th 2016 ---------- 388
Figure 5.3.2: Success Rate ------------------------------------------------------------------------ 4040
Figure 5.3.3: Taxi Occupancy Rate -------------------------------------------------------------- 4040
Figure 5.3.4: Passenger Waiting Time ----------------------------------------------------------- 4040
Figure 5.3.5: Messages Exchanged ---------------------------------------------------------------- 411
Figure 5.3.6: Request Process Time --------------------------------------------------------------- 411
Figure 5.3.7: Distnace Ratio ---------------------------------------------------------------------- 4141
Figure 5.4.1: Metrics for Queue length distribution ----------------------------------------------- 56
Figure 5.5.1: Pareto Front for various Passengrs -------------------------------------------------- 60
9
1. Introduction
1.1. Overview
Taxis play a major role in urban transportation network which is in the midst of
a major trend change. A recent report by the Boston Consulting Group claims that
"25\% of Miles Driven in US Could Be in Shared Self-Driving Electric Cars" [14]}.
This paradigm shift has been attributed to three major trends - Ride Sharing,
Autonomous Driving, and Vehicle Electrification. This also implies that by 2030,
arguably, there will hardly be any personal cars in US and on-demand ride sharing will
be the ‘only’ mode of transportation via (autonomous electric) taxicabs [13].
However, ride sharing unlike carpooling poses various challenges as well.
While carpooling is pre-coordinated between a number of passengers, ride sharing is
dynamic. It requires real-time adaptation of the route followed, depending on incoming
ride requests as well as the detour (deviation from the current route) tolerance of the
on-board passengers. Taxis might also require to adapt their travel route depending on
the sudden cancellation of passenger requests, road conditions, etc. One more critical
challenge we faced is the absence of a dedicated publicly available taxi ride-sharing
data.
Existing taxi systems like Uber/Ola/Lyft, which are popular these days, use a
centralized command [18]. Their centralized computational framework allot taxis to
passengers based on the shortest distance and other optimal factors. However, this
involves the use of a large economic venture to deploy this framework. Also, the taxi
drivers receive only partial fare of the ride and that too on a weekly cycle [16]. Another
issue with the centralized system lies in its poor scalability.
In this project, we model the dynamic ride sharing problem and path estimation
in a local cooperative taxi network as a multi-objective optimization problem.
Passengers directly communicate with taxi drivers and the requests are processed
locally (with the hardware and software available) in the taxi for making ride decisions.
This involves finding an optimality by each taxi and forwarding the request ahead (in a
hop-by-hop manner), if certain inherent constraints are not met. Every taxi in the
network (has an associated pheromone matrix with it and it) executes Ant Colony
Optimization Algorithm. We have proposed a novel framework with constraints and
objective functions to find optimal match between taxi and a particular passenger
10
request. This makes sure that a passenger is served with the best taxi, reducing his
waiting time, travelling time, and fare. At the same time we also ensure that every driver
gets a fair chance based on his/her location and the number of requests s/he has already
served, so that a reasonable profit is made by all the taxi drivers during a given time
frame.
1.2. Scope
The aim of the algorithm is to optimize the ride sharing scenario by utilizing the power
of a decentralized system. For the implementation purpose we attach a TCP a port to
each taxi and communication happens through this port. But this has it’s own liability,
lack of scaling capability being one of the prominent ones. Hence, we want to shift the
implementation to much more bigger space where scaling is obvious and easy. One
such method is to implement each taxi as a thread for simulation or by using MPI
programming model.
Some of the limitations of our strategy include first hop restriction i.e. if no taxi is
present within the transmission range of a requesting passenger, the search will not
return any taxi. As it is a distributed taxi system, if the timer at the passenger end
expires before receiving any REPLY then also the ride sharing fails. Hence, an optimal
value of the timer has to be found through further experimentation. With respect to
implementation, there are only 65,000 known ports and few of which are reserved. This
can be a limitation with respect to further scaling of the taxi system. We further need to
implement a queuing model at the taxi-end to compute the performance of each taxi per
day. This should include response time, idle time and average utilization. These metrics
have a direct bearing on the revenue of taxis. Consequently, the proposed revenue
model needs to be implemented to get a sense of commercial viability of the system.
1.3. Objective
The aim of the project is to build a distributed taxi system and optimize the route taken
by a taxi in a ride sharing scenario. In the 7th semester, as a part of the Research Credits
course the mathematical model consisting of objective functions and the constraints
11
were framed also the codebase for a simple distributed and dynamic ride sharing taxi
network was built. In the 8th semester, we would like to extend this work.
The objectives defined for this project include:
 Computing performance metrics for the scaled taxi system.
 Measuring the performance of the Ant Colony Algorithm.
 Building a queuing model for the passenger requests at the taxi end.
 Design of revenue model for the taxi system.
1.4. Outcomes
Here we list our proposed performance metrics. Each metric is calculated for 24-hour-
period from midnight to the next midnight and we observe how they varied over the
entire day through peak and non-peak hours.
1. Success Rate of Ride Sharing (SUCC ): Ratio of the total number of

rs
confirmed ride-sharing requests (successful)to the total number of REQUEST

messages generated by all the passengers.
2. Success Rate of nth passenger (n<=4): (SUCC Nth PASS): Ratio of rs
acceptance of nth passenger, (given that there are already n-1 passengers in the
taxi) to the total number of confirmed passenger requests. We take average of
all taxis in the system.
3. Distance Ratio of Ride Sharing (DIST ): Ratio of the sum of total shortest-
rs
path distances between the pickup and drop-off locations of individual satisfied
ride sharing requests to the total distance travelled by all the taxis with two or
more passengers.
4. Average Passenger Waiting Time (WT ): Mean time elapsed between a time
rs
a REQUEST is sent by P and the time P is picked up by a taxi. We take the

average of all the passenger waiting times (for a particular day).
5. Average Taxi Occupancy Rate (TOR): Ratio of the time a taxi had two or
more passenger(s) (Tusabl e) to the total time the taxi travelled on road (Tt ot
al). We take the average of all the taxis in the system.
6. Average Number of Messages (per Shared Ride)(Messg ):It is the ratio of rs
the total number of messages exchanged in the system to the total number of
successful shared rides.
12
7. Request processing time (RPT ) :Mean time elapsed between a time a

r
REQUEST is sent by P and the time when a REPLY comes back or the τphas
expired whichever occurs earlier.
Along with these performance metrics, the performance of Ant colony

algorithm has to be analyzed. In order to do this, metrics like HyperVolume,
Generational Distance will be computed and reported.
13
2. Research Background
In the current day situation with increasing traffic on roads it is very unlikely for people
willing to drive to their destinations. Generally, they prefer to take a cab service and
also share the ride if possible, with others travelling in the same route. This method of
sharing rides is proved to be beneficiary for both the customers and the driver as it
reduces the travel cost, fuel consumed and the traffic congestion. The existing cab
services offer ride sharing option to customers at lower rates but the major hindrance
they face is the accumulation of many requests normally during peak hours at the
centralised server which forms the bottleneck leading to dropping of requests and
passengers taking individual rides. This is the main idea of this research, to come up
with a completely distributed and dynamic system that can handle avalanche of ride
share requests resulting in profiting both the customer and the driver.
2.1. Literature Survey

Dynamic ride sharing has been addressed in [8] and in [19]. In[8], a novel algorithm
that focuses on dynamic scheduling of shared taxi ride requests using a distributed
system is presented. Every request from a passenger is sent to a set of taxis in a local
network (within 200 meters). The pickup and drop off are considered and two separate
events and their accommodation into the taxi’s permanent schedule is evaluated
individually with the constraint that the pick up event should be before drop off. The
taxis that receive the request put the events into their temporary schedule and evaluate
the eligibility of accounting them using a Triangulation method. The customer receives
a set of responses with the cost, availability of seats and travel time which are sorted
and the best solution is chosen. The main objective of this technique is to reduce the
total distance travelled by the taxi and to decrease the delay in any passengers travel
due to the detour.
The dynamic ride sharing has also been addressed in[19], where the main goals focuses
on to satisfy quickly many shared ride requests and to reduce the total travelled distance
by the taxis thereby reducing the energy consumed. It proposes a fast taxi searching
algorithm with a lazy shortest path finding strategy which is claimed to satisfy 25%
more shared rides requests in a simulation of GPS trajectory dataset. A central
organization operates the whole service and maintains a spatio-temporal index for every
14
taxi which is updated at regular interval whenever the taxi is a part of the service or
when an event like pickup, drop-off or rerouting occurs. All taxi request are processed
using a queue and each query is applied a Taxi Searching algorithm followed by a
Scheduling procedure to ensure a taxi with minimal increase in travel distance
satisfying all the requirements of the request is allotted. The paper also proposes a
pricing scheme which aims at increasing the profit of the driver and decreases the
individual passenger cost. The taxi searching algorithm uses a spatio-temporal index to
find the taxis nearby the pickup point of the new request, this index is from a
precomputed matrix which divides a geographical map into grids and takes the central
location as representing all the places within the grid and stores the distance and time
required to travel between every pair of grid locations, this is done to avoid the
computational expense of finding the shortest distance for every taxi. It uses two types
of taxi selection algorithm where one considers the distance between current location
and pickup location only and the other considered both pickup and drop-off locations,
in the later the taxi that is closer to both by equal distance is chosen. After a set of
feasible taxis are chosen the request is inserted into the schedule of the taxi that need
minimal increase in travel distance. The pricing scheme distributes the fare evenly
among all the passengers for shared distance they travel together.
In [12], [7], [21] the ant colony algorithm has been applied to Vehicle Routing Problems
(VRP). Generally, there are multiple objective functions that need to be optimized. In
[12], hierarchical ant colonies have been used, where one aims to minimize the number
of vehicles and the other aims at minimizing total distance travelled with the former
given more priority. The multi-objective optimization is adapted using artificial ant
colonies that parallelly try to optimize two objective functions over the previously
computed shortest path.
An extension of the MACS-VRPTW for a multi-objective context in given in [7]. The

novelty of the work presented in the paper is that all the objective functions are equally
considered with no hierarchy. The final solution is not a single optimum but a set of
pareto optimal solutions. Here, no solution can be improved in any objective without
damaging the other objectives. MACS-VRPTW presents the use of a single optimum
and is truly not a general multiobjective algorithm. In this paper they have presented a
single solution which optimises all the objective functions. A single ant colony system
is used to solve the three objective functions which minimizes the number of vehicles
15
used, the total travelling time, the total delivery time. The algorithm uses different
visibilities for each of the objective functions. The optimal solution is stored in a unique
pheromone matrix which is used to discover new good solutions.
The formal definition of a multi-objective optimization is given in [6] and it also

proposes a method of using an ACO algorithm for solving such problems. It discusses
about various types of strategies that can be used in deciding pheromone trials for
colonies, the paths which get pheromone update and defining the heuristic factors. A
generic framework which uses ACO to find the solutions to multi-objective problem is
proposed and four different variants of the same are visited in detail. These variants are
majorly based on the number of ant colonies and number of pheromone structures
considered, where the approach to define pheromone factor, heuristic factor and
pheromone update for each differ significantly. The proposed technique is
experimented on multi-objective Knapsack problem and a comparison of the results
obtained from the variants is made. The paper [21] proposes a dynamic Vehicle Routing
Problem in which the entire day is divided into time equal time slices. A request from
a customer is assigned to a particular time slice. Each time slice runs a static VRP. The
aim is to optimize the total travel time. The main elements defined in the paper include:
the events manager, the ant colony system and the pheromone conservation procedure.
The events manager receives the request from the customer, the events manager creates
static problems for a time slice and runs the ant colony system and assign a commitment
to a driver. The events manager also updates the pheromone matrix using the good
solutions from a time slice. The paper formulates the solution considering the dynamic
VRP to be similar to set of static VRP.
Most of the taxi systems use a centralized approach. The paper [5] has highlighted the
use of a distributed taxi service. The distributed taxi selection involves exchange of
messages between customer and taxi driver. One critical challenge is in the Blocking
time, where the unoccupied taxis are barred to participate in parallel selection
processes. The algorithm starts when a passenger sends a request. All the neighboring
taxis which have received it check if this the time to reach customer is less than the
mentioned passenger reaching time in the request. If so, they replace it with their
estimated passenger reaching time and forward to its neighbors and at the same time
start their selection and rejection timers. The taxi at the farthest permissible end will
not forward the request but send only Reply messages and start their acceptance timers.
16
The intermediate nodes filter out the most minimum request to their parent and finally
to the passenger. The passenger selects taxi with the most minimum passenger reaching
time and sends back a confirmation. If the acceptance timer has expired than the taxi
will unblock itself. This reduces the blocking time. They have also mentioned a greedy
approach in which the passenger sends a request and the taxi whose passenger reaching
time is greater than tolerance time will forward the request. This ensures that as soon
as a request comes the unoccupied taxi with minimum Haversine distance reaches the
passenger in less time. The paper has also addressed the hotspot recommendation
systems for taxis to efficiently search for customers. They have divided the dataset
based on the day of the week and time of the day. The entire city is divided into square
grids based on their GPS coordinates. This is followed by applying K-means clustering
based n the pickup locations. Here, the centroid of cluster is chosen to be a
recommendation given to the taxi driver. In order to strike a balance between taxi
profitability and availability, they recommendation is provided by assigning a score to
the locations based on the distance of the taxi. Hence nearby locations will be given a
higher score. They have experimented with the NYC dataset.
The paper [15], has used ant colony algorithm in a distributed approach for the
travelling salesman problem. A distributed multi-agent setup is used to aid the creation
of the complex environment that ants interact. The ants starting from a initial location
in the environment, called anthill, travel from one node to another based on the amount
of pheromone trials between the nodes; in search of optimal path for the Travelling
Salesman Problem. A single agent in this configuration can monitor one or more nodes
and is responsible for communicating messages of the ants across the environment. The
ants are represented as software object that traverse through the nodes to solve the TSP
by communicating through the agents. Experiments are conducted to obtain the optimal
number of machines that resulted in minimum average execution time for various TSP
datasets. [17] has highlighted the use of online social networking sites like Facebook
for dynamic ride sharing systems. The passenger will enter his pickup, drop off
locations along with his bid. Here, the drivers who are online and have less detour
among all of them will be considered. The passenger can choose the driver based on
the ratings the driver has received. The driver is free to choose the rides which have a
smaller detour or a greater profit or a ride with a passenger who is connected to him on
the social network graph. The paper also highlights the use of a multi agent dynamic
17
ride sharing system. Here, the main objectives include minimisation of greenhouse
emissions or the distance travelled and to maximize ride matches. One of the constraints
include that a driver will accept the ride only if the dynamic request is compatible in
terms of time with the other passengers destination reaching time. The optimal
assignment between drivers and passengers is done by using a cost matrix and finding
the best solution using a modified version Hungarian algorithm in O(N^3). The optimal
solution is the one in which joint path is smaller than the two individual paths.
Some of the challenges in dynamic ride sharing problems has been highlighted in [4]
and it includes dynamic arrival of riders and drivers, anticipation of future requests,
deviations from the planned trip. Implementation of the dynamic ride sharing system in
a large city can lead to large optimisation problem and hence a centralised system may
not work well and decomposition approaches can be employed. The paper also
highlights the need to understand user behaviour and preferences. On an overall outlook
of the paper, the authors have highlighted the major optimisation challenges which arise
when developing a dynamic ride sharing system.
Ride sharing problem has been formulated and proved to be NP hard in [9], by reducing
from the 3-Dimensional Matching problem. The authors have proposed a two-phase
greedy approach to solve this problem. In the rst phase, it matches the 2n requests into
n pairs based on the shortest distance to serve any request pair but on the worse pickup
choice. In the second phase, they have assigned drivers to the pairs formed in the
previous phase, under the assumption that the distance from a driver k to a pair of
requests is distance from k to the nearer pickup location of the two. This algorithm
guarantees to output a solution with at most 2.5 times the optimal cost.
A dynamic taxi ridesharing algorithm which classifies an incoming request into one of
nine classes and iteratively finds a solution is given in [25]. The nine classes are formed
on the basis of number of passengers and male or female passengers only requests. A
taxi that can satisfy the class constraints and accommodate more passengers within the
same time interval and a small detour threshold is given more priority. This system
works with a central database and a server that manages the requests and routing. The
dynamic location of a taxi is periodically updated to the central server using GPRS.
Among all the taxis that form the solution set the one that can reach the passenger first
is chosen, it’s travel path is rerouted and sent to the driver. The ride cost depends on
total number of passengers, their preferences and distance travelled. For every five
18
minute travel distance a standard fee increment is done. The main focus of this paper
is to allow maximum shared rides for daily commuters with pick up and drop off to be
“one-to-many” and “many-to-one” .
Use of multiple ant colonies has been explored in [12] to solve their own objective
functions. The pheromone matrix maintained is unique for each of the ant colonies. It
is claimed in the paper that use of separate ant colonies will be effective when the size
of the problem increases and the number of vehicles increase. Although there is a limit
on the communication, it is desired that dierentant colonies will add to the concentrated
efforts to simultaneously find paths by increasing the probability that a vehicle
continues to use routes that it has found to be successful and not be distracted by the
other routes.
Measuring the performance of ant colony becomes important. [26] has shown metrics
that can be used to measure how good evolutionary algorithms perform. An equi-distant
computational grid was defined over a the decision space variable. The grid intersection
point was assigned successive numbers using a binary representation. In order to obtain
the decision variable values, the binary string was mapped to its respective integer.
Some of the performance metrics measured in the paper include final generational
distance which measures the distance between the known pareto front solution and the
true pareto front solution. Spacing is used to measure the distance variance of vectors
in the neighborhood of pareto front solutions.
In [27], a comparison between ant colony algorithm and genetic algorithm was
presented. The multi-objective functions defined aimed to minimize the cost, time and
drivers. Here they have considered there exists only one path from source to destination
with a varying number to stations on the path. Each edge between any two stations is
said to be having multiple annotations, by this it means that an edge can represent many
routes that connect the two stations. This assumption makes the problem exponentially
hard to solve. Four set of experiments were run 20 times on each algorithm. They
consider variants of multiobjective Ant Colony Algorithm based on number of
pheromone structures and number of ant colonies. A local search is incorporated in the
ACO algorithm which is defined as the set of route plans that become reachable when
one of the edge in the existing route is replaced. Performance of the algorithm were
shown by quality indicators like Hypervolume which measures the volume covered by
the approximate pareto optimal set with respect to reference points with the highest
19
values of the objective functions which are present in the true optimal set. For
minimization inverse of this metric has to be considered. Other metrics measured
include generational distance and inverted generational distance which measures how
far the elements in the approximate pareto front are from the true pareto optimal set.
The experiments show that multiobjective ACO with single pheromone structure and
ant colony performs the best compared to others. This is reasoned out as an effect of
the way the pheromone update is done on the Pareto-dominance set compared to
updating solutions that are non-dominant over single objective. Genetic algorithm
results give a better Hypervolume Indicator value than ACO variants, but the ACO with
local search and single pheromone and ant colony performs the best among all except
that it leaves out some search space which causes the value of HV to decrease.
The paper [28] puts forth the use of Evolutionary Algorithms (EA) for computing the
pareto-optimal set for Multi Objective Problems (MOPs). They propose an algorithm
which is a variation of Differential Evolution (DE) for MOPs to generate Pareto-
optimal frontier. DE is a sub branch of EA which was developed by (Storn and Price
1995) to solve optimization problems in continuous domains. The algorithm presented
in this paper uses Gaussian Distribution to sample the population and for choosing the
critical step-length parameter in the algorithm. In addition, this algorithm modifies the
method of reproduction, replacement and adjusting variable value, compared to DE.
The algorithm was tested on two benchmark problems and the results were compared
with that of Strength Pareto Evolutionary Algorithm (state-of-the-art EA for MOPs)
using metrics like error ratio, generational distance and Knowles and Corne method.
20
3. Methodology
3.1. Proposed Approach
Our proposed distributed algorithm works in a synchronous message-driven manner.
A city is divided into 1 x 1 KM grids and the pheromone matrix is divided into
3 x 3 KM grids (to make sure pheromones propagate through the city grids).
The rows and columns of a pheromone matrix can represent the center of each
grid. All locations within that grid will be represented by that center. However,
these grids can also be replaced by clusters based on traffic intensity. Note, the
passenger REQUEST triggers the ride-sharing process (Algorithm 1) and starts the
timer τp at 60 seconds to obtain REPLY back from the taxis until the timeout. The
passenger REQUEST goes to a network layer entity which keeps track of the set of
taxis in the same grid as the passenger and broadcasts the REQUEST to those taxis.
Each taxi has its own computing device and each computing device will have a
pheromone matrix (adjacency matrix/list), initially assigned with random values.
When a taxi receives a REQUEST, it executes Algorithm 2 which invokes the Ant
Colony Optimization (ACO) algorithm (Algorithm 3) to obtain the new route which
accommodates the new request in the taxi’s existing path and a value C is
calculated according to Eqn 7 (see Definitions, Acronyms and Abbreviations) when
a scalarized approach is adopted however when we consider a truly multi-objective
approach the pareto front s obtained. When there are multiple solutions on the pareto
front, a knee point has to be determined. In our approach we have used the marginal
utility function to determine the knee point. Equation 11, shows the utility function.
𝑓(𝑈, 𝜔) = 𝜔𝑓1 + (1 − 𝜔)𝑓2 (11)
In the above equation f1 represents the detour and f2 represents the total travel time.
For every solution on the pareto front, the above equation is computed for 10 random
values of 𝜔. The value of 𝜔 is chosen in the rang [0,1]. The count of pareto solution
which leads to minimum value of the utility function is noted and the pareto solution
which leads to maximum count over 10 computations is noted. This solution is then
sent back to the passenger (via REPLY message) and the timer τp is started at 60
seconds to receive CONFIRMATION from passenger. This ensures that the taxis are
not blocked forever. A passenger selects the taxi with the most optimal metric
and sends CONFIRMATION to that.
21
If one or more constraint(s) is/are not satisfied while trying to include a new passenger
request, then the taxi broadcasts the request to next hop peers. All taxis that
received the REQUEST either send a response with the cost or notify that it cannot
accommodate the request to the passenger. One among all the taxis that sent REPLY
to the passenger, receives a CONFIRMATION message from the passenger and
updates its path to new route using the pre-computed route using an API [3]. The
confirmed taxi then updates it’s pheromone values according to the new path and
broadcasts the same to all taxis in its grid. In this way, our distributed approach
solves the overloading of a central server problem faced by centralized solutions.
Each taxi on receiving a REQUEST runs the ACO algorithm provided it satisfies the
capacity constraint. The computation of the new path depends on the probability
obtained from it’s own pheromone and visibility factor values. The visibility is
defined in terms of distance and time. The probability is given The paper [10] explains
local and global pheromone update, The local pheromone update is made when
an ant chooses its next path so as to simulate the natural evaporation and to ensure that
no path becomes too dominant whereas a global pheromone update is done after
one complete iteration to incorporate deposition of pheromone on the path that
gave the best cost as in [21]. This global update is given as:
The order of i and j will be according to the optimal route. The updated values
of the pheromone are utilized by the ants in the next iteration where the selection
is dominated by the cumulative best path. After running the algorithm for several
iterations it is proven that the ants follow the shortest path to their destination. The taxi
which best optimizes Equation 7 , with its newly computed route is chosen and
allotted to passenger. The route decided by this taxi will also be used to update
the pheromone matrix of all other nearby taxis using Eqn-10.
22
23
Example use case:

As an example, consider two taxis, with taxi id as 1 and 2 respectively. Taxi
with id 1 has no passenger allotted to it and taxi with id 2 has a passenger who
was picked from Chicago Cultural Center (41.883764, -87.624953) and is on
the way to his destination, Chicago French Market (41.884139, -87.640974).
Suppose both the taxis (which are close by to the passenger request) receive a
new REQUEST with pickup location as Tiffany Dome (41.8839, 87.6250) and
destination location as Lyric Opera of Chicago (41.8826, 87.6374). Both the
taxis run algorithm 3. According to this algorithm, All\_Nodes array for taxi 1
will be {Tiffany Dome, Lyric Opera of Chicago} and for taxi 2 will be {Tiffany
Dome, Chicago French Market, Lyric Opera of Chicago}. The taxis construct
the route iteratively according to lines 7-19 where each start with their current
location as first node and choose the next location as the node with highest
probability. Suppose taxi 1 has its route to be {current taxi location, Tiffany
Dome, Lyric Opera of Chicago} and taxi 2 route is {current taxi location,
Tiffany Dome, Chicago French Market, Lyric Opera of Chicago}. Assuming
the new route does not violate any of the constraints Equation 4 – Equation 6
for both the taxis, the detour distance for taxi 1 will be the distance from the
current location to Tiffany Dome whereas taxi 2 has to undergo some detour
24
from its previous route to accommodate the new passenger request. The taxi
that best optimizes Equation 7 for a scalarized approach or a better knee point
solution for truly multi-objective problem will be chosen and allotted to
passenger. The pheromone value of the locations in the route of taxi that was
allotted to passenger will be used to update the nearby taxis, according to
Equation 10. Considering a case where taxi 2 does not satisfy the constraints
Equation 4 – Equation 6 then this taxi will broadcast the received REQUEST to
nearby taxis. The taxis which receive the request, will run the ACO algorithm
and compute the route. If any taxi cannot accommodate a REQUEST because
the passenger waiting time is estimated to be more than 10 minutes then it sends
a negative cost response to the passenger (without broadcasting to any nearby
taxis as the other taxis will almost certainly be located further from the
passenger).
Fulfilment of objectives
The methodology which we will adopted to fulfill the objectives for this
semester are:
 To measure Performance metrics:

 Record if a passenger request was accepted or rejected to
measure overall success rate.
 In order to measure success rate of nth passenger request, record
if the passenger who was allotted the taxi was 1,2,3 or 4.
 The taxi end code will pass back the passenger waiting time that
it has computed.
 Distance ratio is measured by computing the ratio of shortest
distance between each accepted ride to the total distance
travelled by taxi with 2 or more passengers.
 Taxi occupancy rate will be measured by the total time spent by
the taxi with two or more passengers to the total time a taxi
spends.
 Request processing time is measured using a timer which starts
when a passenger sends request and ends when a passenger
25
request is either confirmed and allotted a taxi or when the request

is rejected by the taxi system.
 No of messages exchanged in the system is noted down by
incrementing a global variable whenever a passenger/taxi
broadcasts a request. Broadcast message is considered as 1
message and reply from each taxi is considered as individual
messages.
 To measure performance of Ant colony algorithm:
 A scalarized version the multi-objective function was considered
for choosing the solutions. We would like to consider the
objective functions as truly multi-objective and hence find a
solution on the pareto front.
 Followed by this we would like to measure the performance of
ant colony algorithms by considering metrics like
HyperVolume, Generational Distance.
 Analysis of how requests are lined up at the queue of each taxi followed
by building a model for the queue in order to see how this would impact
the performance of the taxi system.
 Implementing a dynamic revenue model for the taxi system. A revenue
model should take into account:
 the total distance travelled travelled (includes even the detour)
 the break even point of each taxi driver.
 how frequently the requests are occuring.
 the community and the area the requests are made.
 the maintenance cost of the vehicle (varies from vehicle to
vehicle)
 Why is it better than the current approach to solve the problem?

Existing taxi systems like Uber/Ola/Lyft, which are popular these days, use a
centralized command. Their centralized computational framework allot taxis to
passengers based on the shortest distance and other optimal factors. However,
this involves the use of a large economic venture to deploy this framework.
Also, the taxi drivers receive only partial fare of the ride and that too on a weekly
26
cycle. Another issue with the centralized system lies in its poor scalability. In
this project we exploring a distributed approach.
We model the ride sharing problem as an multi-objective optimization problem.

A typical multi-objective problem is bound to have a compromise solution since
an optimal solution to all objectives simultaneously can't be obtained. This
"compromise" solution leads to an optimization framework where we try to
reach a sub-optimal solution accommodating competing and collaborating
objectives. This type of problems are hard to solve by classical optimization
techniques where guaranteed convergence of the solution is one of the founding
principles. Thus, we resort to Ant-Colony based meta-heuristic algorithm to
find solutions to the constrained multi-objective problem. An Ant Colony
Optimization algorithm can build a sub-optimal solution from the strongest
segments of the best solutions. ACO uses an iterative construction of solutions.
The constructive behavior in the colony helps initiate transitions between each
iteration. Essentially, this is a greedy approach but works well as a multi-agent
system by leveraging the probability distributions between transitions for the
iteration sequences. However, the performance of ACO can't be pre-determined
and depends on the tuning of parameters to solve the optimization problem.
Therefore, it is difficult to comment on the superiority of ACO over its peers
such as Genetic Algorithms, which uses stochastic operators or Simulated
Annealing. However, we anticipate the flexibility of the ACO metaheuristic
endowed with parallel search in computational grids and dynamic memory
structures facilitated by pheromones to handle the challenges adeptly.
27
3.2. High Level System Architecture
Figure 3.2.1: High Level Architecture of Taxi System
 Network Controller: This is an entity which keeps track of the network of

taxis. Every taxi periodically (every 60 seconds) updates the Controller about
its current location and the Controller updates the grid details accordingly, i.e.,
the taxis which left the grid are removed while the ones that joined are added
into the grid. Based on an incoming request from a client, the Controller can
provide the list and location of taxis co-located with the passenger in the same
grid. The Controller can also serve a taxi's request to find out the other taxis
within first hop of taxis current location. This request is made when a taxi is
unable to accommodate a passenger due to constraints and wants to broadcast
to other peers in the next hop.
 Passenger: Passenger is the prime entity who sends a REQUEST message for
availing taxi ride-sharing service. Passengers can be distributed across the city.
However, the passenger density across the city is not evenly distributed. We
shall show with an in depth data analysis how the passenger distribution is
scientifically handled in our system. Passenger requests from their smart
devices capture their current location coordinates. Also, the passenger request
captures the current grid number. Passenger requests are being sent to the
Network Controller which is a network layer entity that keeps track of all the
taxicabs in different grids at a particular instant.
28
 Taxis: Taxis are independent entities which are mobile through the system and
changes the location while travelling around the city. When a taxi receives a
passenger request, it runs the Ant Colony Optimization (ACO) algorithm to
obtain the new route which accommodates the new request in the taxi's existing
path. The computation of the new path depends on the probability obtained from
it's own pheromone and visibility factor values. All constraints (Equation 4,5,6)
are checked and a value C is calculated according to Equation 7. This is then
sent back to the passenger (via REPLY message) which confirms to the taxi
with minimum detour distance (Equation 1). If one or more constraint(s) is/are
not satisfied while trying to include a new passenger request, then the taxi
broadcasts the request to next hop peers. All taxis that received the request either
send a response with the cost or notify that it cannot accommodate the request
to the passenger. One among all the taxis that sent REPLY to the passenger,
receives a CONFIRMATION message from the passenger and updates its path
to new route using the pre-computed route using an API[3]. The confirmed taxi
then updates it's pheromone values according to the new path and broadcasts
the same to all taxis in its grid. This way the ride-sharing decision making is
distributed among the available nearby taxis and can help share the passenger
load and profitability among the peers. In this way, our distributed solution
solves the overloading of a central server problem faced by centralized
solutions.
 ACO Algorithm: ACO algorithm has been used to allot a taxi and optimize its
route for a passenger request. The ACO algorithm utilizes the methodology of
real ants to find the optimal solution to an objective function. Real ants use
pheromone trails as an indicator in choosing the best path to their destinations.
The general idea is that each ant chooses its next path using a probabilistic value
computed from the pheromone value and some heuristics(or visibility). The
visibility is defined in terms of distance and time. The probability is given as:
There can be three kinds of modifications in ACO algorithm based on the local
and global pheromone update patterns. The local pheromone update is made
29
when an ant chooses its next path so as to simulate the natural evaporation and
to ensure that no path becomes too dominant whereas a global pheromone
update is done after one complete iteration, that is after all ants reach their
destinations. The global pheromone update incorporates deposition of
pheromone on the path that gave the best cost.
This global update is given as:
The order of i and j will be according to the most optimal route. The updated
values of the pheromone are utilized by the ants in the next iteration where the
selection is dominated by the cumulative best path. After running the algorithm
for several iterations it is proven that the ants follow the shortest path to their
destination.
 Queue Model: Queue Model has 3 major functions - acquireRequest,

feedRequest, deleteRequest. Acquire request is basically responsible for getting
request from the user bypassing the flask queue and adding it to the request
processing queue. While adding the request to the process queue, we need to
take into consideration of the priority in which these requests are processed.
Priority here is based on the vicinity the request was generated and whether the
taxi is moving in the direction of the destination location of the request. Feed
request’s job is to feed the taxi with requests to process one after the other based
on their priority. Delete Request is used when a taxi confirms a request. When
a taxi confirms a request this is sent to all the taxis in the range and these taxi
make sure not to process that request by deleting it from their queue provided
its not processed yet.
 Revenue Model: Consider a mass of taxi operators normalized to 1 who have
to make a decision regarding picking up a passenger by making a detour, or
follow a previously charted route for existing passengers in the car. The
proposed structure applies to a shared taxi ride, where two or more passengers
have to be accommodated. The choice of detour that has to be made by the
driver involves the cost of fuel, the additional revenue to be earned and any
unanticipated shock, like a traffic jam, that the non-detour route is free of. The
third condition may be considered as a strong assumption, and can be relaxed
30
later. Nevertheless, it can be meaningful if we consider that both routes involve

some risk, but the detour risk is greater. The risk involved in both direct and
detour drives is measured by the coefficient of risk aversion 'r', according to the
Arrow (1965) and Pratt (1964) measure of relative risk aversion, that follows a
probability density function g( r) supported by r 𝜖[0,1]. The taxi operator is risk
averse and his preference follows a von Neumann-Morgenstern type expected
utility specification. The expected utility of profit for the driver choosing the
straight (denoted by S) route is written as,
(12)
where, is the profit from choosing the straight route.

Note that, XS is the number of miles travelled under route S, the price is a
function of the number of miles travelled , the assumption

of concavity is for allowing convergence and substitutability with other long-
distance transport), while the variable cost (fixed cost does not offer additional
inference to this model) is a strictly increasing function of the number of miles
travelled. . We define 𝛿 > 0 as a fixed return associated
with the straight route. The fixed return is required to ensure interior solutions
for the model, as we will show, and in terms of economic interpretation, it is an
element to ensure that the taxi driver operates under risk and does not choose to
accept a fixed reservation income of x that is available from any other external
sources, such as unemployment benefit. Substituting the above information,
equation 12 can be written as . The utility

of profit for the driver choosing the detour (denoted by D) route is written as,
where, is the profit from

choosing the detour route. Note that, 𝜀 𝜖 [−𝑎, 𝑎] is the uniformly distributed
support with a probability density function f (𝜀) for the shock associated with
the detour. XD is the distance travelled under detour and remaining symbols are
as before. Thus, utility can be re-written as: EUD =
The point where , we

determine indifference between the two options in terms of the fixed component
31
of the model, namely, 𝛿 *. Alternatively, one can also find critical values of any
other parameter which would solve for this indifference. It is easy to show then
that , the taxi drivers would choose to take detour and conversely,
they would avoid the detour. One can find a distribution of drivers who
would choose one or the other or do both from time to time. 𝛿 can technically
represent many things, from EMI paid to banks for buying the car, insurance
premium, cost of maintenance, fixed fee received etc.
4. Environment Requirements
This section talks about any hardware and software requirements that we have on the project
at this point of time.
4.1. Hardware Requirements

 Miami Cluster Machine
 Linux/Windows/MAC machine to connect to clusters through NoMachine(An
interface which provides an SSH platform)
 All network protocols like TCP and and HTTP
 A Minimum of 16 GB RAM
 For running experiments 2 nodes and 4 processors per node were utilized.
4.2. Software Requirements
 Python 3.x
o Matplotlib 2.0 +
o Numpy
o Pandas
o Requests
o Threading
o CSV
 Flask 0.12.x
 NoMachine - to connect to clusters
 DUO mobile app for 2F authentication
 HERE API
 Google Directions API
32
4.3. Data Requirements
Our datasets include individual taxi trips from Shanghai (Continuous GPS traces of
4000 taxis for 2 years ending in 2007), San Francisco(SFO)(GPS traces of 535 taxis,
22 days in May, 2008), New York City(NYC)(Single trip information worth
143,352,415(≈143.35 million) trips for 1 year (2016))and Chicago(112,860,054 single-
ride taxi trip data from 2013 till 2017).
After careful consideration we have decided to evaluate our proposed algorithm over
the Chicago taxi dataset which is both recent as well as voluminous and publicly
available. The dataset has divided the Chicago Metropolitan region in 77 Community
Areas and a even larger number of Census tracts.
Figure 4.3.1: Request Points in Chicago Dataset
33
5. Results
5.1 Verification of Here API:
We are using the HERE API in order to generate routes between 2 places. This required
verification of the API in order to check if it gives the correct routes. Hence the routes
generated by HERE API were compared with Google Maps.
 Route between Chicago cultural center and Brookfield zoo
Figure 5.1.1: Route shown by Google API
Figure 5.1.2: Route shown by HERE API - 1
34
 Route between Chicago French market and shedd aquarium
Figure 5.1.1.3: Route shown by Google API - 1I
Figure 5.1.4: Route shown by HERE API - 1I
As it can be seen from the above two routes, the route generated by both of them are
same and even though HERE API does not suggest the shortest route the generated by
HERE API is one of the possible routes that Google maps also suggests as it can be
seen from route 2.
35
5.2 Temporal Analysis of the dataset:

Considering variation of passenger count throughout an usual office day, we can
distinctly identify certain non-peak (2-7 AM) and peak (8-11 AM and 5-9 PM) hours.
Passenger count remains stable around 12 noon to 4 PM. We have plotted the passenger
request variations for Chicago taxi-ride data over the weekdays and weekends of one
whole week each during July 2017 summer. A similar trend was observed for another
week in February 2017. We have normalized number of requests in an hour with respect
to the number of requests through the same week. The patterns during the weekdays
are surely commensurate. Fridays and Saturdays have similar patterns while the
Sundays are different. For Saturdays (party night), peak hours is 7 PM - 11:59 PM and
non-peak hour is 4-10 AM. For Sundays, peak hour (much less passengers than Friday
and Saturday) is 12 midnight - 3 AM and non-peak is 4-10 AM.
Distribution of passenger requests on weekdays during a week in february
Figure 5.2.1: Distribution of passenger requests on weekdays during a week in February
Figure 5.2.2: Distribution of passenger requests on weekend during a week in July
36
Figure 5.2.3: Distribution of passenger requests on weekdays during a week in July
Request distribution was also analysed on holiday in that year like 4th of july,
christmas, new year and valentine’s day.
37
It can be observed that 25th december had least number of passenger requests
throughout the day compared to other days. Whereas other days like 1st january, 4th of
July ad 14th February are party nights and hence the number of passenger requests
coming through the day sees a high during the late nights and evening time.
5.3 Taxi System performance
Experimental Setup
We have conducted experiments for Sunday (Dec 11 2016) data by considering peak
th
hours as (12 AM-3AM) and non peak as (4AM-10AM). Experiments were conducted
separately for wireless transmission ranges (Tx ), 100m and 250m,respectively during
both peak and non-peak hours. It was observed that there were 1611 passenger requests
during non-peak hours which were served by a total of 736 unique taxis. Given that all
the trips were single-passenger rides, and a shared ride can accommodate a maximum
of 4 passengers, we experimented with 1/4 (~200) and 1/2 (~400) of those 736 taxis.
Similarly, during peak hours, there were 4022 passenger requests and a total of 973
unique taxis. So, we experimented with 1/4 (~250) and 1/2 (~500) of those 973 taxis.
The trend in passenger request for Sunday (Dec 11 2016) is shown below.
th
Figure 5.3.1: Distribution of passenger requests on Sunday, December 11th 2016
38
Computation of performance metrics:
 Success Rate of Ride Sharing(SUCC ): Ratio of the total number of

rs
confirmed ride-sharing requests (successful)to the total number of REQUEST

messages generated by all the passengers.
 Distance Ratio of Ride Sharing (DIST ): Ratio of the sum of total
rs
shortest-path distances between the pickup and drop-off locations of individual

satisfied ride sharing requests to the total distance travelled by all the taxis with
two or more passengers.
 Average Passenger Waiting Time (WT ): Mean time elapsed between
rs
a time a REQUEST is confirmed and the time P is picked up by a taxi. We take

the average of all the passenger waiting times (for a particular day).
 Average Taxi Occupancy Rate (TOR): Ratio of the time a taxi had two
or more passenger(s) (T ) to the total time the taxi travelled on road (T ). We
usable total
take the average of all the taxis in the system.

 Request processing time (RPTrs): Mean time elapsed between between
a time a REQUEST is sent by P and the time when a REPLY comes back or the
τ has expired, whichever occurs earlier.
p
 Average Number of Messages (per Shared Ride)(Messgrs): It is

the ratio of the total number of messages exchanged in the system to the total
number of successful shared rides.
 Success Rate of nth passenger (SUCCrs Nth PASS): Ratio of
acceptance of nth passenger, (given that there are already n-1 passengers in the
taxi) to the total number of confirmed passenger requests. We take average of
all taxis in the system.
39
Initial Results
Figure 5.3.2: Success Rate
Figure 5.3.3: Taxi Occupancy Rate
Figure 5.3.4: Passenger Waiting Time
40
Figure 5.3.5: Distnace Ratio
Figure 5.2.3.6: Request Process Time
Figure 5.3.7: Messages Exchanged
41
Figure 5.3.8: Success of Nth passenger
Analysis of initial results:

It can be observed from the results (Figure 17) that the success rate (with Tx = 250m) was
higher during non peak hours as more taxis can be reached while compared with Tx = 100m.
During peak hours, the passenger requests arrive more frequently resulting in a queuing up of
the passenger requests at the taxi end and hence longer response time. In order to handle this,
we have set τp to 60 Seconds. However, this might get timed out given the longer taxi response
time and hence results in low success rate.
The Distance Ratio of Ride Sharing (Figure 16) gives an intuition of the detour distance that a
taxi takes and how it varies w.r.to taxi occupancy. For all the different categories considered,
the values are all above 1 indicating that Taxi ride sharing is much more efficient in terms of
distances covered by all the taxis for individual trips. Thus, it validates our assumption that
ride-sharing has environmental benefits as a whole. The DIST increases with the SUCC as
rs rs
42
higher taxi occupancy results in further shortening of total distance travelled, if individual trips
were undertaken. During a Peak hour the DIST decreases as the occupancy of taxi increases.
rs
Average Passenger Waiting Time (Figure 13) is observed to be low, this is because taxis were
initialized based on distribution of passenger requests and this resulted in taxis to remain close
to the densely populated areas. Also, since the Tx is low (100 - 250m), the taxis could reach
the passengers quickly. It can be observed that WTrs increases with increasing Tx. During Peak
hour, more requests are served and hence detour time slips in adding up to the WT . Hence, a rs
higher WT is noticed.
rs
Average Taxi Occupancy Rate (Figure 12) shows that for 250 taxis during peak hours 50% of
the time, the taxis carry 2 or more passengers. Inverse of (TOR) will indicate the time during
which a taxi had either one or no passenger. As the number of taxis increased from 250 to 500,
higher availability resulted in lower chances of ride sharing. The same trend can be observed
during non-peak hours. Also, during non peak hours due to less number of passenger requests,
TOR is much lower compared to peak hours. Also, with the increase in Tx , taxi availability
increases pushing down the TOR.
The results obtained for Messages exchanged are shown in Figure 14 and the Messg increase rs
as the number of taxis increase and the Tx increases. Since the passenger requests are broadcast
in nature (and we did not consider the entire broadcast as a single message) increased taxi
availability increases the Messg exchanged. Request Processing Time (Figure 15) is generally
rs
within 10 seconds in both peak and non-peak hours, except for the peak hour case with 500
taxis (Tx = 250m). This case has a 5-times- larger RPTr s value than the case with 250 taxis.
This result directly correlates with the largest number of messages being processed for this
case.
SUCC Nth PASS is plotted in Figure 17. As the number of passengers in the taxi increases,
rs
the taxi will be subject to constraints so that other passengers are not disturbed during their
service, this reduces the chance of a new passenger request from being accepted. Also, the taxi
detour and travel time may also increase for a taxi with capacity greater than 2, which can
decrease the selection of this taxi. Hence, it can be seen from Figure 17 that the success rate of
2nd passenger is lesser than 1st and 3rd passenger is lesser than the success rate of the 2nd
passenger. However, success rate of 4th passenger request seems to be an aberration which
needs further experimentation to be explained.
43
On introspection of the results, it was observed that results could be improved by doing
modifications to the code. Some of the modifications done to the code include:
 Broadcasting to second hop was considered only if the capacity constraint was not
satisfied.
 A random 2 minute waiting time was considered at every pickup location of the
passenger.
 The passenger would resend the request (randomly 2 or 3 times) within a random
interval of 5 minutes if his request would be rejected.
 We ran multiple iterations of the taxi system.
We ran the taxi system for 10 iterations. From the previous experiments it was observed that
Tx=250m gave better results. On running the experiments by varying timers we observed better
results when the timer at the taxi end was 60 seconds and the timer at the passenger end was
90 seconds. Considering the above factors we experimented the taxi system with timer values
as taxi end timer = 60 seconds and passenger end timer as 90 seconds.
Multiple iterations were done in order to check if the taxi system was behaving consistently.
Results obtained in the iterations are listed in the tables below:
Iteration 1:
Metrics Non-peak hours Peak hours
Total acceptance rate 73.122% 64.22%
Distance ratio of ride sharing 3.09 2.308
Avg no of messages exchanged 62.81 59.55
Request processing time 4.29sec 10.68sec
Passenger waiting time 34.074sec 74.46sec
44
Figure 5.3.9: Success of Nth Passenger Iterartion 1
Iteration 2:
Figure 5.3.10: Success of Nth Passenger Iterartion 2
45
Iteration 3:
Figure 5.3.11:Success Of the Nth Passenger Iteration 3
46
Iteration 4:
Figure 5.3.12: Success Of the Nth Passenger Iteration 4
Iteration 5:
Avg no of messages exchanged 55.35 60
Passenger waiting time 32.99sec 77 sec
47
Figure 5.3.13: Success Of the Nth Passenger Iteration 5
From the above 5 iterations it can be seen that the values were consistent over all the iterations.
The average over all the iterations are shown in the below.
As it can be seen the results majorly improved especially the success rate. Some of the reasons
for improvements include removal of unnecessary broadcasting of requests. Re-sending of
passenger requests also improved the success rate. Re-sending of requests also simulates the
48
real time behaviour of a passenger.
Decreasing first hop

The first hop was decreased to 100m in order to check if there were any performance variation
in the taxi system.
The common configurations followed for this setup include:
 Tx = 100m
 taxi end timer = 60 sec
 passenger end timer = 90 sec
10 iterations were run with the above configurations and average was considered.
Iteration 1:

49
Iteration 2:

Iteration 3:

Iteration 4:

Iteration 5:

Request processing time 5.37 7.95sec
50
The average over all the iterations are shown in the below table.
Average results over 10 iterations:

Success rate of Nth passenger request
From the above it can be seen that success rate over 10 iterations are almost similar to that
when the first hop was considered. It can also be observed that the passenger waiting time is
very low, this is because the taxis are within 100m radius of the passenger request. This method
is recommended will provide good results when taxis are initialised closer to the passenger
request. When the taxis are not close to the passenger requests then this method won’t work
well as the distance considered is too low. However with good taxi initialization, this
configuration of the taxi system is better in terms of faster service to the passenger.
Increasing first hop

The first hop was decreased to 500m in order to check if there were any performance variation
in the taxi system.
The common configurations followed for this setup include:
51
 Tx = 500m
 taxi end timer = 60 sec
 passenger end timer = 90 sec
10 iterations were run with the above configurations and average was considered.
Iteration 1:

Iteration 2:

Iteration 3:

The average over all the iterations are shown in the below table.
52
Average results over 10 iterations:

Success rate of Nth passenger request
From above it can be seen that the total acceptance rate has increased in comparison to Tx=
100m and Tx = 250m. This is because more taxis are present when the first hop is increased to
500m. This results in an increased chance of selection of the taxis. Another observation is the
request processing time during peak hours. The increased time could be because of queuing of
requests which results in more time for processing the requests. It can also be observed that the
passenger waiting time has increased, this is due to taxis which have been considered from a
greater first hop compared to the previous configurations. Even though the these values are
high they are still reasonable in terms of passenger perspective. Hence, this configuration
provides better results by increasing the total acceptance rate.
Comparison of the results of the above configurations is provided in the below graphs.
53
Figure 5.3.14: Performance Metrics for 500m Range
54
We can observe that the success rate, average messages exchanged, request processing time
and passenger waiting time increases linearly with first hop distance. This can be reasoned by
the number of taxis that are present within the first hop in various situations. We know that
with more taxis the chance of getting a ride is more but the number of messages sent also
increases which leads to more time for processing a request. It can also be observed that
passenger waiting time is more as first hop increases. For the same first hop during peak hours
the waiting time increases more as there is comparatively more traffic and hence more
congestion.
5.4 Queue Model

To verify how effective our queuing model works, we ran a few iterations of the taxi requests
and noted various parameters and compared them to the results before queuing model.
Metrics Non-peak hours
Total acceptance rate 34.82%
Avg no of messages exchanged 193.6
Request processing time 95.457sec
Passenger waiting time 108.0974sec
Reasons for bad performance:
i. Connection timed out at passengers end

ii. PWT is more
iii. Delay in confirmation
iv. No taxi in first hop
55
5.5 Queue length distribution

In order to check if the requests that hit the taxis follow any distributions, the queue length
distribution ws analysed. In order to do so, whenever a request hits a taxi these requests were
collected in a list and after the simulation was done this would be analysed. The requests which
hit the taxi include the below:
 Passenger request - This request hits the taxi when a passenger requests for the taxi.
 Passenger confirmation - This request hits the taxi when the passenger back end chooses
the taxi with minimum detour and total travel time.
 Broadcast pheromone request - This request hits the taxi when a taxi sends a broadcast
pheromone request to other taxis.
The queue length was analysed for both peak and non peak hours. The requests which hit the
taxi every 5 minutes is plotted.
Non-Peak hours:
The below plot is for taxi with id 3716
Figure 5.5.1: Metrics for Queue length distribution Non Peak hours
The below plots is for taxi with Id 3784
56
Observations and Analysis: It can be observed that there is no particular distribution followed
during non- peak hours. Also, it can be observed that the count of requests hitting the taxi every
5 minutes is less. The plots are very sparsely distributed, indicating that the requests which hit
the taxi are also sparsely distributed.
Peak hours:
The below plots is for taxi with Id 4760.
57
The below plot is for taxi with Id 4768.
Figure 5.5.2: Metrics for Queue Length distribution Peak Hours
Observations and Analysis: It can be observed that there is no particular distribution followed
by both the taxi during peak hours. Also, it can be observed that the count of requests hitting
the taxi every 5 minutes is comparatively high. The plots for the incoming requests are densely
distributed, indicating that the requests which hit the taxi are very frequent.
The requests which hit the taxi are dependent on the location of the taxi as well as the time that
the request originates. As a taxi with passenger keeps moving towards his destination the taxi
will be able to receive the requests on its way only. Hence the taxi’s destination will be a factor
in determining the requests which it will receive.
58
5.6 Pareto Front Analysis

When there are multiple solutions on the pareto front , one solution needs to be selected. This
is because when a taxi receives multiple solutions from the taxis to which it sent a request, then
a taxi needs to select one solution in order to confirm the request. In a truly multi-objective
context a pareto front needs to be determined and a knee point in the pareto front is determined.
This knee point solution corresponding to the respective taxi will be selected. The knee point
was determined using the linear marginal utility function.
The pareto front has been plotted for few passenger requests in the diagram below. The graphs
indicate all the taxi solutions (both detour as well as total travel time) obtained for a particular
passenger request, the non-dominated (pareto) front and the knee point solutions as well.
Passenger Id: 1
Passenger Id : 2
59
Passenger Id: 3
Passenger Id: 4
Figure 5.4.3: Pareto Front for various Passengrs
From the above graphs it can be observed for passenger Id 1, there were three taxis that returned
their solution to the passenger and the passenger’s backend had to choose one among the three
solutions. In the three solutions, the non-dominated solution is marked in red and green. To
choose one of the solutions among the non-dominated solutions. By using the marginal utility
function, the knee point was determined. It can be observed that the knee point obtained is
much closer to the origin than the other solution on the pareto front.
For passenger Id 2, many taxis received responded to the passenger request with their solutions
comprising of detour and travel time. These solutions were filtered and the non-dominated
solutions were obtained. Among the non-dominated solution the knee point was determined
and the taxi which had obtained that solution was selected and a confirmation from the
passenger end was sent to the taxi.
60
Passenger Id 3 received back two solutions from 2 taxis. Here, there was only one non
dominated solution and the same was identified to be the taxi to be confirmed for the passenger
request.
Another case is for passenger Id 4, where the passenger request went to multiple taxis and all
taxis sent back the same value for detour and total travel time. In this case, one of the taxis will
be selected.
Using the utility function is similar to doing a scalarization of the multi objective problems.
Hence another approach of identifying the pareto front was done. Here, the proximity to line y
=x was considered and the point (0,0) was chosen as the reference point. The reason for
choosing y = x line is that it ensures to provide an equal trade-off between both the objectives
and does not favour either of the objectives. The point (0,0) is an ideal point with detour 0 and
travel time 0. Euclidean distance between the pareto front and origin was chosen to select the
taxi to send response back to the passenger.
The pareto front has been plotted for few passenger requests in the diagram below. The graphs
indicate all the taxi solutions (both detour as well as total travel time) obtained for a particular
passenger request, the non-dominated (pareto) front and the knee point solutions as well. Here
the knee point was selected on the basis of proximity to the origin.
Passenger Id: 5
61
Passenger Id: 6
Figure 5.4.4: Pareto Front Analysis Passenger 6 and 7
For passenger Id 5, many taxis sent back their solutions but only 3 solutions were on the non
dominated front and in this one solution was selected for confirmation to the passenger. The
solution selected was closer to the origin compared to other non-dominated solutions. For
passenger Id 6, two taxis returned their solutions and in that solution was on the pareto front
and this was considered the knee point and this was returned to the taxi as a confirmation.
The performance of the taxis did not vary much on considering the two different methods of
selecting knee point in the non dominated pareto front.
62
6. Conclusions
This project brings into light how taxis play a major role in urban transportation network which
is in the midst of a major trend change. We here have successfully developed a system that
does not have a centralized command. The entire taxi system is built as distributed network of
taxis capable of peer to peer communication.
Here, A city is divided into 1 x 1 KM grids and the pheromone matrix is divided into
3 x 3 KM grids (to make sure pheromones propagate through the city grids). The rows
and columns of a pheromone matrix can represent the centre of each grid. All locations within
that grid will be represented by that centre. However, these grids can also be replaced by
clusters based on traffic intensity. A request made by a passenger goes to each of the taxi in
a certain range (100m, 250m or 500m). These taxi then make feasibility test as to whether or
not to pick up passenger with that particular request. ACO algorithm calculates the cost of
picking up the passenger and then the result is communicated back to passenger who makes
the request. The passenger will automatically select the taxi with the least cost in the vicinity.
To verify if this theoretical model actual suffices all the characteristics of a taxi system and if
it does, how good is the model is compared to current state of art, we tested the model against
few performance metrics like Total Taxi Acceptance Rate, Average Waiting Time, Average
Response Time, Taxi Occupancy Rate etc. The experiments were run on the Chicago taxi
dataset of a single day and various performance metrics were noted and analysed. The model
was constantly incorporated with improvements based on the previous iteration’s analysis to
reach a stage that is acceptable. A few notable metrics - Request Acceptance: 85.67%, Passenger
Waiting time: About 88 seconds, Distance Ratio – 3.47.
This model was built and tested on Linux environment, hence when deployed on a practical
situation would require us to manage various other factors to achieve this theoretical numbers.
Nevertheless, this particular project serves a certificate that decentralized taxi network is novel
idea to be used and deployed which also caters to the needs of both taxi drivers and the
passenger.
63
7. Future Work
Some of the limitations of our strategy include first hop restriction i.e. if no
taxi is present within the transmission range of a requesting passenger, the
search will not return any taxi. As it is a distributed taxi system, if the timer
at the passenger end expires before receiving any REPLY then also the ride
sharing fails. Hence, an optimal value of the timer has to be found
through further experimentation. With respect to implementation, there are only
65,000 known ports and few of which are reserved. This can be a limitation with
respect to further scaling of the taxi system. We further need to implement a queuing
model at the taxi-end to compute the performance of each taxi per day. This should
include response time, idle time and average utilization. These metrics have a
direct bearing on the revenue of taxis. Consequently, the proposed revenue
model needs to be implemented to get a sense of commercial viability of the
system.
The aim of the algorithm is to optimize the ride sharing scenario by utilizing
the power of a decentralized system. For the implementation purpose we attach a
TCP a port to each taxi and communication happens through this port. But this has
its own liability, lack of scaling capability being one of the prominent ones.
Hence, we want to shift the implementation to much more bigger space where
scaling is obvious and easy. One such method is to implement each taxi as a
thread for simulation or by using MPI programming model.
64
8. References
[1]Landscan geographic information science & technology. https://landscan.ornl.gov/.
[2] Sjtu wireless and sensor network lab - taxi trace data.
http://wirelesslab.sjtu.edu.cn/taxi_trace_data.html.
[3] Build apps with here maps api and sdk platform access - here developer
2019.https://developer.here.com/, 2019.
[4] Niels Agatz, Alan Erera, Martin Savelsbergh, and Xing Wang. Optimization for
dynamic ride-sharing: A review.European Journal of Operational
Research,223(2):295–303, 2012
[5] Anmol Agrawal, Vaskar Raychoudhury, Divya Saxena, and Ajay D

Kshemkalyani.Ecient taxi and passenger searching in smart city using distributed
coordination.In 2018 21st International Conference on Intelligent Transportation
Systems (ITSC),pages 1920–1927. IEEE, 2018.
[6] Ines Alaya, Christine Solnon, and Khaled Ghedira. Ant colony optimization for
multi-objective optimization problems. InTools with Artificial Intelligence,
2007.ICTAI 2007. 19th IEEE International Conference on, volume 1, pages 450–457.
IEEE,2007.
[7] Benjamín Barán and Matilde Schaerer. A multi objective ant colony system for
vehicle routing problem with time windows. In Applied informatics, pages 97–102,
2003.
[8] Kanika Bathla, Vaskar Raychoudhury, Divya Saxena, and Ajay D
Kshemkalyani.Real-time distributed taxi ride sharing. In 2018 21st International
Conference on Intelligent Transportation Systems (ITSC), pages 2044–2051. IEEE,
2018.
[9] Xiaohui Bei and Shengyu Zhang. Algorithms for trip-vehicle assignment inride-
sharing. InProc. AAAI, 2018.
[10] Alberto Colorni, Marco Dorigo, Vittorio Maniezzo, et al. Distributed optimization
by ant colonies. InProceedings of the rst European conference on artificial life,volume
142, pages 134–142. Paris, France, 1991.
[11] NYC Open Data. Open data for all new yorkers.
https://opendata.cityofnewyork.us/, 2017.
65
[12] LME Gambardella and G Taillard. A multiple ant colony system for vehicle
routing problems with time windows.[in:] corne d., dorigo mf: New ideas in
optimization, 1999.
[13] LEANNA GARFIELD.Only 20% of americans will own a car in 15

years,new study nds.https://www.businessinsider.in/only-20-of-americans-will-own-a-
car-in-15-years-new-study-nds/articleshow/58519992.cms, MAY 4, 2017.
[14] Boston Consulting Group. Press release : By 2030, 25% of miles driven in us
could be in shared self-driving electric
cars. https://www.bcg.com/d/press/10april2017-future-autonomous-electric-vehicles-
151076, 2017.
[15]Sorin Ilie and Costin Bădică. Multi-agent approach to distributed ant

colonyoptimization.Science of Computer Programming, 78(6):762–774, 2013.
16] Uber Technologies Inc. Payments and earnings. https://www.uber.com/en-
GH/drive/resources/payments/, 2019.
[17] Alexander Kleiner, Bernhard Nebel, and Vittorio A Ziparo. A mechanism for
dynamic ride sharing based on parallel auctions. In IJCAI, volume 11, pages 266–272,
2011.
[18] Rachel Linnewiel.Uber dismantled by blockchain:Decentralized ride-hailing is

coming.https://medium.com/davnetwork/uber-dismantled-by-blockchain-
decentralized-ride-hailing-is-coming-9c85d2bba6fa,September, 2018.
[19] Shuo Ma, Yu Zheng, and Ouri Wolfson. T-share: A large-scale dynamic taxi
ridesharing service. InData Engineering (ICDE), 2013 IEEE 29th International
Conference on, pages 410–421. IEEE, 2013.
[20] Matthias Grossglauser Michal Piorkowski, Natasa Sarajanovic-Djukic. Crawdad

dataset ep/mobility (v. 2009-02-24), traceset: cab.
https://crawdad.org//ep/mobility/20090224/cab/, February, 2009.
[21] Roberto Montemanni, Luca Maria Gambardella, Andrea Emilio
Rizzoli, andAlberto V Donati. Ant colony system for a dynamic vehicle routing
problem.Journal of Combinatorial Optimization, 10(4):327–343, 2005.
[22] Chicago Data Portal. Taxi trips.

https://data.cityofchicago.org/Transportation/Taxi-Trips/wrvz-psew, August, 2017.
66
[23] Statista: The Statistics Portal. Monthly number of uber’s active users worldwide
from 2016 to 2018 (in millions). https://www.statista.com/statistics/833743/us-users-
ride-sharing-services/, 2019.
[24] Wolfram Schneider. Bbbike extracts. https://extract.bbbike.org/, 2019.
[25] Chi-Chung Tao. Dynamic taxi-sharing service using intelligent transportation

system technologies. In Wireless Communications, Networking and Mobile
Computing, 2007. WiCom 2007. International Conference on, pages 3209–3212.
IEEE,2007.
[26] Van Veldhuizen, David A., and Gary B. Lamont. "On measuring multiobjective
evolutionary algorithm performance." In Proceedings of the 2000 Congress on
Evolutionary Computation. CEC00 (Cat. No. 00TH8512), vol. 1, pp. 204-211. IEEE,
2000.
[27] Herbawi, Wesam, and Michael Weber. "Ant colony vs. genetic multiobjective
route planning in dynamic multi-hop ridesharing." In 2011 IEEE 23rd International
Conference on Tools with Artificial Intelligence, pp. 282-288. IEEE, 2011.
[28] Abbass, Hussein A., Ruhul Sarker, and Charles Newton. "PDE: a Pareto-frontier
differential evolution approach for multi-objective optimization problems." In
Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No.
01TH8546), vol. 2, pp. 971-978. IEEE, 2001.
67

Report PW19SS101 PDF

Uploaded by

Copyright:

Available Formats

Report PW19SS101 PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Report PW19SS101 PDF

Uploaded by

Copyright:

Available Formats

Dissertation on

“Dynamic Taxi Ride Sharing for distributed taxi Network”

Under the guidance of

Internal Guide External Guide

January – May 2019

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

(Established under Karnataka Act No. 16 of 2013)

100ft Ring Road, Bengaluru – 560 085, Karnataka, India

(Established under Karnataka Act No. 16 of 2013)

This is to certify that the dissertation entitled

‘Title of the project’

Aishwarya Manjunath 01FB15ECS019

Signature Signature Signature

We hereby declare that the project entitled “Dynamic Taxi

01FB15ECS019 Aishwarya Manjunath

01FB15ECS048 Anusha Kamath

I wish to express my sincere thanks to Dr. Shylaja S S, ChairPerson of Computer Science

Sustainability of local co-operative taxi networks in the face of competition

1.1. Overview ............................................................................................................................. 10

1.2. Scope ............................................................................................................................... 11

1.3. Objective ......................................................................................................................... 11

1.4. Outcomes ......................................................................................................................... 12

2. Research Background .............................................................................................................. 14

2.1. Literature Survey ............................................................................................................. 14

3.1. Proposed Approach .......................................................................................................... 21

3.2. High Level System Architecture ....................................................................................... 28

4. Environment Requirements ...................................................................................................... 32

4.1. Hardware Requirements ................................................................................................... 32

4.2. Software Requirements .................................................................................................... 32

4.3. Data Requirements ........................................................................................................... 33

5.1 Verification of Here API: ....................................................................................................... 34

5.2 Temporal Analysis of the dataset: .......................................................................................... 36

5.4 Queue Model ......................................................................................................................... 55

5.5 Queue length distribution ....................................................................................................... 56

5.6 Pareto Front Analysis ............................................................................................................. 59

7. Future Work ............................................................................................................................ 64

Definitions, Acronyms and Abbreviations

The mathematical model comprising of objective functions and constraints include:

Table 2: Variables and their Meanings

Figure 3.2.1: High Level Architecture of Taxi System----------------------------------------------28

Figure 4.3.1: Request Points in Chicago Dataset ------------------------------------------------- 333

Figure 5.1.1: Route shown by Google API - 1 ---------------------------------------------------- 344

Figure 5.1.2: : Route shown by HERE API - 1 --------------------------------------------------- 344

Figure 5.1.3: : Route shown by Google API - 1I ----------------------------------------------- 3535

Figure 5.1.4: : Route shown by HERE API - 1I -------------------------------------------------- 355

Figure 5.3.2: Success Rate ------------------------------------------------------------------------ 4040

Figure 5.3.3: Taxi Occupancy Rate -------------------------------------------------------------- 4040

Figure 5.3.4: Passenger Waiting Time ----------------------------------------------------------- 4040

Figure 5.3.5: Messages Exchanged ---------------------------------------------------------------- 411

Figure 5.3.6: Request Process Time --------------------------------------------------------------- 411

Figure 5.3.7: Distnace Ratio ---------------------------------------------------------------------- 4141

Figure 5.4.1: Metrics for Queue length distribution ----------------------------------------------- 56

Figure 5.5.1: Pareto Front for various Passengrs -------------------------------------------------- 60

1. Success Rate of Ride Sharing (SUCC ): Ratio of the total number of

confirmed ride-sharing requests (successful)to the total number of REQUEST

a REQUEST is sent by P and the time P is picked up by a taxi. We take the

7. Request processing time (RPT ) :Mean time elapsed between a time a

Along with these performance metrics, the performance of Ant colony

2.1. Literature Survey