[pgrouting-dev] GSoC 2023 - Final report: Implement-pgr_KSP-and-Add-All-Overloads

pgRouting pgrouting-dev
1

Hello everyone,

With GSoC coming to an end, I hereby present my final report of the work I have done over the past three months. It has been an amazing experience and great learning, working with the pgRouting community and mentors. This report follows the guidelines set by Google and OSGeo GSoC Admins.

1.(a) Title:

  • Implement pgr_KSP and Add All Overloads

1.(b) Organisation:

  • pgRouting under OSGeo
  1. Abstract:
  • This GSoC project deals with the implementation of the Overloads of the existing function pgr_KSP in pgRouting.
  • pgr_KSP This function is used to Calculate the K Shortest Paths between the source and target node of a graph.
  • The addition of Overloads will help to calculate the K Shortest Paths for the following scenarios.
  • single source and multiple targets
  • multiple sources and single target
  • multiple sources and multiple targets
  • combinations of sources and targets
  1. The State of the Project Before GSoC:
  • The pgr_KSP function was already there in pgRouting but it didn’t have the following overloads One-to-Many, Many-to-One, Many-to-Many, and Combinations.
  1. The addition that my project brought to pgRouting:

  • The pgr_ksp function has expanded its functionality and usability by incorporating various overload options. These options include:

  • One-to-Many Paths: Users can now find the k shortest paths from a single source to multiple target nodes. This is useful in scenarios where you have one starting location (source) and multiple potential destinations (targets).

  • Many-to-One Paths: Similarly, users can find the k shortest paths from multiple source nodes to a single target node. This could be used when you have several starting locations and want to reach a common destination.

  • Many-to-Many Paths: Your implementation allows users to find the k shortest paths between multiple source nodes and multiple target nodes. This covers more complex scenarios where there are multiple starting and ending locations.

  • Combinations of Sources and Targets: Your work enables users to mix and match different source and target combinations, creating a flexible solution that caters to a wide range of routing requirements.

  • By adding these overloads, the pgr_ksp function is more versatile and capable of addressing various routing needs. This expansion of functionality enhances the usefulness of pgRouting for real-world applications, making it more accessible and valuable to developers, researchers, and users who require advanced routing solutions.

  1. Potential Future Work:
  • Performance Optimization: As the complexity of routing scenarios increases, the computation time for finding k shortest paths can also grow. There’s potential to further optimize the algorithm, perhaps by exploring parallel processing, heuristics, or indexing techniques to speed up the computation of paths.
  • Documentation and Examples: Comprehensive documentation and usage examples are crucial for users to understand and utilize the function effectively. Improving documentation and providing practical examples would aid in the adoption of your enhancements.
  1. Links:
  1. Images:

I am absolutely thrilled to have had the incredible opportunity to be a part of both the GSoC and OSGeo communities. The knowledge and skills I’ve gained throughout this enriching period are invaluable assets that will undoubtedly shape my path in future development endeavours. Knowing that my code could potentially bring value to the community fills me with great satisfaction. I want to express my heartfelt gratitude to everyone who has offered their unwavering support and guidance. Here’s to the power of collaboration and shared learning! Thank you all immensely!

Thanks and Regards,

Aniket Agarwal