Optimal Route (Visual)

The Drawing - Optimal Route (Visual) menu selection is enabled when the optional Business Tools extension has been installed and the focus is on a drawing window or on a drawing layer in a map window that contains lines and at least two points (between which a route can be selected). If you have not activated the Business Tools extension with a valid Business Tools serial number you will not be able to use the Optimal Route (Visual) command.

 

The Optimal Route (Visual) command provides an interactive dialog that allows choosing locations within a road network so that an optimal route between the locations may be found through the road network, taking into account the length of the roads and speed limits on the roads. In the main display pane the dialog shows a visual preview of the drawing in which locations are selected and routes are found. The dialog also lists the locations to be traversed and relevant options for the road network.

 

Locations to be visited may be selected from any point in the drawing meeting one of the following criteria:

 

·      The point is located exactly at the endpoint of a line.

·      The point is located exactly at one of the coordinates that defines a line.

·      The point is located closer to the line than the distance given in the drawing's location precision property (open the drawing, click on View - Properties and then the Precision […] button).

 

The drawing of road lines used must be a true road network that is a connected network. If there are small breaks between the road lines or if the ends of adjacent lines are not exactly coincident the drawing cannot be used as a road network.

 

To operate the dialog, open a drawing that has a road network of lines as well as points on the lines that are to be visited. Launch Optimal Route (Visual) and then in the preview pane click on the points to be visited to add each point as a location. As each point is clicked, it will be highlighted with red selection color and added to the list of locations to be visited in the lower left pane of the dialog. The start location will be shown with a larger red dot and the end location will be shown with a larger red diamond. Clicking a point that has been already selected will deselect it from the route.

 

By default, the system will find an optimal path through all of the locations from the first location to the last location regardless of the order in which locations between the first and the last appear in the list. To force the system to find an optimal path through the locations in the order in which they appear in the locations list, check the Use list order box before locating a route. To order the locations within the list, either click them in the preview pane in the desired order or change the order in the list. To re-order locations in the list use the up and down buttons in the locations list pane's toolbar.

 

If any points are selected in the drawing when the Optimal Route (Visual) dialog is launched they will be automatically added to the locations list for the route. A start location may then be designated by highlighting it in the locations list and clicking the Move to Top button and an end location may be designated by highlighting it in the locations list and then clicking the Move to Bottom button. If the dialog is re-run in a drawing and no points are selected, the dialog will launch with whatever was the last used list of locations. This makes it easy to re-run the dialog without having to re-click points into the locations list.

 

Locations will be listed in the locations list pane using their object ID numbers. If each point has a field called "Name" pressing the Show Name button will show the contents of the Name field for each location in the list. Using the Show Name button provides a much more user friendly list of locations than just using the object ID's.

 

Options in the lower right section of the dialog allow choosing which field specifies the length of the roads, the field specifying the speed of travel over each road and the units of measure. If desired, a report can be created using a variety of styles that provides driving directions for the route.

 

When all options have been selected, pressing the Locate Route button will identify the optimal route between the points to be visited. The route will be shown in red selection color. Pressing the Trace Route button will launch an animation that shows a small dot travelling over the route. When a route has been located, we can click the Save Report button to save a report of driving directions as a comments component in the project under whatever name we like.

 

When happy with the located route, press OK and the route will appear in the drawing as new line object that traverses the route. The new line object will be selected. To avoid creating duplicated objects in the drawing it is a good idea to Cut the new route line object and to Paste it into a new drawing.

 

To find an optimal route between locations:

 

1. Open a projected drawing that contains lines that form a connected road network and at least two points. Lines should have a field that can be used as the Speed field. If all roads are to be treated as having the same speed, simply create a "speed" field and fill it with 1 for all lines. Launch the Optimal Route (Visual) dialog.

2. In the preview pane, click on the point that is to be the starting point for the route. Next, click on each point that is to be visited in order. All points must be on the road network (that is, lying exactly at the end of one of the lines that make up the network). The clicked points will appear as locations to be visited in the locations list.

3. Choose [All Objects] for the Roads value.

4. Choose Length (I) to use as the Length value as well as the unit of measure. The unit of measure will depend on the projection in use and is normally meters (for meter-based projections like Orthographic) or feet (usually used only in US specific projections).

5. Choose the name of the field giving the speed value in the Speed combo as well as the units of measure (the default is meters per hour, which quite likely will be changed to miles per hour or kilometers per hour).

