[pgrouting-dev] Some GSoC ideas about pgRouting(full)

Hi, everyone,

Sorry, I forgot to write my ideas about pgRouting in my last email. :slight_smile:


1> about C++ Boost graph algorithms, there are still some graph algorithms not in pgRouting(planer graph algorithms, etc.)

2> about Vehicle Routing Problem: Pickup and Delivery, use shortest path algorithms(Dijkstra, Dijkstra + Heap, Bellman Ford, SPFA, etc.)

3> about Support for variable priorities (order, vehicle), maybe use Astar algorithms is better.

4> about Chinese Postman Problem, it’s an easy problem on undirected graph.Otherwise, this problem is NP-Hard.Maybe heuristic algorithms(Astar etc.) will be helpful.Use Kruskal algorithms(only consider vertices with odd degree) to make MST and match these vertices, then we get approximate solution with less time complexity.

It would be very kind of you if you could tell me any suggestion or information for this project so that I can make my ideas better. :slight_smile:

Maoguang Wang