Approach Integrating Mixed-Integer Programming and Constraint Programming for Planning Rotations of Inland Vessels in a Large Seaport

Abstract

During the past decade, inland vessels have gained importance in container transport because of their reliability, low environmental impact, and major capacity for increased exploitation. Although inland vessels are crucial in container transport between terminals in the port and the hinterland, in a large seaport like the one in Rotterdam, Netherlands, only 62% of the inland vessels leave the port on time. The other vessels have to stay in the port area for a longer time than planned. This situation leads to uncertainty in waiting times of vessels at terminals and low utilization of terminal quay resources. A two-phase approach is proposed that integrates mixed-integer programming (MIP) and constraint programming (CP) to solve the problem by generating optimal rotation plans for inland vessels. In the first phase, the single-vessel optimization problem is formulated on the basis of MIP and solved with state-of-the-art MIP solvers. In the second phase, the multiple-vessel coordination problem is formulated on the basis of CP, and a large neighborhood search–based heuristic is proposed to solve the problem. Commercial CP solvers are also used for comparison. Simulation results show that the proposed large neighborhood search–based heuristic outperforms the commercial CP solver with regard to both the solution quality and the computation time. Moreover, simulation results with respect to departure time of the last vessel, total sojourn time, and waiting time show significant improvement with earlier departure times and shorter sojourn times and waiting times.

Get full access to this article

View all access options for this article.

References

Moonen

, Van de Rakt

, Miller

, Van Nunen

, and Van Hillegersberg

. Agent Technology Supports Inter-organizational Planning in the Port. In Managing Supply Chains: Challenges and Opportunities, Copenhagen Business School Press, Denmark, 2007, pp. 201–225.

Douma

A. M.

Aligning the Operations of Barges and Terminals Through Distributed Planning. PhD dissertation. University of Twente, Enschede, Netherlands, 2008.

Melis

, Miller

, Kentrop

, Van Eck

, Leenaarts

, Schut

, and Treur

. Distributed Rotation Planning for Container Barges in the Port of Rotterdam. Intelligent Logistics Concepts, 2003, pp. 101–116.

, Negenborn

R. R.

, and Lodewijks

. A Distributed Constraint Optimization Approach for Vessel Rotation Planning. In Proceedings of the 5th International Conference on Computational Logistics, Valparaiso, Chile, Springer International Publishing, Switzerland, 2014, pp. 61–80.

Shaw

Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. In Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming, Pisa, Italy, Springer, New York, 1998, pp. 417–431.

Pisinger

, and Ropke

. Large Neighborhood Search. In Handbook of Metaheuristics, International Series in Operations Research & Management 146, Springer, New York, 2010, pp. 399–419.

Ropke

, and Pisinger

. An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, Vol. 40, No. 4, 2006, pp. 455–472.

, Negenborn

R. R.

, and Lodewijks

. A Two Phase Approach for Inter-terminal Transport of Inland Vessels Using Preference-Based and Utility-Based Coordination Rules. In Proceedings of the 6th International Conference on Computational Logistics, Delft, Netherlands, Springer, Switzerland, 2015, pp. 281–297.