6. Press the Locate Route button to see a preview of the route in the preview pane. To animate the route, press the Trace Route button.

7. If a driving instructions report is required, choose the report options desired and click the Save report button. This will create a new comments component in the project that reports the driving instructions for the route.

8. If happy with the route, press OK. A new line object will be created in the main drawing and highlighted in red selection color. The line object is a single line that includes all coordinates traversed in the route. To save this line, Cut it, create a new drawing and then Paste it into the new drawing. It is usually useful to save the new line that represents the route so that it may be used together with the original drawing in a map, with the new route line formatted to make the route obvious (using a thicker line, etc).

9. If the Save report option was chosen, the system will generate a report and save it into a new comments component.

 

Controls

 

(Visual preview pane)

Displays the drawing in default gray color.

images\btn_zoom_tofit.gif

Zoom To Fit - Zoom so that the entire drawing fits within the preview pane.

images\btn_zoom_in.gif

Zoom In - Magnify the view as if seen from a closer distance.

images\btn_zoom_out.gif

Zoom Out - Reduce the view as if seen from farther away.

images\btn_zoom_box.gif

Zoom Box - Zoom to the size of the cursor box drawn with the mouse.

images\btn_center.gif

Center Point - Pan the view so that the spot clicked is centered.

images\btn_grabber.gif

Grabber - Interactive pan: click and drag with the grabber hand. The scene will be panned so that the initial point is moved to the spot where the drag is released.

images\btn_opt_route_trace_route.gif

Trace Route - Animate the route using a moving black dot to trace out the route.

(locations list pane)

A list of locations to be visited in order by the route. The starting location is at the top of the list and the end location is at the bottom of the list. Location are identified by their internal Manifold ID numbers and, if desired, by the contents of a Name field in the drawing's table if the Show Names button is pushed in.

images\btn_delete_thing.gif

Delete - Delete the highlighted location from the locations list pane. Clicking a location that has been already selected will also deselect it from the route and delete it from the locations list pane.

images\btn_goto.gif

Center - Center the highlighted location in the window.

images\btn_ping.gif

Ping - Locate the highlighted location by drawing converging circles to it. A great way to see what the highlighted location is.

images\btn_move_to_top.gif

Move to Top - Move the highlighted location to the top of the locations list pane.

images\btn_move_up.gif

Move Up - Move the highlighted location up one position in the locations list pane.

images\btn_move_down.gif

Move Down - Move the highlighted location down one position in the locations list pane.

images\btn_move_to_bottom.gif

Move to Bottom - Move the highlighted location to the bottom of the locations list pane.

images\btn_opt_route_show_names.gif

Show Names - In the locations list display names for locations taken from a Name column for the point in the drawing's table.

Use list order

If checked, Manifold will create an optimal route that goes through all of the locations in the locations list in order. If not checked (the default) Manifold will begin at the first location and end up at the last location but will find an optimal route that goes through all of the other locations at least once in the best possible way.

Locate Route

Enabled when two or more points have been selected in the preview pane and added to the locations list. Press to create an optimal route between the locations in the desired order. Note: until the OK button is pressed, the located route is only a preview.

Roads

Objects to be used for road lines. [All Objects] or [Selection] or a saved selection.

Length

Choose a field to use that gives the length of each line in the road network. Choose the unit of measure used for the value in the field. Use the intrinsic field Length (I) if there is no explicit length field. On large road networks for which optimal routes may be repeatedly calculated, it is more efficient to create a "length" field in the table and to copy into that length column the contents of the Length (I) intrinsic field using the transform toolbar for tables. This will avoid a recalculation of Length (I) on the fly for each run and will improve performance. Lines with a zero or negative value for Length will be ignored and will not be used in the route.

Speed

Choose a field to use that gives the speed of travel for each line in the road network. Choose the units of measure used for the length and time values in the field, for example, miles per hour or kilometers per hour. By default, if a column named Speed is available in the drawing's table it will be automatically loaded into the Speed box.

Split roads at intersections

If checked, split road lines into separate lines at intersections with other roads.

Save report

Enabled when a route has been located. Press to create a comments component in the project that contains a driving directions report.

Names

Field to use for road names and location names in the driving directions report. If [None] is selected, the report will be created using a format without road names or location names. When names are used, the report will note all points that are passed by the route even if they are not in the locations list. By default, if a column named Name is available in the drawing's table it will be automatically loaded into the Name box.

