DARP

newride.py

from operator import itemgetter
import scipy.sparse.csgraph as csgraph
import numpy as np
import itertools
import random


requests=[]
allrequests=[]
predecessors=[]
dist=[]
startpositions=[]
revenuemap=[]	
avgrevenue=0


#returns path from node a to b a,b<100 >=0
#Includes a AND b
def getpathfrom(nodefrom,nodeto):
	nodes=[]
	if nodefrom==nodeto:
		return nodes
	nodes.append(nodeto)
	while predecessors[nodefrom][nodeto] != nodefrom:
		nodes.append(predecessors[nodefrom][nodeto])
		nodeto=predecessors[nodefrom][nodeto]
	return nodes
			
def method2():
	global requests
	startpositions=[9,19,29,39,49,59,69,79,89,99]
	for j in xrange(10):
		revenue=0
		requests=allrequests
		for i in startpositions:
			cabload=0
			cabpassengers=[]
			currenttime=0
			currentposition=i
			while(currenttime<1440):
				currentposition,currenttime,newrev,cabload,cabpassengers=schedulenextcab(currentposition,currenttime,cabload,cabpassengers)
				revenue+=newrev
			print revenue,i
			
		print "Total Revenue=",revenue
		random.shuffle(startpositions)
		
def schedulenextcab(position,currenttime,cabload,cabpassengers):
	global requests,avgrevenue
	
	if currenttime>1440:
		print "TIME UP"
		return 1500,100,0
		
	heuristic=[]
	
	for request in requests:
		reachtheretime=revenuemap[position][request[0]]*2
		waitingtime=0
		if currenttime+reachtheretime<request[2]:
			waitingtime=request[2]-(currenttime+reachtheretime)
		if currenttime+reachtheretime>request[3]:
			waitingtime=10000
		
		#dropreward=avgrevenue*cabpassengers.count(request[0])
		
		nodesinbetween=[]
		dropreward=0
		#print position,request[0]-1
		nodesinbetween=getpathfrom(position,request[0])
		if len(nodesinbetween)>0:
			for i in nodesinbetween:
				dropreward+=avgrevenue*cabpassengers.count(i)
		
		heuristic.append([request[5], request[0], request[1], request[2], request[3],request[4]+dropreward-waitingtime-reachtheretime,currenttime+waitingtime+reachtheretime,request[4],dropreward,reachtheretime])
	
		#	Request:
		#	FROM TO START END REVENUE ID
		
		# HEURISTIC
		#  ID FROM  TO  START END  HEURISTICVALUE TIMEIFACCEPTED REVENUE DROPREWARD REACHTHERETIME
	
	bestrequests=sorted(heuristic,key=itemgetter(5),reverse=True)
	
	dropchosen=False
	
	# if cab has 5 people in it, choose a pickup that has a dropreward with it. Remove all occurences of startposition of chosenrequest from cabpassengers.
	# Add end position of bestrequest to cabpassengers
	# if less than 5 then choose best request. 
	# 		If there's a dropreward associated remove startposition of bestrequest from from cabpassengers.
	# 		Add endposition of bestrequest to cabpassengers
	# Set cabload as length of cabpassengers
	
	i=0
	while dropchosen==False:
		if cabload==5:
			if bestrequests[i][8]>0:
				chosenrequest=bestrequests[i]
				#print bestrequests[i][8]/avgrevenue
				cabpassengers=filter(lambda a: a not in getpathfrom(position,bestrequests[i][1]), cabpassengers)
				#print cabpassengers," ",position," ",bestrequests[i][1]
				dropchosen=True
		else:
			chosenrequest=bestrequests[i]
			#print bestrequests[i][8]/avgrevenue
			if bestrequests[i][8]>0:
				cabpassengers=filter(lambda a: a not in getpathfrom(position,bestrequests[i][1]), cabpassengers)
			#print cabpassengers," ",position," ",bestrequests[i][1]
			dropchosen=True
		i+=1
		
	cabpassengers.append(chosenrequest[2])
	cabload=len(cabpassengers)
	currenttime=chosenrequest[6]
	
	
	requests=filter(lambda a: a[5]!=chosenrequest[0],requests)
	#print cabload
	
	#print "Servicing request at "+str(chosenrequest[1])+" "+str(chosenrequest[2])+" reachthere"+str(chosenrequest[9]) + " revenue"+str(chosenrequest[7])+"@"+ str(currenttime)	
	
	return chosenrequest[1],currenttime,chosenrequest[7],cabload,cabpassengers
	
	#########


if __name__=="__main__":
	f=open('test1.asc','r')	
	places,cars,capacity,requestcount = [int(n) for n in f.readline().split()]
	dist=np.zeros((places,places))
	for i in xrange(places):
		dist[i] = [int(n) for n in f.readline().split()]

	for i in xrange(places):
		for j in xrange(places):
			if dist[i][j]==-1:
				dist[i][j]=0
				
	revenuemap,predecessors=csgraph.dijkstra(dist,directed=False,return_predecessors=True)
	
	startpositions=[int(n)-1 for n in f.readline().split()]
	
	#avgrevenue=0
	for i in xrange(requestcount):
		requests.append([int(n) for n in f.readline().split()])
		requests[i][0]-=1
		requests[i][1]-=1
		requests[i].append(revenuemap[requests[i][0]][requests[i][1]])
		requests[i].append(i)
		avgrevenue+= revenuemap[requests[i][0]][requests[i][1]]
	
	allrequests=requests		
	avgrevenue=avgrevenue/requestcount	
	
	############# DEBUGGING #############
	#requests=requests[:10]
	#requestcount=10
	#####################################
	#print sorted(requests,key=itemgetter(1))[:10]

	########input taken##########

	method2()
	
# REQUESTS GO FROM LOCATION 0 to 99
# startpositions go from 0 to 99