Function CPP(mode: smallint; factor: double; startnode,endnode: integer; filename,attributefile: string): integer;
The Chinese Postman Problem (CPP) deals with visiting all links in a street network such as is the case of many real-world tasks: Snow-ploughing, mail delivery, checking street lights etc. This function solves the CPP, by adding additional links to the network and thereby turning it into an Eulerian Graph.
Many different variations of CPP exist and mode is a constant, which describes the kind of problem to be solved:
0: All links will have to be visited once, no links has one-way restrictions and travel between link-ends is not limited to the links.
Example: Inspection of a network by helicopter
1: All links will have to be visited once, no links has one-way restrictions.
Example: Inspection of a street network (walking).
2: All two-way links will have to be travelled in both directions, one-way links only once.
Example: Snow-ploughing
3: All links will have to be travelled once, one-way streets in the correct direction.
Example: Inspection of a street network (by car).
So far mode 0, 1 and 2 has been implemented in RW Net Pro.
The whole idea behind solving the CPP, is to minimize the amount of additional travel, that is travelling on links, which has already been visited.
The factor parameter (between 0.1 and 1) defines how many possible combinations of additional travel is included in the optimization. For small datasets, just use 1. For larger datasets reduce to 0.25, to speed up the calculation time. If factor becomes too low, you will get error -54.
It is possible to define a startnode and endnode if you don't want a round-trip as result. 2 different and valid node numbers will force the resulting dataset to have un-even degree for the 2 specified nodes. Otherwise just specify 0 for both nodes.
It is possible to define which links has to be visited and which are optional, so they are only used if it reduces the overall length of the Eulerian Graph. To do this call function SetLinkResult with 0 or 1 for all links:
0: Optional
1: Has to be visited
If optional links are chosen, so that the graph is disconnected without these, you risk getting a disconnected output graph as a result, which is not an Eulerian Graph. No error is returned in that case.
Output from the function is a new dataset with filename as defined in the function call. The new dataset contains all the links of the original dataset plus some new ones, which may be duplicates of the old ones. The new dataset will contain a linkID, a reference to the original linkID from the input dataset, a logical field which describes, if it is a direct duplicate and one-way information. By using the linkID field, it is possible to link the new dataset with further attribute fields from the original dataset. This could be road class, street name etc.
It is optionally possible to store one-way attributes of the new dataset in a textfile, ready for being read by function AttributeCreate. Use parameter attributefile for this. If this parameter is an empty string, no attribute file is created. This is only really relevant for mode 2.
A progress event is available (CPPprogress) that also allows you to break off the processing before finalization, if the processing time seems to be too long. Street networks with 1000-2000 links is considered a large dataset for this procedure and may result in computing times up to ½ hour. Exact time depends on many factors such as network structure, mode and factor, so it isn't possible to give precise estimates, but mode 0 is the slowest, followed by mode 1 and then mode 2.
Format of the new dataset is as defined in property GISformat.
The return value of the function is the length of additional travel (mode 0) or cost of additional travel (other modes).
Once a new dataset has been generated, you should call function EulerRoute to generate the actual route.
Possible error codes: -10 -18 -30 -32 -40 -41 -50 -52 -53 -54
Versions: Pro
ActiveX / VCL / CLX component: RWcalc
This sample code assumes a SHP file called "link" and in the case of a mode 2 calculation, you also need a text file with the attributes in.
mode = 1
NWCreateSHP("link",false,"")
if mode=2 then
AttributeCreate("attribute.txt")
end if
NWload()
if mode=2 then
RWnetBase1.AttributeLoad(true);
end if
All links in the shp file should be included in the route
for i = 1 to rwnetbase1.linkmax()
SetLinkResult(i,1)
next i
startx = 1010
starty = 23009
stopx = 562
stopy = 23409
if different_nodes=true then
The route should start and end in these nodes
Coordinate2Node(startx,starty,startnode,dist)
Coordinate2Node(stopx,stopy,endnode,dist)
else
Any nodes will do
startnode = 0
endnode = 0
end if
Main processing
if mode=2 then
AddCost = CPP(mode,1,startnode,endnode,"cpp_out","attribute_cpp.txt")
else
AddCost = CPP(mode,1,startnode,endnode,"cpp_out","")
end if
NWUnLoad()
if AddCost>0 then
print "Additional cost: "+str$(result)
process output
NWCreateSHP("cpp_out",true,"")
NWload()
if mode=2 then
AttributeCreate("attribute_cpp.txt")
AttributeLoad(true)
end if
find new startnode based on same coordinates as before
Coordinate2Node(startx,starty,startnode,dist)
Create euler route - final result
length = EulerRoute(startnode)
if length-1<>LinkMax() then
print "Not a fully covering route"
end if
Generate a new table with route as result
RouteFileCreate("route",2)
RouteFileFieldAdd("linkID",field_integer,0,0)
RouteFileFieldAdd("Order",field_integer,0,0)
dist = 0
for i = 1 to length-1
t = RouteGetLink(i)
RouteFileRecordAdd(1,str$(t)+" "+str$(i))
if t>0 then
RouteFileRecordAddSection(t,0,1)
else
RouteFileRecordAddSection(-t,1,0)
end if
dist = dist+GetLinkDist(abs(t))
next
RouteFileClose()
print "Route : "+str$(dist)+" km"
NWUnLoad()
else
print "Error: "+str$(AddCost)
end if