| This dissertation addresses three problems related to the road network marking. These problems are studied from a mathematical and a computational point of view. In the mathematical part, linear integer programming formulations and heuristics are presented. The oriented object approach for transport is used for modeling the problems.;First of all, this work presents the road marking activities in a general context. Three complementary management levels are distinguished: the stage of general planning for the road network, the stage of seasonal planning, and finally, at the operational level, the stage of the completed activities follow-up. Specifically, this project addresses the vehicle routing problem for the seasonal planning stage, but the tools developed in this thesis can also be used at the follow-up stage. The first problem studied is an extension of location-arc routing problems, which from here on will be called "capacitated arc routing problem with refill points".;In this problem, we have a limited capacity vehicle which must serve arcs (to trace lines on the roadway). The servicing vehicle (SV) is filled on the spot by another vehicle (the refilling vehicle, RV) which must return to the depot after each filling. The aim is to minimize the total routing cost of the two vehicles. A linear integer model is developed. The mathematical model is built on a mixed graph, based on the models for the CARP (capacitated arc routing problem). The edges are transformed into arcs by replacing each edge by two opposed arcs, and by adding constraints to restrict the passage of service in only one of the two directions. To solve the problem, the graph was augmented by adding two sets of arcs connecting each node with the depot and the depot with each node. Problem instances were solved using a cutting plane algorithm. This algorithm makes a relaxation of connectivity. At each iteration, the violated are added until obtaining a feasible solution. The suggested method is able to solve, in acceptable time, small size problems on mixed graphs and small or medium sized problems on directed graphs.;The second problem studied is an extension of the first one. In this case, the refilling vehicle does not have a restriction on the number of times that it can meet the servicing vehicle (SV) before returning to the depot. A linear integer model and a heuristic are presented. The developed heuristic procedure consists of three stages: find a giant tour for SV, divide the tour into sections, where each one is feasible for SV, and select the sections satisfying the autonomy of SV at a minimal cost. Variations to the basic heuristic method are also presented. Given these variations, it is possible to quickly find solutions compromising no more than 4% of the total cost in the tested problems.;The third situation studied is a generalization of the other two problems. This case considers multiple servicing and refilling vehicles. A linear integer model is presented and a heuristic method is proposed. This heuristic consists of three stages: in the first stage, a generalized assignment problem is considered; in the second stage, the refill points and trajectories are determined for the servicing vehicles; and in the third stage the routings for the refilling vehicles are considered.;The last section presents the object oriented library developed to study the problems. This library includes solutions to several vehicles routing problems such as the capacitated arc routing problem with refill points, which also implies the presence of all the subjacent algorithms (shortest path, arc routing, etc).;Finally, one cannot doubt the importance of the problems studied in this thesis as an opening way to several interesting problems in the field of road marking maintenance and in other fields, and as an adding-value tool for the integration of operations research algorithms within information systems in order to optimize the resources allocated to the road network maintenance. |