Turns

Choose the writing style used to report turns. none results in no turns reported. The other three styles allow choice of turns using either compass directions (for example, to turn North or South at a given intersection) or relative directions (for example, to turn right or left at a given intersection), of both relative and compass (the default).

OK

Accept the current route shown in the preview pane and add a line object to the drawing representing the route. If no route has been as yet created using the Locate Route button, pressing OK is the same as Cancel.

Cancel

Exit the dialog without making any changes to the drawing.

 

Example

 

Let's use the Optimal Route (Visual) dialog to find a route between locations.

 

images\eg_optimal_route_01.gif

 

We begin with a drawing of roads that has several points in the drawing as well. The points have been exactly located at the ends of lines using snap mode to snap to the ends of lines when creating points.

 

images\eg_optimal_route_02.gif

 

If we open the drawing's table we can see that each line has a Name and a Speed for the road represented by that line. The speed shows the actual speed used on that road which in some cases is substantially larger than the posted speed limit. We have the Length (I) intrinsic field turned on for display so that at a glance we can see the length of each road line.

 

images\eg_optimal_route_03.gif

 

If we select the points and view the drawing's table with the Selection Filter button pushed in so that only the selection is visible, we can see that the each point also has a Name value describing the point.

 

images\eg_optimal_route_04.gif

 

When we launch the Optimal Route (Visual) dialog it shows the drawing in a preview display in the upper pane. Points in the drawing are shown in bright green color by default. Any color desired may be specified in the Tools - Options - Color page.

 

images\eg_optimal_route_05.gif

 

We begin building a route by clicking the start location in the dialog's preview pane.

 

images\eg_optimal_route_06.gif

 

When we click the first location desired, it appears as a larger red diamond. The red color indicates it has been selected as part of the route and the larger diamond indicates it is the end location of the route (with only one location selected the initial location is also the end location).

 

images\eg_optimal_route_07.gif

 

In the locations list pane a new location is listed using the Manifold object ID number.

 

images\eg_optimal_route_08.gif

 

If we press in the Show Names mode button the locations list pane will report the Name for that location as well.

 

images\eg_optimal_route_09.gif

 

To add the next location we click on it in the preview pane.

 

images\eg_optimal_route_10.gif

 

When clicked it also appears as a larger red diamond. The larger diamond indicates it is the end location for the route. The initial location has changed to a larger red dot. The larger dot indicates it is the start location for the route.

 

images\eg_optimal_route_11.gif

 

In the locations list pane the new location appears below the first location.

 

images\eg_optimal_route_12.gif

 

We can add a third location by clicking on it in the preview pane.

 

images\eg_optimal_route_13.gif

 

The last location added appears as a larger red diamond to indicate it is the end location. Note that the previous end location (now the middle location of the route) appears as a smaller red dot, the red color indicating it has been selected as part of the route.

 

images\eg_optimal_route_14.gif

 

The third location added to the route also appears at the bottom of the locations list.

 

images\eg_optimal_route_15.gif

 

We can continue in this way to add two more locations to the route. The start location and the end location are shown as a larger dot and a larger diamond respectively and the intermediate locations appear as smaller red dots.

 

images\eg_optimal_route_16.gif

 

Each location also appears in the locations list.

 

images\eg_optimal_route_17.gif

 

Before finding routes we set up options. For the length of the road lines we will use the Length (I) intrinsic field. Since the drawing is in Orthographic projection and Use English measurement units is turned off in our installation, we use meters as the unit of length. The speeds are given in miles per hour using the Speed field in the table. For the report, we will use the absolute style of directions, using compass directions.

 

images\eg_optimal_route_18.gif

 

If we press the Locate Route button a route will appear in the preview pane. If we press the Trace Route button we can see how the route passes through the various locations from start location to end location. Some of the road segments are used more than once.

 

We can also press the Save report box so that a comments component giving driving directions will be generated.

 

 

images\eg_optimal_route_19.gif

 

If we press OK to accept the route, a new line object is generated in the drawing and a comments component containing driving instructions is added to the project. The new line, shown in red selection color, might be difficult to see in the drawing. We use CTRL-X or Edit - Cut to Cut the new line object out of the drawing. We then paste it into the project pane as a new drawing.

 

images\eg_optimal_route_20.gif

 

We can then show the new drawing in a map together with the original roads drawing as seen above. We've formatted the new drawing with thicker lines so that the red selected route line is more visible.

 

