1 Introduction

Arc routing problem (ARP) is one of the well-studied problems of the operations research literature. There are many real-life applications of ARP such as garbage collection, post-delivery, snow plow, salinization of snowy roads (Assad and Golden 1995; Campbell and Langevin 2000; Eglese and Li 1992). PP is a variant of ARP in which the postman is required to pass through each edge of the network starting and ending with a predefined point with minimum possible cost. PP is undirected if traversing edges in each direction is possible, it is directed if traversing is permitted in only one direction, and it is mixed if a subset of the edges are directed. Similarly, if service costs do not depend on the traversing direction, PP is symmetric, and it is asymmetric otherwise. Finally, there are postman problems in which more than one vehicle is used (Hertz 2005). We direct interested readers to the study by Dror (2012) in which ARP and its variations (including variants of the postman problem) are analyzed in detail.

In real-life applications, service costs appointed to the edges may vary from pass to pass due to the natural conditions, traffic density or the weather conditions. For instance, service costs are related to the amount of snow on the roads if the implied application is snow plow. We basically assume that the roads are closed due to excessive amount of snow and the snow plow vehicle is required to pass through each road at least once in order to open them for a minimum extent. However, all the snow cannot be cleaned with a single pass of the vehicle. Hence, the amount of snow decreases with each pass of the vehicle. Similarly, postman learns the roads better with each pass implying that passing times tend to reduce throughout the post-delivery process. These variations in the service costs may alter the resulting cost-minimizing routes as well. Thus, variability of service costs should be taken into account that we undertake in this study.

PP with symmetric service costs belongs to class P, and it is easily solvable (Assad and Golden 1995). There is no need to pass through any edge more than twice for symmetric networks. PP with symmetric costs is known as CPP in the literature. On the other hand, more realistic version of the PP having asymmetric costs (Ávila et al. 2016), which is known as windy postman problem (WPP), is shown to be NP-hard by Guan (1984). It is possible and usually expected that some edges of the network will be traversed more than twice if there are nodes with odd degrees for WPP instances.

In this study, we concentrate on the PP in which service costs of the edges vary depending on the number of passes. Hence, costs do not vary with the time as they are in time-dependent ARPs (Gendreau et al. 2015), but with the passing numbers. If the costs are symmetric, i.e., the problem is CPPVSC, then it still belongs to class P. We show that no edge can be traversed more than twice in the optimal solution of CPPVSC. On the other hand, WPPVSC is naturally a difficult problem. We propose two heuristic solution strategies and show their accuracies and efficiencies on four sets of test instances from the literature and on one set of test instances we generate that includes relatively denser networks.

The rest of the paper is organized as follows. In the next section, a brief review of the related literature is given. Next, we provide the mathematical formulation of the postman problem with variable service costs (PPVSC). Later on, we analyze CPPVSC in detail. Heuristic solution strategies for solution of WPPVSC are given in the solution approaches section. Moreover, we expose the success of the heuristics in numerical results section. Finally, we conclude the paper and point out future research directions.

2 Related studies

Time-dependent routing problems are treated under two main titles in the literature which are node routing (traveling salesman problem Malandraki and Dial 1996; Li et al. 2005; Schneider 2002; Cordeau et al. 2012; Taş et al. 2016, vehicle routing problem Malandraki and Daskin 1992; Ichoua et al. 2003; Donati et al. 2008; Guan 1984; Dussault et al. 2013; Koç et al. 2016; Setak et al. 2015) and arc routing. One observation is that there are time-dependent traveling salesman and vehicle routing studies with deterministic or stochastic service costs, but arc routing studies assume only deterministic service costs. One reason behind this phenomenon may be the fact that time-dependent node routing problems have been studied more than the time-dependent arc routing problems. We direct the interested readers to the paper by Gendreau et al. (2015) that represents the state-of-the-art about the time-dependent routing problems. We provide a brief review of the time-dependent arc routing studies in the following.

Tagmouti et al. (2007) concentrates on the capacitated time-dependent arc routing problem. The authors transform the problem into the node routing problem and propose a solution method based on column generation. Tagmouti et al. (2010) also considers the same problem and introduces a variable neighborhood descent heuristic. Tagmouti et al. (2011) follows the same line of research, but the arc routing problem it takes assumes dynamic arc capacities. The authors adapt the variable neighborhood descent heuristic of Tagmouti et al. (2010) as the solution strategy. Besides, Black et al. (2013) utilizes variable neighborhood search and tabu search methods for prize collecting time-dependent arc routing problem. A variant of WPP is studied by Dussault et al. (2013) in which a snow plow application is considered. The authors assume that the service costs of the roads decrease if the snow plow vehicle has already passed. They offer a heuristic named cycle permutation local search as the solution method. Hence, subject of Dussault et al. (2013) is similar to our analysis, but it is assumed in Dussault et al. (2013) that service costs decrease only after the first pass while we generalize the idea and assume that each pass affects the service costs. Moreover, the authors assume a mixed network but allow passing through reverse directions by closing the roads during snow plow. These special conditions do not apply for our case. Another study is due to Sun et al. (2015) in which a new integer program for time-dependent Chinese postman problem is proposed. The authors generate valid constraints and employ a cutting plane algorithm as the solution method. Finally, Vincent and Lin (2015) offers an iterated greedy heuristic for the solution of prize collecting time-dependent arc routing problem. The authors illustrate effectiveness of their method on several test sets.

3 Mathematical model

Before giving the mathematical formulation of PPVSC, we, respectively, describe the sets, parameters and variables that are used in the formulation. First of all, we define \({\mathcal {G}}=({\mathcal {V}},{\mathcal {E}})\) as the graph of the nodes denoted by \({\mathcal {V}}\) and the edges represented by \({\mathcal {E}}\). We use i and j indexes for the nodes and (i, j) for the edges. Set of times of the passes on the edges is given by \({\mathcal {T}}\), and we let k stand for the order of the pass, while t denotes the total number of passes. Service cost of edge (i, j) \(k^{\text {th}}\) time is given by \(c_{ij}^k\) and we assume that \(c_{ij}^{k_1}\ge c_{ij}^{k_2}\) if \(k_1\le k_2\). That is, service costs do not become more costly as the number of the passes increases which is intuitive since the postman is expected to learn the roads better as the number of passes increases in the post-delivery application. Similarly, if each pass on the edges represents the shoveling of the accumulated snow on a specific edge, then the cost of the shoveling should not increase by the number of the passes on that edge as the snow becomes less and less at each pass of the snow plow vehicle. Moreover, we also assume that \(c_{ij}^k>0\) for any k, i.e., free rides are not allowed. It should be noted that by passing the edge (i, j), we mean to traverse it by going from i to j. The service cost of an edge is defined as the traversing cost of the edge which includes the cost of the shoveling operation taken place on the edge and the cost of the travel on the edge itself. We interchangeably use service cost and the traversing cost for the same concept throughout the study. We also refer to the service cost of the edges as the length of the edges especially in the solution approaches section in which we embrace the problem in the graph theory context. If service costs of the edges (i, j) and (j, i) at each pass are identical, i.e., \(c_{ij}^k=c_{ji}^k\)\((i,j) \in {\mathcal {E}}, k \in {\mathcal {T}}\), then the costs possess a symmetric structure, and the problem becomes CPPVSC. On the other hand, if \(c_{ij}^k\ne c_{ji}^k\) for any \((i,j) \in {\mathcal {E}}, k \in {\mathcal {T}}\), then the problem at hand is WPPVSC. It should be noted that the implied asymmetry among the costs can be easily justified. For instance, the slopes of the roads may cause traversing on a specific direction more difficult than the opposite direction, or as the name of the problem suggests, the wind may have more effect on specific directions. Another parameter that is used in the formulation is \(d_{ij}^t\) which denotes the total cost of traversing the edge (i, j) t times. Mathematically, \(d_{ij}^t=\sum \nolimits _{k=1}^tc_{ij}^k\). Note that \(d_{ij}^{t_1}\le d_{ij}^{t_2}\) for \(t_1\le t_2\). It is easy to see that if the service costs (\(c_{ij}^k\)) are symmetric, then the total service costs (\(d_{ij}^t\)) are also symmetric, and if the service costs are asymmetric, then the total service costs are most likely asymmetric as well. Finally, we use two set of variables named \(x_{ij}\) and \(y_{ij}^t\). \(x_{ij}\) stands for the number of passes on edge (i, j) and \(y_{ij}^t\) indicates whether or not the number of passes on edge (i, j) is exactly t, i.e., \(y_{ij}^t=1\) if \(x_{ij}=t\) and \(y_{ij}^t=0\), otherwise. A summary of the set, parameter and variable definitions is provided in Table 1 for the sake of convenience.

Table 1 Sets, parameters and decision variables
Full size table

Below, we give the mathematical formulation of the postman problem with variable service costs.

$$\begin{aligned}&\text {PPVSC:} \nonumber \\&\min \sum \limits _{(i,j) \in \mathcal {E}}\sum \limits _{t \in \mathcal {T}} d_{ij}^ty_{ij}^t \end{aligned}$$
(1)
$$\begin{aligned}&\text{ s.t. } \nonumber \\&\sum \limits _{(i,j) \in \mathcal {E}}x_{ij}=\sum \limits _{(j,i) \in \mathcal {E}}x_{ji}&i \in \mathcal {V} \end{aligned}$$
(2)
$$\begin{aligned}&x_{ij}+x_{ji}\ge 1&(i,j) \in \mathcal {E} \end{aligned}$$
(3)
$$\begin{aligned}&ty_{ij}^t\le x_{ij}&(i,j) \in \mathcal {E},t \in \mathcal {T} \end{aligned}$$
(4)
$$\begin{aligned}&x_{ij}\le \sum \limits _{t \in \mathcal {T}}ty_{ij}^t&(i,j) \in \mathcal {E} \end{aligned}$$
(5)
$$\begin{aligned}&y_{ij}^t \in \{0,1\}&(i,j) \in \mathcal {E},t \in \mathcal {T} \end{aligned}$$
(6)
$$\begin{aligned}&x_{ij}\ge 0 \text { and integer}&(i,j) \in \mathcal {E} \end{aligned}$$
(7)

