An exact algorithm for the container drayage problem under a separation mode. (October 2017)

• Record Type: Journal Article
• Authors: Song, Yujian; Zhang, Jiantong; Liang, Zhe; Ye, Chunming
• Is Part Of: Transportation research. Volume 106(2017)
• Page Start: 231
• Page End: 254
• Publication Date: 2017-10
• Subjects: Container drayage -- Separation mode -- A-VRPTW -- Branch-and-price-and-cut algorithm; Logistics -- Periodicals; Transportation -- Periodicals; 388.011
• DOI: 10.1016/j.tre.2017.07.010
• Languages: English
• ISSNs: 1366-5545

Abstract

Highlights: We investigate a new variant of the container drayage problem under a separation mode. We present a graphical representation and then reduce the original problem to an asymmetric multiple traveling salesman problem with time windows. We develop a branch-and-price-and-cut algorithm to solve the problem. A hybrid acceleration strategy for solving the pricing problem and a pair of bounds are introduced for performance improvement. We conduct extensive computational experiments on a set of randomly generated instances to validate the proposed approach and obtain managerial insights. Abstract: In this paper, we consider the container drayage problem under a separation mode in which a container can be separated from the truck during (un-)loading operation, and some emptied containers should return to the depot for maintenance. The problem is equivalently transformed into a variant of the asymmetric vehicle routing problem with time windows (a-VRPTW) based on a determined-activities-on-vertex (DAOV) graph. We present an arc-flow formulation and propose a branch-and-price-and-cut algorithm to exactly solve it. Computational results on a set of randomly generated instances show that the proposed algorithm outperforms CPLEX in terms of efficiency and effectiveness and the separation mode is advantageous over the stay-with mode.