Distance calculation between

1451
14
03-20-2012 05:28 AM
Highlighted
New Contributor
Hello,

I will try to explain my problem by means of a the figurethat I attached in this post.

In the figure you can see the study area. Each small dot represents a biomass collection location. As you can see, the dots are divided in three different colors in order to create 3 subareas which each are visited by a truck to collect the biomass. The blue lines represents the existing road network in the study area. The large blue dot is the central biomass plant location, which is currently not relevant for the explanation of the problem.

For each of the 3 subareas, the biomass should be collected by a truck at each dot. This should be done in a way the distance to be traveled is as low as possible. Therefore, I would like to develop an algorithm which satisfies 2 important conditions:

1) After the first dot is visited, the next dot to be visited is the dot that is the closest to the first dot. The third dot, is the dot that is the clost to the second dot, and so on. In general, one could say that the next dot is the dot closest to the current dot, except dots that are already visited.
2) The sequence of the dots that are visited should afterwards be consultable for further analysis, just like the total distance and the distance that is traveled between each dot.

If possible, the distance over the existing road network should be calculated. However, since not all collection points are connected to a road network, Euclidian distance with also be satisfying.

I hope my explanation is clear !

Many thanks in advance...

Thomas Voets
Tags (2)
Reply
0 Kudos
14 Replies
Highlighted
by
Occasional Contributor
Hi Thomas,

I�??m not sure why you need this rule:
1) After the first dot is visited, the next dot to be visited is the dot that is the closest to the first dot. The third dot, is the dot that is the clost to the second dot, and so on. In general, one could say that the next dot is the dot closest to the current dot, except dots that are already visited.


The lowest cost route does not necessarily visit orders in the sequence defined in your rule, unless you have some business requirement to do so.

If your objective is just to minimize the total travel distance, your problem should be solved with VRP solver.  Here is the way to setup your problem:

  • Introduce 3 routes (also called trucks) each corresponding to one subarea, i.e. R1, R2 and R3.  Assuming that trucks will return to the biomass plant location when finishing visit all biomass collection locations, you can introduce plant location as a Depot and use it as route end depot (setting it in Route �??EndDepotName�?�). 

  • Load all biomass collection locations as Orders.  For each order, set its correpsonding �??RouteName�?�, i.e.  all biomass collection locations to be visited by R1 will have RouteName set to R1 (you may open order attribute table, select a bunch of orders, right click RouteName field to open �??Field Calculator�?� and do a batch set ).  Set all order assignment rule to �??Preserve Route.�?�

The solver will return the low cost solution visiting all collection locations. You can find the route cost summary and other time and cost information in route properties.

Please go through the help and tutorial doc for more details on VRP solver:
http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#/Exercise_7_Servicing_a_set_of_orders_w...
http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#/Vehicle_routing_problem_analysis/00470...

I hope this helps.

Thanks.

Anna
Reply
0 Kudos
Highlighted
New Contributor
Thanks a lot!

I will go through the documents and keep you updated if I can solve my problem with it.

Kind Regards,

Thomas Voets
Reply
0 Kudos
Highlighted
New Contributor
Here a short update of the status of my problem:

I have very little experience with network analyst. So, when I was opening the 'Make Vehicle Routing Problem Layer', I had to add my input analysis network. Therefore, I first created a network dataset. When I wanted to load my network dataset as the input analysis network for the Vehicle Routing Problem Layer I get following message: "Network has no cost attributes." This is quite strange because I added a cost attribute (see figures attached in this post). Can somebody help me? Which (cost) attributes should I further add to my network dataset, based on the description of my problem mentioned above?

Thanks in advance!

Thomas
Reply
0 Kudos
Highlighted
by
Occasional Contributor
Hi Thomas,

VRP solver needs a time cost attribute. The time cost attribute is used to define the traversal time along the elements of the network. This attribute is required, since the vehicle routing problem solver minimizes time.

