Smart and Safe Cab Finder Algorithm


Smart and Safe Cab Finder Algorithm 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:-
double cal=50*maprating[res];
cal=cal-double(z)-(5*maptrip[res]);
  1. 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.
  2. 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.
  3. 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  [](http://)

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.

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

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

  3. 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.
upload