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

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_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.


Best Regards,
Maoguang Wang

pgRouting Directed Chinese Postman.pdf (77.4 KB)