CareerCup

In-Person? Yeah right. When is the homework due?

Is this a case of a dynamic stable matching ? The car's preferences keep changing. The passengers however luckily are known in advance - is there an algorithm that deals with this?

Note: This is just pseudo code... And I think it's right but you be the judge.

//First extend the taxi structure as follows.
struct Taxi{ 
int location;//an int from 0 to 49 
bool isHired//true or false
TaxiHireRequest* current_job; //the current job if the taxi is hired.
};


//now the main functionality.

unsatisfied = 0;
non_revenue_dist = 0;

foreach Job in TaxiHireRequests do {
	bestTaxi = NULL;
	contender = NULL;
	
	foreach Car in Taxis do{
		if (isHired) {
			tmp_time = getTime(Car.current_job.Source, Car.current_job.Destination) + Car.current_job.Time_of_Request;
			time_left = tmp_time - getCurrentTime;
			waitTime = time_left + getTime(Job.Source, Job.Destination);
			contender = (waitTime < Job.Max_wait) ? Car : NULL;
		}
		else {
			contender = (getTime(Car.Location, Job.Source) < Job.Max_wait_time) ? Car : NULL;
		}
		// We now select the best car. This is essentially greedy in nature.
		if (contender != NULL){
			if (bestTaxi == NULL) bestTaxi = contender;
			else {
				if (getDist(bestTaxi.Location, Job.Source) > getDist(contender.Location, Job.Source)) {
					bestTaxi = contender;
				}
				else if (getDist(bestTaxi.Location, Job.Source) == getDist(contender.Location, Job.Source)) {
					bestTaxi = (getTime(contender.Location, Job.Source) < getTime(bestTaxi.Location, Job.Source)) ? contender : bestTaxi;
				}
				else {
					//Do nothing! This is here for the giggles. :D
				}
			}
		}
	}
	non_revenue_dist += getDist(bestTaxi.Location, Job.Source);
	unsatisfied = (bestTaxi == NULL) ? unsatisfied + 1: unsatisfied;
}

print unsatisfied;
print non_revenue_distance;

Correction:

waitTime = time_left + getTime(current_job.Destination, Job.Source);

Did anyone else try this?

Hi llwire,

Doesn't your code have the problem, that the same taxi might be chosen as bestTaxi for multiple jobs. So beside current job you also need to take care if the taxi has already been alloted for next job.

Just a try:

Sort the jobs by max_waiting_time.
Step 1: For each job, find the taxi at the nearest location(s) and assign it for the job if it can reach within the waiting time. This way we are minimizing both the unsatisfied and non-revenue distance.

Step 2: However, we also need to take care that what happens when a taxi has completed current job. I would update each location with those taxis as well which have their destination set to that location and have additional wait time for that taxi, equal to the time for current job
and repeat step 1.

Please let me know your views

Yes, an assigned taxi maybe assigned more jobs if its final destination is closest to the new job while still meeting the wait time requirement. Consider a case where the an assigned taxi is already heading to the destination of the next pickup. In such a case, you wouldn't need to assign a new taxi when the non revenue distance for the assigned one is 0.

There is a flaw in the code above, however. The algorithm here only assigns one extra job to a car. As a matter of fact, it is possible for one car to handle all the jobs if every request destination is the source of the next request provided the time constraints are met. For that case, the Taxi structure needs to be modified to include a list (priority queue) of next jobs. This priority queue would be ordered with distance as the priority and max wait time as the tie breaker.

As a greedy solution, the algorithm must try to greedily service every request with one taxi until that taxi can no longer service any more requests with respect to the constrains of the problem. It is only then that a new car is used.

What do you think?

consider, u sort in by distance wise

there are 6 people, person1 is at a minimum distance of 20 from taxi1, and at a distance of 21 from taxi2
consider all the 6 person stands in a straight line(left to right) so that taxi1 is between person 1 and person 2,
while taxi 2 is at a distance of 21 on the left side of person1 so no point of using taxi 2 considering infinite waiting time.


person 2 at dist 23
p3 at d 24
p4 at d 25
p5 at d 26
p6 at d27

if taxi 1 services person1 1st, the unwanted_distance will be 20*2+23+1+1+1+1=40+27=67

if taxi 2 services person 1unwanted_dist=21
so for 6 people with taxi1 unwanted_dist=27
for person1 the unwanted_dist=22 so total unwanted_dist=27+21=48


