article

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

Authors:

Claudio Gambella,

Joe Naoum-Sawaya,

Bissan GhaddarAuthors Info & Claims

INFORMS Journal on Computing, Volume 30, Issue 3

Pages 554 - 569

https://doi.org/10.1287/ijoc.2017.0800

Published: 01 August 2018 Publication History

Abstract

This paper addresses a generalization of the vehicle routing problem in which the pick-up locations of the targets are nonstationary. We refer to this problem as the vehicle routing problem with floating targets and the main characteristic is that targets are allowed to move from their initial home locations while waiting for a vehicle. This problem models new applications in drone routing, ridesharing, and logistics where a vehicle agrees to meet another vehicle or a customer at a location that is away from the designated home location. We propose a Mixed Integer Second Order Cone Program MISOCP formulation for the problem, along with valid inequalities for strengthening the continuous relaxation. We further exploit the problem structure using a Lagrangian decomposition and propose an exact branch-and-price algorithm. Computational results on instances with varying characteristics are presented and the results are compared to the solution of the full problem using CPLEX. The proposed valid inequalities reduce the computational time of CPLEX by up to 30% on average while the proposed branch and price is capable of solving instances where CPLEX fails in finding the optimal solution within the imposed time limit.

References

[1]

Agharkar P, Bullo F (2014) Vehicle routing algorithms to intercept escaping targets. Amer. Control Conf. (ACC), 2014 (IEEE, Piscataway, NJ), 952-957.

[2]

Aïvodji UM, Gambs S, Huguet MJ, Killijian MO (2015) Privacy preserving carpooling. Odysseus 2015--6th Internat. Workshop Freight Transportation Logist., Ajaccio, France.

[3]

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.

Digital Library

[4]

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.

Digital Library

[5]

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.

Digital Library

[6]

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.

Digital Library

[7]

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.

[8]

Bopardikar SD, Smith SL, Bullo F (2011) On vehicle placement to intercept moving targets. Automatica 47(9):2067-2074.

Digital Library

[9]

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.

[10]

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.

[11]

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.

[12]

Choubey NS (2013) Moving target travelling salesman problem using genetic algorithm. Internat. J. Comput. Appl. 70(2):975-8887.

[13]

Coelho LC, Laporte G (2013) The exact solution of several classes of inventory-routing problems. Comput. Oper. Res. 40(2):558-565.

Digital Library

[14]

Cordeau JF (2006) A branch-and-cut algorithm for the dial-a-ride problem. Oper. Res. 54(3):573-586.

Digital Library

[15]

Dantzig GB, Ramser JH (1959) The truck dispatching problem. Management Sci. 6(1):80-91.

Digital Library

[16]

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.

[17]

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.

Digital Library

[18]

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.

Digital Library

[19]

Fischetti M, González JJS, Toth P (1995) Experiments with a multicommodity formulation for the symmetric capacitated vehicle routing problem. Proc. 3rd Meeting EURO Working Group Transportation, Barcelona, Spain, 169-173.

[20]

Fisher ML (2004) The Lagrangian relaxation method for solving integer programming problems. Management Sci. 50(12 _supplement):1861-1871.

[21]

Fisher ML, Jörnsten KO, Madsen OB (1997) Vehicle routing with time windows: Two optimization algorithms. Oper. Res. 45(3):488-492.

Digital Library

[22]

Frangioni A (2005) About Lagrangian methods in integer optimization. Ann. Oper. Res. 139(1):163-193.

[23]

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.

Digital Library

[24]

Gutin G, Punnen AP (2002) The Traveling Salesman Problem and Its Variations, Vol. 12 (Springer Science & Business Media, Berlin).

[25]

Hammar N (2002) Approximation results for kinetic variants of TSP. Discrete Comput. Geometry 27(4):635-651.

Digital Library

[26]

Helvig CS, Robins G, Zelikovsky A (2003) The moving-target traveling salesman problem. J. Algorithms 49(1):153-174.

[27]

Jiang Q, Sarker R, Abbass H (2005) Tracking moving targets in the non-stationary travelling salesman problem. Complexity Internat. 11:171-179.

