forked from DeepNeuron/Uber_Profit_Model
-
Notifications
You must be signed in to change notification settings - Fork 22
/
Solve_IP.m
executable file
·153 lines (132 loc) · 5.49 KB
/
Solve_IP.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
function [x,obj_ip,time_ip] = Solve_IP(max_hours_per_week,time_slot_available,region_available,avg_revenue_trip,p_max,p_min)
%% This function solve the IP Model of Uber Driver Scheduling Problem
% max_hours_per_week: Maximum number of hours the driver can contribute per
% week
% time_slot_available: a 7*24 matrix to indicate the driver's availablility
% in each hour of a week. 1 indicates available and 0 indicates not
% Region_available: a 1*5 vector indicates which region the driver likes
% to drive in; 1 indicates like and 0 indicates dislike
% weight_var_multiplier: multiplier used to adjust the weight of variability
% weight_demand_multiplier: multiplier used to adjust the weight of demand
%% Import Data
% Right click on the "Data_Demand_Variability.csv", select "Import Data"
T = readtable('Data/Processed_Data/Data_Demand_Variability.csv');
% Get Column Names
% T.Properties.VariableNames
% Store each column as a varaible
Weekday = T.Weekday;
Timeslot = T.Timeslot;
%AverageVariability = T.AverageVariability;
Max_Duration = T.AverageMax;
Avg_Traffic = T.Avg_Traffic;
Region = T.Region;
%% Convert Traffic into Probability of Getting new Customers
% P_new_customer is a vertical vector of the same size with Avg_Traffic
P_new_customer = Cvt_Traffic_Probability(Avg_Traffic,p_max,p_min);
%% Convert Max_Duration to Minimum Trips per Hour
% Max_Duration is the average Max Duration of Trips within that region &
% time slot. It is recorded on second.
% The timeslots are at the unit of 2 hours
Min_Trips = 7200./Max_Duration;
%% Adjust the data based on the given parameters - driver's preference
weekday_choices = 1:7;
time_choices = [0 1 7 8 16 17 18 19 20 21 22 23];
timeslot_choices = [0 1 2 3 4 5]; % Timeslots that cooresponds to the above time_choices
n_weekdays_choices = size(weekday_choices,2);
% n_timeslot_choices = size(weekday_choices,2);
n_timeslot_choices = size(timeslot_choices,2);
n_weekdays = 7; % Number of weekdays
% Initialize indices of element to be removed: all are 0 in the beginning
indices_to_be_rm = zeros(size(Weekday));
for d = weekday_choices % Row
for t = time_choices % Column
if time_slot_available(d,t+1) == 0 % Mark as un-available
% Find the timeslot and weekday that cooresponding to that hour
t_ind = find(time_choices==t);
timeslot_to_be_rm = timeslot_choices(floor((find(time_choices==t)-1)/2)+1)+1;
%if mod(t_ind,2) == 0
% timeslot_to_be_rm = timeslot_choices(floor(find(time_choices==t)/2));
%else
% timeslot_to_be_rm = timeslot_choices(floor(find(time_choices==t)/2)+1);
%end
weekday_to_be_rm = d;
% Mark the indices of the elements to be removed
indices_to_be_rm(Weekday == weekday_to_be_rm & Timeslot == timeslot_to_be_rm) = 1;
end
end
end
% Mark unavailable reigons
if sum(region_available)<5
% find(region_avilable==0)-1 because the index in region starts with 0
unavailable_region = find(region_available==0)-1;
% If the regions in the unavailable_region shows in Region, it will be
% marked with 1
unavailable_region_ind = ismember(Region, transpose(unavailable_region));
indices_to_be_rm(unavailable_region_ind) = 1;
end
% Removed all marked instances
% We need to backwards
if sum(indices_to_be_rm) >0
ind_to_be_removed = find(indices_to_be_rm == 1);
%ind_to_be_removed
for i = sum(indices_to_be_rm):-1:1
ind = ind_to_be_removed(i);
%size(Weekday)
Weekday(ind) = [];
Timeslot(ind) = [];
Min_Trips(ind) = [];
P_new_customer(ind) = [];
Region(ind) = [];
end
end
% Number of variables
n_x = size(Min_Trips,1);
%% Formulate the IP
% A vector of cost coefficients
% Probability of Getting new Customer * Average Trips/Hour
f = transpose(P_new_customer.*Min_Trips).*avg_revenue_trip;
% Integer Variables
intcon = 1:n_x;
% Constraint 1: Maximum number of hours per week
A1 = ones(1,n_x); % Lhs
b1 = max_hours_per_week/2; % rhs
% Constraint 2: You cannot be in 2 regions during the same time
% Initialize A2 and b2
A2 = zeros(n_weekdays_choices*n_timeslot_choices,n_x);
b2 = ones(n_weekdays_choices*n_timeslot_choices,1); % Upper limit should be 1
row_count = 0;
for d = weekday_choices
for t = timeslot_choices
row_count = row_count+1;
ind_marked = (Weekday == d & Timeslot == t);
A2(row_count,ind_marked) =1;
end
end
A = [A1;A2];
b = [b1;b2];
lb = zeros(n_x,1);
ub = ones(n_x,1);
tic;
[x,fval] = intlinprog(-f,intcon,A,b,[],[],lb,ub);
time_ip = toc;
obj_ip = -1*fval;
%% Present the Solution
select_list = find(x==1);
% Set a basis for the weekday
day_number_benchmark = datetime(2017,04,9);
% Set a list of our pre-defined timeslot
timeslots = {'12AM - 2AM'; '7AM - 9AM'; '4PM - 6PM'; '6PM-8PM'; '8PM-10PM'; '10PM-12AM'};
for i = 1:sum(x)
select_time = Timeslot(select_list(i));
select_day = Weekday(select_list(i));
select_region = Region(select_list(i));
weekday_name = day(day_number_benchmark+select_day,'name');
timeslot = timeslots(select_time +1);
%string_output = ['Recommendation ' num2str(i) ': Region ' num2str(select_region) ', ' timeslot ', ' weekday_name];
%p_new = P_new_customer(select_list(i));
%min_trip = Min_Trips(select_list(i));
%string_output = ['Recommendation ' num2str(i) ': Region ' num2str(select_region) ', ' timeslot ', ' weekday_name ', ' p_new ', ' min_trip];
%disp(string_output)
end
%string_output = ['Total Revenue Earned: ' num2str(obj_ip)];
%disp(string_output)