A two-commodity flow formulation for the truck and trailer routing problem
Enrico Bartolini  1@  , Michael Schneider  1@  
1 : Deutsche Post Chair of Optimization of Distribution Networks, School of Business and Economics, RWTH Aachen University

In the Capacitated Truck and Trailer VRP (CTTRP) a limited fleet of capacitated trucks and trailers is available at a depot to serve a set of customers. Trailers are non-autonomous vehicles that can be pulled by a truck to increase its capacity. Each customer must be served by exactly one vehicle, but some of them, called truck customers, can only be reached by a truck without trailer. Trucks are thus allowed to detach and park their trailer en route at any (non-truck) customer location, make a subtour to visit some customers without trailer, and then return back to pick up the trailer before continuing the trip. We propose a two-commodity flow formulation for the CTTRP and some valid inequalities to strengthen it. We report computational results with a branch-and-cut algorithm based on the new formulation on instances derived from benchmark sets. The algorithm solves instances with up to 30 customers.

Online user: 1 RSS Feed