There are hundred of requests in the list which are accepted a day before(in advance registered). Each requests is the for picking the rider(Rider is the name given to passenger/customer) from the requested location at specified time and drop to the requested location at specified time. Every day, Before the service starts, these requests are scheduled to certain number of vehicles such that all the requirements of the customer and service provider can be met.This scheduling, assigning various number of requests to different vehicles before they go for operation is named Off-Road scheduling(I gave this name).
Now the vehicles are in the operation, they are operating at various parts of the city. There will be operator in the office waiting for a call from the riders to register either real time request or in-advance request. If the request is for in-advance, then simply save the request and schedule on next day as mentioned above. But if the request is for real-time, then operator should be able to confirm the request, meaning: the request will be assigned to any of the vehicles that best fit to provide the service for that request. In case if request can’t be fit into any of the operating vehicles then either operator can request caller to pick some other suitable time so that it can be fulfilled by existing vehicles or assign the new vehicle in the stock to service depending upon the priority of the request. ( This type of scheduling is named as On-Road Scheduling, I gave the name). To help on On-road and Off-Road scheduling, you will have the web service that will returns the estimated time to cover the distance between two location and also the service that gives the current location of the vehicle.
Problem Solution
Following is a simple algorithm that works for both Off-road and On-road scheduling that may need optimization. Off-Road algorithm runs once from 1 to 8.And On-road algorithm runs once the new request arrives from 7 to 8.
1. V: # of vehicles to be operated
2. C[V]: capacity of vehicles
3. Z: initial location, depot. Initailly all vehicles are
at Z, i.e. current_pd.loc=Z;current_pd.time=time at Z.
4. S[V]: dynamic array that stores the pick up and drop
off to be done by each vehicles, initially all empty.
5. R list of requests accepted in advance, for this we
do off-road scheduling before vehicles move to the field
6. Sort the R list with respect to their pick up time
7. foreach(r in R) :Request loop
a.PickDrop p=getpick(r),PickDrop d=getdrop():
PickDrop class has two attributes:time and
request id. Infact Schedule output is the list
of PickDrop objects
b. foreach(v in V) ::Vehicle loop
i.PickDrop[] tempd=v.S[v]
//retrieving PickDrops previously assign
to vehicle v.
ii.Current_pd=getNextServing(v);
//this method returns PickDrop within S[v]
for which vehicle is directing or PickDrop
where the vehicle have just reached and have
not directed for next PickDrop. The web
service will help to implement this method
by giving current location of vehicle.
iii.tempd=removeAllPDs(Current_pd.index);
//this is to remove all the PickDrops
in temp that has be served.
iv.Insert p and d into pd then sort w.r.t. time
v.If((C[v]-r.seats_demand)>0)
1.foreach(pd in tempd) ::PICKDROP loop
a.first_loc=current_pd.loc;
b.second_loc=pd.loc;
c.est_time=current_pd.time+
getEstimate(first_loc,second_loc);
//getEstimate() is from web service.
d.rq_time=pd.time;
e.if(rq_time-TOL'<'est_time'>''<'rq_time+tol)
//tol is the tolerance
i.Current_pd=pd;
ii.Continue;
f.else
i.if(v.index==V &&
//Request r is not fitted to any vehicles)
1.Add new vehicle v’ so that # of
Vehicles,V=V+1 and assign p
and d to v’--- OR --- deny the
request in case of online
scheduling.
2.Goto Request loop for next request.
ii.break this loop;
//coz this vehicle did not fit this
request, so
GOTO Vehicle loop for next vehicle.
2.v.S[v]=tempd; //Vehicle v got new schedule
3.GOTO request loop; //since request r has
been satisfied by vehicle v.
8. Terminate the program.
No comments:
Post a Comment