Abstract In this work we introduce the parking warden tour problem (PWTP), a new arc routing problem arising in irregular parking detection to model the maximization of the fines collected by a team of parking wardens. The peculiarity of the PWTP is that the arc revenue depends on the time elapsed from the previous inspection of a warden, since the revenue on a road link slumps to zero if a warden has just visited the link. For this new arc routing problem and a variant of it, we propose two mixed integer linear program formulations, a simple but effective matheuristic based on them and a bounding procedure. All the solution approaches have been tested and compared on both real instances generated on a road network area of Milano, through a survey and on real‐like random instances.

Traditional car sharing services have been based on the two‐way scheme, where the user picks up and returns the vehicle at the same parking station. Some innovative services permit also one‐way trips, that is, the user is allowed to return the vehicle in another station. The one‐way scheme is more attractive for the users, but may lead to an unbalance between the user demand, and the availability of vehicles or free lots at the stations. In such cases, the service provider could reallocate the fleet and restore a better distribution of the vehicles among the stations. In the case of electric car sharing, such a problem is more complex because the travel range depends on the level of the battery charge. This article presents a new approach for the relocation of electric vehicles (EVs), carried out by the staff of the service provider to keep the system balanced. Such an approach generates a challenging Paired Pickup and Delivery Problem with Time Windows with new features that to the best of our knowledge have never been considered in the literature. We call such a problem the EV relocation problem (EVRP). We yield a mixed integer linear programming (MILP) formulation of the EVRP and some techniques to speedup its solution through a state‐of‐the‐art solver (CPLEX). Moreover, we develop a simple but effective heuristic based on such a formulation and four upper bound generation methods. We test the performances of both the MILP formulation and the heuristic on instances built on the Milan road network. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(4), 292–305 2014

Abstract The present work tackles a recent problem in the class of cardinality constrained combinatorial optimization problems for the planar graph case: the minimum k‐cardinality cut problem. Given an undirected edge‐weighted connected graph the min k‐cardinality cut problem consists in finding a partition of the vertex set V in two sets V1, V2 such that the number of the edges between V1 and V2 is exactly k and the sum of the weights of these edges is minimal. Although for general graphs the problem is already strongly 𝒩𝒫‐hard, we have found a pseudopolynomial algorithm for the planar graph case. This algorithm is based on the fact that the min k‐cardinality cut problem in the original graph is equivalent to a bi‐weighted exact perfect matching problem in a suitable transformation of the geometric dual graph. Because the Lagrangian relaxation of cardinality constraint yields a max cut problem and max cut is polynomially solvable in planar graphs, we also develop a Lagrangian heuristic for the min k‐cardinality cut in planar graphs. We compare the performance of this heuristic with the performance of a more general heuristic based on a Semidefinite Programming relaxation and on the Goemans and Williamson's random hyperplane technique. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(4), 195–208 2006