Journals Proceedings

Abstract

In routing problems, the aim is to determine a least cost route for vehicles covering a specified set of locations, subject to some constraints. How the cost is calculated and minimized in these problems may include fuel consumption and other environmental criteria, such as pollution level. An example is determination of optimal routes for vehicles in solid waste collection in order to minimize the environmental impact caused by the vehicle itself. We address the problem in a broad level, known in literature as the General Routing Problem. Using a mathematical and computational model, in this paper we solve the problem of determining a least cost circuit which covers given subsets of arcs, edges and nodes of a mixed graph, subject to turn restrictions on nodes (restrictions that avoid bad turns of vehicles in real-life street networks). The well known problems, such as the Mixed Chinese Postman Problem and the Traveling Salesman Problem are particular cases of this general problem. Our solution is based on an efficient graph transformation that makes it possible to solve the resulting problem as a standard TSP. Computational results confirm the efficiency of the method in solving relatively large problems with good quality.