This paper presents the capacitated and economic districting problem (CEDP), which searches for the best edge partition defining connected, capacitated, and balanced districts in an undirected connected graph, weighing the economic value of each district. This problem provides a comprehensive description of the decision making on service networks districting, where the order by which the districts are serviced plays a role in the profit. This is observed in the arrangement of districts for meter reading, as the day in which each district is read impacts the revenue. Two integer linear programming formulations are proposed for CEDP, accompanied by a proof of [Formula: see text]-hardness. To tackle large instances, a greedy randomized adaptive search procedure (GRASP) metaheuristic, embedded with reactive parameter tuning, statistical filtering of solutions subjected to intensification, and a set of solution repairing procedures, is proposed. The GRASP is hybridized to each model to evaluate the outcomes of combining their individual merits. Computational experiments were performed on a new benchmark composed of 144 instances of different sizes, edge densities, network topologies, balance tolerances, and district capacities. The results show the effectiveness of the exact methodologies in solving the models and providing optimal solutions for the set of small instances. The GRASP was capable of tackling large networks, achieving feasible solutions to almost all instances. The results also show that the hybridized methodologies outperformed their standalone counterparts with respect to the attained primal and dual bounds.

This work provides a theoretical study of the Green Vehicle Routing Problem (G-VRP), which is an NP-hard problem that generalizes the Vehicle Routing Problem (VRP) and integrates it with the green logistics. In the G-VRP, electric vehicles with limited autonomy can recharge at Alternative Fuel Stations (AFSs) to keep visiting customers. This problem was introduced by [3] and approached later by [4], and [5], all of which consider that consecutive AFSs visits are not allowed, i.e., a solution cannot have an edge between two AFSs. In this work, two G-VRP versions are investigated, (i) where consecutive AFSs visits are not allowed, and (ii) where consecutive AFSs visits are allowed, i.e., a solution may have an edge between two AFSs. This research proposes combinatorial properties and lower bounds which have the potential to strengthen the mathematical formulations for both G-VRP versions, thus improving exact solution methodologies.

This paper is talking about Open Capacitated Arc Routing Problem,which is a combinational optimization problem.The objective is mainly to search for a solution of minimum cost.