so we see the above solution provided fails

the last 3 lines written again corrected*

if taxi 2 services person1 unwanted_dist=21
so for rest 5 people with taxi1 unwanted_dist=27
so total unwanted_dist=27+21=48

I'm sorry but I'm not sure what you're talking about. Nowhere in the solution do we sort according to distance. Also, I don't think the scenario you're describing is entirely accurate. You don't consider, at all, the start and end points of any of the trips which are very important in the taxi selection.

For instance if taxi1 in selected for a pickup, which is at d 20 away, where is the person going? If it is as you say and person 2 is at d 21 from taxi one's final destination then, how much time does it take taxi 1 to finish his current pickup and go back to pick up person? Can he make it in given waiting time? If taxi one can make it in time it doesn't matter if taxi 2 is free at d 23 away from person. You have to send taxi 1 because it is the shortest non revenue distance while still meeting the wait time requirement. This is what the algorithm does.

You can't assume that requests should be handled on a 1 to 1 basis. Since the positions of the taxis are always changing, one taxi may serve more customers than the others.

My logic:-
struct distance{
	int distance[50][50];
	int Time[50][50];
};
struct taxi{
	bool isHired;
	int location;
	int destination;
}
struct MrXYZ{
	struct taxi t[25];
}
struct caller{
	int Source;
	int destination;
	int max_waiting_time;
}

Conditions will be :-

 1. if(taxi[i].isHired == 0 && taxi[i].location == caller.Source)
	change attribute of Taxi and Hire it.
 2. else if(taxi[i].isHired==1&& taxi[i].end == caller.Source &&distance.Time[taxi[i].location][taxi[i].end]< caller.max_waiting_time)
	change attribute of taxi and Hire it.
 3. else {
		if(taxi[i].isHired == 0 && distance.Time[taxi[i].location][caller.Source]<caller.max_waiting_time){
			if(distance.distance[taxi[i].location][caller.Source]<min){
				taxi_index = i;
			}
		}
		if(taxi[i].isHired == 1 && distance.Time[taxi[i].location][taxi[i].end]+distance.Time[taxi[i].end] [caller.Source]<caller.max_waiting_time){
			if(distance.distance[taxi[i].end][caller.Source]<min){
				taxi_index = i;
			}
		}
		change attribute of taxi and Hire it on the basis of minimum value otherwise send don't hire it.
	}

Hard to believe they asked you this question. This is a linear programming problem, you can use Excel Solver (an extension to Microsoft Excel) to solve it. Generally linear programming is used to solve operations research problems. Operations research is a MBA course.

There are two key issues:
i) The local optimal solution (obtained by greedy algo) does not guarantee the global optimal solution.
ii) The number of optimal solution may be more than one since the two goals are paradoxical to each other. For example, in some cases, just reject all requests to maintain 0 non-revenue distance would be an optimal solution.

The following is the code. The general idea is to enumerate all possible schedules and find the best ones. The algo goes like this: for each request, i) reject it; ii) choose possible taxi to accept the request. For each option, record the result (i.e., the number of rejected requests and accumulated non-revenue distance). At the end, scan all solutions and find best ones.

public class Status{
		public Taxi[] taxis;
		public int rejected_request=0;
		public int non_revenue_distance=0;
		
		public Status clone(){
			Status s0=new Status();
			s0.taxis=this.taxis.clone();
			s0.rejected_request=this.rejected_request;
			s0.non_revenue_distance=this.non_revenue_distance;
			return s0;
		}
	}
	
