G E B W E B

Will the USD continue to tank, or will the greenback make a comeback? Follow the day-to-day movements with this widget for Mac OS X.

The US dollar index is computed from the exchange rate with the Euro, Yen, British Pound, Canadian Dollar, Swedish Krona and the Swiss Franc. It was introduced in 1973 and was initially set to 100. Since then, it has been as high as 160 and as low as 75, where it is now. If you’re an international investor with US-denominated assets, you almost certainly want to track the US dollar. If you’re an American, you should definitely be concerned with the decline of the dollar as a result of your government’s policies. Lowering interest rates makes the dollar less valuable. And that means inflation and more expensive imported stuff such as oil.

Graphics and idea are from Fabian Graciano. Yeah, that’s why it looks so much more awesome than my previous widgets The data feed is graciously sponsored by INO.com. Thank you! Comments, requests and bug reports are very welcome! Just leave your feedback on this website. I’ll do my best to respond.

Download: US Dollar Index Widget.

Instructions: Mac OS X 10.4 Tiger is required. If you’re using Safari, click the download link. When the widget download is complete, Show Dashboard, click the Plus sign to display the Widget Bar and click the widget’s icon in the Widget Bar to open it. If you’re using a browser other than Safari, click the download link. When the widget download is complete, unarchive it and place it in /Library/Widgets/ in your home folder. Show Dashboard, click the Plus sign to display the Widget Bar and click the widget’s icon in the Widget Bar to open it.

A while ago, I made OptiMap, a Google Maps mashup that will take a number of locations and give you the best way to visit all of them. By best, I mean fastest. Since then, I have been exposed to various ideas on applications for this tool. One is in the real-estate business, where prospective home buyers want to visit a number of houses for sale.

To make things easier for anyone interested in applying this tool, there is now a way for your website to make search requests automatically. This is done by sending a http GET request to http://gebweb.net/optimap/index.php?loc0=start&loc1=dest1&loc2=dest2. Here, start should be replaced by the address or (latitude, longitude) pair where your trip starts and ends, and dest1 and dest2 each should be replaced by either an address or a (latitude, longitude) pair you want to visit.

Up to 20 locations can be specified in the variables loc0, loc1, …, loc19. Remember to http-encode any whitespace etc. in your address strings. This is done automatically if you use the html form element to store your data. Example:


<form NAME="roundtrip" METHOD="get" ACTION="http://gebweb.net/optimap/index.php">
<input NAME="loc0" TYPE="text" />
<input NAME="loc1" TYPE="text" />
<input NAME="loc2" TYPE="text" />
<input NAME="loc3" TYPE="text" />
<input TYPE="submit" VALUE="Submit" />
</form>


In some applications, you will not want the user to be typing in addresses himself, so the html form hidden input element may be more suitable than the text input element. The value of such an element can be set with php when the page is created. It can also be changed with JavaScript, with the following code (assuming the form is called “roundtrip”):


document.roundtrip.elements["loc0"].value = "2 Bloor St West, Canada";
document.roundtrip.elements["loc1"].value = "(37.4419,-122.1419)";


If you have any comments, bugs or feature requests, please leave a comment on this site

UPDATE: This widget no longer works. Please consider the Commodities Widget instead.

Apple Mac OS X (version 10.4 and above) has this neat feature called dashboard. It lets tiny programs, called widgets, run as an overlay to your screen when you press ‘F12′. There are widgets that show the current time in any timezone, hurricane advisories, stock quotes, your computer’s vital stats, and much more.

I’ve got a certain desire to stay updated on the price oil, since it’s often related to world events. For instance, a spike in the oil price might mean a hurricane is headed towards the Gulf of Mexico or that there is more unrest in the Middle East. So to satisfy this urge for oil price updates, I’ve created the Oil Price Widget. It works on Mac OS X Tiger and gathers information from 321energy.com, which is displayed in a small window on the dashboard.

Download: Oil Price Widget.

Instructions: Mac OS X 10.4 Tiger is required. If you’re using Safari, click the download link. When the widget download is complete, Show Dashboard, click the Plus sign to display the Widget Bar and click the widget’s icon in the Widget Bar to open it. If you’re using a browser other than Safari, click the download link. When the widget download is complete, unarchive it and place it in /Library/Widgets/ in your home folder. Show Dashboard, click the Plus sign to display the Widget Bar and click the widget’s icon in the Widget Bar to open it.

