Logic-Based Benders Decomposition for an Inter-modal Transportation Problem

Abstract

This paper studies a real-life inter-modal freight transportation problem, comprised by three consecutive stages: disposition where orders are picked up by trucks, transferred and unloaded to a set of warehouses in Central and Eastern Europe, inter-region transport where the orders are packed into trailers, which are shipped to warehouses in Turkey using different inter-region transport modes, and last-mile delivery where the orders unloaded at the warehouses in Turkey are picked up by vans and delivered to their final destination. The objective is to minimise total transport and tardiness cost. After restricting the routes in the disposition stage, we formulate a mixed-integer linear program that captures the entire delivery process. Then, we propose a Benders’ decomposition and prove the validity of a set of optimality cuts and of a subproblem relaxation. We show the impact of this approach on large-scale real instances under user-imposed time limits. We further strengthening the master problem with a set of valid inequalities and speed up the solution of the subproblem using Constraint Programming.

This research has been supported by the EU through the COG-LO Horizon 2020 project, grant number 769141 and the GSRI through the i@transport project, grant number T2E$\mathrm {\Delta }$K00345.