Inspiration
The project serves as a sequel to https://github.com/charlespnh/Recreational-Algorithmic-Project-II, but a with completely different architecture design and new programming languages. In particular, the core concept involves the Euclidean traveling salesman problem (TSP) where given a list of locations, we are interested in a circular route minimizing the total distance or duration, and efficient point location where given a list of locations, we want to find other closest locations to the route. The idea, although may be abstract, find itself in many application in logistics and transportation. Specifically, with delivery drivers tend to work under pressure (Amazon, UPS, public transportations) with no time for errands, the project offers helps by providing optimized routes as well as closest nearby places that drivers may be interested, without compromising the schedule.
What it does
There are 2 queries that the project support: solve for optimal delivery route and query database for locations nearby. The entire project serves as RESTful backend application and thus, computations are exposed through the URL endpoints.
How we built it
- Compute optimal route: We make use of external API, the Google Map Direction API, to solve the traveling salesman problem. The request for computation is mainly handled through route /tsp/solve with core functionality implemented in Go as well as the Gin web framework.
- Compute point location: The idea of efficient point location is to minimizes the locations we have scan go through in the database. In particular, we 'hexagonalize' our world map into hexagonals. As such, looking for nearby locations is simply index into the shared hexagonal area which is much more efficient. This is achieved by the open-source H3 library for geospatial index system. The database of choice is PostgreSQL, and the interaction against H3 library and database is through NodeJS and ExpressJS web framework.
Challenges we ran into
The technologies used are very much new to me. I've only learned Go a few days ago, and I have absolutely no experience in relational database. Like most others, my time is spent mostly on debugging. A hard part of the project is to manage the design as well: a database, 2 programming languages are involved with many more libraries.
Accomplishments that we're proud of
It is quite unbelievable that a large part of the project is done, given that the design is quite complex and that many tools are new to me. There are core features that unfortunately hasn't been implemented due to time, but they will be much quicker to implement given that the base of the project has been set up.
What we learned
A new programming language, a new database and that I can stay up for over 24 hours without going to sleep
What's next for Orthanc
An important feature to implement is compute the optimal TSP route that go through at least one of the nearby locations. Another important feature is the frontend, handling user inputs and make requests to the APIs via friendly interface.
Log in or sign up for Devpost to join the conversation.