A Branch-and-Cut Algorithm for the Single Truck and Trailer Routing Problem with Satellite Depots

José Manuel Belenguer (), Enrique Benavent (), Antonio Martínez (), Christian Prins (), Caroline Prodhon () and Juan G. Villegas ()
Additional contact information
José Manuel Belenguer: Departament d’Estadística i Investigació Operativa, Universitat de Valéncia, 46100 Burjassot (Valéncia), Spain
Enrique Benavent: Departament d’Estadística i Investigació Operativa, Universitat de Valéncia, 46100 Burjassot (Valéncia), Spain
Antonio Martínez: Southampton Management School, Faculty of Business and Law, University of Southampton, Highfield, Southampton SO17 1BJ, United Kingdom
Christian Prins: Institut Charles Delaunay, Laboratoire d’Optimisation des Systémes Industriels (LOSI), Université de Technologie de Troyes, 10004 Troyes Cedex, France
Caroline Prodhon: Institut Charles Delaunay, Laboratoire d’Optimisation des Systémes Industriels (LOSI), Université de Technologie de Troyes, 10004 Troyes Cedex, France
Juan G. Villegas: Departamento de Ingeniería Industrial, Facultdad de Ingeniería, Universidad de Antioquia, 050010 Medellín, Colombia

Transportation Science, 2016, vol. 50, issue 2, 735-749

Abstract: In the single truck and trailer routing problem with satellite depots (STTRPSD), a truck with a detachable trailer based at a main depot must serve the demand of a set of customers accessible only by truck. Therefore, before serving the customers, it is necessary to detach the trailer in an appropriate parking place (called either a satellite depot or a trailer point) and transfer goods between the truck and the trailer. This problem has applications in milk collection for farms that cannot be reached using large vehicles. In this work we present an integer programming formulation of the STTRPSD. This formulation is tightened with several families of valid inequalities for which we have developed different (exact and heuristic) separation procedures. Using these elements, we have implemented a branch-and-cut algorithm for the solution of the STTRPSD. A computational experiment with published instances shows that the proposed branch-and-cut algorithm consistently solves problems with up to 50 customers and 10 satellite depots, and it has also been able to solve instances with up to 20 satellite depots and 100 clustered customers.

Keywords: branch-and-cut; cutting planes; truck and trailer routing problem; vehicle routing problem (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2014.0571 (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:ortrsc:v:50:y:2016:i:2:p:735-749

Access Statistics for this article

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