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

726
7
Jump to solution
02-04-2013 06:50 AM
DanielLewis1
New Contributor II
Hello,

For a given individual, I'm looking to create the least cost route that would take in 1 of each kind of facility in my dataset.

Let's assume I have 10 facilities of 5 types, with 2 facilities in each type. I would like to return a distance in which one of each of those 5 types of facilities is visited, in any order, finishing either: 1) back at the origin point, which is distinct from the facilities, 2) at a different destination point, that is again distinct from the facilities, or 3) At the final point of the facilities to be visited.

One of each of the types of facilities must be visited, so there would be 5 total visits, and in this case, 5 facilities would not be visited as visiting them does not fall on the shortest path.

Is this possible?

It strikes me that this is like a travelling salesman problem: rather than visit each city in a set of regions, the salesman must visit just 1 city per region in a set of regions containing many cities.

Thanks in advance,

Dan
Tags (2)
0 Kudos
1 Solution

Accepted Solutions
MichaelRice
New Contributor III
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:


  1. Create a new VRP layer.

  2. Open the layer properties by right-clicking the layer in the table of contents and selecting 'Properties'.

  3. 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.

  4. 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.

  5. Add a new 'Route' item.

  6. 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.

  7. 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.

  8. 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.

  9. 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 solution in original post

0 Kudos
7 Replies
RamB
by
Occasional Contributor III
Hallo,

if you are comfortable with model builder (Are you?), then I can suggest a  way out.

regards,
0 Kudos
DanielLewis1
New Contributor II
Yes, happy with model builder.

I've a python geoprocessing solution for the the problem, but it's brute force, and as you might expect it rapidly falls over as the number of facilities or number of classes of facilities rises!

Many Thanks!
0 Kudos
MichaelRice
New Contributor III
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?
0 Kudos
DanielLewis1
New Contributor II
Hi Michael,

Thanks for the link, it's interesting reading. When it came to applications within ArcGIS I suspected that it wouldn't necessarily be directly implementable.

Yes, I did think that VRP might be the way to do it, I've been experimenting with setting capacities and pick ups as binary constraints for a route between fixed "depots", but have yet to figure out the exact work around. Any advice you have would be greatly received.

The specific application I'm interested is related to the an individual's food environment and the notion of 'trip chaining', so I'm hoping to get a sense of the area of opportunity, or activity, for individuals who might wish to visit a set of particular types of food store (i.e. markets, butchers, grocers, discount retailers etc.) from their home location, or between paired locations like home-school, home-work. I'm exploring the idea that you could derive a measure of opportunity, or efficiency, by looking at the extent to which particular chains deviate from least cost routes, and how this might relate to behaviours.

In this sense we're talking a limited number of types, maybe 3 to 5, but within each type there is the potential for a largish number of facilities (up to 50 for a constrained local area, or particular route) depending on the local density of food stores.
0 Kudos
MichaelRice
New Contributor III
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:


  1. Create a new VRP layer.

  2. Open the layer properties by right-clicking the layer in the table of contents and selecting 'Properties'.

  3. 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.

  4. 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.

  5. Add a new 'Route' item.

  6. 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.

  7. 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.

  8. 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.

  9. 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.
0 Kudos
RamB
by
Occasional Contributor III
Hi

I saw your reply that you have a brute force script, i had something similar on mind. I would relate your problem to the classic probability problems of picking a color ball from a bag without replacement. Similarly my model was to add a different category of stops after each solve analysis and add new layer till you reach the final destination. (it would have been a combination of greedy algorithm + shortest path). Lets ignore the model builder, as you already have a script that works for you.

After your reply I was thinking about a VRP solution, which is already in discussion here. And as stated in the previous suggestion, you would have to use the capacities parameter to solve it. After a little bit of iterations I came up with the following combination, (did not h to time to develop a logical algorithm). Assuming you had 4 categories of stops to pick or drop packages, let us say they are 14, 23, 33, 44 (total = 114, yes there can be various such combinations). Now if you set the VRP solver to take 4 stops such that the total demand, pickup or drop off, adds up to 114, then there is just one possible combination which will consist of each stop only once. it is more or less a TSP problem. But this can lead to multiple solutions, that may are may not result in optimum paths. you can extend this to n categories by generating a unique combination like above.

You could also try Michaels suggestion above. thanks for the article, it is very interesting.

regards,
0 Kudos
DanielLewis1
New Contributor II
Thanks for the answers guys, I appreciate you taking the time to help me out.

Dan
0 Kudos