A set-covering formulation for a drayage problem with single and double container loads

Subject Areas : Mathematical Optimization

A. Ghezelsoflu ¹ , M. Di Francesco ² , A. Frangioni ³ , P. Zuddas ⁴

1 - Department of Mathematics and Computer Science, University of Cagliari, Cagliari, Italy
2 - Department of Mathematics and Computer Science, University of Cagliari, Cagliari, Italy
3 - Department of Computer Science, University of Pisa, Pisa, Italy
4 - Department of Mathematics and Computer Science, University of Cagliari, Cagliari, Italy

Received: 2020-10-07 Accepted : 2020-10-07 Published : 2018-12-01

Keywords: Drayage  Vehicle routing problem  Street, turns  Set covering,

Abstract :

This paper addresses a drayage problem, which is motivated by the case study of a real carrier. Its trucks carry one or two containers from a port to importers and from exporters to the port. Since up to four customers can be served in each route, we propose a set-covering formulation for this problem where all possible routes are enumerated. This model can be efficiently solved to optimality by a commercial solver, significantly outperforming a previously proposed node-arc formulation. Moreover, the model can be effectively used to evaluate a new distribution policy, which results in an enlarged set of feasible routes and can increase savings w.r.t.the policy currently employed by the carrier.