[28]

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.

Digital Library

[29]

Laporte G (1992) The traveling salesman problem: An overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(2): 231-247.

[30]

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.

[31]

Mehrotra A, Trick MA (1996) A column generation approach for graph coloring. INFORMS J. Comput. 8(4):344-354.

Digital Library

[32]

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.

Digital Library

[33]

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.

[34]

Reyes D, Savelsbergh M, Toriello A (2017) Vehicle routing with roaming delivery locations. Transportation Res. Part C: Emerging Tech. 80(July):71-91.

[35]

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.

[36]

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.

[37]

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.

[38]

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.

[39]

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.

[40]

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.

[41]

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.

[42]

Toth P, Vigo D (2014) Vehicle Routing: Problems, Methods, and Applications, 2nd ed. (SIAM, Philadelphia).

[43]

Varone S, Aissat K (2015) Multi-modal transportation with public transport and ride-sharing. ICEIS 2015--17th Internat. Conf. Enterprise Inform. Systems, Barcelona, Spain.

Cited By

Zhang WJacquillat AWang KWang S(2023)Routing Optimization with Vehicle–Customer CoordinationManagement Science10.1287/mnsc.2023.473969:11(6876-6897)Online publication date: 29-Mar-2023
https://dl.acm.org/doi/10.1287/mnsc.2023.4739
Liu STang SZheng JNi L(2022)Unsupervised Learning for Human Mobility BehaviorsINFORMS Journal on Computing10.1287/ijoc.2021.109834:3(1565-1586)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1287/ijoc.2021.1098
Dragomir AVan Woensel TDoerner K(2022)The pickup and delivery problem with alternative locations and overlapping time windowsComputers and Operations Research10.1016/j.cor.2022.105758143:COnline publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1016/j.cor.2022.105758
Show More Cited By

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

Recommendations

Numerically Safe Lower Bounds for the Capacitated Vehicle Routing Problem

The resolution of integer programming problems is typically performed via branch and bound. Nodes of the branch-and-bound tree are pruned whenever the corresponding subproblem is proven not to contain a solution better than the best solution found so ...
Reoptimization in Lagrangian methods for the 0-1 quadratic knapsack problem

The 0-1 quadratic knapsack problem consists of maximizing a quadratic objective function subject to a linear capacity constraint. To exactly solve large instances of this problem with a tree search algorithm (e.g., a branch and bound method), the ...
A Lagrangian heuristic algorithm for the time-dependent combined network design and routing problem

During the planning of communication networks, the routing decision process distributed and online often remains decoupled from the network design process, that is, resource installation and allocation-planning process centralized and offline. To ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image INFORMS Journal on Computing

INFORMS Journal on Computing Volume 30, Issue 3

August 2018

16 pages

ISSN:1526-5528

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 August 2018

Accepted: 06 November 2017

Received: 13 July 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang WJacquillat AWang KWang S(2023)Routing Optimization with Vehicle–Customer CoordinationManagement Science10.1287/mnsc.2023.473969:11(6876-6897)Online publication date: 29-Mar-2023
https://dl.acm.org/doi/10.1287/mnsc.2023.4739
Liu STang SZheng JNi L(2022)Unsupervised Learning for Human Mobility BehaviorsINFORMS Journal on Computing10.1287/ijoc.2021.109834:3(1565-1586)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1287/ijoc.2021.1098
Dragomir AVan Woensel TDoerner K(2022)The pickup and delivery problem with alternative locations and overlapping time windowsComputers and Operations Research10.1016/j.cor.2022.105758143:COnline publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1016/j.cor.2022.105758
Baloch GGzara F(2020)Strategic Network Design for Parcel Delivery with Drones Under CompetitionTransportation Science10.1287/trsc.2019.092854:1(204-228)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1287/trsc.2019.0928
Boysen NFedtke SSchwerdfeger S(2020)Last-mile delivery concepts: a survey from an operational research perspectiveOR Spectrum10.1007/s00291-020-00607-843:1(1-58)Online publication date: 21-Sep-2020
https://dl.acm.org/doi/10.1007/s00291-020-00607-8

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents