|
Boost : |
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk