Many security companies offer patrolling services, where guards have to inspect facilities or streets on a regular basis. Patrolling routes should be cost efficient, while the inspection patterns should not be predictable for of-fenders. Also cash-in-transit services result in routing problems, where cost minimization and route inconsistency have to be traded-off. We introduce this setting as multi-objective periodic node, edge, arc routing problem with the objectives being minimizing the costs and minimizing the route consistency. It is mathematically formulated and transformed into an asymmetric capacitated vehicle routing problem, once with a simple-graph and once with a multi-graph. In order to solve the problem, we propose to embed an adaptive large neighborhood search procedure into multi-objective solution frameworks. We implement three frameworks, namely multi-directional local search (MDLS), ε-constraint heuristic (ECH), and ε-box splitting heuristic (EBSH). The methods were tested on artificial as well as on real-world in-stances. In an extensive computational study, we show that EBSH and ECH seem to be the superior methods. Furthermore, the results indicate that considering more than one shortest paths between nodes, can significantly increases solution quality.