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

Claudio Gambella (), Joe Naoum-Sawaya () and Bissan Ghaddar ()
Additional contact information
Claudio Gambella: IBM Research, Mulhuddart, Dublin 15, Ireland
Joe Naoum-Sawaya: Ivey Business School, University of Western Ontario, London, Ontario N6G 0N1, Canada
Bissan Ghaddar: Ivey Business School, University of Western Ontario, London, Ontario N6G 0N1, Canada

INFORMS Journal on Computing, 2018, vol. 30, issue 3, 554-569

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.

Keywords: vehicle routing; moving targets; Lagrangian decomposition; branch and price (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0800 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:3:p:554-569

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().