Yesterday I attended my first MobiDevDay conference and presented a talk titled “Functional Programming for the Rich Mobile Web with F#.
The scenario for the demo’ed sample app is that a central website receives orders for flowers from all across the US. Local florists can look at the orders in their area and choose to fill the ones they can – with the help of the sample app. The app has only two screens as shown below:
The first screen shows a list of unfilled orders near the florist’s location. The florist selects from the available list, the orders he/she can fill and then generates a delivery route.
Although the app is small it is representative of a production app in terms of functionality as shown by the architecture diagram below:
A real production app would add security and perhaps better error handling.
The mobile web app was built with F#, WebSharper (which I believe is the best method for building such apps), JQuery mobile, and Bing Maps API. It also leverages the SQL type provider for database access.
Source Code: https://mobidevday2013.codeplex.com/
One problem that had to be tackled was optimizing the delivery route. The list of orders are geocoded based on the delivery zip code and then a route is generated with each delivery location as a waypoint in the route.You don’t want a route which crisscrosses the entire metro area! This can happen if the route points are arbitrarily ordered.
Optimizing a route is close to the the famous Travelling Salesman Problem which is NP-hard. Consider a single path from a starting point and going through 10 delivery locations (which are all connected in the underlying graph representation):
Let’s say you have a distance (cost) between any two pairs of points on the graph. A naïve approach would be to generate all possible paths and add the total distance travelled and then choose the path with the minimum distance. However the number of paths grows exponentially with the number of route points. There 3+ million possible paths with just 10 route points (10!).
To tackle this issue, I worked out a heuristic, greedy algorithm which works by picking the nearest point from the starting point and then the next nearest and the next nearest and so on until all points are covered (note this is not globally optimum but still gives reasonable results in practice).
open System let calcDist (lat1, lon1) (lat2, lon2) = let r = 3958.75 // earth radius in miles let radPerDegree = 0.017453293 // radians per degree PI/180 let phi_1 = (90.0 - lat1) * radPerDegree let phi_2 = (90.0 - lat2) * radPerDegree let th_1 = lon1 * radPerDegree let th_2 = lon2 * radPerDegree let d = r * Math.Acos( Math.Sin(phi_1) * Math.Sin(phi_2) * Math.Cos(th_1 - th_2) + Math.Cos(phi_1)*Math.Cos(phi_2) ) d let shortestPath (points:(string*(float*float))) = let allPairsDist = [for i in 0..points.Length-1 do for j in i+1..points.Length-1 do let z1,p1 = points.[i] let z2,p2 = points.[j] let dist = calcDist p1 p2 yield z1, (z2, dist) yield z2, (z1, dist)] let latLong = points |> Map.ofArray let graph = allPairsDist |> Seq.groupBy (fun (a,b) -> a) |> Seq.map (fun (a,xs) -> a,xs |> Seq.map snd |> Seq.toArray |> Array.sortBy snd) |> Map.ofSeq let shortestPath = let startList = [fst points.] let visitedSet = Set startList let rec sp ((zfrom::_) as path) sDone = let edges = graph.[zfrom] edges |> Array.tryPick (fun (z,d) -> if sDone |> Set.contains z then None else Some z) |> function | Some z -> sp (z::path) (sDone |> Set.add z) | None -> path |> List.rev sp startList visitedSet shortestPath |> List.map (fun z -> z,latLong.[z]) //testing let points = [| "48331",(42.50513,-83.40723) "48036",(42.59383,-82.91332) "48030",(42.49648,-83.09847) "48239",(42.39228,-83.28202) "48127",(42.33438,-83.27392) "48197",(42.20213,-83.62049) "48104",(42.2709,-83.72782) "48009",(42.53483,-83.22416) "48393",(42.52053,-83.54914) "48307",(42.65928,-83.12248) "48238",(42.23993,-83.15082) |] shortestPath points