Traveling Salesman Problems with Profits

References

• Arora S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM (1998) 45(5):753–782Crossref, Google Scholar
• Arora S., Karakostas G. 2+ε approximation algorithm for the k-MST problem. Proc. 11th Annual ACM-SIAM Sympos. Discrete Algorithms (2000) (ACM Press, New York) 754–759Google Scholar
• Awerbuch B., Azar Y., Blum A., Vempala S. New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM J. Comput. (1998) 28(1):254–262Crossref, Google Scholar
• Balas E. The prize collecting traveling salesman problem. Networks (1989) 19(6):621–636Crossref, Google Scholar
• Balas E. The prize collecting traveling salesman problem. II: Polyhedral results. Networks (1995) 25(4):199–216Crossref, Google Scholar
• Balas E. New classes of efficiently solvable generalized traveling salesman problems. Ann. Oper. Res. (1999) 86:529–558Crossref, Google Scholar
• Balas E., Gutin G., Punnen A. The prize collecting traveling salesman problem and its applications. Traveling Salesman Problem and its Variations (2002) (Kluwer Academic Publishers, Dordrecht, The Netherlands) 663–695Google Scholar
• Balas E., Martin G.Roll-a-Round: Software Package for Scheduling the Rounds of a Rolling Mill (1985) (Balas and Martin Associates)Google Scholar
• Bauer P. The circuit polytope: Facets. Math. Oper. Res. (1997) 22(1):110–145Link, Google Scholar
• Bauer P., Linderoth J. T., Savelsbergh M. W. P. A branch and cut approach to the cardinality constrained circuit problem. (1998) . Technical report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GAGoogle Scholar
• Bienstock D., Goemans M., Simchi-Levi D., Williamson D. A note on the prize collecting traveling salesman problem. Math. Programming (1993) 59:413–420Crossref, Google Scholar
• Blum A., Ravi R., Vempala S. Constant-factor approximation algorithm for the k-MST problem. J. Comput. System Sci. (1999) 58(1):101–108Crossref, Google Scholar
• Boctor F. F., Laporte G., Renaud J. Heuristics for the traveling purchaser problem. Comput. Oper. Res. (2003) 30:491–504Crossref, Google Scholar
• Bookbinder J. H., Sural H. Vehicle routing with unrestricted backhauls. INFORMS Cincinnati Conf. (1999) OHGoogle Scholar
• Brideau R. J. III., Cavalier T. M. The maximum collection problem with time dependent rewards. TIMS Internat. Conf. (1994) Anchorage, AKGoogle Scholar
• Butt S. E., Cavalier T. M. A heuristic for the multiple tour maximum collection problem. Comput. Oper. Res. (1994) 21(1):101–111Crossref, Google Scholar
• Butt S. E., Ryan D. M. An optimal solution procedure for the multiple tour maximum collection problem using column generation. Comput. Oper. Res. (1999) 26(4):427–441Crossref, Google Scholar
• Caramia M., Ricciardi N., Scozzari A., Storchi G. Tourist flows organization in an artistic town. Proc. CUPUM’99: Comput. Urban Planning Urban Management (1999) Venice, ItalyGoogle Scholar
• Chao I.-M., Golden B. L., Wasil E. A. A fast and effective heuristic for the orienteering problem. Eur. J. Oper. Res. (1996a) 88(3):475–489Crossref, Google Scholar
• Chao I.-M., Golden B. L., Wasil E. A. The team orienteering problem. Eur. J. Oper. Res. (1996b) 88(3):464–474Crossref, Google Scholar
• Coullard C. R., Pulleyblank W. R. On cycle cones and polyhedra. Linear Algebra Its Appl. (1989) 114/115:613–640Crossref, Google Scholar
• Cowling P., Sciomachen A. Optimization in steel hot rolling. Optimization Industry (1995) (Wiley, New York) 55–66Google Scholar
• Current J., ReVelle C. S., Cohon J. L. Efficient algorithms for solving the shortest covering path problem. Transportation Sci. (1994) 28:317–327Link, Google Scholar
• Deitch R., Ladany S. P. The one-period bus routing problem: Solved by an effective heuristic for the orienteering tour problem and improvement algorithm. Eur. J. Oper. Res. (2000) 127:69–77Crossref, Google Scholar
• Dell’Amico M., Maffioli F., Sciomachen A. A Lagrangian heuristic for the prize-collecting travelling salesman problem. Ann. Oper. Res. (1998) 81:289–305Crossref, Google Scholar
• Dell’Amico M., Maffioli F., Värbrand P. On prize-collecting tours and the asymmetric travelling salesman problem. Internat. Trans. Oper. Res. (1995) 2(3):297–308Crossref, Google Scholar
• Diaby M., Ramesh R. The distribution problem with carrier service: A dual based penalty approach. ORSA J. Comput. (1995) 7(1):24–35Link, Google Scholar
• Dueck G. New optimization heuristics: The great deluge algorithm and the record-to-record travel. J. Comput. Physics (1993) 104(1):86–92Crossref, Google Scholar
• Dunn J. S. Scheduling underway replenishment as a generalized orienteering problem. (1992) . Unpublished Master’s thesis, Naval Postgraduate School, Monterey, CAGoogle Scholar
• Ehrgott M. Approximation algorithms for combinatorial multicriteria optimization problems. Internat. Trans. Oper. Res. (2000) 7(1):5–31Crossref, Google Scholar
• Erkut E., Zhang J. The maximum collection problem with time-dependent rewards. Naval Res. Logist. (1996) 43(5):749–763Crossref, Google Scholar
• Feillet D.Problèmes de tournées avec gains: Étude et application au transport inter-usines (2001) . Unpublished doctoral dissertation, Laboratoire Productique Logistique, École Centrale ParisGoogle Scholar
• Feillet D., Dejax P., Gendreau M., Gueguen C. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. (2003) . Technical report, Laboratoire Informatique d’Avignon, Université d’Avignon, FranceGoogle Scholar
• Fischetti M., Toth P., Golden B. L., Assad A. A. An additive approach for the optimal solution of the prize-collecting traveling salesman problem. Vehicle Routing: Methods and Studies (1988) (Elsevier Science Publishers, B.V.) 319–343Google Scholar
• Fischetti M., Salazar González J. J., Toth P. A branch-and-cut algorithm for the generalized traveling salesman problem. Oper. Res. (1997) 45(3):378–394Link, Google Scholar
• Fischetti M., Salazar González J. J., Toth P. Solving the orienteering problem through branch-and-cut. INFORMS J. Comput. (1998) 10(2):133–148Link, Google Scholar
• Fischetti M., Salazar González J. J., Toth P., Gutin G., Punnen A. The generalized traveling salesman and orienteering problems. Traveling Salesman Problem and its Variations (2002) (Kluwer Academic Publishers, Dordrecht, The Netherlands) 663–695Google Scholar
• Fomin F. V., Lingas A. Approximation algorithms for time-dependent orienteering. Inform. Processing Lett. (2002) 83:57–62Crossref, Google Scholar
• Gendreau M., Hertz A., Laporte G. New insertion and postoptimization procedures for the traveling salesman problem. Oper. Res. (1992) 40:1086–1094Link, Google Scholar
• Gendreau M., Laporte G., Semet F. The covering tour problem. Oper. Res. (1997) 45:568–576Link, Google Scholar
• Gendreau M., Laporte G., Semet F. A branch-and-cut algorithm for the undirected selective traveling salesman problem. Networks (1998a) 32:263–273Crossref, Google Scholar
• Gendreau M., Laporte G., Semet F. A tabu search heuristic for the undirected selective traveling salesman problem. Eur. J. Oper. Res. (1998b) 106:539–545Crossref, Google Scholar
• Gensch D. H. An industrial application of the traveling salesman subtour problem. AIIE Trans. (1978) 10(4):362–370Crossref, Google Scholar
• Ghiani G., Improta G. An efficient transformation of the generalized vehicle routing problem. Eur. J. Oper. Res. (2000) 122:11–17Crossref, Google Scholar
• Goemans M. X., Williamson D. A general approximation technique for constrained forest problems. SIAM J. Comput. (1995) 24(2):296–317Crossref, Google Scholar
• Golden B. L., Assad A., Dahl R. Analysis of a large scale vehicle routing problem with an inventory component. Large Scale Systems (1984) 7:181–190Google Scholar
• Golden B. L., Levy L., Vohra R. The orienteering problem. Naval Res. Logist. (1987) 34(3):307–318Crossref, Google Scholar
• Golden B. L., Storchi G., Levy L. A time-relaxed version of the orienteering problem. (1986) . Technical Report Series MS/S 86-014, College of Business and Management, University of Maryland, College Park, MDGoogle Scholar
• Golden B. L., Wang Q., Liu L. A multifaceted heuristic for the orienteering problem. Naval Res. Logist. (1988) 35:359–366Crossref, Google Scholar
• Golden B. L., Wang Q., Sun X. A neural network solution to the generalized orienteering problem. INFORMS Dallas Conf. (1997) Dallas, TXGoogle Scholar
• Göthe-Lundgren M., Jörnsten K., Värbrand P. On the nucleolus of the basic vehicle routing game. Math. Programming (1996) 72:83–100Crossref, Google Scholar
• Göthe-Lundgren M., Maffioli F., Värbrand P. A Lagrangian decomposition approach for a prize collecting traveling salesman type problem. (1995) . Technical Report LiTH-MATH-R-1995-10, Linköping Institute of Technology, Linköping, SwedenGoogle Scholar
• Gueguen C.Méthodes de résolution exacte pour les problèmes de tournées de véhicules (1999) . Unpublished doctoral dissertation, Laboratoire Productique Logistique, École Centrale ParisGoogle Scholar
• Gutin G., Punnen A.Traveling Salesman Problem and Its Variations (2002) (Kluwer Academic Publishers, Dordrecht, The Netherlands) Google Scholar
• Helmberg C. The m-cost ATSP. Lecture Notes Comput. Sci. (1999) 1610:242–258Crossref, Google Scholar
• Johnston M. R.Dynamic routing with competition: Foundations and strategies (1999) . Unpublished doctoral dissertation, Massey University, Auckland, New ZealandGoogle Scholar
• Kabadi S. N., Punnen A. Prize-collecting traveling salesman problem. INFORMS Washington Conf. (1996) Washington, D.C.Google Scholar
• Kantor M. G., Rosenwein M. B. The orienteering problem with time windows. J. Oper. Res. Soc. (1992) 43(6):629–635Crossref, Google Scholar
• Kataoka S., Morito S. An algorithm for the single constraint maximum collection problem. J. Oper. Res. Soc. Japan (1988) 31(4):515–530Google Scholar
• Kataoka S., Yamada T., Morito S. Minimum directed 1-subtree relaxation for score orienteering problem. Eur. J. Oper. Res. (1998) 104:139–153Crossref, Google Scholar
• Keller C. P. Multiobjective routing through space and time: The MVP and TDVP problems. (1985) . Unpublished doctoral dissertation, Department of Geography, The University of Western Ontario, London, Ontario, CanadaGoogle Scholar
• Keller C. P. Algorithms to solve the orienteering problem: A comparison. Eur. J. Oper. Res. (1989) 41:224–231Crossref, Google Scholar
• Keller C. P., Goodchild M. The multiobjective vending problem: A generalization of the traveling salesman problem. Environ. Planning B: Planning Design (1988) 15:447–460Crossref, Google Scholar
• Kubo M., Kasugai H. On symmetric subtour problems. Japan J. Indust. Appl. Math. (1992) 9:383–396Crossref, Google Scholar
• Labbé M., Laporte G., Rodríguez-Martín I., Crainic T. G., Laporte G. Path, tree and cycle location. Fleet Management and Logistics (1998) (Kluwer Academic Publishers, Norwell, MA) 187–204Crossref, Google Scholar
• Laporte G., Martello S. The selective traveling salesman problem. Discrete Appl. Math. (1990) 26:193–207Crossref, Google Scholar
• Laporte G., Mercure H., Nobert Y. Optimal tour planning with specified nodes. R.A.I.R.O. Recherche Opérationnelle (1984) 18(3):203–210Google Scholar
• Leifer A. C., Rosenwein M. B. Strong linear programming relaxations for the orienteering problem. Eur. J. Oper. Res. (1994) 73:517–523Crossref, Google Scholar
• Liang Y.-C., Smith A. E. An ant colony approach to the orienteering problem. (2001) . Technical report. Department of Industrial and Systems Engineering, Auburn University, Auburn, ALGoogle Scholar
• Lin S. Computer solutions of the traveling salesman problem. Bell System Comput. J. (1965) 44:2245–2269Crossref, Google Scholar
• Lopez L., Carter M. W., Gendreau M. The hot strip mill production scheduling problem: A tabu search approach. Eur. J. Oper. Res. (1998) 106(2–3):317–335Crossref, Google Scholar
• Millar H. H., Kiragu M. A time-based formulation and upper bounding scheme for the selective traveling salesperson problem. J. Oper. Res. Soc. (1997) 48(5):511–518Crossref, Google Scholar
• Mittenthal J., Noon C. E. Insert/delete heuristic for the travelling salesman subset-tour problem with one additional constraint. J. Oper. Res. Soc. (1992) 43(3):277–283Crossref, Google Scholar
• Moser H. D. Jr. Scheduling and routing tactical aerial reconnaissance vehicles. (1990) . Unpublished Master’s thesis, Naval Postgraduate School, Monterey, CAGoogle Scholar
• Nocito J. B. Heuristic solutions to the two-player orienteering problem. (1993) . Unpublished Master’s thesis, University of Maryland, College Park, MDGoogle Scholar
• Noon C. E., Mittenthal J., Pillai R. A TSSP+1 decomposition strategy for the vehicle routing problem. Eur. J. Oper. Res. (1994) 79:524–536Crossref, Google Scholar
• Pearn W. L., Chien R. C. Improved solutions for the traveling purchaser problem. Comput. Oper. Res. (1998) 25(11):879–885Crossref, Google Scholar
• Pekny J. F., Miller D. L. An exact parallel algorithm for the resource constrained travelling salesman problem with application to scheduling with an aggregate deadline. ACM 18th Annual Comput. Sci. Conf. (1990) (ACM Press, New York) 208–214Google Scholar
• Pekny J. F., Miller D. L., McRae G. J. An exact parallel algorithm for scheduling when production costs depend on consecutive system states. Comput. Chem. Engrg. (1990) 14:1009–1023Crossref, Google Scholar
• Ramesh R., Brown K. M. An efficient four-phase heuristic for the generalized orienteering problem. Comput. Oper. Res. (1991) 18(2):151–165Crossref, Google Scholar
• Ramesh R., Yoon Y.-S., Karwan M. H. An optimal algorithm for the orienteering tour problem. ORSA J. Comput. (1992) 4(2):155–165Link, Google Scholar
• Renaud J., Boctor F. F. An efficient composite heuristic for the symmetric generalized traveling salesman problem. Eur. J. Oper. Res. (1998) 108(3):571–584Crossref, Google Scholar
• ReVelle C. S., Laporte G. New directions in plant location. Stud. Locational Anal. (1993) 5:31–58Google Scholar
• Singh K. N., van Oudheusden D. L. A branch and bound algorithm for the traveling purchaser problem. Eur. J. Oper. Res. (1997) 97:571–579Crossref, Google Scholar
• Srinivasan V., Thompson G. L. An operator theory of parametric programming for the transportation problem—I. Naval Res. Logist. Quart. (1972a) 19:205–226Crossref, Google Scholar
• Srinivasan V., Thompson G. L. An operator theory of parametric programming for the transportation problem—II. Naval Res. Logist. Quart. (1972b) 19:227–252Crossref, Google Scholar
• Tasgetiren F. M., Smith A. E. A genetic algorithm for the orienteering problem. Proc. 2000 Congress Evolutionary Comput (2000) San Diego, CA:1190–1195Crossref, Google Scholar
• Toth P., Vigo D.The Vehicle Routing Problem (2001) 9(SIAM, Philadelphia, PA) Google Scholar
• Tsiligirides T. Heuristic methods applied to orienteering. J. Oper. Res. Soc. (1984) 35(9):797–809Crossref, Google Scholar
• Volgenant T., Jonker R. On some generalizations of the traveling-salesman problem. J. Oper. Res. Soc. (1987) 38(11):1073–1079Crossref, Google Scholar
• Voss S. Dynamic tabu search strategies for the traveling purchaser problem. Ann. Oper. Res. (1996) 63:253–275Crossref, Google Scholar
• Wang Q., Sun X., Golden B. L. Using artificial neural network to solve generalized orienteering problems. Proc. 1996 Artificial Neural Networks Engrg. (1996) St. Louis, MOGoogle Scholar
• Wang Q., Sun X., Golden B. L., Jia J. Using artificial neural networks to solve the orienteering problem. Ann. Oper. Res. (1995) 61:111–120Crossref, Google Scholar
• Wren A., Holliday A. Computer scheduling of vehicles from one or more depots to a number of delivery points. Oper. Res. Quart. (1972) 23:333–344Crossref, Google Scholar
• Wu T. Optimization models for underway replenishment of a dispersed carrier battlegroup. (1992) . Unpublished Master’s thesis, Naval Postgraduate School, Monterey, CAGoogle Scholar