Problème du postier chinois | EPFL Graph Search

vignette|Le graphe des arêtes du cube n'est pas eulérien (sommets de degré 3), mais peut l'être rendu en dédoublant quatre de ses douze arêtes, ce qui ajoute un degré à chaque sommet et fournit un parcours de postier. En théorie des graphes et en algorithmique, le problème du postier chinois, ou problème du postier (en anglais route inspection problem) consiste à trouver un plus court chemin dans un graphe connexe non orienté qui passe au moins une fois par chaque arête et revient à son point de départ. Le nom du problème vient du fait qu'il a été étudié par le mathématicien chinois Meigu Guan en 1962, et qu'il modélise la tournée d'un facteur devant effectuer le plus efficacement possible sa tournée en passant au moins une fois par chaque rue de son secteur. vignette|Ce support de table figure un parcours de postier non minimal (6 arêtes dédoublées). Le problème peut être réduit à la recherche d'un couplage maximal de poids minimum, et ainsi être résolu en temps polynomial dans le ca

A general framework for routing problems with stochastic demands

Michel Bierlaire, Mohammad Yousef Maknoon, Iliya Dimitrov Markov, Sacha Varone

We introduce a unified modeling and solution framework for various classes of rich vehicle and inventory routing problems as well as other probability-based routing problems with a time-horizon dimension. Demand is assumed to be stochastic and non-stationary, and is forecast using any forecasting model that provides expected demands over the planning horizon, with error terms from any empirical distribution. We discuss possible applications to various problems from the literature and practice: from health care, waste collection, and maritime inventory routing, to routing problems based on event probabilities, such as facility maintenance where the breakdown probability of a facility increases with time. We provide a detailed discussion on the effects of the stochastic dimension on modeling and the solution methodology. We develop a mixed integer non-linear model, provide examples of how it can be reduced and adapted to specific problem classes, and demonstrate that probability-based routing problems over a planning horizon can be seen through the lens of inventory routing. The optimization methodology is heuristic, based on Adaptive Large Neighborhood Search. The case study is based on waste collection and facility maintenance instances derived from real data. We analyze the cost benefits of open tours and the availability of better forecasting methodologies. We demonstrate that relaxing the distributional assumptions on the error terms and calculating probabilities using simulation information has only a minor impact on computation time. Simulating the error terms on the final solution further allows us to verify the low level of occurrence of undesirable events, such as stock-outs, overflows or breakdowns, with a moderate impact on the routing cost compared to alternative realistic policies. What is more, simulating the objective of the final solution shows that it is an excellent representation of the real cost.

2017

Modeling and Analysis of Beaconless and Beacon-Based Policies for a Swarm-Intelligent Inspection System

Nicolaus Correll, Alcherio Martinoli

We are developing a swarm-intelligent inspection system based on a swarm of autonomous, miniature robots, using only on-board, local sensors. To estimate intrinsic advantages and limitations of the proposed possible distributed control solution, we capture the dynamic of the system at a higher abstraction level using non-spatial probabilistic microscopic and macroscopic models. In a previous publication, we showed that we are able to predict quantitatively the performances of the swarm of robots for a given metric and a beaconless policy. In this paper, after briefly reviewing our modeling methodology, we explore the effect of adding an additional state to the individual robot controller, which allow robots to serve as a beacon for teammates and therefore bias their inspection routes. Results show that this additional complexity helps the swarm of robots to be more efficient in terms of energy consumption but not necessarily in terms of time required to complete the inspection. We also demonstrate that a beacon-based policy introduces a strong coupling among the behavior of robots, coupling which in turn results in nonlinearities at the macroscopic model level.

2005

A general framework for routing problems with stochastic demands

Michel Bierlaire, Mohammad Yousef Maknoon, Iliya Dimitrov Markov, Sacha Varone

2017