Research Internship: Modeling and Solving the Robust Truck Appointment Scheduling Problem

Title: Modeling and Solving the Robust Truck Appointment Scheduling Problem
Laboratory: LITIS, RI2C team (Université Le Havre Normandie). Topics: Operations research,
complex systems, logistics, drones, blockchain, temporal graphs.
Duration: 4 to 6 months, ideally starting in February 2025. Possibility to continue with a Ph.D.
starting in September 2025.
Prerequisites: Master’s level (M2) student with good skills in C++ and Operations Research
(Cplex/Gurobi solvers, metaheuristics).
Contacts: Éric Sanlaville (eric.sanlaville@univ-lehavre.fr), Christophe Duhamel
(christophe.duhamel@univ-lehavre.fr), Sophie Michel (sophie.michel@univ-lehavre.fr).

Description:
Truck gates at port terminals are significant points of congestion, particularly for container
terminals. This congestion can significantly impact the performance of supply chains and the
attractiveness of ports. To address this issue, port authorities have implemented Truck
Appointment Systems (TAS [Murty and Liu, 2005]), requiring each truck delivering or picking
up a container to reserve a specific time slot (entry/exit) with a predefined capacity. The
objective is to streamline truck flows and maintain efficient exchanges with the hinterland.
The TAS problem is modelled here from the perspective of transport operators. A fleet of
trucks must handle a set of container transport requests over the course of a day. Each request
involves two successive operations: picking up a container and delivering it. One of these
operations takes place at the terminal, and both must comply with specific time windows. The
goal is to minimize overall operational costs, including transport costs, contractual penalties
for excessive waiting times, and time slot preferences, while respecting operational
constraints.
As part of the MOSART project, the problem has been modelled as a variant of the PDPTW
(Pickup and Delivery Problem with Time Windows [Desaulniers et al., 2002]) and a mixed-
integer linear programming formulation has been proposed. Additionally, we developed a
hybrid Biased Random Key Genetic Algorithm (BRKGA [Resende and Ribeiro, 2010]) to provide
high-quality solutions in reasonable computation times.
The objective of this Master’s internship is to integrate data uncertainties, particularly
regarding container availability dates. Within the framework of robust optimization, various
robustness criteria will be studied, and both the model and the metaheuristic will be adapted
to find robust solutions with respect to these uncertainties. These modifications will then be
evaluated on instances derived from Kingston Port, Jamaica, to analyze the impact of
uncertainties and measure the level of robustness in a potential reactive approach.

Keywords: Operations Research, transportation problem, robust optimization, linear
programming, genetic algorithm, C++.
References:
• [Desaulniers et al., 2002] Desaulniers, G., Desrosiers, J., and Solomon, M. M. (2002).
Pickup and delivery problem with time windows. Transportation Science, 36(5):543–
555.
• [Murty and Liu, 2005] Murty, K. G., and Liu, J. (2005). Truck appointment systems to
alleviate congestion at container terminals. Operations Research, 53(2):230–245.
• [Resende and Ribeiro, 2010] Resende, M. G. C., and Ribeiro, C. C. (2010). A biased
random-key genetic algorithm for combinatorial optimization. Journal of Heuristics,
16(3):243–273.