Until recently, from the moment I created a second project in my solution, I started muttering against Visual Studio because I had to change the same information in several places to update the configuration of my projects. Maybe this is over now...
Suppose you have a Visual Studio solution with several projects : two libraries, a DLL build from them, a few EXE projects to test the DLL. Suppose the two libraries and the DLL use a third-party library, and you'd like to be able to change the version of this library easily. Suppose also that you'd like to add pre-compiler definititions to all the projects.
Visual Studio offers a feature to solve this issue, the Visual Studio Property Sheets, or VSProps. These files are more or less equivalent to the configuration/properties part of the Project files. You can assign Property Sheets to Projects, and Property Sheets can inherit from other Property Sheets. Such a tool can greatly ease the management of project configurations in Visual Studio.
With suitable property sheets, each configuration data appears once: changing the version of the library, or which values are defined, does not require you to change them in each project.
Creating a Property Sheet
To create a Property Sheet, choose 'View' -> 'Property Manager'. Right-click on the project into which you want to add the Sheet, choose 'Add new project property sheet...', and specify a name and a path.
The new sheet appears as a sub-node in each of the existing configurations. Right-click one one of those sub-nodes, choose 'Properties', and you are presented with the full dialog that you already know from the properties of a project.
The values you enter here will be used by any project that uses this property sheet (the first such project being the project into which the sheet was created).
Inheriting the values of Property Sheet
If you look at the 'General' tab of the project's properties, you will notice the 'Inherited Project Property Sheets' property now has the name of the Property Sheet you just created. This means that this project uses all the values defined in the property sheet.
A project may use several property sheets, listed in this field. The values in the ones listed on the top override, when applicable, those that come from sheets listed below.
Note that Property Sheets themselves can inherit values from other property sheets. You can thus build hierarchies of sheets to separate concerns (e.g. one sheet to configure the libraries used in the project, and one other to configure the compiler settings).
Example: choosing a library version
Suppose several projects in your solution use a third-party library that's available in two different versions that you wish to support. Build two separate sheets, one for version X and one for version Y of the third-party library. In each sheet, specify the include path to add and the lib to link with. Name them libX.xml and libY.xml. Then you build a single property sheet lib.xml that has no configuration value but inherits either from libX.xml or libY.xml. Let all your projects inherit from lib.xml. The effect is that changing the version of the library only entails changing which sheet lib.xml inherits from. One change, for the whole solution...
Thursday, August 27, 2009
Thursday, August 20, 2009
Finding compromises when planning a route
We now have wonderful mapping tools with Google Maps and the likes, GPS units in our cars, or mapping programs we can install on our computers. But I've never been really satisfied with those tools when it comes to planning a trip and choosing a route...
Those tools generally offer control on whether you want the shortest or the quickest route, with or without highways, but that's pretty much all... Google Maps now offers one or two alternative routes, which is a good step, but I still think it's not enough.
Let's take an example... To go from Antibes to Méribel-Les-Allues (in the French Alps, approx 206 km from Antibes on straight line, but with the mountains in between), there are many possible routes. The shortest one is 385 km, for a duration of 6h49. The quickest one lasts 5h19, for 566 km. Most GPS units will be able to give you those two routes, but there are many others...
Wouldn't it be nice if, after giving those two routes, the unit would ask you if you want to look for a compromise between the two? This should give you a route that's shorter than 566 km, and quicker than 6h49, if there are some. It could e.g. give you the route that's 405 km for 5h57.
Those three routes would be displayed in a table, ordered by distance or by duration, to your choice. For each couple of consecutive routes, you could ask the unit to look for another compromise between the two selected routes, and this would display a new route in the table, with both the distance and the time in the interval defined by the two previously selected routes. Or, if there is no such route, this pair would not be selectable any more.
You would end up with a set of routes that represent different ways to compromise between the two inherently conflicting goals that are distance and duration... For my example trip, such a table would have entries like :
A route that is 512 km and lasts 6h03 would not be displayed: its distance is between the pair 530...405, but it's duration is larger than both: it's clearly not a good compromise in terms of time and distance...
Of course, the nec-plus-ultra would be to compute the cost of the trip, rather than the distance, taking distance, fuel consumption and tolls into account. One site I know that computes such costs is ViaMichelin. In this case, the quickest route costs 98€, and the economical route costs 42€. But am I ready to spend 1h30 more in my car, for a total of more than 7 hours? Not sure, if the kids are in the car... And that's when I'd really like to know if there is a route that's much less expensive than the quickest one, for only slightly more time...
All the data is there... Why don't we get those informations?
Finding the compromises
Finding the best route in terms of distance or time is known as solving a Shortest Path Problem. In our case, we want to simultaneously take into account two conflicting objectives, so we have a Multi-Objective problem. Sophisticated techniques have been devised for such problems, but maybe we can limit ourselves to a simple one...
Let's suppose that, for each route segment, we know the time and the distance. We can then compute any combination of the two. Let x be a number between 0 and 1. For each route segment, let's denote t the time it takes, and d its distance. Instead of either the distance d or the time t, let's now give, as input to the shortest path algorithm, the value x.t + (1-x)d. For x=0, the result is the shortest path. For x=1, the result is the quickest path. For any value in between, the result is either the shortest path, or the quickest one, or a compromise between both.
To each value of x, we can thus associate a route. The unit first computes the routes for for x=0 and x=1. When the user asks for a compromise between two routes, those two routes define the interval x1..x2 that the unit must explore with a dichotomy. We start with (x1+x2)/2, and see which route this gives. If it's the same than for x1, we know that the compromize we want, if it exists, is between (x1+x2)/2 and x2. If it's the same than for x2, we know that we have to look between x1 and (x1+x2)/2. If it's neither, then we've just found a new route that we can display to the user. If the interval between the two values becomes too small, then we can stop the search and notify that it was not possible to find a compromise between the two routes.
Pretty simple, no?
And given the fact that recent computers can compute routes between any two points on a continent in around 1/10th of a second, it should be possible to answer in less than one second for each compromize sought... A GPS unit would probably need more time, but only the users willing to wait would have to...
In a few seconds, the user would get a list of possible compromise, and would be in the position to choose with much more informations...
Those tools generally offer control on whether you want the shortest or the quickest route, with or without highways, but that's pretty much all... Google Maps now offers one or two alternative routes, which is a good step, but I still think it's not enough.
Let's take an example... To go from Antibes to Méribel-Les-Allues (in the French Alps, approx 206 km from Antibes on straight line, but with the mountains in between), there are many possible routes. The shortest one is 385 km, for a duration of 6h49. The quickest one lasts 5h19, for 566 km. Most GPS units will be able to give you those two routes, but there are many others...
Wouldn't it be nice if, after giving those two routes, the unit would ask you if you want to look for a compromise between the two? This should give you a route that's shorter than 566 km, and quicker than 6h49, if there are some. It could e.g. give you the route that's 405 km for 5h57.
Those three routes would be displayed in a table, ordered by distance or by duration, to your choice. For each couple of consecutive routes, you could ask the unit to look for another compromise between the two selected routes, and this would display a new route in the table, with both the distance and the time in the interval defined by the two previously selected routes. Or, if there is no such route, this pair would not be selectable any more.
You would end up with a set of routes that represent different ways to compromise between the two inherently conflicting goals that are distance and duration... For my example trip, such a table would have entries like :
| 566 km | 5h19 |
| 530 km | 5h34 |
| 405 km | 5h57 |
| 385 km | 6h49 |
A route that is 512 km and lasts 6h03 would not be displayed: its distance is between the pair 530...405, but it's duration is larger than both: it's clearly not a good compromise in terms of time and distance...
Of course, the nec-plus-ultra would be to compute the cost of the trip, rather than the distance, taking distance, fuel consumption and tolls into account. One site I know that computes such costs is ViaMichelin. In this case, the quickest route costs 98€, and the economical route costs 42€. But am I ready to spend 1h30 more in my car, for a total of more than 7 hours? Not sure, if the kids are in the car... And that's when I'd really like to know if there is a route that's much less expensive than the quickest one, for only slightly more time...
All the data is there... Why don't we get those informations?
Finding the compromises
Finding the best route in terms of distance or time is known as solving a Shortest Path Problem. In our case, we want to simultaneously take into account two conflicting objectives, so we have a Multi-Objective problem. Sophisticated techniques have been devised for such problems, but maybe we can limit ourselves to a simple one...
Let's suppose that, for each route segment, we know the time and the distance. We can then compute any combination of the two. Let x be a number between 0 and 1. For each route segment, let's denote t the time it takes, and d its distance. Instead of either the distance d or the time t, let's now give, as input to the shortest path algorithm, the value x.t + (1-x)d. For x=0, the result is the shortest path. For x=1, the result is the quickest path. For any value in between, the result is either the shortest path, or the quickest one, or a compromise between both.
To each value of x, we can thus associate a route. The unit first computes the routes for for x=0 and x=1. When the user asks for a compromise between two routes, those two routes define the interval x1..x2 that the unit must explore with a dichotomy. We start with (x1+x2)/2, and see which route this gives. If it's the same than for x1, we know that the compromize we want, if it exists, is between (x1+x2)/2 and x2. If it's the same than for x2, we know that we have to look between x1 and (x1+x2)/2. If it's neither, then we've just found a new route that we can display to the user. If the interval between the two values becomes too small, then we can stop the search and notify that it was not possible to find a compromise between the two routes.
Pretty simple, no?
And given the fact that recent computers can compute routes between any two points on a continent in around 1/10th of a second, it should be possible to answer in less than one second for each compromize sought... A GPS unit would probably need more time, but only the users willing to wait would have to...
In a few seconds, the user would get a list of possible compromise, and would be in the position to choose with much more informations...
Subscribe to:
Posts (Atom)