Arc Routing Problems with Time Duration Constraints and Uncertainty

Le problème résolu dans cette thèse est divisé en deux parties: 1) la localisation-affectation pour les tournées sur les arcs en tenant compte des caractéristiques des secteurs, c'est-à-dire le problème de conception des secteurs (SDP), 2) le routage robuste sur les arcs avec contraintes de durée (RARPTD). Les objectifs de cette recherche sont les suivants: 1) développer une formulation mathématique pour la conception des secteurs en considérant le temps de passage sur les arcs et le niveau de service requis. Le résultat du modèle mathématique donne une solution optimale pour le problème de localisation-affectation pour les tournées sur les arcs, 2) proposer un algorithme heuristique efficace, qui assure à la fois des coûts acceptables et de bonnes caractéristiques des secteurs. L'algorithme heuristique donne une solution applicable pour le problème de conception des secteurs, 3) développer une formulation mathématique déterministe pour le problème de tournées sur les arcs avec contraintes de durée et concevoir un jeu de données d'incertitude des temps de parcours et de service, 4) proposer une formulation résoluble pour le problème de tournées robustes sur les arcs avec contraintes de durée. Les essais sont conduits avec des données générées aléatoirement et avec un cas réel de réseau. L'analyse des résultats démontre que l'algorithme heuristique en trois étapes est plus facile à utiliser que l'algorithme branch-and-cut. De plus, l'algorithme heuristique en trois étapes peut générer une bonne solution avec des secteurs concis et bien conçus. En ce qui concerne le RARPTD, les essais montrent que les réseaux de petite taille peuvent être résolus rapidement. L'analyse de sensibilité indique que: 1) il existe toujours deux façons d'améliorer la robustesse de la solution optimale: payer le prix de la robustesse ou ajuster l'allocation des arcs aux secteurs, 2) lorsque le nombre de véhicules augmente, la solution optimale sous faible niveau d'incertitude peut être plus robuste, mais le coût des solutions optimales sous le même niveau d'incertitude augmente.

Abstract

The problem solved in this thesis is divided into two parts: 1) location-allocation arc routing with considering the characteristics of sectors, namely, the sector design problem (SDP), 2) robust arc routing with time duration based on the sectoring result of sector design (RARPTD). The objectives of this research are: 1) to develop a location-allocation arc routing mathematical formulation with considering the deadheading time and required service level. The result of the mathematical model provides an optimal solution for the location-allocation arc routing problem, 2) to design an effective and efficient heuristic algorithm, which ensures both acceptable cost and good sector characteristics. The heuristic algorithm provides an applicable solution for the sector design problem, 3) to develop the deterministic mathematical formulation for the arc routing problem with time duration and deadheading time and design the uncertainty support set of the service time and deadheading time, 4) to propose a solvable formulation for the robust arc routing problem. The result of the robust formulation provides the robust optimal solution for the robust arc routing problem with time duration. Experiments are conducted with randomly generated instances and a real network case. The results analysis demonstrates that the three-stage heuristic algorithm is computationally more tractable than the branch-and-cut algorithm and could yield high quality solution with compact and good shaped sectors. As for the part of RARPTD, experiments demonstrate that small-sized networks can be solved to optimality quickly and sensitivity analysis indicates: 1) there are always two ways to improve the robustness of the optimal solution: pay the price of robustness or adjust the allocation of required edges, 2) when the number of vehicles increases, the optimal solution under low uncertainty level can be more robust but the cost of the optimal solutions under the same uncertainty level increases.