We minimize the total service cost in the objective function (1). In the first set of constraints (2), we ensure that total arrivals to and departures from each node are equal, implying that the postman, or the snow plow vehicle, should leave each node as many as the number of times she visits the node. Constraint (3) guarantees that each edge of the network is visited at least once. It should be noted that although it is possible to traverse the edges in each direction, it is not required. It can be, and is expected to be, the case in the solution that some of the edges are traversed through only one direction. Constraint (4) makes sure that if \(y_{ij}^t\) is 1, then \(x_{ij}\) is at least t. On the contrary, if \(x_{ij}=t\), then the variable \(y_{ij}^t\) should be equal to 1 which is achieved by constraint (5). It can be observed that since the objective is in the direction of minimization, among the variables existing on the right hand side of constraint (5), only the related \(y_{ij}^t\) variable is set to 1 in the optimal solution. For instance, suppose that \(x_{ij}=6\) for a specific edge (i, j). Then, the right hand side of constraint (5) written for edge (i, j) should be at least 6. First, setting the right hand side of the constraint to a value that is larger than 6 increases the objective function unnecessarily. Hence, the right hand side will be exactly 6 in the optimal solution. This can be achieved by simply setting \(y_{ij}^6\) to 1 which increases the objective function value by \(d_{ij}^6\). Observe that any other solution leads to a larger objective function value. For example, if \(y_{ij}^4\) and \(y_{ij}^2\) are both set to 1 to achieve a total of 6 at the right hand side of the constraint, then their combined effect on the objective function value will be \(d_{ij}^4+d_{ij}^2\) which is greater than or equal to \(d_{ij}^6\) since \(d_{ij}^6=\sum \nolimits _{k=1}^6c_{ij}^k\) while \(d_{ij}^4+d_{ij}^2=\sum \nolimits _{k=1}^4c_{ij}^k+\sum \nolimits _{k=1}^2c_{ij}^k\) and \(c_{ij}^k\) values are nonincreasing in k. Therefore, constraint (5) ensure that only the \(y_{ij}^t\) variable associated with the value of \(x_{ij}\) is equal to 1. As a consequence, if \(y_{ij}^t\) variable takes value 1, then \(x_{ij}\) is equated to t by collaborative efforts of constraints (4) and (5). This implies that it is possible to take \(x_{ij}\) variables as continuous in the model knowing that its value will always be integral. We exploit this phenomenon to significantly increase the solution efficiency as stated in the computational results section. Finally, constraint (6) and constraint (7) are the usual binary, nonnegativity and integrality restrictions.

4 Analysis of CPPVSC

It is a well-known fact that CPP is polynomially solvable. A polynomial time algorithm can be described as follows; if all the nodes have even degrees, then there is an Euler tour that passes through each edge only once and it is obviously optimal. If there are vertices with odd degrees, then their numbers should be even. A new complete graph consisting only the vertices with odd degrees can be formed in which the edge lengths correspond to the lengths of the shortest paths obtained on the original network. In other words, the length between nodes i and j on the new graph is equal to the length of the shortest path between nodes i and j on the original network. Then, a minimum weight perfect matching problem is solved in polynomial time in the newly formed complete graph. Edges of the shortest paths corresponding to the links selected in the perfect matching are then added to the original network to form a new network in which all the vertices have even degrees, and length of the Euler tour on that new network gives the minimum cost.

The algorithm mentioned above that solves classical CPP in polynomial time also solves CPPVSC as well. Note that it is not possible to equate arrivals to and departures from odd degree nodes by traversing the neighboring edges only once. This implies that there must be paths between the odd degree nodes including the edges traversed at least two times. Such paths with minimum possible travel costs can be found by constructing a complete network with odd degree nodes and searching for the minimum weight perfect matching on that network as described above. The only difference is that shortest paths between nodes should be calculated using \(c_{ij}^2\) values for each odd degree node pair. Moreover, although the passing costs tend to decrease by the number of passes, no edge is traversed more than twice. This is why we need only the \(c_{ij}^2\) values to calculate shortest path lengths. We express this observation in a more formal way in the proposition given below.

Proposition 1

If the costs are symmetric, i.e., \(c_{ij}^k=c_{ji}^k\) for \((i,j) \in {\mathcal {E}}, k \in {\mathcal {T}}\), then \(x_{ij}\le 2\) for \((i,j) \in {\mathcal {E}}\) in the optimal solution.

Proof

First of all, if all the vertices have even degrees than the Euler tour that passes each edge only once is optimal meaning that there is no need to pass any edge more than once even in the case that second time passes have very low costs. In that case,

