A Polynomial-Time Algorithm for the Probabilistic Profitable Tour Problem on a Tree

References

• [1] Afrati F, Cosmadakis S, Papadimitriou CH, Papageorgiou G, Papakostantinou N (1986) The complexity of the travelling repairman problem. Rairo-Theor. Inf. Appl. 20(1):79–87.Crossref, Google Scholar
• [2] Angelelli E, Mansini R, Rizzi R (2023) Solving the probabilistic profitable tour problem on a line. Optim. Lett. 17(8):1873–1888.Crossref, Google Scholar
• [3] Angelelli E, Archetti C, Filippi C, Vindigni M (2017) The probabilistic orienteering problem. Comput. Oper. Res. 81:269–281.Crossref, Google Scholar
• [4] Angelelli E, Bazgan C, Speranza MG, Tuza Z (2014) Complexity and approximation for traveling salesman problems with profits. Theoret. Comput. Sci. 531:54–65.Crossref, Google Scholar
• [5] Averbakh I, Berman O (1994) Routing and location-routing p-delivery men problems on a path. Transportation Sci. 28(2):162–166.Link, Google Scholar
• [6] Averbakh I, Berman O (1995) Probabilistic sales-delivery man and sales-delivery facility location problems on a tree. Transportation Sci. 29(2):184–197.Link, Google Scholar
• [7] Averbakh I, Berman O (1995) Sales-delivery man problems on treelike networks. Networks 25(2):45–58.Crossref, Google Scholar
• [8] Averbakh I, Berman O (1996) A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree. Discrete Appl. Math. 68(1–2):17–32.Crossref, Google Scholar
• [9] Bellalouna M, Murat C, Paschos VT (1995) Probabilistic combinatorial optimization problems on graphs: A new domain in operational research. Eur. J. Oper. Res. 87(3):693–706.Crossref, Google Scholar
• [10] Bertsimas D, Howell LH (1993) Further results on the probabilistic traveling salesman problem. Eur. J. Oper. Res. 65(1):68–95.Crossref, Google Scholar
• [11] Bertsimas D, Jaillet P, Odoni AR (1990) A priori optimization. Oper. Res. 38(6):1019–1033.Link, Google Scholar
• [12] Blanchard M, Jacquillat A, Jaillet P (2024) Probabilistic bounds on the k-traveling salesman problem and the traveling repairman problem. Math. Oper. Res. 49(2):1169–1191.Link, Google Scholar
• [13] Campbell AM, Thomas BW (2008) Probabilistic traveling salesman problem with deadlines. Transportation Sci. 42(1):1–21.Link, Google Scholar
• [14] Chandran B, Raghavan S (2008) Modeling and solving the capacitated vehicle routing problem on trees. Golden B, Raghavan SA, Wasil E, eds. The Vehicle Routing Problem: Latest Advances and New Challenges (Springer US, Boston), 239–261.Crossref, Google Scholar
• [15] Chou X, Gambardella LM, Montemanni R (2021) A tabu search algorithm for the probabilistic orienteering problem. Comput. Oper. Res. 126:105107.Crossref, Google Scholar
• [16] Coene S, Spieksma FC (2008) Profit-based latency problems on the line. Oper. Res. Lett. 36(3):333–337.Crossref, Google Scholar
• [17] Coene S, Filippi C, Spieksma FC, Stevanato E (2013) Balancing profits and costs on trees. Networks 61(3):200–211.Crossref, Google Scholar
• [18] Cornuéjols G, Fonlupt J, Naddef D (1985) The traveling salesman problem on a graph and some related integer polyhedra. Math. Programming 33:1–27.Crossref, Google Scholar
• [19] Costa A, Cordeau JF, Laporte G (2006) Steiner tree problems with profits. Inform. Systems Oper. Res. 44(2):99–115.Google Scholar
• [20] Dumitrescu I, Boland N (2003) Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem. Networks Internat. J. 42(3):135–153.Google Scholar
• [21] Edmonds J (2003) Submodular functions, matroids, and certain polyhedra. Jünger M, Reinelt G, Rinaldi G, eds. Combinatorial Optimization — Eureka, You Shrink!, Lecture Notes in Computer Science, vol. 2570 (Springer, Berlin, Heidelberg), 11–26.Google Scholar
• [22] Feillet D, Dejax P, Gendreau M (2005) Traveling salesman problems with profits. Transportation Sci. 39(2):188–205.Link, Google Scholar
• [23] Frederickson GN, Guan D (1992) Preemptive ensemble motion planning on a tree. SIAM J. Comput. 21(6):1130–1152.Crossref, Google Scholar
• [24] Garcia A, Jodrá P, Tejel J (2002) A note on the traveling repairman problem. Networks Internat. J. 40(1):27–31.Google Scholar
• [25] Goemans MX, Williamson DP (1995) A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2):296–317.Crossref, Google Scholar
• [26] Goldengorin B (2009) Maximization of submodular functions: Theory and enumeration algorithms. Eur. J. Oper. Res. 198(1):102–112.Crossref, Google Scholar
• [27] Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1:169–197.Crossref, Google Scholar
• [28] Hamaguchi Sy, Katoh N (1998) A capacitated vehicle routing problem on a tree. Chwa KY, Ibarra OH, eds. Algorithms and Computation ISAAC 1998, Lecture Notes in Computer Science, vol. 1533 (Springer, Berlin, Heidelberg), 399–407.Google Scholar
• [29] Hanafi S, Mansini R, Zanotti R (2020) The multi-visit team orienteering problem with precedence constraints. Eur. J. Oper. Res. 282(2):515–529.Crossref, Google Scholar
• [30] Henchiri A, Bellalouna M, Khaznaji W (2014) A probabilistic traveling salesman problem: A survey. FedCSIS (Position Papers) (Citeseer, Princeton, NJ), 55–60.Crossref, Google Scholar
• [31] Herer YT (1990) Submodularity and the traveling salesman problem. Technical Report 915, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY.Google Scholar
• [32] Herer YT (1999) Submodularity and the traveling salesman problem. Eur. J. Oper. Res. 114:489–508.Crossref, Google Scholar
• [33] Iwata S (2003) A faster scaling algorithm for minimizing submodular functions. SIAM J. Comput. 32(4):833–840.Crossref, Google Scholar
• [34] Iwata S, Orlin JB (2009) A simple combinatorial algorithm for submodular function minimization. Proc. Twentieth Annual ACM-SIAM Symposium Discrete Algorithms, SODA ‘09 (Society for Industrial and Applied Mathematics, Philadelphia), 1230–1237.Google Scholar
• [35] Iwata S, Fleischer L, Fujishige S (2001) A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4):761–777.Crossref, Google Scholar
• [36] Jaillet P (1985) Probabilistic traveling salesman problems. PhD thesis, Massachusetts Institute of Technology, Boston.Google Scholar
• [37] Jaillet P, Odoni AR (1988) The probabilistic vehicle routing problem. Golden BL, Assad AA, eds. Vehicle Routing: Methods and Studies (North-Holland, Amsterdam), 293–318.Google Scholar
• [38] Jepsen MK, Petersen B, Spoorendonk S, Pisinger D (2014) A branch-and-cut algorithm for the capacitated profitable tour problem. Discrete Optim. 14:78–96.Crossref, Google Scholar
• [39] Johnson DS, Minkoff M, Phillips S (2000) The prize collecting Steiner tree problem: Theory and practice. Proc. Eleventh Annual ACM-SIAM Symposium Discrete Algorithms, SODA ‘00 (Society for Industrial and Applied Mathematics, Philadelphia), 760–769.Google Scholar
• [40] Johnson DS, Minkoff M, Phillips SJ (2000) The prize collecting Steiner tree problem: Theory and practice. ACM-SIAM Symp. Discrete Algorithms.Google Scholar
• [41] Karuno Y, Nagamochi H, Ibaraki T (1997) Vehicle scheduling on a tree with release and handling times. Ann. Oper. Res. 69(0):193–207.Crossref, Google Scholar
• [42] Klau GW, Ljubić I, Mutzel P, Pferschy U, Weiskircher R (2003) The fractional prize-collecting Steiner tree problem on trees. Di Battista G, Zwick U, eds. Algorithms - ESA 2003 (Springer Berlin Heidelberg, Berlin), 691–702.Crossref, Google Scholar
• [43] Labbé M, Laporte G, Mercure H (1991) Capacitated vehicle routing on trees. Oper. Res. 39(4):616–622.Link, Google Scholar
• [44] Laporte G, Louveaux FV, Mercure H (1994) A priori optimization of the probabilistic traveling salesman problem. Oper. Res. 42(3):543–549.Link, Google Scholar
• [45] Minieka E (1989) The delivery man problem on a tree network. Ann. Oper. Res. 18(1):261–266.Crossref, Google Scholar
• [46] Muslea I (1997) The very offline k-vehicle routing problem in trees. Proc. 17th Internat. Conf. Chilean Comput. Sci. Soc. (IEEE, Piscataway, NJ), 155–163.Google Scholar
• [47] Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14:265–294.Crossref, Google Scholar
• [48] Orlin JB (2009) A faster strongly polynomial time algorithm for submodular function minimization. Math. Programming 118(2):237–251.Crossref, Google Scholar
• [49] Schrijver A (2000) A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory, Ser. B. 80(2):346–355.Crossref, Google Scholar
• [50] Sitters R (2002) The minimum latency problem is np-hard for weighted trees. Cook WJ, Schulz AS, eds. Integer Programming Combin. Optim. 9th Internat. IPCO Conf., Cambridge, MA, May 27–29, 2002, Proceedings 9, (Springer, Berlin, Heidelberg), 230–239.Google Scholar
• [51] Toth P, Vigo D (2014) Vehicle Routing: Problems, Methods, and Applications (SIAM, Philadelphia).Crossref, Google Scholar
• [52] Wu BY (2000) Polynomial time algorithms for some minimum latency problems. Inform. Process. Lett. 75(5):225–229.Crossref, Google Scholar
• [53] Yu Q, Adulyasak Y, Rousseau LM, Zhu N, Ma S (2022) Team orienteering with time-varying profit. INFORMS J. Comput. 34(1):262–280.Link, Google Scholar
• [54] Zhang M, Wang J, Liu H (2017) The probabilistic profitable tour problem. Internat. J. Enterprise Inform. Systems 13(3):51–64.Crossref, Google Scholar