Smart and Safe Cab Finder Algorithm














































Smart and Safe Cab Finder Algorithm



It is used to locate the nearest and safest cab for passengers using specific designed algorithm.

This algorithm is designed to give most safe riding suggestions of all the cabs available in the vicinity .

The algorithms also considers the factors such as:-
1. Number of rides the person has got in that day.
2. Rating of the driver.
3. Distance of the cab from the location of passenger pick up point.

Working of the Algorithm:-

  1. The co-ordinates of the taxis are stored regularly on to the server . Thus , in JSON format we have the details of the taxi (details like gps co-odinates of the taxi , rating of taxi driver and trip details)
  2. That data is processed to make to find the distances of taxis from the current position of the customer using the formula of co-ordinate distnace algorithm.
  3. After getting the distances of taxis , other details are taken into account like Rating of the driver ,Number of rides the person has got in that day ,gender of the customer booking the taxi .
  4. Then the algorithm is used to calculate weightage for different taxis available.
  5. The algorithm used to calculate the weightage is given below:-
  6. The above code snippet just gives a rough idea that the rating of the driver is given a weightage of 50 (as safety is most priority)and no. of trips of the drive is given a weightage of 5.
  7. After calculating the weightages for different taxi , the are put in a min heap and top 5 results or options are provided to customer to choose from.
  8. A distance is fixed and this algorithm is applied only to taxis that are with in that distnace other wise the taxi person would be in loss.

If a female passenger books a cab then equivalent priority is calculated using a formula (developed as dicussions with some experts of the field).

Now with rising cases against female passengers while riding in taxis , this algorithm is designed to find safest taxi for the female passeneger.

While selecting a taxi for the female passenger safety of the passenger is given most weightage , the distance of taxi is given a bit less weightage and the no. of trips the driver has got in that has got is also taken into the consideration , so that drivers with less trips are given the trip.

The top 5 results are given to the female passenger with there details and she can choose the best option for her. The results are calculated by assigning the weightages as explained above.

This formula takes in to consideration a number of factors safety being most priority objective .

But if a male passenger books a taxi then different equivalent is calucalted taking in to cosideration :-

  1. Distance of cab
  2. Number of rides a cab has got till the time.

Now , for male passengers as the risk factor is less . So the weightages are given to the distance of taxi and the no. of trips the driver has got in that day is also taken into the consideration , so that drivers with less trips are given the trip.

The top 5 results are given to the male passenger with there details and he can choose the best option for him. The results are calculated by assigning the different weightages as explained above.

Example:- consider this given input is given 

The output when Female Passenger books the taxi:-
Hi "Ankita" (Female)  The Listed Cabs as per your needs are :
{"user_id": 39, "name": "Lisa" "distance": 27, "rating": 4.908, "trips": 4, "calculated": 198.4}
{"user_id": 31, "name": "Alan" "distance": 30, "rating": 3.89, "trips": 2, "calculated": 154.5}
{"user_id": 4, "name": "Ian" "distance": 53, "rating": 4.22, "trips": 3, "calculated": 143}
{"user_id": 15, "name": "Michael" "distance": 18, "rating": 4.012, "trips": 8, "calculated": 142.6}
{"user_id": 12, "name": "Chris" "distance": 64, "rating": 4.234, "trips": 5, "calculated": 122.7}


The output when male Passenger books the taxi with the same state of taxis and inputs:-
{"user_id": 6, "name": "Theresa" "distance": 43, "rating": 1.987, "trips": 0}
{"user_id": 3, "name": "Jack" "distance": 118, "rating": 1.99, "trips": 1}
{"user_id": 11, "name": "Richard" "distance": 57, "rating": 2.334, "trips": 1}
{"user_id": 2, "name": "Ian" "distance": 147, "rating": 4.994, "trips": 2}
{"user_id": 10, "name": "Georgina" "distance": 88, "rating": 3.81, "trips": 2}

Output :-
Top 5 suggestion are given to the person booking having driver's details .

PSEUDO-CODE


1. Information about the taxis is recieved in form of JSON ;

2. The JSON file is processed by the function file_paser();

3. Distances of the taxis are calculated to find taxis around using the
function calculate_distance ;

4. The latitude and longitudes are converted to radian for calculating the
distance;

5. Top N number of taxis are taken for further processing.

6. Among those selected N taxis Top 5 options of the taxis are found using
the function distance_calculator();

=>distance_calculator() Function is the heart of the code it does all the heavy
lifting of what we need from our code i.e here we calculate the the
equivalent weights of each the taxi drives using the weights assigned to them
and priorities assigned to them. It also takes if the passenger is a male or
female.

7. The distance_calculator() function takes care of all the conditions expalined above.

8. The function gives the result depending on the gender of the passenger.

