POST

Hi Hamish, Unfortunately, the problem you are trying to solve is a variant of the notoriouslydifficult “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 practicallyfast 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.
... View more
01062015
01:03 PM

1

1

10

POST

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 rightclicking 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 ith facility type is represented by the ith 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 ith facility type, then give it a pickup value of one in the ith 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.
... View more
02082013
07:15 AM

0

0

4

POST

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?
... View more
02072013
08:20 AM

0

0

4

POST

Have you looked at the restriction attribute value being returned by those newlyadded 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.
... View more
03212012
08:18 AM

0

0

2

POST

...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?
... View more
03192012
02:20 PM

0

0

2

POST

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).
... View more
03052012
07:27 AM

0

0

3

POST

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).
... View more
03022012
06:54 AM

0

0

3

POST

The "service area" problem is merely a singlesource 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 userspecified cutoff value of x). Therefore, it can be solved in polynomial time using straightforward variants of Dijkstra's algorithm (assuming nonnegative 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.
... View more
03012012
11:59 AM

0

0

3

POST

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();
... View more
12022011
06:41 AM

1

0

4

POST

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.
... View more
11282011
08:01 AM

0

0

3

Online Status 
Offline

Date Last Visited 
11112020
02:23 AM
