Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: zz-x2580
Task: Multi-Vehicle Scheduling Problem
This Assignment must be executed in Python, preferably using Gurobi or Cvxpy solvers.
Scenario: A taxi company operates in a city in the following setting:
• There are 50 stations in the city and let S denote the set of all the stations in the city
• The inter-station travel time is constant and is given by Tij where i, jϵS
• Day is discretized into timeslots of 10 mins. So, there are total 144 timeslots in a day
• Let K denote a set of timeslots in a day such that K = [0,2,3, … ,143], and any timeslot within K is denoted
a kϵK
• Variable Rij(k) denotes the number of passenger requests to go from station iϵS to jϵS in timeslot kϵK, so
R12(0) denotes the number of passenger requests to go from station 1 to station 2 in the 0th timeslot.
• Assume there are 100 taxis in the company’s fleet
Data: You have the following information:
• Inter-station travel time Tij: numpy array of shape (50,50) where 50 corresponds to the stations
• Passenger request data Rij(k) : a numpy array of shape (50,50,144) where 50 corresponds to the stations
and 144 are the timeslots in a day.
Task: Formulate a scheduling problem as LP or ILP and solve it with any solver:
• Decision variable (suggestion): xcij(k)ϵ{0,1} which is 1 if taxi c is scheduled in timeslot k to go from station
i to station j and 0 otherwise – may use additional/alternate decision variable(s) if required
• Objective: Maximize the overall number of schedules ( = served demands).
Note:
• Scheduled here means that taxi c was dispatched (moved with passenger) from station i at timeslot k to go
to station j.
• A taxi can only be dispatched to other station if there are enough passenger request, e.g., if there are 2
passenger requests from station i → j in timeslot k, then we can schedule at max two taxis from station i
in timeslot k. All the additional taxis in this case should remain in the same station in which they are standing
idle, i.e., i → i.
• A taxi needs travelling time to go from one station to the other, so it cannot be scheduled in the timeslots
when it is travelling. So, only idle taxis can be scheduled.
• You can generate the entire day’s schedule at once or can also use Receding Horizon approach to generate
the schedules in a repeated manner in each timeslot.
• You can randomly initialize the starting location of each taxi and a taxi can at max serve one passenger
request at a time.
• Sub-Task: Plot the overall served demand in the day vs fleet size (increase fleet size in orders of 100,i.e.,
100,200,300….) – At roughly fleet size can we fulfill at least 50% of the total demand?
1. Submit a presentation explaining your formulation, assumptions, and solution.
2. Submit your code as a .py or .ipynb file.
