The Vehicle Routing Problem with Floating Targets: Formulation and Solution Approaches

References

• Agharkar P, Bullo F (2014) Vehicle routing algorithms to intercept escaping targets. Amer. Control Conf. (ACC), 2014 (IEEE, Piscataway, NJ), 952–957.Google Scholar
• Aïvodji UM, Gambs S, Huguet MJ, Killijian MO (2015) Privacy preserving carpooling. Odysseus 2015—6th Internat. Workshop Freight Transportation Logist., Ajaccio, France.Google Scholar
• Asahiro Y, Horiyama T, Makino K, Ono H, Sakuma T, Yamashita M (2006) How to collect balls moving in the Euclidean plane. Discrete Appl. Math. 154(16):2247–2262.Crossref, Google Scholar
• Baldacci R, Bartolini E, Mingozzi A (2011) An exact algorithm for the pickup and delivery problem with time windows. Oper. Res. 59(2):414–426.Link, Google Scholar
• Baldacci R, Maniezzo V, Mingozzi A (2004) An exact method for the carpooling problem based on Lagrangean column generation. Oper. Res. 52(3):422–439.Link, Google Scholar
• Barnes JW, Wiley VD, Moore JT, Ryer DM (2004) Solving the aerial fleet refueling problem using group theoretic tabu search. Math. Comput. Model. 39(6):617–640.Crossref, Google Scholar
• Bit-Monnot A, Artigues C, Huguet MJ, Killijian MO (2013) Carpooling: The 2 synchronization points shortest paths problem. 13th Workshop Algorithmic Approaches Transportation Model., Optim., Systems, Sophia Antipolis, France.Google Scholar
• Bopardikar SD, Smith SL, Bullo F (2011) On vehicle placement to intercept moving targets. Automatica 47(9):2067–2074.Crossref, Google Scholar
• Bopardikar SD, Smith SL, Bullo F, Hespanha JP (2009) Dynamic vehicle routing with moving demands-Part I: Low speed demands and high arrival rates. Amer. Control Conf., 2009. ACC’09 (IEEE, Piscataway, NJ), 1454–1459.Google Scholar
• Bopardikar SD, Smith SL, Bullo F, Hespanha JP (2010) Dynamic vehicle routing for translating demands: Stability analysis and receding-horizon policies. IEEE Trans. Automatic Control 55(11):2554–2569.Crossref, Google Scholar
• Bruck BP, Incerti V, Iori M, Vignoli M (2015) On the development of a practical carpooling application. Odysseus 2015—6th Internat. Workshop Freight Transportation Logist., Ajaccio, France.Google Scholar
• Choubey NS (2013) Moving target travelling salesman problem using genetic algorithm. Internat. J. Comput. Appl. 70(2):975–8887.Google Scholar
• Coelho LC, Laporte G (2013) The exact solution of several classes of inventory-routing problems. Comput. Oper. Res. 40(2):558–565.Crossref, Google Scholar
• Cordeau JF (2006) A branch-and-cut algorithm for the dial-a-ride problem. Oper. Res. 54(3):573–586.Link, Google Scholar
• Dantzig GB, Ramser JH (1959) The truck dispatching problem. Management Sci. 6(1):80–91.Link, Google Scholar
• Desrochers M, Desrosiers J, Solomon M (1992) A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. 40(2):342–354.Link, Google Scholar
• Dumas Y, Desrosiers J, Gelinas E, Solomon MM (1995) An optimal algorithm for the traveling salesman problem with time windows. Oper. Res. 43(2):367–371.Link, Google Scholar
• Elhedhli S, Li L, Gzara M, Naoum-Sawaya J (2011) A branch-and-price algorithm for the bin packing problem with conflicts. INFORMS J. Comput. 23(3):404–415.Link, Google Scholar
• Fischetti M, González JJS, Toth P (1995) Experiments with a multi-commodity formulation for the symmetric capacitated vehicle routing problem. Proc. 3rd Meeting EURO Working Group Transportation, Barcelona, Spain, 169–173.Google Scholar
• Fisher ML (2004) The Lagrangian relaxation method for solving integer programming problems. Management Sci. 50(12_supplement):1861–1871.Link, Google Scholar
• Fisher ML, Jörnsten KO, Madsen OB (1997) Vehicle routing with time windows: Two optimization algorithms. Oper. Res. 45(3):488–492.Link, Google Scholar
• Frangioni A (2005) About Lagrangian methods in integer optimization. Ann. Oper. Res. 139(1):163–193.Crossref, Google Scholar
• Gendreau M, Hertz A, Laporte G, Stan M (1998) A generalized insertion heuristic for the traveling salesman problem with time windows. Oper. Res. 46(3):330–335.Link, Google Scholar
• Gutin G, Punnen AP (2002) The Traveling Salesman Problem and Its Variations, Vol. 12 (Springer Science & Business Media, Berlin).Google Scholar
• Hammar N (2002) Approximation results for kinetic variants of TSP. Discrete Comput. Geometry 27(4):635–651.Crossref, Google Scholar
• Helvig CS, Robins G, Zelikovsky A (2003) The moving-target traveling salesman problem. J. Algorithms 49(1):153–174.Crossref, Google Scholar
• Jiang Q, Sarker R, Abbass H (2005) Tracking moving targets in the non-stationary travelling salesman problem. Complexity Internat. 11:171–179.Google Scholar
• Kohl N, Madsen OB (1997) An optimization algorithm for the vehicle routing problem with time windows based on Lagrangian relaxation. Oper. Res. 45(3):395–406.Link, Google Scholar
• Laporte G (1992) The traveling salesman problem: An overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(2):231–247.Crossref, Google Scholar
• Mallick M, Vo BN, Kirubarajan T, Arulampalam S (2013) Introduction to the issue on multitarget tracking. IEEE J. Selected Topics Signal Processing 7(3):373–375.Crossref, Google Scholar
• Mehrotra A, Trick MA (1996) A column generation approach for graph coloring. INFORMS J. Comput. 8(4):344–354.Link, Google Scholar
• Mingozzi A, Bianco L, Ricciardelli S (1997) Dynamic programming strategies for the traveling salesman problem with time window and precedence constraints. Oper. Res. 45(3):365–377.Link, Google Scholar
• Ozbaygin G, Karasan OE, Savelsbergh M, Yaman H (2017) A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations. Transportation Res. Part B: Method. 100(June):115–137.Crossref, Google Scholar
• Reyes D, Savelsbergh M, Toriello A (2017) Vehicle routing with roaming delivery locations. Transportation Res. Part C: Emerging Tech. 80(July):71–91.Crossref, Google Scholar
• Ryan DM, Foster BA (1981) An integer programming approach to scheduling. Wren A, ed. Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling (North-Holland, Amsterdam), 269–280.Google Scholar
• Smith SL, Bopardikar SD, Bullo F (2009a) A dynamic boundary guarding problem with translating targets. Proc. 48th IEEE Conf. Decision Control (CDC) Held Jointly 2009 28th Chinese Control Conf., Shanghai, China, 8543–8548.Google Scholar
• Smith SL, Bopardikar SD, Bullo F, Hespanha JP (2009b) Dynamic vehicle routing with moving demands-Part II: High speed demands or low arrival rates. Amer. Control Conf., 2009. ACC’09, St. Louis, 1466–1471.Google Scholar
• Stieber A, Fügenschuh A (2016) Variants in modeling time aspects for the multiple traveling salesmen problem with moving targets. Optim. Online, http://www.optimization-online.org/DB_HTML/2016/06/5518.html.Google Scholar
• Stieber A, Fügenschuh A, Epp M, Knapp M, Rothe H (2015) The multiple traveling salesmen problem with moving targets. Optim. Lett. 9(8):1569–1583.Crossref, Google Scholar
• Sundar K, Rathinam S (2013) Algorithms for routing an unmanned aerial vehicle in the presence of refueling depots. CoRR abs/1304.0494, http://arxiv.org/abs/1304.0494.Google Scholar
• Thomas PR, Bhandari U, Bullock S, Richardson TS, du Bois JL (2014) Advances in air to air refuelling. Progress Aerospace Sci. 71(November):14–35.Crossref, Google Scholar
• Toth P, Vigo D (2014) Vehicle Routing: Problems, Methods, and Applications, 2nd ed. (SIAM, Philadelphia).Crossref, Google Scholar
• Varone S, Aissat K (2015) Multi-modal transportation with public transport and ride-sharing. ICEIS 2015—17th Internat. Conf. Enterprise Inform. Systems, Barcelona, Spain.Google Scholar