The routing problems are important for logistic and transport sphere. Basically, the routing problems related to determining the optimal set of routes in the multigraph. The Chinese postman problem (CPP) is a special case of the routing problem, which has many potential applications. We propose to solve the MCPP (special NP-hard case of CPP, which defined on mixed multigraph) using the reduction of the original problem into General Travelling Salesman Problem (GTSP). The variants of CPP are pointed out. The mathematical formulations of some problems are presented. The algorithm for reduction the MCPP in multigraph into GTSP is shown. The experimental results of solving MCPP in multigraph through the reduction into GTSP are presented.
is a multiset of undirected edges (edges); : ∪ → is a cost function giving non-negative weights of arcs and edges between vertices.
In the routing problems, it is not necessary to visit all vertices, edges and arcs of the multigraph. Two subsets of edges and arcs ⊆ and ⊆ are defined. The arcs and edges from and must necessarily appear in the solution. Let the subset of vertices ⊆ consist of those vertices that must appear in the route.
The goal of all routing problems is to define a minimum cost set of routes, that traverses all the arcs and edges from the multisets and and includes all vertices of the set . 2
The VRP is a special case of the GRP with = ∅ and = ∅, i.e. the restrictions
on the edges and arcs, which must necessarily appear in the route, are absent. The
VRP is to determine the Hamiltonian cycle of minimum cost, which traverse all
vertices of the subset [
In the case, when = , the problem reduces to one of the most famous problem of combinatorial optimization – the classical Traveling Salesman Problem (TSP). 3 4
Another special case of the GRP is the Arc Routing Problem (ARP), it is to determine the minimum cost set of routes, that traverses all required edges and all required arcs of original multigraph. In the ARP, there are no restrictions on the presence of vertices in the route, i.e. = ∅. The CPP is the variant of ARP. In the original formulation, the CPP is the problem, where the postman should traverse through every street in the given area.
The CPP was originally studied by the Chinese mathematician Kwan Mei-Ko in 1960.
A problem is called the Chinese Postman Problem after him. Kwan Mei-Ko defined
the problem on undirected graph. Today, there are many various classifications of
CPP, including classifications based on the graph type, on the type of solution route
and other restrictions and additions [
In the modern world, the number of companies and industries that are interested in
building an optimal route of product delivery is growing. For example, the postman
delivering letters or leaflets wants to know the optimal route that traverses every street
in the given area, starting and ending at the office. Apart from the traditional
application of the CPP to solving the routing problems such as path planning of
snowplows or serving teams, there are a wide range of applications including robot
exploration, testing web site usability and finding broken links [
Below, the most popular variants of the CPP are presented. 4.1
The formulation of the Chinese Postman Problem in undirected graph (UCPP) is an original formulation of the CPP problem. The UCPP is a special case of ARP, where = ∅ and = . The UCPP belong to class of problems. 4.2
The Chinese Postman Problem in directed graph (DCPP) is the modification of UCPP, where every arc (directed edge) can be traversed in one direction. Another name of problem is the New York Street Sweeper Problem. The DCPP is a special case of ARP, where = and = ∅ . The DCPP belong to class of problems. 4.3
The Windy Chinese Postman Problem (WCCP) is the interesting generalization of classical CPP, which has many real uses. In WCPP the cost of traversing some edge depends on way of traversing. The WCPP is a special case of ARP, where = , = ∅ and at least for one edge the cost of traversing in direct way is differ from cost of traversing it in opposite way. The DCPP belong to class of -hard problems, which cannot be solved in polynomial time. 4.4
The Rural Chinese Postman Problem (RCPP) is a special case of ARP, where ⊆ , ⊆ . Another name of RCPP is the Selecting Chinese Postman Problem. In all above defined CPP problems, it is necessary to find a closed shortest route, that traverses all edges or arcs of the original multigraph at least once. In the real world, it is not always necessary to traverse all roads (edges or arcs). It is enough to traverse only a set of requires arcs and edges ( and ). The RCPP belong to class of hard problems, which cannot be solved in polynomial time. 4.5
The Mixed Chinese Postman Problem (MCPP) is a well-known version of the CPP, where multigraph contains both arcs and edges. The MCPP is a special case of ARP, where = and = . The MCPP belong to class of -hard problems.
There are other variants of the problem, such as Hierarchical Postman Problem (HCPP), k-Chinese Postman Problem (k-CPP), Chinese Postman Problem with Time Windows and others.
The MCPP is one of the most important problem of the ARP. The MCPP is a special case of ARP, for which = ≠ ∅ , = ≠ ∅ .
An edge { , } (an unordered pair of vertices) from the set is fixed. Let ( , ) is ordered pair of vertices (this mean, that should traverse { , } from vertex to vertex ). Note, that, ∀ , ∈ , ( , ) = , and ( , ) = , , it means that the cost of traversing the edge in any directions is the same.
The mathematical formulation of the MCPP problem is presented below. Let = {1, 2, … , | + | }, = {1, 2, … , || }. Indexation on the set of vertices is defined as : → , ∀ ∈ ∀ ∈ ≠ ⇒ ≠ , = ( ). On the multiset ∪ indexation is defined as : ∪ → , ∀ ∈ ( ∪ ) ∀ ∈ ( ∪ ) ≠ ⇒ ≠ , = ( ).
Route = ( , , , , … , , ) is the solution of the MCPP that satisfies to the following properties: = = ( ∪ /{ , , ,
, = 1,2, … , − 1 ; ); , … ,
} = ∅.
Let ( ) = ∑ ( ) is the cost of the MCPP route. Let ℳ be a set of solutions of the MCPP. It is necessary to find a route ∈ ℳ that satisfies the following property ∀ ∈ ℳ ( ) ≤ С() or ( ) = min∈ℳ ( С( )). • • • 6
The MCPP can be reduced to an equivalent ARP. When problem defined in directed
graph (DCPP), it can be reduced to the asymmetric TSP. When problem defined in
mixed or undirected graph, it can be reduced to GTSP [
Originally, the reduction algorithm was presented for the graph [
The process of reduction the MCPP to GTSP is to transform the original graph =< , ∪ , > into equivalent GTSP on complete graph =< , , >.
Each arc ∈ between to vertices ∈ , ∈ is represented as vertex ∈ , which must be used in the solution at least once, where is the serial number of parallel arc. Each edge ∈ between to ∈ , ∈ is represented as two vertices ∈ , ∈ , one of which must be used in the solution, another may not be used, where is a serial number of parallel edge, , are the serial numbers of parallel arcs between two vertices. After replacing the arcs and edges in vertices, the cost from each pair of vertex ∈ , ∈ in graph compute, as = + , The example of original multigraph is shown on Fig. 1. Each arc and edge has the cost of traverse. Each vertex has the serial number. After that, should replace each arc and edge as vertex. We received new graph 8 verteces. The can be calculates according to the formula | | = | | + 2| |. with
The cost from each pair of vertices is calculated by formulas (see Table 1, see Table 2). The vertices represent the edge are marked with a color in the table (different colors for different edges). In the work, the nearest neighbor heuristic algorithm (NN) and its modifications were applied to solve the GTSP problem. Nearest Neighbor heuristic belongs to the group of tour construction heuristics. In the tour construction methods, the route is built by adding new vertices at each step, according to some rules, while the already existing tour does not improve.
The algorithm starts building the route from the some starting vertex, and then selects the nearest vertex from another cluster to the start point and adds it to the route. Then, the nearest vertex, belonging to an unused cluster, should appear in the route, until all the clusters are used. After adding the vertices, we return to the starting point.
Time complexity of the algorithm in the best and worst case – (| | ) [
Time complexity of the algorithm in the best and worst case – (| | ) [
Another modification of NN is the heuristic, in which the shortest edge between two vertices from different clusters is selected as the starting edge for the route, and then NN is applied to the found edge (the end vertex of shortest edge is the starting vertex for NN).
Time complexity of the algorithm in the best and worst case – (|
| ) [
This method is a joint modification of the methods RNN and INN, which based on the
fact, that in the problem there are several edges with a minimum weight. It is
proposed to find the lengths of routes for all minimal edges [
Time complexity of the algorithm in the best case is (| | ) and in the worst case
is (|
8.5
| ) [
The algorithm starts building the route from some starting vertex, and, then, selects the nearest vertex to the start vertex and adds it to the route. Then the nearest vertex, belonging to an unused cluster, to the first vertex in the solution or the last is added, should appear in the route, until all the clusters are used. Thus, the route grows from both ends, the vertices can be added at the beginning of the route, and at the ending of the route. After adding all the vertices, we return to the starting point.
Time complexity of the algorithm in the best and worst case – (| | ) [
The main idea of the heuristic is that the vertices most remote from the others should
be paid special attention during the construction of the route to avoid their later
inclusion in the route with higher cost. To make such heuristic possible, the concept of
“loneliness” of the city was introduced. Together with the distance to the nearest
neighbor, the closeness of the nearest neighbors will also be the criteria for adding the
next vertex to the route. “Lonely” neighbors, i.e. most remote, will be preferable to
others. At the preprocessing stage, a new distance matrix is obtained, such that shorter
new distances from the vertex to the others are a weighted function of short old
distances to these vertices, and a higher loneliness of this city. Then NN is applied to the
new matrix [
Time complexity of the algorithm in the best and worst case – (| | ).
The heuristic is a modification of the NLN and DENLN heuristics, the weighted
distance function is also calculated here, considering the “loneliness” of the city, but the
DENLN algorithm is already applied in the next stages [
Time complexity of the algorithm in the best and worst case – (| | ) [
The algorithm for graph transformations and solving GTSP was written on C++ in MS Visual Studio 2015.
To test all algorithms, the two databases were used. For multigraph, the test data
sets were not found. However, graph is a special case of multigraph (without parallel
arcs and edges) and algorithm can be tested on graph data sets. In Bönisch’s database
the input data for 50, 100, 200 vertices in graph are presented [
The time performance and error rate of proposed approach were measured as follows: • Test data were loaded in console program. • The measurements for each input data set were carried out 10 times. The results of computational time were obtained as the average of 10 runs of the program: ⋯ .
= • Error rate of the TSP algorithms was evaluated according to the formula = С( )С ( ) , where С( ) is the resulting length of the route of the MCPP, С( ) is С( ) the optimum length of the route of the MCPP given in input data.
All test provides on Mac Book Pro 13 retina 2014 (Intel Core i5, 2.6 GHz). For all tests from test database the time and error rate were computed. On Fig. 4, Fig. 5, Fig. 6, Fig. 7, Fig. 8, Fig. 9, Fig. 10 the results are presented in the form of diagrams, where for each described above algorithm the average computational time and error rate are depicted.
Diagrams allow determine the Pareto-Optimal algorithms on two criteria: computational time and error rate. For all tested dimension this groups are similar and contain RNN and INN algorithms. The Pareto-Optimal algorithms is shown in Table 3. In Table 4, Table 5, Table 6, Table 7, Table 8, Table 9, Table 10, Table 11, Table 12, Table 13, Table 14, Table 15, Table 16, Table 17 the same results are provided and for both computational time and error rate the standard deviation were calculated. Small values of standard deviation for error rate show that error rate is grouped around the average value. It speaks about the reliability of the results. In tables () – is the minimum of , () – is the maximum of , () – is the average of , () – is the dispersion of , () – is the standard deviation of , in last to columns the lower and upper limits of the confidence interval are shown. The obtained results make it possible to conclude that the proposed approach is applicable to MCPP and gives good results in terms of computational time and error, taking into account the fact, that one of the simplest heuristics was used (the nearest neighbor heuristic). 11
The way of solving the MCPP in multigraph were proposed. Previously, the MCPP were solved only in a mixed graph.
The algorithm for transforming the MCPP in multigraph into the equivalent arc routing problem the GTSP were described, implemented in C++ and tested.
The approach to transforming the MCPP in mixed multigraph into equivalent ARP was evaluated on test data from the open databases. Testing has shown that this approach can be applied to the solve the MCPP in multigraph and should be further investigated with various algorithms for solving the GTSP. In our future work, it is possible to apply and investigated other existing algorithms for GTSP. Next, we are going to develop test data for the mixed multigraph. () √ () √ − () √ () √ 50 100 200 500 1000 1500 2000 3000 |V| () 14,50% 14,79% 15,27% 20,30% 20,63% 20,31% 20,24% 21,20% () 50 100 200 500 1000 1500 2000 3000 |V| 14,44% 14,76% 15,41% 20,36% 20,68% 20,17% 21,32% 22,33% ()