[pgrouting-dev] [SoC] [GSoC 2018] Final Report - Implement Minimum cost flow and ChPP for pgRouting

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

[pgrouting-dev] [SoC] [GSoC 2018] Final Report - Implement Minimum cost flow and ChPP for pgRouting

Maoguang Wang
Hi all,

I am Maoguang Wang, and This is my final report for my GSoC project.

Title:  Implement Minimum-cost flow Algorithm by the Boost Graph Library and Chinese Postman Problem for pgRouting

Organization: pgRouting under OSGeo


Minimum-cost flow problem is an extension of maximum flow problem with an added cost (per unit flow) for each edge. The Chinese Postman Problem (ChPP) in a directed graph can be solved by Minimum-cost flow algorithm.

I have added Minimum-cost flow algorithm and directed ChPP algorithms to pgRouting during this GSoC period.

Implemented functions


  • pgr_ChPP

  • pgr_ChPP_Cost
  • pgr_minCostMaxFlow
  • pgr_minCostMaxFlow_Cost

State of the art before the project: pgRouting didn't have above functionalities before my GSoC. 

Addition that my project brought to pgRouting: 
The deliverables are code, full documentation, documentation tests, pgTap of above functions.

Future Directions:
  • Double confirm the documentation.
  • Implement undirected ChPP algorithms.
  • Implement windy or other complex ChPP problems.
  • Test the implementation in real cases.

pgrouting-dev mailing list
[hidden email]

pgRouting Directed Chinese Postman.pdf (105K) Download Attachment