CITY MAP
This is a project completed in the second year of university for the Communication and Design course with two other students. It is written entirely in C++ on a Linux system with Git, but the code cannot be released online due to copyright by the univeristy. Most of the code was written by me. Using map data from a bin file, we displayed graphics for features of the map such as green spaces, buildings, streets and intersections. Intersections and features can be searched using the text field at the top of the window. Paths can be found between intersections. In addition to the map graphics, we also developed an algorithm to find the best sequence of paths for a delivery truck to pick up and drop off packages. This is similar to the famous traveling salesman problem, but with extra restrictions such as truck capacity.
VIDEO DEMONSTRATION
 Zoom 0.PNG |  Zoom 1.PNG |  Zoom 3.PNG |
|---|---|---|
 Zoom 2.PNG |  Zoom 4.PNG |  Zoom In.PNG |
ZOOM LEVELS
Streets and text are hidden until the zoom level is appropriate. Zooming is done by scrolling the mouse wheel or clicking the zoom buttons. Streets are coloured based on speed limit with the faster streets showing up first.
 Help SONAR.PNG |  Green Areas SONAR.PNG |  Dixie and Dundas.PNG |
|---|---|---|
 Woodbine Beach SONAR.PNG |  College and University.PNG |  Square One SONAR.PNG |
 CM SONAR.PNG |  Hong Kong SONAR.PNG |
EXPLORING
The user can click on most features and intersections, which display's their name on the status bar. The user can also search for intersections and features by their name. A map of a different city can be loaded from a bin file by entering the file path into the text field or using the city name and country name.
 Destination Intersection.PNG |  Click Find Path.PNG |  Big Path.PNG |
|---|---|---|
 Directions SONAR.PNG |
PATH FINDING
Dijkstra's algorithm is used to find the best path between two intersections in the city. Step by step driving directions are provided. The path can be chosen by typing the names of the two intersections or by clicking the two intersections on the map. The pathfinding takes left turns and right turns into account and avoids turning when possible.
TRAVELING COURIER
This algorithm finds a good sequence for a delivery truck to to pick up and drop off a series of packages located anywhere in the city. It is subjected to a finite truck capacity and 45 second computational time. The initial process is like Dijkstra, but searches the entire map. This process has n log n complexity and uses multi-threading. After it is done, a path from a delivery location to anywhere on the map can be found very quickly with the O(n) traceback routine. This is important when the entire courier path is being constructed and rearranged. The second process is Multi-Start. The first phase starts at every depot and travels to the next best delivery location based on travel time. The best path from this phase is passed to the second phase, which does the same thing, except that it has a 10% chance of going to the second best location instead of the best. There is potential to find a shorter overall path this way, even if one segment is longer. It repeats this ten thousand times. The third process is random 3-opt. Four consecutive delivery instructions are randomly shuffled. This has the effect of disconnecting three paths and reconnecting in a different way. It can help undo paths that cross over. This repeats until the 45 second limit is over. This algorithm has been tested with orders of more than 200 deliveries at a time.
