LOWER BOUNDS FOR A VEHICLE ROUTING PROBLEM WITH MOTION CONSTRAINTS

Satyanarayana G. Manyam, Sivakumar Rathinam, Swaroop Darbha, and Karl J. Obermeyer

References

  1. [1] G. Dantzig, R. Fulkerson, and S. Johnson, Solution of a large-scale traveling-salesman problem, Journal of the Operations Research Society of America, 1954, 393–410.
  2. [2] S. Lin and B.W. Kernighan, An effective heuristic algorithm for the traveling-salesman problem, Operations Research, 21(2), 1973, 498–516.
  3. [3] E.L. Lawler, J.K. Lenstra, A.R. Kan, and D.B. Shmoys, The traveling salesman problem: A guided tour of combinatorial optimization, vol. 3 (Chichester: Wiley, 1985).
  4. [4] M. Padberg and G. Rinaldi, A branch-and-cut algorithmfor the resolution of large-scale symmetric traveling salesman problems, SIAM Review, 33(1), 1991, 60–100.
  5. [5] G. Gutin and A.P. Punnen, Travleing salesman problem and its variations (Dordrecht, The Netherlands: Kluwer Academic Publishers, 2002).
  6. [6] G. Reinelt, The traveling salesman problem – Computational solutions for TSP applications. Lecture notes in computer science, No. 840 (Berlin, Heidelberg: Springer-Verlag, 1994).
  7. [7] D. Applegate, R.E. Bixby, V. Chvatal, and W.J. Cook, The traveling salesman problem – A computational study (Princeton, NJ: Princeton University Press, 2006).
  8. [8] L.E. Dubins, On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents, American Journal of Mathematics, 79, July 1957, 497–516.
  9. [9] W. Malik, S. Rathinam, S. Darbha, and D. Jeffcoat, Combinatorial motion planning of multiple vehicle systems, Proc. 45th IEEE Conf. on Decision and Control, 2006, 5299–5304.
  10. [10] S. Rathinam, R. Sengupta, and S. Darbha, Resource allocation algorithm for multivehicle systems with nonholonomic constraints, IEEE Transactions on Automation Science and Engineering, 4(1), 2007, 98–104.
  11. [11] K. Savla, E. Frazzoli, and F. Bullo, On the point to point and traveling salesman problem for Dubins’ vehicle, Proc. American Control Conf., 2005, 786–791.
  12. [12] S. Yadlapalli, W. Malik, S. Darbha, and M. Pachter,A lagrangian based algorithm for a multiple depot, multipletraveling salesman problem, Nonlinear Analysis: Real WorldApplications, 10, August 2009, 1990–1999.
  13. [13] P. Oberlin, S. Rathinam, and S. Darbha, Today’s traveling salesman problem, IEEE Robotics and Automation Magazine, 17, December 2010, 70–77.
  14. [14] K. Helsgaun, An effective implementation of the lin-kernighan traveling salesman heuristic, European Journal of Operations Research, 126(1), 2000, 106–130.
  15. [15] Z. Tang and U. Ozguner, Motion planning for multitarget surveillance with mobile sensor agents, IEEE Transactions on Robotics, 21(5), 2005, 898–908.
  16. [16] H. Chitsaz and S. LaValle, Time-optimal paths for a dubins airplane, 46th IEEE Conf. on Decision and Control, 2007, 2379–2384.
  17. [17] C. Tomlin, I. Mitchell, and R. Ghosh, Safety verification of conflict resolution manoeuvres, IEEE Transactions on Intelligent Transportation Systems, 2(2), 2001, 110–120.
  18. [18] S.M. LaValle, Planning algorithms (Cambridge: Cambridge University Press, 2006).
  19. [19] G. Nemhauser and L. Wolsey, Integer and combinatorial optimization (Hoboken, NJ: Wiley-Interscience Publication, 1988).
  20. [20] C.E. Noon and J.C. Bean, An efficient transformation of the generalized traveling salesman problem, INFOR, 31(1), 1993, 39–44.

Important Links:

Go Back