Modeling and Solving the Truck Appointment System

¹ University of Le Havre Normandie, LITIS, 76063 Le Havre Cedex, France
² University of Le Havre Normandie, LMAH, 76063 Le Havre Cedex, France

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Abstract

The Truck Appointment System (TAS) problem is a key component of container terminal operations, aiming to coordinate truck arrivals through time slot allocation. From the perspective of transportation companies, it must be combined with vehicle routing decisions, leading to a complex extension of the Pickup and Delivery Problem with Time Windows. Routing decisions must be synchronized with terminal access constraints and fleet compatibility in order to optimize a combination of routing costs, waiting time penalties, and time slot preferences. In this paper, we propose a 3-phase matheuristic (3PM), to address this integrated problem. The first phase generates feasible pre-assignments of terminal time slots and fleets to requests, significantly reducing the combinatorial search space. The second phase solves the resulting routing subproblems using a branch-and-price approach, producing a pool of feasible routes with fixed terminal arrival times. The third phase re-optimizes both route selection and time slot assignments through a column generation scheme coupled with an integer linear programming model, allowing for a significant reduction of waiting time penalties. Computational experiments conducted on realistic instances derived from the Port of Kingston with up to 150 requests demonstrate the effectiveness of the proposed approaches. The three-phase matheuristic efficiently solves instances with up to 111 requests for a single fleet, providing high-quality solutions within reasonable computation times. Larger instances can be addressed when considering multiple fleets, either with shared or partitioned requests. Overall, the results show that combining decomposition techniques with column generation provides an effective approach for solving integrated routing and scheduling problems arising in port logistics.