9. Finally , the top 5 results of the taxis are further parsed using the function finalresult()
and it is given to customer for choosing the taxi;


double angle_degtorad(double val) {}

double calculate_distance(double lat2d, double long2)
{
return (radius * central_ang);
}
class cab
{

public :
void distance_calculator()
{
finalresult();
}
void finalresult()
{
}
void file_paser()
{
distance_calculator() ;
}
};

int cur_id;

int main()
{
cab obj;
obj.file_paser();
return 0;
}



NOW THE ACTUAL CODE:-

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <cmath>
#include <fstream>

using namespace std;

#define pi 3.14159265358979323846
#define radius 6371.0

ifstream list_of_cabs ("/Users/babayaga/Desktop/customers3.json");
ofstream recommendations_of_cabs ("answer2.json");

double angle_degtorad(double val)
{
return ( val * pi / 180);
}

double ltd1d=0,long1=0;

double calculate_distance(double lat2d, double long2)
{
double ltd1, lng1, lat2, lng2,
delta_lon, central_ang;

ltd1 = angle_degtorad(ltd1d);
lng1 = angle_degtorad(long1);
lat2 = angle_degtorad(lat2d);
lng2 = angle_degtorad(long2);
// crecommendations_of_cabs<<"ltd1d "<<ltd1<<" long1 "<<long1<<endl;
delta_lon = lng2 - lng1;
central_ang = acos ( sin(ltd1) *
sin(lat2) + cos(ltd1) *
cos(lat2) * cos(delta_lon) );
return (radius * central_ang);
}
class cab
{

public :
long long int length, i, j, x, y, m,n, f, fi, id[100000];
int cur_id;
int linecnt,gender;
// gender=1 for female as female are priority in this algorithm
char string_latd[1000],
string_longtd[1000],
id_as_string[1000], name[1000];
double lat2d, long2;
string line,cust_name;
map<int,int>maptrip;
map<int,double>maprating;
map<int,string>mapname;
map<int,double>mapdist;
map<int,double>mapval;
priority_queue< pair<double,int> >priority_customer;
priority_queue< pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > >priority_customer_male;
void distance_calculator()
{
int z=calculate_distance(lat2d, long2);
if (z<=150) //considering in-city cabs
{
// Converting id to int format.
id[i] = atoll(id_as_string);
int res=id[i];
i++;
double cal=50*maprating[res];
cal=cal-double(z)-(5*maptrip[res]);
pair<double,int>prvar;
prvar.first=cal;
prvar.second=res;
mapdist[res]=z;
mapname[res]=name;
mapval[res]=cal;
// crecommendations_of_cabs<<"id "<<res<<" val "<<cal<<endl;
if(gender)priority_customer.push(prvar);
pair<double,int>prman;
prman.first=maptrip[res];
prman.second=res;
priority_customer_male.push(prman);
}
}
void finalresult()
{
int lop=5;
while(!priority_customer.empty()&&lop--&&gender)
{
pair<double,int>res_pr=priority_customer.top();
priority_customer.pop();
int res=res_pr.second;
recommendations_of_cabs << "{\"user_id\": " << res << ", \"name\": " << mapname[res]<<" \"distance\": "<<mapdist[res];
recommendations_of_cabs<< ", \"rating\": " << maprating[res]<< ", \"trips\": " << maptrip[res]<<", \"calculated\": " << mapval[res]<< "}"<<endl;
}
lop=5;
recommendations_of_cabs<<endl<<endl;
while(!priority_customer_male.empty()&&lop--)
{
// crecommendations_of_cabs<<"lp "<<lop<<endl;
pair<double,int>res_pr=priority_customer_male.top();
priority_customer_male.pop();
int res=res_pr.second;
recommendations_of_cabs << "{\"user_id\": " << res << ", \"name\": " << mapname[res]<<" \"distance\": "<<mapdist[res];
recommendations_of_cabs<< ", \"rating\": " << maprating[res]<< ", \"trips\": " << maptrip[res]<< "}"<<endl;
}
}
void file_paser()
{
if (list_of_cabs.is_open())
{
linecnt=0;
while (getline(list_of_cabs, line))
{
// ccrecommendations_of_cabs<<"##"<<line<<endl;

f = 0; x = 0; y = 0; fi = 0; m = 0, n = 0;
length = line.size();
if(linecnt==0)
{
// crecommendations_of_cabs<<"If"<<endl;
for (j = 0; j < length; j++)
{
if (line[j] == '"')
f++;

else if (line[j] == ':')
fi++;
// crecommendations_of_cabs<<"f "<<f<<" fi "<<fi<<endl;
if (f == 3)
{
j++;

while (line[j] != '"')
{
string_latd[x] = line[j];
x++; j++;
}

j--; string_latd[x] = '\0';
ltd1d=atof(string_latd);
// crecommendations_of_cabs<<"++ "<<ltd1d<<endl;

}
else if (f == 7)
{
j++;

while (line[j] != '"')
{
string_longtd[y] = line[j];
y++; j++;
}

j--; string_longtd[y] = '\0';
long1=atof(string_longtd);
// crecommendations_of_cabs<<"++ "<<long1<<endl;
}
if (fi == 3)
{
j += 2;

while (line[j] != ',')
{
name[n] = line[j];
n++; j++;
}

j--; name[n] = '\0';
f += 2;
fi++;
gender=atoi(name);
}
else if (fi == 5)
{
j += 2;
n=0;
while (line[j] != '}')
{
name[n] = line[j];
n++; j++;
}

j--; name[n] = '\0';
f += 2;
fi++;
cust_name=name;
}
}

linecnt++;
if(gender==1)recommendations_of_cabs<<"Hi "<<cust_name<<" (Female) " <<" The Listed Cabs as per your needs are :"<<endl;
else recommendations_of_cabs<<"Hi "<<cust_name<<" (Male) " <<" The Listed Cabs as per your needs are : "<<endl;
}
else
{
// crecommendations_of_cabs<<"else"<<endl;
for (j = 0; j < length; j++)
{
if (line[j] == '"')
f++;

else if (line[j] == ':')
fi++;
// crecommendations_of_cabs<<"f "<<f<<" fi "<<fi<<endl;
// To get latitude of the location.
if (f == 3)
{
j++;

while (line[j] != '"')
{
string_latd[x] = line[j];
x++; j++;
}

j--; string_latd[x] = '\0';
}
else if (f == 13)
{
j++;

while (line[j] != '"')
{
string_longtd[y] = line[j];
y++; j++;
}

j--; string_longtd[y] = '\0';
}
if (fi == 2)
{
j += 2;

while (line[j] != ',')
{
id_as_string[m] = line[j];
m++; j++;
}

j--; id_as_string[m] = '\0';
cur_id=atoi(id_as_string);
// crecommendations_of_cabs<<"$$ "<<cur_id<<endl;
fi++;
}
else if (fi == 4)
{
j += 2;

while (line[j] != ',')
{
name[n] = line[j];
n++; j++;
}

j--; name[n] = '\0';
f += 2;
fi++;
}
else if (fi == 7)
{
j += 2;
int cnt=0;
char a[1000000];
// crecommendations_of_cabs<<"Entered "<<j<<" fi "<<fi<<endl;
while (j<length&&line[j] != ',')
{
a[cnt++] = line[j];
// crecommendations_of_cabs<<" j "<<j<<endl;
// crecommendations_of_cabs<<line[j];
j++;
}
// crecommendations_of_cabs<<endl;
j--; a[cnt] = '\0';
// id.push_back(atoi(name));
// crecommendations_of_cabs<<"$mapped$ "<<cur_id<<" cnt "<<cnt<<" name "<<atoi(a)<<endl;
maptrip[cur_id]=atoi(a);
fi++;
}
else if (fi == 9)
{
j += 2;
int cnt=0;
char a[1000000];
// crecommendations_of_cabs<<"Entered "<<j<<" fi "<<fi<<endl;
while (j<length&&line[j] != '}')
{
a[cnt++] = line[j];
// crecommendations_of_cabs<<" j "<<j<<endl;
// crecommendations_of_cabs<<line[j];
j++;
}
// crecommendations_of_cabs<<endl;
j--; a[cnt] = '\0';
// rating.push_back(atoi(name));
// crecommendations_of_cabs<<"$mapped$ "<<cur_id<<" cnt "<<cnt<<" name "<<atof(a)<<endl;
maprating[cur_id]=atof(a);
fi++;
}
}
// in string to float.
lat2d = atof(string_latd);
long2 = atof(string_longtd);
distance_calculator();
}

}
finalresult();
}
list_of_cabs.close();
recommendations_of_cabs.close();
}
};