images\eg_optimal_route_21.gif

 

The driving directions (fragment shown above) enumerate each segment of the route in text form. The driving directions also show the total time, total distance and average speed over the route. The illustration above shows driving directions using the "absolute" Turns style.

 

images\eg_optimal_route_22.gif

 

The illustration above shows driving directions using the "relative" Turns style.

 

images\eg_optimal_route_23.gif

 

The third illustration above shows the default style, which uses both compass absolute and relative turns driving directions.

 

Which style is desired is a matter of taste. The absolute style uses compass directions and so is less ambiguous than the relative style in case of errors where the driver gets off a route and must rejoin it at some later point. However, the relative style is easier for most ordinary people to follow when driving. The both style is the default because it is completely unambiguous.

 

It is often the case that a road shown in a drawing is made up of multiple lines laid end to end. Manifold will collapse the driving directions for such end-to-end lines of identical name into a single line in the report. However, if the road changes name along the end-to-end sequence of lines the driving directions will note the newly named road as a new line in the report.

 

Units of Measure used by Intrinsic Fields

 

The units of measure used by the Length (I) and Area (I) intrinsic fields depend upon both the projection of the drawing and the Tools - Options setting for the Use English measurement units option as follows:

 

·      If the drawing is in Latitude / Longitude (that is, unprojected) Length (I) is reported in degrees and Area (I) is reported in square degrees.

·      If the drawing is projected and the Use English measurement units option is turned off, Length (I) is reported in meters and Area (I) is reported in square meters.

·      If the drawing is projected and the Use English measurement units option is turned on, Length (I) is reported in feet and Area (I) is reported in square feet.

 

Troubleshooting

 

Simple errors that may cause problems:

 

·      Points to be used as locations are either not on lines or are not within the drawing's precision factor distance of a line. Since the default precision factor for a projected drawing is 0.000001 meter (about one thousandth of a millimeter) it is highly unlikely that points placed in drawings using anything other than Snap functions will be adequately close to a line to be considered "on" the line.

·      The drawing of roads might not be a real network, that is, the ends of adjacent lines may not be coincident, there may be dangles or undershoots, breaks in the lines or other disconnects that prevent the lines shown from being used as a real network. Use Normalize Topology to "clean" the road network if need be, but keep in mind that poorly drawn road drawings might not be repairable even with the Normalize Topology tool.

·      The units of measure used in the dialog do not correspond with the units of measure used in the drawing or used in the Speed or Length fields.

·      The drawing is not projected and covers a sufficiently large area that errors arise. Always use a drawing that has been projected using a projection appropriate to the region of interest. For small regions (say, the size of a state or province in most countries), Orthographic is a fine meter-based projection that is a good bet.

 

Notes

 

Strictly speaking, a drawing used for optimal route computation need not be projected. However, since degrees of Latitude vary in size from the Equator to the Poles any task that requires accuracy should use only projected drawings.

 

When showing route lines in maps, using a line style with directional arrows is an easy way to show direction.

 

What do we do if our drawing is in Orthographic or other meter-based projection but we would like to have length units in miles? We can turn on the Use English measurement units option and then create an Active Column that converts the Length (I) intrinsic column from feet to the equivalent distance in miles and then use the Active Column in the Length box.

 

Tech Tip on Performance

 

The task of locating an optimal route through a given number of locations in optimal order is NP-full. That is, solving the task can be mathematically shown to require examination of all possible permutations of the source data to achieve an absolute optimum. Therefore, the task is not solvable for any number of locations above 10 to12 because the required computing time expands so enormously beyond that number of locations.

 

A computation strategy for locating optimal routes when there are more locations is to use an heuristic algorithm that gives good results even if the results are not a mathematically perfect optimal route. Manifold uses this strategy. When there are ten or fewer locations Manifold will compute an exact solution. With eleven or more locations, Manifold uses an heuristic algorithm to find the optimal route.

 

It sometimes comes as a surprise to network newbies that finding an optimal route through a number of locations is much harder if the system must find the best route through them when they are taken in any order than if locations are visited in a given list order. The reason is that finding an optimal route through many locations in a given order is a simple matter of repeatedly finding the shortest path between only two locations: from the first location to the second, from the second to the third and so on.

 

In contrast, finding a route that minimizes travel time through many locations in free order requires solving the entire problem before even the second location to visit can be determined.

 

See Also

 

Network User's Introduction

Optimal Route