Please search for "Time Attribute" in VRP help page for more details:
http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#/Vehicle_routing_problem_analysis/00470...

Here is more information for network attribute:
http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#/Understanding_the_network_attribute/00...

Thanks.

Anna
Reply
0 Kudos
Highlighted
New Contributor
Thanks a lot Anna,

I've gone trough all this but I still get the same remark: " network has no cost attributes". However I added the 'meter' cost attribute

I created it like this:

I added the attribute 'Meters' with usage type 'cost', unites 'meters' and data type 'double'.
Then I createdn evaluator. It consists of 2 rows with 2 different sources:

Source 1: 'Road Segments', direction 'from-to', element 'edge', type 'field', value 'distance' (which refers to the column of the attribute table of the road segments in which the distance in meters is given)
Source 2: 'Road sgements', direction 'to-from', element 'edge', type 'field', value 'distance' (which refers to the column of the attribute table of the road segments in which the distance in meters is given)

Do you have any idea why it is still not working despite the fact I added this cost attribute? Should I add more of them for my problem in which I just want to visits different locations in a sequence that minimizes total transport distance?

Thanks again!

Thomas
Reply
0 Kudos
Highlighted
by
Occasional Contributor
Hi Thomas,

You need a "Time" cost attribute which has the unit of "seconds, minuts or hours." You may either add a new travel time field in the Road Segement feature class and use it as the time attribute source value, or just use a field evaluator to calculate the time value based on the distance field value, i.e. time = distance/60.

[ATTACH=CONFIG]13112[/ATTACH]

In addition, I noticed that you open 'Make Vehicle Routing Problem Layer' to solve VRP. Unless you want to use the model builder or write your python script to call the solver, you don't need to use this tool. In ArcMap, you will need to click Network Analyst on the Network Analyst toolbar and click New Vehicle Routing Problem to create a VRP layer. Please read the tutorial for more details:

http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#/Exercise_7_Servicing_a_set_of_orders_w...

If it still doesn't work, could you please post your the network dataset here?

Thanks.

Anna
Reply
0 Kudos
Highlighted
New Contributor
Thanks a lot,

But still not working...

Here are my data. The zipfile contains 5 different layers:

'Gebied A', 'Gebied B', 'Gebied C': the point layers with the locations where the biomass is collected.
'Study Area': shapefile layer of the study area
'Overpelt Fabriek': the point layer which represents the location where the biomass is centrally processed. This is also the location where the transport vehicle start to collect the biomass.
'Wegsegmenten': this means 'road segments'. This is the road network in the study area. The last column 'lengte' represents the 'length' of the different road segments.

Hope these data are the data you are looking for?

Many thanks in advance!

Thomas Voets
Reply
0 Kudos
Highlighted
by
Occasional Contributor
Hi Thomas,

I looked at the data. You didn't add the time cost attribute. I added it for you which looks like this:
[ATTACH=CONFIG]13153[/ATTACH]

In your data, each area includes more than 600 orders. Since you want one truck dedicated to each area, I would suggest you to create a VRP layer for each area and solve the three areas independently. Otherwise, you have to introduce the specialty to match orders with the dedicated vehicles (see VRP help to understand specialties).

In addition, one truck cannot finish visiting all orders a day, so you have to introduce multiple routes with each representing a day to cover all orders.

Finally, in your street segment data, there are some disconnected areas where duplicated junctions were created and each  is connected to a subset of adjacent edges. I used the Integrate tool to merge them. Solving problem on a disconnected network will cause some unassigned orders.

Please find the network dataset (disconnected Dataset and fixed Dataset) and the corresponding test layers in the attachment and also watch this VRP vedio:

http://video.arcgis.com/watch/686/vehicle-routing-problem-example-appliance-delivery

Thanks.

Anna
Reply
0 Kudos
Highlighted
New Contributor
Thanks a lot,

I will deal with it this afternoon and keep you updates. Many thanks!

Thomas Voets
Reply
0 Kudos