goal is to find optimal routes for multiple vehicles visiting a set of locations. (When there's only one vehicle, it reduces to the Traveling Salesman Problem) - NP-hard problem - For scheduling public buses, school buses in metro cities, delivery chains. Vehicle Routing Problem
famous VRPTW. - Why capacitated? To control the overflow/overload of buses, trucks etc. - Lower bound on occupancy : This problem also has 85% as the lower bound on occupancy for maximum utilization of resources like bus seats and fuel - Time Windows : To deal with office/school opening times and strict delivery schedules. Making the problem more practical. - Cover maximum distance by a bus in a tour Capacitated Vehicle Routing Problem with Time Windows
the problem - 2 constraints need to be optimised, the total distance travelled by all the buses to solve the problem and number of buses used for the same. Both need to be minimised. - 2 constraints need to be just taken care of. The bus has to visit all the nodes on time always, and the bus capacity should be 85% at least to run the bus on that route.
input is mapped to a high dimensional vector space and fed into an RNN decoder. - The decoder uses beam search which keeps track of the most probable paths and follows the one with minimum length. - An attention mechanism uses the RNN hidden state, along with the embedded inputs and gives a probability distribution over the next input- this repeats until a termination condition under the constraints is reached.
WITH TIME WINDOWS MACS- VRPTW ACS for number of buses ACS for total distance The goal of the first colony, ACS-buses, is to try to diminish the number of buses used, while the second colony, ACS-distance, optimizes the feasible solutions found by ACS-buses. Both colonies use independent pheromone trails but collaborate by sharing the variable ψ(Total path) managed by MACS-VRPTW
finding the shortest path from the nest to a food source. • An ant repeatedly hops from one location to another to ultimately reach the destination (food). • Ants deposit an organic compound called pheromones while tracing a path. The intensity of the pheromone is an indicator of the utility of that arc to build better solutions.
updated as: where 0 ≤ ρ < 1 and 1 – p represent the pheromone evaporation rate, and Δτ ij is related to the performance of each ant. • The probability of the kth ant at node i choosing node j using the pheromone trail τ ij is given by :
Time: When the bus reaches a node prior to it’s schedule time, we calculate it’s waiting time Wait time = max(Next Node’s departure time - Current time - distance between nodes / speed * 60 , 0) Current time + distance between nodes / speed * 60 + wait time + Distance of that node from Bosch Bidadi / speed * 60 <= Time to reach office Handling Time Windows
updated as: Current time += distance between nodes / speed * 60 + wait time - We have assumed the speed to be 60kmph in our program. Handling Time Windows
m artificial ants are activated to construct m solutions • Compared to current solution and, in case any one solution is better, it is sent to MACS-VRPTW • MACS-VRPTW uses this solution to update the current tour • After solutions generation, the global updates are performed ACS-buses • Searches for a feasible solution by maximizing the number of visited nodes. • Starts computation using v-1 vehicles (one vehicle less than the smallest number of vehicles in current feasible solution) • Produces a solution only when the number of visited nodes in current best solution is increased
be later used in algo easily) Populate a Distance Matrix based on the actual shortest distances between two Geo Locations using Google Maps Distance Matrix API. Otherwise, our algorithm guarantees > 85% occupancy all the times (as ants visit all the possible nodes once) Optimise the path for the given points, and find the number of buses used. No bus can run on that route (given the constraint of total travel distance per day) However, we still give the best number The complete workflow! < 85% bus occupancy on route Otherwise Current running time maintained for all the buses which helps understand which nodes to visit.
the pickup-drop services. Due to budget limitations, parking place limitations, less management staff, the organisation might decide to use maximum of 5 buses, even if 7 are actually required! Adding one extra constraint (For practicality purposes)
path using the input data Some nodes are left out because that path does not have 85% occupancy Bus capacity: 20 Total Customers: 30 85% Bus Capacity: 17 Best case remaining : 13 (<17, hence another bus can’t run for remaining number)
problem can be solved using metaheuristic approaches, and can be modelled as a VRPTW problem. We tried clustering, and other approaches which didn’t work like metaheuristics. Hardships! Understanding what the problem demands Optimising two constraints at the same time We had earlier worked on problems like TSP etc, where only one constraint had to be optimised. It took us long enough to understand how to take care of two constraints at the same time efficiently Keeping the track of current time We assume the bus always run at speed 60km/h. Then we had to understand how to keep track of bus current time.
as we are going to run the simulation for the data. References: http://people.idsia.ch/~luca/tr-idsia-06-99.pdf We have the code uploaded to GitHub : https://github.com/shreyasbapat/Route-Optimisation THANKS
shreyasbapat
d_endo
sutetotanuki
nrslib
harunatsujita
biacco42
kaitokudou
katty0324
hatsu38
ymtdzzz
waka292
wenas
mackey0225
garrettdimon
cromwellryan
morganepeng
bkeepers
addyosmani
rocio
marcduiker
ufuk
thoeni
jponch
akosma
eitanlees
