The k-Traveling Repairman Problem with Stochastic Service Request Times

References

• Ahmadi T, Hesaraki AF, Mahmoodi A, Marandi A (2025) Managing customer waiting times in an inventory system using conditional value-at-risk measure. Ann. Oper. Res. 344(1):1–45.Crossref, Google Scholar
• Aras N, Yurdakul A (2016) A new multi-objective mathematical model for the high-level synthesis of integrated circuits. Appl. Math. Model. 40(3):2274–2290.Crossref, Google Scholar
• Archer A, Levin A, Williamson DP (2008) A faster, better approximation algorithm for the minimum latency problem. SIAM J. Comput. 37(5):1472–1498.Crossref, Google Scholar
• Ausiello G, Leonardi S, Marchetti-Spaccamela A (2000) On salesmen, repairmen, spiders, and other traveling agents. Bongiovanni G, Petreschi R, Gambosi G, eds. Algorithms and Complexity. CIAC 2000, Lecture Notes in Computer Science, vol. 1767 (Springer, New York), 1–16.Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Bertsimas DJ, Van Ryzin G (1991) A stochastic and dynamic vehicle routing problem in the Euclidean plane. Oper. Res. 39(4):601–615.Link, Google Scholar
• Bertsimas DJ, Jaillet P, Odoni AR (1990) A priori optimization. Oper. Res. 38(6):1019–1033.Link, Google Scholar
• Bhowmik S (2019) Digital twin of subsea pipelines: Conceptual design integrating IoT, machine learning and data analytics. Offshore Tech. Conf. D011S010R004.Google Scholar
• Bigras LP, Gamache M, Savard G (2008) The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times. Discrete Optim. 5(4):685–699.Crossref, Google Scholar
• Blum A, Chalasani P, Coppersmith D, Pulleyblank B, Raghavan P, Sudan M (1994) The minimum latency problem. Proc. Twenty-Sixth Annual ACM Sympos. Theory Comput. (ACM, New York), 163–171.Google Scholar
• Boland N, Dethridge J, Dumitrescu I (2006) Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Oper. Res. Lett. 34(1):58–68.Crossref, Google Scholar
• Bulhões T, Sadykov R, Uchoa E (2018) A branch-and-price algorithm for the minimum latency problem. Comput. Oper. Res. 93:66–78.Crossref, Google Scholar
• Chang KH (2015) Reliability analysis. Chang KH, ed. e-Design (Academic Press, Boston), 523–595.Crossref, Google Scholar
• Citi Bike (2024) September 2024 monthly report. Accessed October 19, 2024, https://citibikenyc.com/.Google Scholar
• Conway RW, Maxwell WL, Miller L (1967) Theory of Scheduling (Addison-Wesley, Boston).Google Scholar
• Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transportation Sci. 53(4):946–985.Link, Google Scholar
• Dayarian I, Crainic TG, Gendreau M, Rei W (2015a) A branch-and-price approach for a multi-period vehicle routing problem. Comput. Oper. Res. 55:167–184.Crossref, Google Scholar
• Dayarian I, Crainic TG, Gendreau M, Rei W (2015b) A column generation approach for a multi-attribute vehicle routing problem. Eur. J. Oper. Res. 241(3):888–906.Google Scholar
• Desaulneirs G, Desrosiers J, Solomon MM (2005) Column Generation (Springer, New York).Crossref, Google Scholar
• Domschke W, Scholl A, Voβ S (1997) Produktionsplanung: Ablauforganisatorische Aspekte (Springer, Berlin).Crossref, Google Scholar
• Dror M (1994) Note on the complexity of the shortest path models for column generation in VRPTW. Oper. Res. 42(5):977–978.Link, Google Scholar
• Fakcharoenphol J, Harrelson C, Rao S (2007) The k-traveling repairmen problem. ACM Trans. Algorithms 3(4):40.Crossref, Google Scholar
• Feillet D, Dejax P, Gendreau M, Gueguen C (2004) An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks 44(3):216–229.Crossref, Google Scholar
• Fischetti M, Laporte G, Martello S (1993) The delivery man problem and cumulative matroids. Oper. Res. 41(6):1055–1064.Link, Google Scholar
• Godinho MT, Gouveia L, Pesneau P (2014) Natural and extended formulations for the time-dependent traveling salesman problem. Discrete Appl. Math. 164(1):138–153.Crossref, Google Scholar
• Hvattum LM, Løkketangen A, Laporte G (2006) Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic. Transportation Sci. 40(4):421–438.Link, Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, Boston), 33–65.Crossref, Google Scholar
• Irnich S, Villeneuve D (2006) The shortest-path problem with resource constraints and k-cycle elimination for k ≥ 3. INFORMS J. Comput. 18(3):391–406.Link, Google Scholar
• Jaillet P (1988) A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Oper. Res. 36(6):929–936.Link, Google Scholar
• Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Luo Z, Qin H, Lim A (2014) Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints. Eur. J. Oper. Res. 234(1):49–60.Crossref, Google Scholar
• MAWSS (2025) News. Accessed February 24, 2025, https://www.mawss.com/news/.Google Scholar
• Méndez-Díaz I, Zabala P, Lucena A (2008) A new formulation for the traveling deliveryman problem. Discrete Appl. Math. 156(17):3223–3237.Crossref, Google Scholar
• Mihai S, Yaqoob M, Hung DV, Davis W, Towakel P, Raza M, Karamanoglu M, et al. (2022) Digital twins: A survey on enabling technologies, challenges, trends and future prospects. IEEE Comm. Surveys Tutorials 24(4):2255–2291.Crossref, Google Scholar
• Muritiba AEF, Bonates TO, Da Silva SO, Iori M (2021) Branch-and-cut and iterated local search for the weighted k-traveling repairman problem: An application to the maintenance of speed cameras. Transportation Sci. 55(1):139–159.Link, Google Scholar
• Nagarajan V, Ravi R (2008) The directed minimum latency problem. Goel A, Jansen K, Rolim JDP, Rubinfeld R, eds. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, APPROX RANDOM 2008, Lecture Notes in Computer Science, vol. 5171 (Springer, Berlin), 193–206.Crossref, Google Scholar
• Navidi F, Gortz IL, Nagarajan V (2020) Approximation algorithms for the a priori traveling repairman. Oper. Res. Lett. 48(5):599–606.Crossref, Google Scholar
• Neikov OD, Yefimov NA (2019) Powder characterization and testing. Neikov OD, Naboychenko SS, Yefimov NA, eds. Handbook of Non-Ferrous Metal Powders, 2nd ed. (Elsevier, Oxford, UK), 3–62.Crossref, Google Scholar
• Ngueveu SU, Prins C, Calvo RW (2010) An effective memetic algorithm for the cumulative capacitated vehicle routing problem. Comput. Oper. Res. 37(11):1877–1885.Crossref, Google Scholar
• Nucamendi-Guillén S, Martinez-Salazar I, Angel-Bello F, Moreno-Vega JM (2016) A mixed integer formulation and an efficient metaheuristic procedure for the k-Travelling Repairmen Problem. J. Oper. Res. Soc. 67(8):1121–1134.Crossref, Google Scholar
• Perron L, Furnon V (2023) Google OR-tools. Accessed December 15, 2023, https://developers.google.com/optimization/.Google Scholar
• Pham DT, Klesmüller GP (2024) Hybrid value function approximation for solving the technician routing problem with stochastic repair requests. Transportation Sci. 58(2):499–519.Link, Google Scholar
• Picard JC, Queyranne M (1978) The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling. Oper. Res. 26(1):86–110.Link, Google Scholar
• Priyanka E, Thangavel S, Gao XZ, Sivakumar N (2022) Digital twin for oil pipeline risk estimation using prognostic and machine learning techniques. J. Indust. Inform. Integration 26:100272.Google Scholar
• Psaraftis HN, Wen M, Kontovas CA (2015) Dynamic vehicle routing problems: Three decades and counting. Networks 67(1):3–31.Google Scholar
• Righini G, Salani M (2006) Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim. 3(3):255–273.Crossref, Google Scholar
• Righini G, Salani M (2009) Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Comput. Oper. Res. 36(4):1191–1203.Crossref, Google Scholar
• Roberti R, Mingozzi A (2014) Dynamic ng-path relaxation for the delivery man problem. Transportation Sci. 48(3):413–424.Link, Google Scholar
• Saharidis GK, Dimitropoulos C, Skordilis E (2014) Minimizing waiting times at transitional nodes for public bus transportation in Greece. Oper. Res. 14(3):341–359.Crossref, Google Scholar
• Sahni S, Gonzalez T (1976) P-complete approximation problems. J. ACM 23(3):555–565.Crossref, Google Scholar
• Sarbazi-Azad H (2003) A mathematical model of deterministic wormhole routing in hypercube multicomputers using virtual channels. Appl. Math. Model. 27(12):943–953.Crossref, Google Scholar
• Simchi-Levi D, Berman O (1991) Minimizing the total flow time of n jobs on a network. IIE Trans. 23(3):236–244.Crossref, Google Scholar
• Sutton I (2015) Reliability, availability, and maintainability. Sutton I, ed. Process Risk and Reliability Management, 2nd ed. (Gulf Professional Publishing, Oxford, UK), 667–688.Crossref, Google Scholar
• Thomas BW (2007) Waiting strategies for anticipating service requests from known customer locations. Transportation Sci. 41(3):319–331.Link, Google Scholar
• van Ee M, Sitters R (2018) The a priori traveling repairman problem. Algorithmica 80(10):2818–2833.Crossref, Google Scholar
• van Eijl CA (1995) A polyhedral approach to the delivery man problem. Eindhoven University of Technology, Memorandum COSOR 9519.Google Scholar
• Yan Q, Wang H, Wu F (2022) Digital twin-enabled dynamic scheduling with preventive maintenance using a double-layer q-learning algorithm. Comput. Oper. Res. 144:105823.Crossref, Google Scholar
• Zhao Z, Shen L, Yang C, Wu W, Zhang M, Huang GQ (2021) IoT and digital twin enabled smart tracking for safety management. Comput. Oper. Res. 128:105183.Crossref, Google Scholar