An adaptive guidance meta-heuristic for the vehicle routing problem with splits and clustered backhauls

Abstract

This paper presents the case study of an Italian carrier, Grendi Trasporti Marittimi, which provides freight transportation services by trucks and containers. Its trucks deliver container loads from a port to import customers and collect container loads from export customers to the same port. In this case study, all import customers in a route must be serviced before all export customers, each customer can be visited more than once and containers are never unloaded or reloaded from the truck chassis along any route. We model the problem using an Integer Linear Programming formulation and propose an Adaptive Guidance metaheuristic. Our extensive computational experiments show that the adaptive guidance algorithm is capable of determining good-quality solutions in many instances of practical or potential interest for the carrier within 10 min of computing time, whereas the mathematical formulation often fails to provide the first feasible solution within 3 h of computing time.

Keywords:

• vehicle routing problem with splits
• backhauls
• drayage
• adaptive guidance
• meta-heuristics

View correction statement:

Erratum: An adaptive guidance meta-heuristic for the vehicle routing problem with splits and clustered backhauls

Acknowledgements

This work was partially supported by Grendi Trasporti Marittimi. The authors are also grateful to Claudia Archetti for providing the Split Tabu code, to Gunes Erdogan for his careful comments on previous versions of the paper and Teodor Gabriel Crainic for the enlightening talks on this topic. The authors are grateful to Sardinia Regional Government for the financial support (P.O.R. Sardegna F.S.E. Operational Programme of the Autonomous Region of Sardinia, European Social Fund 2007–2013—Axis IV Human Resources, Objective l.3, Line of Activity l.3.1)