DEVELOPMENT OF A MIDDLEWARE FOR SEARCHING SHORTEST-PATH IN TIME-DEPENDENT GRAPH

• Main Author: Imantoro, Cendhika
• Format: Final Project
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/43706
• Institution: Institut Teknologi Bandung

Time-dependent graph defined as a graph that represent dynamic object. Searching shortest-path in this graph requires consideration of graph state in multiple time instance. Path building process does not only involve choosing right node to visit. It also involve picking the right time to visit the node. Because of that, searching shortest-path in time-dependent graph requires different handling. A software that can provide this handling is needed. This software can be implemented in form of a middleware. With proper design, middleware is capable of interacting with varying data sources. Middleware also can be designed to be compatible with multiple application software. In this final project, a middleware for searching shortest path in time-dependent graph is built as the final product. Main problems in building this middleware are choosing right model for time-dependent graph and choosing shortest-path algorithm to be used. There are two models that used in the middleware, time-expanded graph and time aggregated graph. Time-expanded graph is used in path-building process. Timeaggregated graph is used for data transfer from data source. Shortest-path algorithm that choosen to be used in the middleware is algorithm for directed acyclic graph. This algorithm is further optimized by using timestamp attribute in time-expanded graph model. Validation process shows that implemented middleware fulfill required functional requirements. Implemented middleware can be used with Neo4j and PostgreSQL database as data source. The middleware is ready to receive additional support for other databases. The middleware is not strongly coupled with application software, thus allowing it to be used by varying application software.