Branch-and-Cut and Iterated Local Search for the Weighted k-Traveling Repairman Problem: An Application to the Maintenance of Speed Cameras

References

• Abeledo H, Fukasawa R, Pessoa A, Uchoa E (2013) The time dependent traveling salesman problem: Polyhedra and algorithm. Math. Programming Comput. 5(1):27–55.Crossref, Google Scholar
• Angel-Bello F, Alvarez A, García I (2013) Two improved formulations for the minimum latency problem. Appl. Math. Model. 37(4):2257–2266.Crossref, Google Scholar
• Archer A, Levin A, Williamson D (2008) A faster, better approximation algorithm for the minimum latency problem. SIAM J. Comput. 37(5):1472–1498.Crossref, Google Scholar
• Archetti C, Bertazzi L, Laporte G, Speranza M (2007) A branch-and-cut algorithm for a vendor-managed inventory-routing problem. Transportation Sci. 41(3):382–391.Link, Google Scholar
• Augerat P, Belenguer JM, Benavent E, Corberan A, Naddef D, Rinaldi G (1998) Computational results with a branch-and-cut code for the capacitated vehicle routing problem. Technical Report 495, Istituto di Analisi dei Sistemi ed Informatica, Rome.Google Scholar
• Ausiello G, Leonardi S, Marchetti-Spaccamela A (2000) On salesmen, repairmen, spiders, and other travelling agents. Bongiovanni G, Petreschi R, Gambosi G, eds. Algorithms and Complexity. Lecture Notes in Computer Science, vol. 1767 (Springer, Berlin), 1–16.Google Scholar
• Bianco L, Mingozzi A, Ricciardelli S (1993) The travelling salesman problem with cumulative costs. Networks 23(2):81–91.Crossref, 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
• Bissoli D, Chaves G, Ribeiro G (2016) Drivers to the workover rig problem. J. Petroleum Sci. Engrg. 139:13–22.Crossref, Google Scholar
• Bjelić N, Vidović M, Popović D (2013) Variable neighborhood search algorithm for heterogeneous traveling repairmen problem with time windows. Expert Systems Appl. 40(15):5997–6006.Crossref, Google Scholar
• Blum A, Chalasani P, Coppersmith D, Pulleyblank B, Raghavan P, Sudan M (1994) The minimum latency problem. Proc. 26th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 163–171.Google Scholar
• Bruck B, Iori M (2017) Non-elementary formulations for single vehicle routing problems with pickups and deliveries. Oper. Res. 65(6):1597–1614.Link, Google Scholar
• Bruck B, Cruz F, Iori M, Subramanian A (2019) The static bike sharing rebalancing problem with forbidden temporary operations. Transportation Sci. 53(3):882–896.Link, 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
• Christofides N, Eilon S (1969) An algorithm for the vehicle-dispatching problem. J. Oper. Res. Soc. 20(3):309–318.Crossref, Google Scholar
• Christofides N, Mingozzi A, Toth P (1979) The vehicle routing problem. Christofides N, Toth P, Mingozzi A, CS, eds. Combinatorial Optimization (John Wiley and Sons, London), 315–338.Google Scholar
• Conway RW, Maxwell WL, Miller LW (1967) Theory of Scheduling (Dover Publications, Mineola, NY).Google Scholar
• Dirichlet PGL (1889) Werke, vol. 1 (Reimer, Berlin).Google Scholar
• Fakcharoenphol J, Harrelson C, Rao S (2003) The k-traveling repairman problem. Proc. 14th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 655–664.Google Scholar
• Fakcharoenphol J, Harrelson C, Rao S (2007) The k-traveling repairmen problem. ACM Trans. Algorithms 3(4):655–664.Crossref, Google Scholar
• Ghosh JB (1996) Computational aspects of the maximum diversity problem. Oper. Res. Lett. 19(4):175–181.Crossref, Google Scholar
• Gouveia L, Voß S (1995) A classification of formulations for the (time-dependent) traveling salesman problem. Eur. J. Oper. Res. 83(1):69–82.Crossref, Google Scholar
• Grimaldi RP (1994) Discrete and Combinatorial Mathematics: An Applied Introduction (Addison-Wesley, Boston).Google Scholar
• Jaillet P, Wagner MR (2006) Online routing problems: Value of advanced information as improved competitive ratios. Transportation Sci. 40(2):200–210.Link, Google Scholar
• Jothi R, Raghavachari B (2007) Approximating the k-traveling repairman problem with repairtimes. J. Discrete Algorithms 5(2):293–303.Crossref, Google Scholar
• Krumke S, Paepe W, Poensgen D, Stougie L (2003) News from the online traveling repairman. Theoret. Comput. Sci. 295(1–3):279–294.Crossref, Google Scholar
• Kuo CC, Glover F, Dhir KS (1993) Analyzing and modeling the maximum diversity problem by zero-one programming. Decision Sci. 24(6):1171–1185.Crossref, Google Scholar
• Liao T, Guo HY (2013) A heuristic approach for on-line signal repair problems. J. Eastern Asia Soc. Transportation Stud. 10:897–915.Google Scholar
• Lourenço H, Martin O, Stützle T (2019) Iterated local search: Framework and applications. Gendreau M, Potvin JY, eds. Handbook of Metaheuristics, 3rd ed. International Series in Operations Research and Management Science (Springer, Berlin), 129–168.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
• Melo Silva M, Subramanian A, Vidal T, Ochi L (2012) A simple and effective metaheuristic for the minimum latency problem. Eur. J. Oper. Res. 22(3):513–520.Crossref, 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
• Minieka E (1989) The delivery man problem on a tree network. Ann. Oper. Res. 18(1):261–266.Crossref, Google Scholar
• Miranda-Bront JJ, Méndez-Díaz I, Zabala P (2014) Facets and valid inequalities for the time-dependent travelling salesman problem. Eur. J. Oper. Res. 236(3):891–902.Crossref, Google Scholar
• Mladenović N, Urošević D, Hanafi S (2013) Variable neighborhood search for the travelling deliveryman problem. 4OR 11(1):57–73.Google Scholar
• Nagarajan V, Ravi R (2008) The directed minimum latency problem. Goel A, Jansen K, Rolim J, Rubinfeld R, eds. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science, vol. 5171 (Springer, Berlin), 193–206.Crossref, Google Scholar
• Ngueveu S, Prins C, Wolfler Calvo R (2010) An effective memetic algorithm for the cumulative capacitated vehicle routing problem. Comput. Oper. Res. 37(11):1877–1885.Crossref, Google Scholar
• Nucamendi-Guillé S, Angel-Bello F, Martinez-Salazar I, Cordero-Franco A (2018) The cumulative capacitated vehicle routing problem: New formulations and iterated greedy algorithms. Expert Systems Appl. 113:315–327.Crossref, Google Scholar
• Nucamendi-Guillén S, Martínez-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
• Onder G, Kara I, Derya T (2017) New integer programming formulation for multiple traveling repairmen problem. Transportation Res. Procedia 22:355–361.Crossref, Google Scholar
• Picard JC, Queyranne M (1978) The time-dependent travelling salesman problem and its application to the tardiness problem in one-machine scheduling. Oper. Res. 26(1):86–110.Link, Google Scholar
• Poon KK, Shiu WC (2008) On the Dirichlet’s box principle. Internat. J. Math. Ed. Sci. Tech. 39(6):833–838.Crossref, Google Scholar
• Qian F, Gribkovskaia I, Halskau Ø (2011) Helicopter routing in the Norwegian oil industry: Including safety concerns for passenger transport. Internat. J. Physical Distribution Logist. Management 41(4):401–415.Crossref, Google Scholar
• Reinelt G (1991) TSPLIB–A traveling salesman problem library. ORSA J. Comput. 3(4):376–384.Link, Google Scholar
• Ribeiro G, Laporte G (2012) An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Comput. Oper. Res. 39(3):728–735.Crossref, Google Scholar
• Ribeiro G, Laporte G, Mauri G (2012) A comparison of three metaheuristics for the workover rig routing problem. Eur. J. Oper. Res. 220(1):28–36.Crossref, Google Scholar
• Rittaud B, Heeffer A (2014) The pigeonhole principle, two centuries before Dirichlet. Math. Intelligencer 36(2):27–29.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
• Sahni S, Gonzalez T (1976) P-complete approximation problems. J. ACM 23(3):555–565.Crossref, Google Scholar
• Salehipour A, Sörensen K, Goos P, Bräysy O (2011) Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem. 4OR 9(2):189–209.Google Scholar
• Sitters R (2002) The minimum latency problem is NP-hard for weighted trees. Cook W, Schulz A, eds., Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 2337 (Springer, Berlin), 230–239.Google Scholar
• Tanaka S, Araki M (2013) An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. Comput. Oper. Res. 40(1):344–352.Crossref, Google Scholar
• Tsitsiklis J (1992) Special cases of travelling salesman and repairman problems with time windows. Networks 22(3):263–282.Crossref, Google Scholar
• Wu B (2000) Polynomial time algorithms for some minimum latency problems. Inform. Processing Lett. 75(5):225–229.Crossref, Google Scholar
• Wu BY, Huang ZN, Zhan FJ (2004) Exact algorithms for the minimum latency problem. Inform. Processing Lett. 92(6):303–309.Crossref, Google Scholar