19 Jun 2018 - Dan Kristiansen
An aSTEP application with a greedy heuristic approach to the capacitated vehicle routing problem.
aSTEP is a spatiotemporal data management and analytics platform, that aims to help developers build their own location based services. aSTEP is a collaborative and inherited project that spans over a bachelor semester at Aalborg University. The project is distributed between multiple groups that each have individual, aswell as collaborative, responsibility for features of aSTEP.
The aSTEP feature of this report concerns the Logistics solution, which allows a freight forwarder to receive routes to a given workload list input.The solution is implemented using the savings algorithm, and Large NeighborhoodSearch to optimize the routes from the savings algorithm. To be able to calculate the routes of the workload list, the algorithm needs to know the duration between the set of locations relevant for the workload. Durations are calculated through Open Source Routing Machine, which uses Multi Level Dijkstra to calculate durations based on data provided by Open StreetMap. To ease development, Continuous Integration has been set up through GitLab Runner. Depending on the project, the CI setup deploys either to Artifactory or GitLab Container Registry. To host the frontend, a script has been implemented to pull and deploy the latest content from the Registry.
To understand the system, we give the figure below. The Input component takes as input a road network, a list of distribution centers, and a list of fixed pickup points. We model the above information as a graph, where vertices represent road intersections, the distribution centers, or the fixed pickup points and edges represent road segments connecting vertices. If a workload file is available, e.g., from a company or open benchmarks, the system provides a parser to parse the workload file into a JSON file that consists of the workload information, i.e., source, destination, size, weight, and preferred delivery interval. Otherwise, the system provides a workload generator to generate synthetic workload.
Participants are provided with opportunities to try both the user mode and developer mode by using mode toggle (Label 2). Workload can be uploaded by a workload file (Label 3) or can be generated by clicking the “Generate” button (Label 6). Labels 4 and 5 show different parameters where participants can change for configuring the algorithms for route generation, route optimization, and synthetic workload generation, which are only available in the developer mode. The final routes are shown in a map interface (Label 8), where different routes are shown in different colors. In addition, distribution centers are shown as squares and delivery points are shown as circels. In the information bar, participants can choose different routes (Label 9) to check the specific information of the chosen route, e.g., delivery time at each delivery point on the route (Label 10). The whole plan of the deliver routes can be saved as a file (Label 7)