What really happens when you hit the ‘Calculate fastest roundtrip’-button in OptiMap? The problem we attempt to solve is a classic and is called the ‘Travelling Salesman Problem’ or simply TSP.

Before we dive into this intrigueing question, some definitions are useful. Each location will be referred to as a node, with location number denoted . There are nodes in total. The trip between a pair of nodes is called an edge, and the trip from node to is denoted . The full set of nodes and edges is called a graph and is denoted.

We note that in the context of driving directions, there is either a way to go from each node to all of the other nodes, or there is no way to reach that node at all. We will assume that there is a way to reach all the nodes, otherwise there would be no solution at all. For ease of notation, we say that the time it takes to traverse an edge is .

Another characteristic of the problem we try to solve is that the time associated with an edge is not necessarily equal to the time associated with its reverse edge. This is the result of for instance one-way streets and that it’s easier to turn right than left at an intersection. Thus, our graph is directed.

The first part of solving the problem is defining it. We seek to find an ordering of the nodes, starting and ending at node 1, that visits each location exactly once. This ordering should minimize the total time it takes to traverse.

There are possible roundtrips that visits each location exactly once. Evaluating each possible roundtrip, a so-called brute-force approach gets infeasible between 10 to 20 nodes, depending on your patience and hardware. Actually, all known methods of finding the optimal solution use resources exponential in .

With 9 or less nodes, it is feasible to write code in JavaScript. So in this case, you get the optimal roundtrip.

If we’re willing to settle for near-optimal solutions, a number of methods are available. These are called heuristic methods. The simplest of these methods is to always travel to the unvisited node that is closest to the one you’re currently at. This method is referred to as ‘Greedy’ in the performance results below.

There are better methods. ‘Ant Colony Optimization’ is one of them. Inspired by the way ants find food in nature, this method uses a swarm of ants, each of which is fairly dumb, to find an intelligent overall solution. Real ants leave pheromone trails when they walk. They can also smell these trails. If an ant finds food close to the ant colony, this trail will be traversed faster than the others and have a stronger smell, because the pheromone dissipates over time.

By letting virtual ants walk randomly around in the graph, we get roundtrips. The ant roundtrips are evaluated by the time they took to complete, with faster roundtrips being assigned a stronger smell. An important question is how the virtual ants choose which nodes to visit next. Probabilities are assigned to each edge going to an unvisited node, depending on its assigned time and how smelly it is:

Here, is the smell assigned to edge . The ants pick edges according to these probabilites. The constants and can be used to fine-tune the performance of the ant method.

Another trick which is called k2-opting is used when an ant has completed its roundtrip. We pick two edges of the tour, and see if the edges can be swapped to create a better tour.

The k2-opting procedure is repeated until no two edges can be swapped to create a faster roundtrip. k2-opting is a cheap way of improving many TSP heuristics.

Performance:

The numbers are in seconds. The ACO column is with 30 ants and 30 waves, the k2-opt ACO column is with 10 ants and 10 waves, to make up for the extra computation needed to do the rewiring. The results suggest that the current method should find roundtrips very close to the optimal.

Imagine you are a salesperson and have to visit a number of customers. However, you want to spend as little time as possible driving. If you only have to visit two or three locations, it is usually easy to find the optimal route. You can use regular map services such as Google Maps, Yahoo! Maps or MapQuest to find the shortest path between two places. However, as the number of locations to visit grows, the task of finding the order in which to visit the locations becomes daunting.

Despair not, I have created OptiMap, the answer to all your roundtrip troubles. At least the troubles that involve 20 or less locations to visit. There might be time and fuel costs (and thus greenhouse gas emissions) to save here, but don’t come sue me later if you find a better route. The application is only as accurate as the data that Google Maps supplies to it. Furthermore, when 10 or more locations are entered, a heuristic called Ant Colony Optimization (with some other tricks, too) is applied instead of trying every possible ordering, so there’s no guarantee of finding the optimal route. The heuristic usually finds a solution impressively close to the optimal, however.