Re: [boost] [graph] Are you interested in the Route Inspection Problems and Vehicle Routing Problems?

Subject: Re: [boost] [graph] Are you interested in the Route Inspection Problems and Vehicle Routing Problems?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2014-04-14 10:16:31

> From: Ciro Santilli <ciro.santilli_at_[hidden]>

> To: boost_at_[hidden]
> Cc: 
> Sent: Sunday, April 13, 2014 5:23 AM
> Subject: [boost] [graph] Are you interested in the Route Inspection Problems and Vehicle Routing Problems?
> 
> Are you interested in implementations for the following problems:
> 
> - Route Inspection Problems:
> http://en.wikipedia.org/wiki/Route_inspection_problem
> 
>     - classic: find shortest path for undirected graph possibly
> repeating edges. O(n^3).
>         If Eulerian path exists, it is the min.
>     - mixed graphs. NP-complete. AKA Chinese postman problem.
>     - k-Chinese postman problem. N postmen.
> 
> - Vehicle routing problem: http://en.wikipedia.org/wiki/Vehicle_routing_problem
> 
>     Generalization of Route Inspection. NP-complete. Many variants:
>     edges have one ore more weights, and multiple constraints are possible:
> 
>     - carrying capacity of each truck
>     - time to travel an edge and delivery windows for each edge
> 
> All of those problems have extensive literature, and obvious practical
> applications.

Yes, definitely.

> Why don't you use GitHub's Issue tracker instead of the mailing list?
> It integrates better with the code tracking and merge requests, and is
> much easier to search.
> That would greatly reduce contribution barriers to new devs.


I do not know -- that is a Boost-wide decision.

-- Jeremiah Willcock