int cur_id;

int main()
{
//creating object of the class cab
cab obj;
// calling the function
obj.file_paser();
return 0;
}



Now to run the file:-

  1. Copy paste the below the code in file with extention anyname.sh
  2. type the command chmod +x anyname.sh
cd /Users/babayaga/Desktop
g++ /Users/babayaga/Desktop/cab.cpp(folder address of the above code)
./a.out
cat answer2.json

Attached is the input json input file of the algorithm



https://drive.google.com/open?id=1dEFnhtvMnp6apWcapBi1AbRJ9TelDRsI


The below screen shot shows the output when customer is female :-
I have modified a bit here 2 outputs are showing the first output results when customer is female and second output compares the output when same passenger would be considered as male .

Show to just make clear about the can recommendations.





More Articles of Khitish Panigrahi:

Name Views Likes
Rotate Image 142 0
Edit Distance 88 1
Integer to Roman 117 2
Roman to Integer 107 2
Shortest Path Problem 111 2
Dijkstra 115 2
Hamiltonian Path 105 3
Travelling Salesman Problem 109 3
Hamiltonian Cycle 108 3
Number of Operations to Make Network Connected 104 2
Time Needed to Inform All Employees 101 2
Last Stone Weight II(any weight can be picked) 113 2
Last Stone Weight 119 2
Course Schedule II (print the order) 91 2
Course Schedule 103 2
0-1knapsack 116 2
Commutable Islands 224 2
Cheapest Flights Within K Stops 114 2
Friend Circles 99 2
Longest Palindromic Subsequence (Print Subsequence) 107 2
Longest Palindromic Subsequence (print only length) 98 2
longest palindromic substring(improved) 95 2
Longest Common Subsequence (Print the Subsequence) 98 2
Longest Common Subsequence (Print only Length) 100 2
Cycle in Undirected Graph 122 2
IOT SMART HOME 142 2
Working of Home Networks 100 2
Smart and Safe Cab Finder Algorithm 147 2
Minimum Falling Path Sum 174 3
Maximum Length of a Concatenated String with Unique Characters 100 3
Stack Pushing Game(Push Dominoes Game) 101 3
Boats to Save People 120 3
Find Single Non-repeated Number 96 3
Create Ranges 90 3
Triangle 95 3
Restore IP Addresses 100 4
Number of Matching Subsequences 89 3
Max Area of Island 101 3
Number of Islands 85 3
Is Subsequence 99 3
Word Break 98 3
Perfect Number 97 3
Longest Arithmetic Sequence 95 3
Container With Most Water 101 3
Maximal Square 95 3
Best Time to Buy and Sell Stock 100 3
Distance Between Bus Stops 97 3
Validate IP Address 110 3
Longest Mountain in Array 105 4
Sequential Digits 101 3
Path with Maximum Gold 112 3
House Robber with houses arranged in circular manner 127 3
Increasing Triplet Subsequence 110 5
4Sum 106 3
3Sum 97 3
ZigZag Conversion 133 4
House Robber 97 3
Minimum Path Sum 98 3
Unique Paths with obstacles 90 2
Find and Replace Pattern 100 3
Minimum Size Subarray Sum 97 3
Maximum Subarray 103 5
Find All Anagrams in a String 65 3
Permutation in String 66 3
Subarray Sum Equals K 102 3
Maximum Product Subarray 81 4
Permutation with duplicates 77 6
Subsets with duplicates 77 7
Partition Equal Subset Sum 69 5
Relative Sort Array 65 3
Permutations 67 4
Combination Sum 125 4
All combinations that add up to a given sum 69 3
Combinations 84 7
Palindrome Partitioning 70 3
Climbing Stairs 86 5
Fibonacci Number 83 5
Unique Paths 76 3
Longest Increasing Subsequence 66 8
Gas Station 75 7
Minimum number of Perfect square needed to form a number 60 7
Permutation Sequence 141 16
Coin Change 71 6
Multiple Word Searching Algorithm 78 8
Word Search 67 6
Valid Anagram 91 8
Remove Nth Node From End of List 90 6
Linked List Cycle 67 6
Implement strStr() 67 4
Odd Even Linked List 60 6
Valid Palindrome 64 4
Maximum Depth of Binary Tree 60 3
Binary Tree Zigzag Level Order Traversal 78 4
Kth Smallest Element in a BST 47 2
Evaluate Reverse Polish Notation 64 3
String to Integer (atoi) 82 4
Intersection of Two Linked Lists 69 3
Multiply Strings 70 5
Palindromic Substrings 59 4
Add Strings 56 2
Longest Substring Without Repeating Characters 63 4
Longest Palindromic Substring 62 2
Jump Game 68 3
Majority Element 59 2
Top K Frequent Elements 91 7
Factorial Trailing Zeroes 53 2
Excel Sheet Column Number 55 3
Find Peak Element 84 4
Merge Intervals 57 3
Letter Combinations of a Phone Number 69 4
Populating Next Right Pointers in Each Node 66 2
Invert Binary Tree 62 4
Swap Nodes in Pairs 60 5
3Sum Closest 56 2
Permutation Sequence 85 4
Letter Tile Possibilities 124 3
The k-th Lexicographical String of All Happy Strings of Length n 70 3
Children Sum Parent 129 5
Check if Binary Tree is BST 126 5
Delete Node in Linked List without a head pointer 96 2
Connect all siblings in a Binary Search Tree 86 2
Delete a node from BST in C++ 96 3

Comments