Latest Contributions by MichaelRice

‎01-06-2015

Hi Hamish, Unfortunately, the problem you are trying to solve is a variant of the notoriously-difficult “Resource Constrained Shortest Path Problem”. There are algorithms for solving this problem, but they can require exponential time to run in the worst case. So, basically, you cannot hope for a solution which is always practically-fast for all inputs of this problem type. Furthermore, as Melinda pointed out, there is currently nothing in Network Analyst to support such constraints directly anyway. So, even if you wanted to use one of these algorithms, you would have to implement it yourself as a "custom solver". Therefore, unless you want some help/advice on implementing a custom solver in Network Analyst from scratch (which is no trivial task), you will have to consider alternative formulations or be willing to relax your constraints. For example, assuming you have two separate cost attributes (let's call them A and B), you could always define a third cost attribute (C) which represents some weighted combination of the two (e.g., C = x*A + y*B, for some x,y values in the range between 0.0 and 1.0). This would allow you some form of control over how you wish to weight the contribution of each individual attribute in the resulting paths if solving for the "hybrid" cost attribute C. Let us know which direction you might like to take this in, and we can discuss any further options with you then.

‎02-08-2013

Hi Dan, It sounds like you are working in the right direction towards using VRP to solve this problem, as the workaround does indeed require the usage of capacities and pick ups as binary constraints. The basic workflow is outlined below: Create a new VRP layer. Open the layer properties by right-clicking the layer in the table of contents and selecting 'Properties'. Go to the 'Analysis Settings' tab and set the 'Capacity Count' value to k (assuming you wish to represent k different facility types or categories). For all examples in the remaining discussion, I will assume k = 3. Add one or more locations as 'Depots' representing your starting and ending locations. If you require to start and end at the same location or don't care where the route ends, just add one depot. Add a new 'Route' item. Specify the route's starting and ending locations by setting the "StartDepotName" and "EndDepotName" fields based on the 'Depots' you added above. If you leave the end depot unspecified, it will end the route at the last visited facility/order. Assign your route a vector of binary capacities based on the number of facility types (k) that you wish to support. For example, assuming k = 3, give the "Capacities" field a value of "1 1 1". Each value represents a distinct dimension of constraint, representing a distinct facility type. Assuming the i-th facility type is represented by the i-th capacity value, this suggests that we cannot pick up more than one facility location for each of the three facility types. Add all of the appropriate facility locations as 'Orders', assigning each order a "PickupQuantities" field value as follows. If the facility belongs to the i-th facility type, then give it a pickup value of one in the i-th position, but zero in all other positions. For example, assuming k = 3 facility types, if the location is of type 1, then assign it the field value "1 0 0"; if it is type 2, assign it the field value "0 1 0"; etc. Solve the analysis That should pretty much do it. Please let me know if this works for your scenario(s) or if you run into any problems.

‎02-07-2013

Hi Dan, You are right about the problem being related to the traveling salesman problem (TSP). It is a slight variation of TSP which is formally known as the Generalized Traveling Salesman (Path) Problem (the word 'Path' is added to represent cases with fixed origin and destination). Please see a formal description here, including some related algorithms for solving these problem types. Unfortunately, such algorithms as referenced above are not currently part of Network Analyst. Therefore, unless you are willing to write your own version of these algorithms as a custom solver in Network Analyst, you will have to find a workaround using existing Network Analyst solvers. There is a way to do these types of solves using the Vehicle Routing Problem (VRP) solver in Network Analyst with some simple, but effective tricks. If you are interested, let me know, and I will post the workaround for using the VRP solver. Out of curiosity, what is the application of the problem you are trying to solve? What is the typical number of "types" (or "categories") that you are solving for, and what is the total number of facilities in such instances of your problems?

‎03-21-2012

Have you looked at the restriction attribute value being returned by those newly-added edges? You can do this using the Network Identify tool to click on those edges and see their attribute values. Check to make sure that those edges that are supposed to be restricted by your new restriction attribute are 'Prohibited' (indicated by a return value of true from the evaluator), and not 'Traversable' (indicated by a return value of false from the evaluator). Let me know what you find, and we can go from there.

‎03-19-2012

...when I try to add hills and put in restrictions for hills it doesn't work. I assume you mean that, after adding these restrictions, the routing solutions still traverse edges that are supposed to be restricted. Is this correct? If not, can you please clarify what you mean by "it doesn't work". If my assumption above is correct, then did you rebuild your network dataset after adding the new restriction(s)? For most restrictions, you must rebuild the network dataset after adding them for them to take effect (only certain restrictions, such as those with dynamic VBScript evaluators do not require a rebuild). If you have rebuilt your dataset, did you make sure to turn on the new restriction(s) in your analysis layer?

‎03-05-2012

Also, just for added clarification: I discuss the algorithm above as if it can only start/stop at nodes in the graph. This was done merely to simplify the discussion. However, in practice, the service area algorithm (and Dijkstra's algorithm, in general) can be made to start a search from anywhere along an edge and can also terminate partway along an edge (e.g., if the service area cutoff is reached midway along some edge).

‎03-02-2012

Dijkstra's algorithm works for both of the cases you point out. The generic version of Dijkstra's algorithm searches to find the shortest path from a source node to all other nodes in the graph. Therefore, it does actually "go out in every direction" as you suggest. However, if we are only looking for the shortest path to a specific node, the algorithm can simply terminate as soon as it finds the shortest path to that particular node (instead of continuing the search for all remaining nodes). For service area, the search goes out in all directions until it has processed all nodes within the specified cutoff, at which point it terminates (note that this termination criterion is easy to detect because Dijkstra's algorithm processes nodes in monotonically increasing order of their shortest path cost from the source). The nodes within the cutoff range and the edges taken to reach them define the service area (which can be output as lines or as polygons covering these lines).

‎03-01-2012

The "service area" problem is merely a single-source shortest path search with cutoffs (i.e., starting from each facility [the "source"], find the parts of the network that can be reached within travel cost <= x units, for some user-specified cutoff value of x). Therefore, it can be solved in polynomial time using straightforward variants of Dijkstra's algorithm (assuming non-negative edge weights), which, for graphs with n nodes and m edges, runs in O(mlogn) time if using binary heaps for the priority queue data structure or in O(m + nlogn) time if using Fibonacci heaps for the priority queue.

‎12-02-2011

This error suggests you have a licensing issue. Have you properly checked out the Network Analyst extension license before running your solves? Here is the general pattern for initialization and checking out the appropriate licenses: ::CoInitialize(NULL); { HRESULT hr; IArcGISVersionPtr ipVer(__uuidof(VersionManager)); VARIANT_BOOL succeeded; if (FAILED(hr = ipVer->LoadVersion(esriArcGISEngine, CComBSTR(L"10.0"), &succeeded))) return hr; IAoInitializePtr ipAoInitialize(CLSID_AoInitialize); esriLicenseStatus ls; ipAoInitialize->Initialize(esriLicenseProductCodeArcInfo, &ls); ipAoInitialize->CheckOutExtension(esriLicenseExtensionCodeNetwork, &ls); // Do something else...e.g., solve in Network Analyst ipAoInitialize->Shutdown(); ipAoInitialize = NULL; } // Uninitialize COM ::CoUninitialize();

‎11-28-2011

In case it was not clear from my previous post, please also make sure to completely rebuild your network dataset after integrating your features and changing the connectivity policy. The changes will only take effect after a rebuild.

‎11-28-2011

I looked at your dataset, and you do have connectivity issues. Change your connectivity policy to be "Any Vertex" (instead of "End Point"), and run the "Integrate" GP tool, and it should work for you (it worked for me on your dataset). Here is a good resource for you to read on understanding connectivity in the network dataset. I don't have any other features to integrate using GP tool. I am having only the raods shp.file with length as attribute. You don't need multiple feature classes to run Integrate. You can run it on just your single roads shapefile and it will integrate only the features within this shapefile.

‎11-23-2011

It sounds like this is likely a connectivity issue in your network dataset, causing the expected paths to be invalid. You should investigate your connectivity policy in the network dataset properties and also check to make sure that any features you expect to connect to each other actually share a common vertex at the intended connection point (it does not suffice for features merely to touch or cross; they must explicitly share a common vertex at their meeting point in order to establish connection). If this is indeed the case, you can force features that touch to share a common vertex by using the 'Integrate' GP tool.

‎11-23-2011

Yes, this can be done. This requires you to setup a turn restriction attribute in your network dataset. For your turn restriction attribute, you must also create a network attribute parameter, which allows you to adjust the vehicle length for evaluation. Then, you must properly setup the attribute evaluator for your turn restriction attribute to use this parameter for detecting restricted turn scenarios. Here are some resources with examples to help get you pointed in the right direction: Understanding the network attribute Types of evaluators Using parameters with network attributes: this is probably the most important thing for you to understand. The examples given here are applied to edges, but you can easily apply this same approach to your turns. If your logic is more complex than simply checking whether the parameter is below/above some threshold (e.g., you also need to determine if the turn is a left-turn, straight-turn, right-turn, or u-turn), then you might require to create a more complex VBScript evaluator to contain all of this logic (taking into account turn angles, etc. to detect these specific scenarios). Hopefully, this at least gives you a general sense of how it can be done. If you have more specific questions about this process after reviewing the above links, please don't hesitate to ask.

‎11-18-2011

(i changed it to NAD_1983_California_Teale_Albers, pretty uncertain about how they work ). Is that OK? It is up to you to decide which projection works best for your particular purposes, as there are certainly many to choose from, and each has their own unique properties. Here are some good resources to become more familiar with projections and their associated properties: What are map projections? About map projections What are projected coordinate systems? My inclination would be to suggest that you find a good equidistant projection (e.g., see here for an example), as their purpose is to preserve distances as best as possible, and this is what you are ultimately looking for in your algorithm. However, you must also keep in mind any other purposes you might require for your dataset as well. I hope this helps.

‎11-17-2011

If you just wish to get a straight-line Euclidean distance between two junctions in your street network, then using the Pythagorean theorem for your x/y coordinates is fine. However, keep in mind that the x/y coordinates you are using are based on the dataset's associated coordinate system. Therefore, any "distances" you get from using these coordinates will be based on the units of the coordinate system (which may explain why your values are different than what you are seeing from the measure tool). In order to obtain useful distance values using this approach without having to do more complex calculations, I would suggest that you make sure that your dataset is in a projected coordinate system (PCS). You can then figure out the distance-measure-of-choice per unit in your PCS, based on your desired distance measure (e.g., you can determine "meters per unit", "miles per unit", etc.). You can then translate the length of the hypotenuse into the appropriate distance measure using this value. However, you should also make sure that any length attribute you are using in the network dataset for your solves is also based on the same unit of measure, for consistency. Additionally, if your impedance attribute is time-based and not length-based, then you would have to further translate this distance into a valid time estimate instead (e.g., using a maximum expected speed limit). Does this make sense? Please let us know if you have any further questions.

Online Status	Offline
Date Last Visited	‎11-11-2020 02:23 AM

My Ideas

Latest Contributions by MichaelRice

Re: Set variable distance/time limits in Model Builder for Network Analysis

Re: Shortest Path taking in 1 facility each from a number of facility classes

Re: Shortest Path taking in 1 facility each from a number of facility classes

Re: routing with more than 1 barrier/restriction

Re: routing with more than 1 barrier/restriction

Re: Big O cost of computing drive shed/service area

Re: Big O cost of computing drive shed/service area

Re: Big O cost of computing drive shed/service area

Re: Migration from 9.3 to 10.0 getting solver failure.

Re: Problem in finding the Shortest Path

Re: Problem in finding the Shortest Path

Re: Problem in finding the Shortest Path

Re: Conditional restricted turns

Re: Simple optimal route application

Re: Simple optimal route application

Re: Set variable distance/time limits in Model Bui...

Re: Multiple Routes to one destination

Re: OD Cost Matrix: Using separate road line and a...

Re: Migration from 9.3 to 10.0 getting solver fail...