Hello Everyone !!! Welcome to RoastRoute !!!

• brought to you by Team 19

What is RoastRoute ?

• RoastRoute is a Geographic Information System designed to provide a platform for coffee lovers to organize coffee dates, with features that follow state-of-the-art conventions, making it extremely usable and resposive.

Why RoastRoute?

• Roast Route lets you easily locate your favourite coffee shops through our coffee shops button
• Roast Route's find Coffee Dates feature allows you to quickly search for people like you that want to connect over a cup of coffee
• Roast Route has state-of-the-art path-finding algorithms implemented to help you get to your coffee date or your favourite coffee shop as soon as possible

Basic Features

Search Bar

• A search bar supports search by text entry and pin placing
• Search bar supports auto-zooming feature
• 3 search types: by Point of Interest, Street, Intersection

Find nearest coffee shops

Using the GoogleMapsAPI, we query specifically coffee shops that are within a certain distance from the users pin and lets them easily see nearby coffee shops and their ratings.

Find coffee dates

Our team implemented a FASTAPI to allow our application to have users connect with other users on the map and communicate with them.

Path Finding Algorithm

The team tried the implementation of both Dijkstra and A*. We eventually deicided to use Dijkstra for multi-destiation Dijkstra used for solving the travelling courier problem.

Dijkstra	A*
Always guranteed to find optimal path as it considers all nodes in the graph reaching	A* is computationally faster as it uses a underestimate heuristic (estimated travel time from neighbouring node to destination)

Path finding results shown on map:

Path-finding results:

Results	Toronto	London
Travel Times
Computation Times

Travelling Courier Problem

To tackle the travelling courier problem, our team explored different ways of implementing iterative improvement to a result generated by a Greedy algorithm

Approaches	Type	Results
Greedy Algorithm	A Greedy Algorithm is simply an algorithm that always considers the closest legal option when doing a pick-up or drop-off. It continues to do so until no legal options are left to explore, meaning all pickups and drop offs are completed.
Greedy++	Greedy++ is a modified version of Greedy where we implement Multi-Start, meaning we consider all possible starting positions of the Courier route. As there are more than 1 depot, we consider all the possible ways to start the path and take the one that generates the lowest travel time.
Swapping	Taking the best result from Greedy++, we perform a swap by picking 2 locations,(could be a pick up or drop off). We ensure that the swap is legal and generates a better path. If these conditions are met, we alter tha path and make that the new path. We continue doing so until it no longer makes any improvements to the path.
2-opt Reversal	Taking the best result from Greedy++, we implemented 2opt by first making 2 cuts in our existing path, take the middle section and flip it, reconnect them. We ensure that the reversal is legal and it improves our QoR scores. This is not as effective as there are a very small portion of possibilities where this pertubation is legal.
2-opt Shifting + Reversal	Taking the best result from Reversal, we take the best path found so far and introduce a shifting pertubation where we make 2 cuts in our existing path, we take the middle section and shift it down by a number of times. We also ensure that the shift is legal and shows improvment before making any changes.