$$\begin{aligned} x_{ij}={\left\{ \begin{array}{ll} 1 &{} \text {if } (i,j) \text { is traversed through } i \text { to } j, \\ 0 &{} \text {if } (i,j) \text { is traversed through } j \text { to } i. \end{array}\right. } \end{aligned}$$

Here, \(x_{ij}\le 2\) for \((i,j) \in {\mathcal {E}}\) trivially holds. Now, consider the case where some of the vertices have odd degrees. Then, a complete graph including the odd degree vertices can be formed. By the way of contradiction, assume that the minimum cost perfect matching, say matching 1, obtained on the complete graph of the odd degree vertices includes two edges (a, b) and (c, d) such that the shortest paths from a to b and from c to d on the original network share an edge (e, f) of the original network as depicted in Fig. 1.

Fig. 1
figure 1

Illustration of shortest paths between (a, b) and (c, d) pairs

Full size image

Note that the Euler tour obtained on the network after adding the edges of the shortest paths corresponding to the selected links of the minimum cost perfect matching to the original network includes the edge (e, f) at least three times, i.e., \(x_{ef}\ge 3\). For convenience, we let the edge lengths of the complete graph (which correspond to the lengths of the shortest paths on the original network) to be denoted by \(\ell \), for instance the edge length between a and b is given by \(\ell _{ab}\). Total cost of the matching 1 is equal to the sum of the \(\ell _{ab}\), \(\ell _{cd}\) and the total remaining cost (TRC). Since we do not know the exact number and order of passes on edge (e, f), let the passing costs used for calculation of \(\ell _{ab}\) and \(\ell _{cd}\) be denoted by \(c_{ef}^{ab}\) and \(c_{ef}^{cd}\), respectively. Obviously, \(\ell _{ab}=\ell _{ae}+c_{ef}^{ab}+\ell _{fb}\) and \(\ell _{cd}=\ell _{ce}+c_{ef}^{cd}+\ell _{fd}\). Then, total cost of the matching 1 is equal to TRC+\(\ell _{ae}+\ell _{fb}+\ell _{ce}+\ell _{fd}+c_{ef}^{ab}+c_{ef}^{cd}\). Now, suppose that we form another matching, say matching 2, in which instead of edges (a, b) and (c, d), we select (a, c) and (b, d) and the remaining edges of the matching are the same with the ones of the matching 1. Edges (a, c) and (b, d) exist since the newly formed network is complete. Observe that matching 2 is also perfect and its total cost is equal to TRC+\(\ell _{ac}+\ell _{bd}\). We know that there is a path between a and c which goes through node e having the length of \(\ell _{ae}+\ell _{ce}\). Thus, \(\ell _{ac}\le \ell _{ae}+\ell _{ce}\) should hold. Similarly, \(\ell _{bd}\le \ell _{fb}+\ell _{fd}\) also holds. Nevertheless, this implies that TRC+\(\ell _{ac}+\ell _{bd}\le \) TRC+\(\ell _{ae}+\ell _{ce}+\ell _{fb}+\ell _{fd}<\) TRC+\(\ell _{ae}+\ell _{fb}+\ell _{ce}+\ell _{fd}+c_{ef}^{ab}+c_{ef}^{cd}\) which is a contradiction implying that the minimum cost perfect matching cannot include two edges such that corresponding shortest paths share an edge of the original network. Hence, no edge of the original network can be traversed more than twice in the optimal solution. \(\square \)

As Proposition 1 suggests, CPPVSC is as much difficult as CPP which belongs to class P. Therefore, we provide no numerical results for CPPVSC.

5 Solution approaches

In this section, we provide two heuristic strategies for the solution of WPPVSC which are, respectively, called as pass iteration heuristic (PIH) and Lagrangian heuristic (LH).

5.1 Pass iteration heuristic

Observe that if \(c_{ij}^k\) values do not vary with k, i.e., service costs do not change from pass to pass, then WPPVSC reduces to WPP which is known to be NP-hard. Hence, WPPVSC is also NP-hard implying that we must resort to heuristic procedures for the solution of large instances of WPPVSC. It is known that traversing an edge more than twice is possible in WPP and it is even encouraged in WPPVSC since cost of the passing tends to reduce with each pass. Moreover, as the costs are asymmetric, known combinatorial algorithms like the blossom algorithm which finds the minimum cost perfect matching cannot be used. An examination of the literature reveals that metaheuristics have been widely used for solving WPP instances. Another idea for the solution is to utilize the power of the today’s modern solvers which have gained significant strength in the last decade. In addition, the processor and the computer memories have significantly developed. Therefore, we propose a heuristic strategy which exploits the state-of-the-art solver Gurobi (2017). Solving big-sized instances of WPPVSC is difficult mostly due to the large number of binary variables included in the model. This observation calls to mind to decrease the number of binary decision variables by fixing a subset of them a priori in the model. As a result, a good quality solution can be found relatively easily since the number of binary variables involved would be much lower. Moreover, the obtained solution can be used as a starting point in a further attempt to find a better solution.

In order to decrease the number of binary variables, we concentrate on the cardinality of the set of number of the passes, \(\left| {\mathcal {T}}\right| \). We try to compute the lowest possible number of passes that leads to the minimum cost by the following pass iteration idea. Suppose a new parameter \(\phi \) stands for the number of maximum allowable number of passes and let the initial value of \(\phi \) be 2 at the beginning of the algorithm implying that traversing any edge more than twice is not permitted. Hence, values of the \(y_{ij}^t\) variables for \((i,j) \in {\mathcal {E}},t \in {\mathcal {T}}, t\ge 3\) are set to 0. Similarly, upper bounds of the \(x_{ij}\) variables are set to \(\phi \). After fixation of the variables, we have a much smaller model which is called as the restricted model in the sequel. We run the solver Gurobi to solve the restricted model for a predetermined amount of computation time, and the solver is expected to find good quality solutions since there are relatively small number of binary variables in the restricted model, especially for small \(\phi \) values. In addition, since we do not aim to prove the optimality but to obtain good feasible solutions of the restricted model at each iteration, we increase the rate of the time that Gurobi uses to find primal feasible solutions. The solution obtained for the restricted model is also feasible for the original model as well. After finding the solution obtained for a specific value of \(\phi \), its value is increased by 1, i.e., \(\phi \leftarrow \phi +1\) and the solver is rerun for the new value of \(\phi \). Namely, we increase the upper bound of the \(x_{ij}\) variables by 1 and \(y_{ij}^{\phi +1}\) variables are set free (their upper bounds are updated from 0 to 1) to form the newly restricted model. We expect an improvement in the objective function value since a slightly more flexible optimization framework is provided by letting the solver determine the values of more decision variables. However, at the same time, the solution of the restricted model becomes harder as the number of binary variables of the model increases with \(\phi \). Fortunately, we are able to accelerate the solution procedure of the new restricted model by providing the previously found solution as a starting point. Suppose the values of the decision variables coming from the previous restricted model are represented by \(\bar{x}_{ij}\) and \(\bar{y}_{ij}^t\) for \((i,j) \in {\mathcal {E}},t \in {\mathcal {T}}\). We start \(x_{ij}\) and \(y_{ij}^t\) variables of the new restricted model from \(\bar{x}_{ij}\) and \(\bar{y}_{ij}^t\) values using the START attribute of the Gurobi solver. Namely, the comment line \(x_{i, j}\).Set(GRB. DoubleAttr.Start, \(\bar{x}_{i, j}\)) and \(y_{i, j}^t\).Set(GRB.DoubleAttr.Start, \(\bar{y}_{i, j}^t\)) are written for \((i,j) \in {\mathcal {E}},t \in {\mathcal {T}}\) before running Gurobi for the solution of the new restricted model. Hence, the new restricted model will start from a good feasible solution coming from the previous restricted model, and hence, the solution procedure is likely to be more effective. The process continues until the improvement in the objective value after a unit increase in the value of \(\phi \) becomes less than or equal to a final precision parameter \(\epsilon \), or the total solution time exceeds the predetermined time limit. Steps of the algorithm are formally summarized in Algorithm 1. Note that \(O^{(\phi )}\) given in Algorithm 1 represents the objective function value of the solution found for a given value of \(\phi \). We name the algorithm as pass iteration heuristic.

figure a

5.2 Lagrangian heuristic

Another approach suggests relaxing the coupling constraints in an attempt to ease the solution of the WPPVSC. Observe that constraints (4) and (5) include both continuous variables \(x_{ij}\) and binary variables \(y_{ij}\). We relax constraints (4) and (5) in order to decompose the model to easy to solve subproblems one of which only contains continuous variables while the other solely depends on the binary variables. We carry the relaxed constraints to the objective function by multiplying with nonnegative Lagrange multipliers \(\alpha \) and \(\beta \). We let WPPVSC\((\alpha , \beta )\) denote the Lagrangian subproblem

$$\begin{aligned}&\text {WPPVSC}(\alpha , \beta ) \text {:}&\nonumber \\&LB(\alpha , \beta )=\min \sum \limits _{(i,j) \in {\mathcal {E}}}\sum \limits _{t \in {\mathcal {T}}} d_{ij}^ty_{ij}^t \nonumber \\&\quad - \sum \limits _{(i,j) \in {\mathcal {E}}}\sum \limits _{t \in {\mathcal {T}}}\alpha _{ijt} \left( x_{ij}-ty_{ij}^t\right) -\sum \limits _{(i,j) \in {\mathcal {E}}} \beta _{ij}\left( \sum \limits _{t \in {\mathcal {T}}}ty_{ij}^t-x_{ij}\right) \nonumber \\&\text{ s.t. } \ \ (2),(3), (6), (7) \end{aligned}$$
(8)

where \(LB(\alpha , \beta )\) denotes the optimal objective function value of the Lagrangian subproblem for a given Lagrange multiplier set \(\left\{ \alpha ,\beta \right\} \).

5.2.1 Subproblems

Lagrangian subproblem WPPVSC\((\alpha , \beta )\) can be decomposed further into two subproblems. The terms of the objective function including only the continuous variables x together with the constraints involving only these variables form a linear programming (LP) subproblem which is easy to solve. The rest of the objective function along with the remaining constraints involving only binary variables y constitutes a binary integer programming subproblem. We call the former subproblem WPPVSC\(_1(\alpha , \beta )\) and the latter subproblem WPPVSC\(_2(\alpha , \beta )\), which are given below. We let \(Z_1\) and \(Z_2\) denote the optimal objective function values of the subproblems, respectively.

$$\begin{aligned}&\text {WPPVSC}_1(\alpha , \beta ) \text {:}&\nonumber \\&\quad Z_1=\min \sum \limits _{(i,j) \in {\mathcal {E}}}\gamma _{ij}x_{ij} \end{aligned}$$
(9)
$$\begin{aligned}&\quad \text{ s.t. } \ \ (2),(3), \nonumber \\&\quad x_{ij}\ge 0&(i,j) \in {\mathcal {E}} \end{aligned}$$
(10)

where \(\gamma _{ij}=\beta _{ij}-\sum \limits _{t \in {\mathcal {T}}}\alpha _{ijt}\) and

$$\begin{aligned}&\text {WPPVSC}_2(\alpha , \beta ) \text {:}&\nonumber \\&\quad Z_2=\min \sum \limits _{(i,j) \in {\mathcal {E}}}\sum \limits _{t \in {\mathcal {T}}}\theta _{ijt}y_{ij}^t \nonumber \\&\quad \text{ s.t. } \ \ (6) \end{aligned}$$
(11)

where \(\theta _{ijt}=d_{ij}^t-t\left( \beta _{ij}-\alpha _{ijt}\right) \).

Note that WPPVSC\(_1(\alpha , \beta )\) is an LP and hence easily solvable. Besides, WPPVSC\(_2(\alpha , \beta )\) can also be solved to optimality easily by inspection as follows. Since \(y_{ij}^t\) is binary, it can be set to zero or one. If \(\theta _{ijt}\ge 0\), then \(y_{ij}^t=0\) and \(\theta _{ijt}<0\), then \(y_{ij}^t=1\) for \((i,j) \in {\mathcal {E}}, t \in {\mathcal {T}}\) since the objective function is in the direction of minimization.

5.2.2 Subgradient algorithm

The value \(LB(\alpha , \beta )\) is a lower bound on the optimal objective value of the original problem WPPVSC for any Lagrange multiplier set \(\left\{ \alpha , \beta \right\} \). To find the best (largest) lower bound, we solve the Lagrangian dual problem

$$\begin{aligned} Z=\max \limits _{\alpha , \beta \ge 0} LB(\alpha , \beta ) \end{aligned}$$
(12)

by using a subgradient optimization algorithm. At each iteration n of the subgradient optimization procedure, the current lower bound \(LB^n(\alpha , \beta )\) is obtained by optimally solving subproblems WPPVSC\(_1(\alpha , \beta )\) and WPPVSC\(_2(\alpha , \beta )\). Then, Lagrange multipliers \(\alpha ^n\), \(\beta ^n\) are updated using the best available upper bound \(UB^*\). Upper bounds \(UB^n\) are computed at each iteration n by constructing a feasible solution of the original problem from the solution of the subproblems, details of which are given in the next subsection. We report the \(UB^*\) and \(LB^*\) as the outputs of the subgradient procedure. We use three termination criteria for the procedure. The first one stops the subgradient algorithm if \(UB^*-LB^*<\epsilon _1\) for a given small positive value. Second termination criterion depends on the size of the step size parameter \(\pi \), which is employed in the subgradient algorithm. If there is no improvement in the value of best lower bound \(LB^*\) for consecutive N number of iterations, the value of \(\pi \) is halved. When \(\pi \) becomes smaller than a threshold level \(\epsilon _2\), the algorithm is stopped. An observation reveals that convergence of the subgradient algorithm slows down toward the end of the procedure. Hence, another criterion suggests putting an upper bound on the number of iterations in order not to spend too much time toward the end of the algorithm. The upper bound on the number of iterations is called iterlim in the body of the algorithm given below.

Although the subgradient algorithm is theoretically quite promising, its practical efficiency is prone to serious limitations due to the long computation times required by WPPVSC\(_1(\alpha , \beta )\), especially for large instances. Since WPPVSC\(_2(\alpha , \beta )\) is solved by inspection, it generally requires less than 1 minute even for the largest instances with 3000 nodes. On the other hand, the size of the LP subproblem WPPVSC\(_1(\alpha , \beta )\) becomes too large to be solved recurrently in the body of the Lagrangian heuristic numerous times. Hence, we are still in need of making the problem size smaller. Besides, one can easily observe that if there is a feasible solution vector x for WPPVSC\(_1(\alpha , \beta )\) with negative objective function value, values of the x variables can be increased indefinitely to produce an unbounded objective value. This surpasses \(Z_2\) value coming from WPPVSC\(_2(\alpha , \beta )\) and makes \(LB^n\) minus infinity and consequently slows the convergence rate of the subgradient algorithm. In order to make the problem size smaller and to put an upper bound on the x variables, which prevents WPPVSC\(_1(\alpha , \beta )\) from being unbounded, we make use of the period iteration idea which is explained in the previous section. Namely, we begin the procedure as if the number of passes is limited by 2, i.e., \(\phi =2\), and we increase the limit of the number of passes by one after the convergence of the inner Lagrangian heuristic, until no improvement is observed in the reported feasible solution. Moreover, the value of \(\phi \) is put as an upper bound for the value of x variables in the body of WPPVSC\(_1(\alpha , \beta )\) which will prevent unbounded solutions, and speed up the convergence of \(LB^n\). Therefore, the pass iteration idea is the backbone of both heuristics. The steps of the subgradient algorithm integrated with the pass iteration idea are summarized in Algorithm 2. Note that \(O^{(\phi )}\) existing in the body of Algorithm 2 now represents the objective function value of the best feasible solution found by the Lagrangian heuristic for step \(\phi \).

figure b

5.2.3 Generating a feasible solution

As mentioned before, at each iteration, Lagrangian heuristic constructs a feasible solution from the solution of the Lagrangian problem. Since constraints (4) and (5) are relaxed in the Lagrangian problem, values of x and y variables coming from WPPVSC\(_1(\alpha , \beta )\) and WPPVSC\(_2(\alpha , \beta )\) (say \(\bar{x}\) and \(\bar{y}\)) are not expected to be feasible for the original WPPVSC\((\alpha , \beta )\) problem. Nevertheless, a feasible y variable vector can be obtained near the solution of WPPVSC\(_2(\alpha , \beta )\). Once the values corresponding to the \(\bar{y}\) vector is set in the original problem WPPVSC\((\alpha , \beta )\), the model reduces to an LP and can easily be solved to optimality in order to generate feasible x vector as well. The approach we employ for finding the feasible solution depends on that idea. First of all, values of the y variables are set to the \(\bar{y}\) values in the original WPPVSC\((\alpha , \beta )\) to reduce it to an LP. If the LP is feasible, then the solution of it (which will give x values), together with the \(\bar{y}\) values coming from the solution of WPPVSC\(_2(\alpha , \beta )\), constitutes a feasible solution for the original problem. On the other hand, if the LP is infeasible, this means it is impossible to satisfy the relaxed constraints with the \(\bar{y}\) values obtained from WPPVSC\(_2(\alpha , \beta )\). In such a case, instead of setting the values of y variables in the original problem WPPVSC\((\alpha , \beta )\) with the ones coming from WPPVSC\(_2(\alpha , \beta )\), we initiate them from the values coming from WPPVSC\(_2(\alpha , \beta )\) by Gurobi’s START parameter and we let the solver run for a short time. By doing so, we let the solver to refine the \(\bar{y}\) values coming from WPPVSC\(_2(\alpha , \beta )\) so that they become feasible for the original problem. Besides, since a short computation time is allowed for the solver, it will probably generate feasible y values that are in a sense close to the infeasible ones obtained from the solution of WPPVSC\(_2(\alpha , \beta )\). These steps are formally summarized in Algorithm 3.

figure c
Table 2 Performance of Gurobi, PIH and LH on test bed 1
Full size table

6 Computational results

In this section, the selection of the parameters of the PPVSC formulation is given first, and then the efficiency and accuracy of PIH and LH are illustrated on extensive test instances.

6.1 Selection of the parameters

We use 5 different sets of test instances. First set, which we call test bed 1, is due to Golden et al. (1983) including 23 problems denoted by gdb1,...,gdb23. Second set, named test bed 2, is given by Benavent et al. (1992). It includes 34 problems which are denoted as val1A,...,val10D. Third set, entitled as test bed 3, includes 24 problems denoted by egl-e1-A,...,egl-s4-C and is provided in the paper by Li and Eglese (1996). Problem size slightly increases as we go from test bed 1 to test bed 2, and from test bed 2 to test bed 3. These three sets are originally developed for capacitated arc routing problems. We neglect the capacities and take only the arc traveling costs as the initial service costs. We generate the fourth set in order to have denser instances and call it test bed 4. Node places are randomly chosen so that the resulting network is a connected one. Vertices that are closer than 15 meters are accepted as neighbors, and the initial service costs are equated to the length of the edges. There are 12 problems in test bed 4 that are called as 100-1,...,400-3. Finally, the fifth set named test bed 5, generated for WPP, is given in a website (http://www.uv.es/corberan/instancias.htm) and includes 120 problems denoted WA0531,...,WB3065. We take values of the first pass costs, namely \(c_{ij}^1\) parameters, from the sets. Values of the other cost parameters, i.e., \(c_{ij}^k\)\(k \in {\mathcal {T}}, k\ge 2\), are generated using the formula \(c_{ij}^k=\left\lceil \frac{c_{ij}^{k-1}}{2}\right\rceil +\text {Rand}(\frac{c_{ij}^{k-1}}{2})\) where Rand(n) denotes a real number randomly generated within the interval (0,n). Note that \(c_{ij}^k\) values compulsorily possess a nonincreasing structure, and \(c_{ij}^k>0\) for any k by this selection mechanism.

Table 3 Performance of Gurobi, PIH and LH on test bed 2
Full size table

6.2 Accuracy and efficiency of heuristics

In this section, we assess the performance of PIH and LH by comparing the minimum costs found by them with those found by the state-of-the-art MILP solver Gurobi (2017) on the described test sets. We code PPVSC, PIH and LH in Visual Studio environment by C# language and we carry out all experiments using a single Intel i7-4770 core. We let Gurobi, PIH and LH run for at most 1 hour for each of the test problems instances and the minimum objective function values found in the allowed computation times are reported. We, respectively, tabulate the results corresponding to test beds 1, 2, 3 and 4 Tables 2, 3, 4 and 5. Results corresponding to test bed 5 are tabulated in Tables 6 and 7. The first column of the tables includes the instance name, while the second and third columns keep the numbers of vertices and the edges (which are denoted by \(\left| {\mathcal {V}}\right| \) and \(\left| {\mathcal {E}}\right| \)), respectively. Similarly, the fourth, fifth and sixth columns keep the objective value of the best solution found by Gurobi, cpu time Gurobi uses, and the percent deviation between the best solution found by Gurobi and the best possible objective function value reported by Gurobi (which are denoted by \(O^{\text {G}}\), \(T^{\text {G}}\) and Gap), respectively. In addition, the seventh and eighth columns, respectively, keep the objective value of the best solution found by PIH and the cpu time it uses (which are denoted by \(O^{\text {PIH}}\) and \(T^{\text {PIH}}\)). Finally, the best possible objective function value found by LH, and the cpu time LH uses (which are denoted by \(O^{\text {LH}}\) and \(T^{\text {LH}}\)) are given under columns ninth and tenth, respectively.

Table 4 Performance of Gurobi, PIH and LH on test bed 3
Full size table

As can be understood from Table 2, Gurobi, PIH and LH are able to find the optimal solution for each instance of test bed 1. However, the average CPU time used by Gurobi is 5.18 times larger than the average CPU time used by PIH. On the other hand, LH uses 13.36 times larger computation time than Gurobi uses. This is mainly due to the fact that LH has to go through thousands of iterations before convergence. Hence, all three methods can be said to be 100% accurate, but PIH is the most efficient one.

Performance of Gurobi, PIH and LH on test bed 2 is similar to their performances on test bed 1. They are all able to find the optimal solution for each instance and the average time used by Gurobi is 1.55 times of the average time used by PIH, and the average time used by LH is 5.19 times of the average time used by Gurobi, as can be observed in Table 3. From the results of test beds 1 and 2, one may extract that although LH is able to find the optimal solution for each instance, it uses much more computation time than the other alternatives, implying that both Gurobi and PIH are preferable over LH for small instances.

Story is slightly different for test bed 3. There are 10 instances for which Gurobi is unable to prove the optimality, and for 3 of them PIH and LH are able to find better solutions. However, results of Gurobi are better than those of LH four 4 instances, too. If Gurobi and LH are compared on the basis of the average objective function values, it can be said that LH edges out. Hence, PIH is the most accurate one in three solution alternatives for test bed 3. Moreover, PIH is the most efficient one as well, since the average time Gurobi requires is 3.08 times larger than the required time by PIH while the computation time LH requires is 1.52 times larger than the computation time of Gurobi. These results can be seen in Table 4.

Table 5 Performance of Gurobi, PIH and LH on test bed 4
Full size table

Performance of PIH and LH gets better with the increasing problem size. This observation becomes clearer in the results for test bed 4 given in Table 5. Gurobi and LH spend all the allowable time for each of the instances, while PIH converges before time limit exceeds for 4 instances. On average, times, respectively, spent by Gurobi and LH are 1.21 and 1.22 times more than that of PIH spends. The average objective function value found by Gurobi is 16.20 and 16.37% larger than those of the average objective function values, respectively, found by PIH and LH. Results of LH are slightly better than those of PIH. Besides, PIH results are better than Gurobi results for each of the 12 instances, and better than LH for 5 instances while LH results are better than PIH results for 7 instances implying that PIH and LH clearly dominate Gurobi.

Table 6 Performance of Gurobi, PIH and LH on test bed 5: WA instances
Full size table
Table 7 Performance of Gurobi, PIH and LH on test bed 5: WB instances
Full size table

Dominance of PIH and LH over Gurobi becomes even clearer for test bed 5. Not only PIH is more successful than Gurobi for all instances but one of test bed 5 (for one instance both methods produce the optimal solution), costs found by Gurobi is more than 3, 4, 5, and even 6 times of the ones found by PIH for a large number of instances. For example, costs found by Gurobi are 3.68, 4.12, 5.55 and 6.12 times of the cost found by PIH, respectively, for instances WA1032, WA0552, WA1055 and WA1035. On the average, cost of the results found by Gurobi is 1.94 times larger than the cost associated with PIH results. Besides, Gurobi uses all the allowable time for all instances but one while PIH converges before the allowable time limit for several instances. On the other hand, LH outperforms PIH for most of the instances. PIH produces better results for only 6 WA instances and 3 WB instances while LH is better for remaining 54 WA instances and 57 WB instances. Average costs for respective WA and WB instances found by LH are given by 2170222 and 76642, while they are, respectively, 3067783 and 83335.6 for PIH results implying that LH is much more successful than PIH for test bed 5 instances. As a concluding remark, we can say that PIH is more successful than Gurobi for PPVSC instances and its success becomes clearer with increasing problem size. In addition, LH is competitive with PIH for small- and moderate-sized instances, and it becomes more and more successful as the problem size gets larger.

7 Conclusion and future research paths

This paper presents a mathematical formulation for the postman problem with variable service costs. It is assumed that the travel costs of the edges depend on the number of passes and they tend to decrease with each pass. The problem is named Chinese postman problem with variable service costs if the service costs are symmetric, and it is named as windy postman problem with variable service costs, otherwise. CPPVSC is solvable in polynomial time, and it is shown in the paper that no edge is traversed more than twice in the optimal solution. On the other hand, WPPVSC is NP-hard since it can be reduced to WPP which is known to be NP-hard. Two heuristics named PIH and LH are proposed for the solution of WPPVSC instances. In PIH, Gurobi runs for a predetermined amount of time and for a given number of allowable passes at each iteration and the number of allowable passes is increased by one at the next iteration in which the solution obtained at the previous iteration is used as a starting point. In LH, two constraints are relaxed and carried to the objective function after multiplied by positive Lagrangian multipliers and the multipliers are optimized through a subgradient algorithm. A feasible solution is obtained in each step of the algorithm making use of the subproblem solutions. Results of PIH and LH are compared with results of Gurobi, and it is observed that although using the solver as the solution method for small sized WPPVSC instances is possible, PIH dominates Gurobi for instances with moderate and large sizes, and LH outperforms PIH for large instances.

This work can be extended in several directions. First of all, variable service cost idea can be imposed on other variants of PP such as capacitated PP, PP with multiple vehicles, or hierarchical PP. Another idea is to analyze the PP with stochastic service costs. Finally, PP with multiple depots can be addressed under variable service cost assumption.