/**
 * This method computes an optimal taxi schedule in terms of i)minimum request rejection and ii) minimum non-revenue distance
 * @param thrs sorted taxi hire requests based on time.
 * @param taxis
 * @param distance
 * @param time
 */
	public void bestTaxiSchedule(TaxiHireRequest[] thrs, Taxi[] taxis, int[][] distance, int[][] time){
		ArrayList<Status> parallel_world=new ArrayList<Status>();
		Status s0=new Status();
		s0.taxis=taxis;
		parallel_world.add(s0);
		// the null separates the end of possible schedules for last request
		parallel_world.add(null); 
		for(int i=0; i<thrs.length; i++){
			s0=parallel_world.remove(0);
			while(s0!=null){
				updateParallelWorld(s0, thrs[i],distance, time, parallel_world);
				s0=parallel_world.remove(0);
			}
			parallel_world.add(null);
		}
		
		//summarize the final result of different schedules, find skyline schedules
		ArrayList<int[]> skyline_result=new ArrayList<int[]>();
		int[] rej_dist=new int[2];
		rej_dist[0]=parallel_world.get(0).rejected_request;
		rej_dist[1]=parallel_world.get(0).non_revenue_distance;
		skyline_result.add(rej_dist);
		for(int i=1; i<parallel_world.size()-1; i++){
			Status s=parallel_world.get(i);
			int j;
			for(j=skyline_result.size()-1; j>=0; j--){
				rej_dist=skyline_result.get(j);
				if(s.rejected_request>=rej_dist[0] && s.non_revenue_distance>=rej_dist[1]){
					//in skyline, this new point is dominated by the old one
					break;
				}
				else if(s.rejected_request<=rej_dist[0] && s.non_revenue_distance<=rej_dist[1])
					skyline_result.remove(j);
			}
			if(j<0){
				int[] new_result=new int[2];
				new_result[0]=s.rejected_request;
				new_result[1]=s.non_revenue_distance;
				skyline_result.add(new_result);
			}
		}
		
		//out put result
		System.out.println("There are "+skyline_result.size()+" schedule options, whose result is: ");
		for(int i=0; i<skyline_result.size(); i++){
			rej_dist=skyline_result.get(i);
			System.out.println((i+1)+": "+rej_dist[0]+" & "+rej_dist[1]);
		}
	}
	
/**
 * given a current taxi status and a taxi request, create all possible schedules and save it as one parallel world.
 * @param s0
 * @param thr
 * @param distance
 * @param time
 * @param parallel_world
 */
	protected void updateParallelWorld(Status s0, TaxiHireRequest thr, int[][] distance, int[][] time, ArrayList<Status> parallel_world){
		
		//traverse all taxis and schedule one to this task if possible
		for(int taxi_index=0; taxi_index<s0.taxis.length; taxi_index++){
			int client_loc=thr.source;
			int taxi_loc=s0.taxis[taxi_index].location;
			int actual_wait_time=Math.max(0, s0.taxis[taxi_index].ready_after_time-thr.time_of_request);
			actual_wait_time+=time[taxi_loc][client_loc];
			if(actual_wait_time<thr.maximum_waiting_time){
				// schedule this taxi to the request
				Status s1=s0.clone();
				s1.taxis[taxi_index].ready_after_time=thr.time_of_request+actual_wait_time+time[thr.source][thr.destination];
				s1.taxis[taxi_index].location=thr.destination;
				s1.non_revenue_distance+=distance[taxi_loc][client_loc];
				parallel_world.add(s1);
			}
		}
		//schedule I: reject the request
				s0.rejected_request++;
				parallel_world.add(s0);
	}
	
	//main
	public static void main(String[] args){
		
		//generate taxi_hire_request
		TaxiHireRequest[] thrs=new TaxiHireRequest[200];
		for(int i=0; i<thrs.length; i++){
			thrs[i]=new TaxiHireRequest();
			thrs[i].source=((int)(Math.random()*1000))%50;
			thrs[i].destination=((int)(Math.random())*1000)%50;
			thrs[i].maximum_waiting_time=((int)(Math.random()*1000))%100;
			thrs[i].time_of_request=(int)(Math.random()*1000);
			if(i>0)
				thrs[i].time_of_request+=thrs[i-1].time_of_request;
		}
		
		//generate taxi initial status
		Taxi[] taxis=new Taxi[25];
		for(int i=0; i<taxis.length; i++){
			taxis[i]=new Taxi();
			taxis[i].location=((int)(Math.random()*1000))%50;
			taxis[i].ready_after_time=0;
		}
		
		//generate distance and time matrix
		int[][] distance=new int[50][50];
		int[][] time=new int[50][50];
		for(int i=0; i<distance.length; i++)
			for(int j=0; j<distance.length; j++){
				distance[i][j]=(int)(Math.random()*1000);
				time[i][j]=(int)(distance[i][j]/(Math.random()*50+1));
			}
		
		Problem_17886663 p=new Problem_17886663();
		p.bestTaxiSchedule(thrs, taxis, distance, time);
	}