The fleet size and mix problem for capacitated arc routing (Q1064973)

A solution procedure for solving the capacitated arc routing problem is presented. In the work accomplished in this area the objective has been to minimize the total distance travelled. Here, the objective function is extended to include the fixed costs of the vehicles. The solution procedure consists of four phases. In the first phase, the fixed cost component is ignored and a Chinese or rural postman problem is solved depending on the service demand data of the problem. It results in a tour called the giant tour. In the second phase, the giant tour is partitioned into feasible single vehicle tours. A new network is constructed with the node set corresponding to the arcs of the giant tour and with the arc set representing the feasible single vehicle tours. The arc costs include both the fixed and variable costs of the subtours. The third phase consists of solving for the shortest path on this new network. The arcs on the shortest path form the least cost set of feasible vehicle tours represented on the new network. In the last phase a postprocessor is applied to the solution to improve it. The procedure is repeated for different giant tours to improve the final solution. The problem is extended to include upper bounds on the number of vehicles with given capacities using a branch and bound method. Extension to directed networks is given. Some computational results are reported.