Since they're already using the Google Maps API, they could try to adapt the javascript-ified TSP solver: http://gebweb.net/optimap/
Only works well for about 25 points though--but you could use pre-sorting to divide it up into 4 possible best clusters, and then apply the TSP solving on each of them. On Sat, Oct 18, 2008 at 4:10 AM, Jennifer Strahan <[EMAIL PROTECTED]> wrote: > Hello Peter, Michael, Josh and Geowankers, > > Thanks for the detailed description of the problem and for the potential > solutions. > > Does anyone know if there already exists a tool that canvassers can > use? Peter is correct that time is of the essence so there isn't any > time to develop anything. Or, are there any folks in the group willing > to put in some volunteer time to quickly create something? > > Jennifer > > Peter Batty wrote: >> This is actually a (somewhat constrained) traveling salesman problem >> rather than requiring a point to point route, so Google Maps routing >> won't help you. pgrouting supports traveling salesman but I haven't >> used it and don't know what a practical number of points to handle is >> - traveling salesman is a complex problem of course. I was out >> canvassing for the xxxxx campaign recently (the number of x's is a >> clue, in my case at least :) !!), so was an end user of what I assume >> to be the same system here. Of course I immediately wondered about a >> better automated solution than they had also. >> >> I thought it was an interesting problem though so it's worth >> explaining it in a little more detail based on my experience. We went >> out in pairs, and were each given a package of paper sheets. The cover >> page had a printed Google map with markers indicating the houses we >> were to visit (this was the same map for both of us). Then behind that >> we had a set of printed sheets, one or more per street, listing the >> houses we needed to visit on each street in numerical order, with >> details about the person/people to talk to at that house. We were just >> visiting houses of known sporadic supporters and independents, so it >> was a subset of houses - in this case it would vary from maybe 1 to 4 >> out of every 10 houses. One canvasser had odd numbers and one even >> numbers, so you would do opposite sides of the street, so you had >> someone in the same general area for support. Often you would have >> more houses in a block on one side of the street than the other, so >> one person would get ahead of the other. In the area that we were >> canvassing, the blocks were long and thin, so we ended up walking >> along the blocks "lengthwise" as most of the addresses we had were on >> the north-south streets, but it was hard to tell if you were close to >> a house on one of the east-west streets (on a different page from the >> one that you were currently looking at). We ended up missing out some >> of these. In total we had 90 houses in the package, 45 each. >> >> So what we really wanted was to each have a list of our 45 houses in a >> suitable order for us to visit (as opposed to being listed street by >> street in numerical order), with a map showing the route. Doing the >> odd / even thing properly is an extra complication (i.e. taking 90 >> houses and coming up with two routes, which ideally keep the two >> people close to each other). The simplest initial solution to this >> would probably be to take all 90 houses, come up with the best route >> to all those, and then just split it into odd and even after doing >> that. If you got that working, then you could look at something cleverer. >> >> It seems as though for pgrouting you would need to have a reasonable >> street network, which you may or may not have. In some cases, >> especially if you had a pretty dense set of houses to visit, you might >> be able to get a reasonable solution just using the locations of the >> houses and ignoring streets altogether - but clearly in some cases >> this would not work well. >> >> A pragmatic short term solution might be a semi-interactive one - >> display the houses to visit on a map, let a user sketch a line >> visually with an approximate route, buffer around that and find all >> the houses close, and sort them appropriately based on that. And have >> the ability to highlight any houses that were not yet added to the >> route, etc. I suspect that for a short term solution (which is >> presumably what you need), given the challenge of getting a good road >> network, etc, this approach may be your best bet. It would need a bit >> of custom development though, unless someone happens to have something >> like that lying around. >> >> Cheers, >> Peter. >> >> On Thu, Oct 16, 2008 at 12:01 AM, Josh Livni >> <[EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>> wrote: >> >> pgrouting if you have the street data in postgis would be one way. >> >> tho as long as they're drawing over google maps, why not insert a >> little javascript to use the gmaps api routing? >> >> -josh >> >> >> On Thu, Oct 16, 2008 at 1:03 AM, Jennifer Strahan >> <[EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>> wrote: >> >> Hello Geowankers, >> >> I'm forwarding this email from a colleague in hopes that >> someone will >> have some suggestions to pass on. >> >> Thanks for the help. >> >> Regards, >> Jennifer >> >> ps. I've stripped out political references.... that's why >> you'll see >> xxxxx campaign. >> >> -------- Original Message -------- >> Subject: GIS routing question >> Date: Wed, 15 Oct 2008 14:32:43 -0700 (PDT) >> From: [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]> >> To: [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]> >> CC: [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>, >> [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>, >> [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>, >> [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>, >> [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>, >> [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>, >> [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>, >> [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>, >> [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]>, >> [EMAIL PROTECTED] <mailto:[EMAIL PROTECTED]> >> References: >> <[EMAIL PROTECTED] >> <mailto:[EMAIL PROTECTED]>> >> >> >> >> Hi All >> >> My partner is working for the xxxxx campaign and was asked by >> the regional campaign office to look for computer-based >> routing solutions for canvassing. >> >> Nationally, all the campaign offices use a networked, >> web-browser-accessible database called VoteBuilder. It manages >> contacts and lets field coordinators define canvassing >> territories by drawing over a Google map. >> >> VoteBuilder doesn't construct a route for the canvassers-- >> that's up to them. In suburban neighborhoods with winding >> roads and cul-de-sacs it's almost impossible for them to come >> up with an efficient route that doesn't miss some of the >> households. >> >> Some of the local and regional offices have adopted software >> solutions for routing, but the techniques aren't being >> disseminated. >> >> I know there's an extension for ArcGIS to do routing. Is this >> the only solution? >> >> Thanks for any suggestions.. >> >> Louis >> >> >> >> >> >> _______________________________________________ >> Geowanking mailing list >> [email protected] <mailto:[email protected]> >> http://lists.burri.to/mailman/listinfo/geowanking >> >> >> >> _______________________________________________ >> Geowanking mailing list >> [email protected] <mailto:[email protected]> >> http://lists.burri.to/mailman/listinfo/geowanking >> >> >> >> >> -- >> Peter Batty - President, Spatial Networking >> W: +1 303 339 0957 M: +1 720 346 3954 >> Blog: http://geothought.blogspot.com >> ------------------------------------------------------------------------ >> >> _______________________________________________ >> Geowanking mailing list >> [email protected] >> http://lists.burri.to/mailman/listinfo/geowanking > > _______________________________________________ > Geowanking mailing list > [email protected] > http://lists.burri.to/mailman/listinfo/geowanking > _______________________________________________ Geowanking mailing list [email protected] http://lists.burri.to/mailman/listinfo/geowanking
