The Profitable Arc Tour Problem: Solution with a Branch-and-Price Algorithm

References

• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows: Theory, Algorithms, and Applications (1993) (Prentice Hall, Englewood Cliffs, NJ) Google Scholar
• Balas E. The prize collecting traveling salesman problem. Networks (1989) 19(6):621–636Crossref, Google Scholar
• Barnhart C., Hane C. A., Vance P. H. Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Oper. Res. (2000) 48(2):318–326Link, Google Scholar
• Barnhart C., Johnson E. L., Nemhauser G. L., Savelsbergh M. W. P., Vance P. H. Branch-and-price: Column generation for solving huge integer programs. Oper. Res. (1998) 46(3):316–329Link, Google Scholar
• Belling-Seib K., Mevert P., Muller C. Network flow problems with one side constraint: A comparison of three solution methods. Comput. Oper. Res. (1988) 15(4):381–394Crossref, Google Scholar
• Boland N. L., Clarke L. W., Nemhauser G. L. Asymmetric traveling salesman problem with replenishment arcs. Eur. J. Oper. Res. (2000) 123(2):408–427Crossref, 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
• Cohen E., Megiddo N. Algorithms and complexity analysis for some flow problems. Algorithmica (1994) 11:320–340Crossref, 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(1):69–77Crossref, Google Scholar
• Desaulniers G., Desrosiers J., Ioachim I., Solomon M. M., Soumis F., Villeneuve D., Laporte C. T., Laporte G. A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. Fleet Management and Logistics (1998a) (Kluwer Academic Publishers, Norwell, MA) 57–93Crossref, Google Scholar
• Desaulniers G., Lavigne J., Soumis F. Multi-depot vehicle scheduling problems with time windows and waiting costs. Eur. J. Oper. Res. (1998b) 111(3):479–494Crossref, Google Scholar
• Desrochers M., Desrosiers J., Solomon M. M. A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. (1992) 40(2):342–354Link, Google Scholar
• Desrosiers J., Dumas Y., Solomon M. M., Soumis F., Ball M., Magnanti T., Monma C., Nemhauser G. Time constrained routing and scheduling. Handbooks in OR and MS (1995) 8(Elsevier Science Publishers B.V., Amsterdam, North-Holland) Google Scholar
• Eiselt H. A., Gendreau M., Laporte G. Arc routing problems. Part II: The rural postman problem. Oper. Res. (1995) 43(3):399–414Link, Google Scholar
• EURODECISIONLPToolKit, User’s Guide and Technical Reference (1998) 3rd ed.(Eurodécision, Versailles, France) Google Scholar
• Feillet D. Problèmes de tournées avec gains: Ètude et application au transport inter-usines. (2001) . Doctoral dissertation, Laboratoire Productique Logistique, École Centrale ParisGoogle Scholar
• Feillet D., Dejax P., Gendreau M. Planification tactique de transport de marchandises interusine. J. Européen des Systèmes Automatisés (2002) 36(1):149–168Google Scholar
• Feillet D., Dejax P., Gendreau M. Traveling salesman problems with profits. Transportation Sci. (2004a) 39(4):540–553Google 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. Networks (2004b) 44(3):216–229Crossref, Google Scholar
• Fischetti M., Toth P., Golden B., Assad A. An additive approach for the optimal solution of the prize-collecting travelling salesman problem. Vehicle Routing: Methods and Studies (1988) (Elsevier Science Publishers B.V., Amsterdam, North-Holland) 319–343Google Scholar
• Ford L. R., Fulkerson D. R. Maximum flow through a network. Canadian J. Math. (1956) 8:399–404Crossref, Google Scholar
• Fortz B., Labbé M., Maffioli F. Solving the two-connected network with bounded meshes problem. Oper. Res. (2000) 48(6):866–877Link, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) 50(Freeman, San Francisco, CA) Google Scholar
• Gueguen C. Méthodes de résolution exacte pour les problèmes de tournées de véhicules. (1999) . Doctoral dissertation, Laboratoire Productique Logistique, École Centrale ParisGoogle Scholar
• Hochbaum D. S., Olinick E. V. The bounded cycle cover problem. INFORMS J. Comput. (2001) 13(2):104–119Link, Google Scholar
• ILOGILOG, Using the CPLEX Callable Library (1998) 6th ed.(ILOG Inc., CPLEX Division, Incline Village) Google Scholar
• Kennington J. L., Nair V. S. S., Rahman M. H. Optimization-based algorithms for finding minimal cost ring covers in survivable networks. Comput. Optim. Appl. (1999) 14:219–230Crossref, Google Scholar
• Labbé M., Laporte G., Soriano P. Covering a graph with cycles. Comput. Oper. Res. (1998) 25(6):499–504Crossref, Google Scholar
• Laporte G. Modeling and solving several classes of arc routing problems as traveling salesman problems. Comput. Oper. Res. (1997) 24(11):1057–1061Crossref, Google Scholar
• Mathies S., Mevert P. A hybrid algorithm for solving network flow problems with side constraints. Comput. Oper. Res. (1998) 25(9):745–756Crossref, Google Scholar
• Patterson R., Rolland E. The cardinality constrained covering traveling salesman problem. Comput. Oper. Res. (2003) 30:97–116Crossref, Google Scholar
• Savelsbergh M., Sol M. Drive: Dynamic routing of independent vehicles. Oper. Res. (1998) 46(4):474–490Link, Google Scholar
• Thomassen C. On the complexity of finding a minimum cycle cover of a graph. SIAM J. Comput. (1997) 26(3):675–677Crossref, Google Scholar
• Vanderbeck F. On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper. Res. (2000) 48(1):111–128Link, Google Scholar
• Yan S. Approximating reduced costs under degeneracy in a network flow problem with side constraints. Networks (1996) 27(4):267–278Crossref, Google Scholar