Machine Learning and the Traveling Repairman
Preprint
Abstract
The goal of the Machine Learning and Traveling Repairman Problem (ML&TRP) is to determine a route for a "repair crew," which repairs nodes on a graph. The repair crew aims to minimize the cost of failures at the nodes, but as in many real situations, the failure probabilities are not known and must be estimated. We introduce two formulations for the ML&TRP, where the first formulation is sequential: failure probabilities are estimated at each node, and then a weighted version of the traveling repairman problem is used to construct the route from the failure cost. We develop two models for the failure cost, based on whether repeat failures are considered, or only the first failure on a node. Our second formulation is a multi-objective learning problem for ranking on graphs. Here, we are estimating failure probabilities simultaneously with determining the graph traversal route; the choice of route influences the estimated failure probabilities. This is in accordance with a prior belief that probabilities that cannot be well-estimated will generally be low. It also agrees with a managerial goal of finding a scenario where the data can plausibly support choosing a route that has a low operational cost.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Machine Learning for the New York City Power GridIEEE Transactions on Pattern Analysis and Machine Intelligence, 2011
- A New Real-Time Reliability Prediction Method for Dynamic Systems Based on On-Line Fault PredictionIEEE Transactions on Reliability, 2009
- A new formulation for the Traveling Deliveryman ProblemDiscrete Applied Mathematics, 2008
- New approaches to statistical learning theoryAnnals of the Institute of Statistical Mathematics, 2003
- Entropy and the combinatorial dimensionInventiones Mathematicae, 2003
- Condition-based maintenance optimization by means of genetic algorithms and Monte Carlo simulationReliability Engineering & System Safety, 2002
- Global Optimization by Multilevel Coordinate SearchJournal of Global Optimization, 1999
- An improved approximation ratio for the minimum latency problemMathematical Programming, 1998
- Decision theoretic generalizations of the PAC model for neural net and other learning applicationsInformation and Computation, 1992
- The Volume of Convex Bodies and Banach Space Geometry1989