This paper investigates a drayage problem, where a fleet of trucks must ship container loads from a port to importers and from exporters to the same port, without separating trucks and containers during customer service. We present three formulations for this problem that are valid when each truck carries one container. For the third formulation, we also assume that the arc costs are equal for all trucks, and then we prove that its continuous relaxation admits integer optimal solutions by checking that its constraint matrix is totally unimodular. Under the same hypothesis on costs, even the continuous relaxations of the first two models are proved to admit an integer optimal solution. Finally, the third model is transformed into a circulation problem, that can be solved by efficient network algorithms.
An integral LP relaxation for a drayage problem
Di Francesco, M.
;Schirra, S.;Zuddas, P.
2019-01-01
Abstract
This paper investigates a drayage problem, where a fleet of trucks must ship container loads from a port to importers and from exporters to the same port, without separating trucks and containers during customer service. We present three formulations for this problem that are valid when each truck carries one container. For the third formulation, we also assume that the arc costs are equal for all trucks, and then we prove that its continuous relaxation admits integer optimal solutions by checking that its constraint matrix is totally unimodular. Under the same hypothesis on costs, even the continuous relaxations of the first two models are proved to admit an integer optimal solution. Finally, the third model is transformed into a circulation problem, that can be solved by efficient network algorithms.File | Dimensione | Formato | |
---|---|---|---|
mainss.pdf
Open Access dal 01/11/2020
Tipologia:
versione pre-print
Dimensione
247.99 kB
Formato
Adobe PDF
|
247.99 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.