# A robust genetic algorithm for an open pickup-and-delivery problem with time windows and optional cross-docking

Ryan Belbachir, Walid Behiri, Sana Berraf-Belmokhtar, Laurent Bouillaut, Allou Samé

► To cite this version:

Ryan Belbachir, Walid Behiri, Sana Berraf-Belmokhtar, Laurent Bouillaut, Allou Samé. A robust genetic algorithm for an open pickup-and-delivery problem with time windows and optional cross-docking. ROADEF 2026, Université de Tours [UT], Feb 2026, Tours, France. hal-05534866

HAL Id: hal-05534866

https://hal.science/hal-05534866v1

Submitted on 3 Mar 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# A robust genetic algorithm for an open pickup-and-delivery problem with time windows and optional cross-docking

R. Belbachir, W. Behiri, S. Belmokhtar-Berraf, A. Same, L. Bouillaut

Grettia/Cosys, Université Gustave Eiffel, F-77454 Marne-la-Vallée, France.

`{ryan.belbachir, walid-behiri, sana.berraf-belmokhtar, allou same, laurent.bouillaut}@univ-eiffel.fr`

**Keywords** : Open PDPTW, Cross-dock, Genetic algorithm, Dynamic paramters tuning

## 1 Introduction

The rapid growth of e-commerce has considerably increased the demand for goods transportation and delivery services. According to Fevad (the French e-commerce and distance selling federation), e-commerce represented 8.4% of retail sales in 2024. Efficiently managing transport resources is therefore critical to meet this demand without escalating operational costs. Our work focuses on optimizing the middle mile, a critical segment that has received relatively little attention compared to first- and last-mile logistics. Optimizing this segment can lead to substantial long-term gains, given that it represents the longest component of the transportation process and requires recurrent daily operational decisions.

The problem under consideration can be modeled as an extended vehicle routing problem with an optional cross-dock facility. Specifically, it is formulated as an open multi-depot, multi-product VRP with pickup and delivery and time windows. We define a set of sites, each of which may host one or multiple pickup and/or delivery nodes. Requests are represented in a paired pickup-delivery format, allowing a single site to serve multiple requests. An optional cross-dock is available for load consolidation. Each request *r* consists of a pickup node *p*<sub>r</sub> and a delivery node *d*<sub>r</sub>, and due to the optional cross-dock, deliveries can follow three schemes: direct delivery, routing without cross-dock, or routing via cross-dock.

In previous work [2], we proposed an exact solution approach based on a mixed integer linear programming (MILP) formulation to solve this problem. However, due to its NP-hard nature and the additional complexity introduced by optional cross-docking, the MILP model rapidly reaches its computational limits. Addressing practical-sized instances necessitates the use of approximate methods, notably metaheuristics. In this work, we focus on genetic algorithms (GA) as a promising and effective solution approach for the problem at hand. Evolutionary algorithms, including GAs, exhibit performance that is highly sensitive to appropriate parameter tuning [1]. In this work, we aim to achieve an effective balance between exploration and exploitation, primarily controlled through the crossover and mutation rates. First, we develop a robust GA tailored to large-scale instances by using the Taguchi method to systematically tune its control parameters and enhance algorithmic robustness. Second, we introduce a dynamic parameter-tuning strategy for the crossover and mutation rates to preserve a balanced trade-off between exploration and exploitation throughout the search process.

## 2 Genetic algorithm design and parameter tuning

This work extends our previous research [2], in which we proposed a MILP model. While the exact approach provides optimal solutions for small instances, the NP-hard nature of the problem makes it computationally intractable for larger cases, especially when the problem
involves multiple depots and products, time windows, and optional cross-docking operations as modeled by the MILP. To overcome these limitations, we propose a GA designed to efficiently solve large-scale instances of the problem.

The proposed GA follows the classical evolutionary process, consisting of initialization, selection, crossover, and mutation with a specific adaptation to the problem's characteristics, that is the repair mechanism. To generate the initial population, constructive heuristics are employed to create feasible routes without cross-docking: the nearest neighbour and the best-fit insertion heuristics.

To optimize the performance of the metaheuristic, we applied the Taguchi method for selecting the optimal combination of algorithmic parameters. The Taguchi method, known for its robust design approach, enables systematic experimentation by reducing the number of trials needed to identify parameter settings that minimize variability and improve solution quality. By employing this technique, we efficiently determined the most effective parameter configurations, ensuring a more robust and reliable performance of the genetic algorithm across different problem instances. This approach has been widely used in the literature, such robust GA [3].

The crossover operator uses either one-point crossover or two-point crossover, while the mutation operator employs two mechanisms: big swap mutation or block big swap mutation. The rates for both operators as well as the population size are critical to the algorithm's performance, as GAs are highly sensitive to parameter tuning [1]. Through the design of experiments based on the Taguchi method, we systematically evaluated the influence of these parameters on the solution quality, allowing us to identify the most effective combinations.

To further enhance the algorithm's robustness, we implemented a dynamic parameter tuning mechanism that adapts the crossover and mutation rates during the search process. This adaptive strategy aims to balance exploration and exploitation, thereby improving the performance of our GA. We evaluate the performance of our GA using the Li & Lim benchmark instances, which correspond to the closely related problem, the pickup and delivery problem with time windows (PDPTW).

## 3 Conclusion and Perspectives

In this work, we studied an extension of the open vehicle routing problem with pickup and delivery, time windows, and multiple products, with the addition of an optional cross-docking operation. Building upon our previous MILP formulation, we propose a GA to efficiently solve larger instances. The algorithm integrates constructive heuristics and parameter tuning based on the Taguchi method and machine learning for dynamic parameter adjustment. We evaluated our GA using the benchmark of Li & Lim for the PDPTW. This study provides a foundation for further research on hybrid and adaptive metaheuristics applied to complex routing problems. Future research will extend the problem by integrating machine learning to accelerate and improve the repair mechanism. Additional research directions include the modelling of multiple cross-dock facilities and the incorporation of sustainability criteria, such as CO2 emissions.

## References

[1] A. Aleti and I. Moser. A systematic literature review of adaptive parameter control methods for evolutionary algorithms. *ACM Computing Surveys*, 49(3):1–35, 2016.

[2] R. Belbachir, W. Behiri, S. Belmokhtar-Berraf, E. V. Belmega, and L. Hamdad. A MIP for a generalized open vehicle routing problem with pickup and delivery considering optional cross-dock. *2024 10th International Conference on Control, Decision and Information Technologies (CoDIT)*, 1409–1413, 2024.

[3] A. Sahli, W. Behiri, S. Belmokhtar-Berraf, and C. Chu. An effective and robust genetic algorithm for urban freight transport scheduling using passenger rail network. *Computers & Industrial Engineering*, 173:108645, November 2022. doi:10.1016/j.cie.2022.108645.