Relaxing Time Windows by Partial Orders in Routing Problems With Stacking Constraints

Abstract

In vehicle routing problems, time windows are often used to formulate partial order relations between tasks in optimization model and related algorithm. However, time-window and partial order constraints are not equivalent. In the context of stacking operations in container terminals, this study proposed a relaxation method to translate the time-window constraints into the partial order constraints and built a routing optimization model with the partial order constraints. Under the framework of branch and bound (BB) algorithm, this paper studied the relationship between time-window constraints and partial order constraints. The features of the two models are analyzed. The Solomon datasets are used to conduct numerical analysis and examine the differences between the two models in terms of optimization ability and optimality. Revealed by experimental results, the partial-order-based model can be solved with better optimality, while the time-window-based mode can be solved within a shorter time. Moreover, inspired by the effects of narrowing the time windows, it will be a new research direction to develop improved algorithms for partial-order-based model based on time-window-based decomposition method.

Keywords

• Vehicle routing problem
• partial order
• branch and bound algorithm
• container terminal
• logistics management