Thread Scaling of Hexaly on the TDVRPTW across Two Model Encodings. An Experimental Report: External-Function Serialization, Slice-Count Choice, and the Time-Sliced Thread Ladder

Thread Scaling of Hexaly on the TDVRPTW across Two Model Encodings An Experimental Report: External-Function Serialization, Slice-Count Choice, and the Time-Sliced Thread Ladder Florian Rascoussier∗ August 10, 2026

arXiv:2608.10079v1 [math.OC] 10 Aug 2026

Abstract Thread scaling in Hexaly depends first on how the Time-Dependent Vehicle Routing Problem with Time Windows is modeled. We compare two Python encodings: one evaluates continuous travel-time functions through external callbacks, while the other approximates them with time slices evaluated natively by the solver. Independent CPU measurements show that the supported external-function interface uses a single evaluator worker regardless of the requested thread count. The native encoding, by contrast, makes effective use of the allocated cores. Across our selected benchmark panel, wider native searches produce better solutions both at the end of the run and throughout the search, while substantially reducing variation between seeds. Nearly every paired run improves from one to sixteen threads. The choice of encoding has an even larger impact than the thread count: native evaluation provides the strongest gains, at the cost of a travel-time approximation that must be sufficiently fine and independently checked. These descriptive results support multi-threading as a practical way to improve solution quality and stability when the model can exploit it, and show that the modeling approach is central to thread-scaling conclusions in time-dependent routing. Keywords: Vehicle Routing, TDVRPTW, Hexaly, Multi-threading, External Functions, Benchmarking, Dispersion, CPU Accounting

∗ IMT Atlantique, Lab-STICC, CNRS, UMR 6285 (équipe DECIDE) and INSA Lyon, Inria, CITI, UR3720, 69621 Villeurbanne, France; ORCID identifier: 0009-0005-3253-9814.

1

Contents 1 Context and scope

3

2 Experimental protocol

3

2.1

Instances and reference values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.2 The two Hexaly model encodings . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.3

Execution grid, pinning, and measurement . . . . . . . . . . . . . . . . . . . . . . . .

5

2.4

Scoring and metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.5

Hardware and software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3 The external-function encoding: one evaluator thread, by design 3.1

6

One active evaluator at every requested width . . . . . . . . . . . . . . . . . . . . . .

6

3.2 Why the Python callback is serialized . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.3

Diagnostic attempts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.4

Consequences for interpreting the ladder . . . . . . . . . . . . . . . . . . . . . . . . .

7

4 Choosing the slice count for the time-sliced encoding

9

4.1 The slice count affects checker feasibility . . . . . . . . . . . . . . . . . . . . . . . . .

9

4.2

Comparison of the two encodings at equal budget . . . . . . . . . . . . . . . . . . . .

9

4.3

Memory cost of ψ = 96 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

5 The thread ladder on the time-sliced encoding

12

5.1

Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

5.2

Quality per thread level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

5.3

Dispersion across seeds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

5.4

Memory and time to first solution . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

6 Discussion

16

7 Conclusion

16

2

1

Context and scope

We are conducting a solver-comparison campaign on the duration-minimization TDVRPTW as part of PhD research in which we also develop our own solver, KAYROS [1, 2]. Hexaly Optimizer [3] is one of the solvers considered in this campaign, under an academic license that we gratefully acknowledge. The main comparison assigns the same wall-clock budget to every solver and runs each process single-threaded on one physical core. This convention equalizes resources rather than constraining any particular solver: every arm of the campaign, including our own, receives one core and one hour per cell. During the exchange that motivated this report, Hexaly explained that the optimizer is designed for multi-threaded use and that restricting it to one thread may reduce performance and solution quality. We therefore committed to a thread-scaling study under the same instance set and wall-clock budget as the main comparison. Maxime Rougier also clarified that Hexaly primarily uses additional threads to diversify the search and the methods applied. We consequently examine stability across seeds in addition to mean solution quality. The outcome depends strongly on the model encoding, and we organize the report around this distinction. Section 2 introduces the experimental protocol and the two encodings. Section 3 explains why the external-function encoding remains single-worker. Section 4 selects a sufficiently fine time discretization, and Section 5 reports its thread scaling before Sections 6 and 7 discuss the implications.

2

Experimental protocol

2.1

Instances and reference values

The thread ladders use ten TDVRPTW instances from five benchmark families, spanning small literature-derived cases to large urban-traffic instances (Table 1). The panel draws from Dabia2013 [4, 5, 6], Rifki2020 [7], Vu2020 [8], our Lera2026 family derived from the Gehring–Homberger bases [9]1 , and our OpenStreetMap-based Poryos2026 family [11]. The instances and their piecewise-linear travel-time data are distributed as checksummed artifacts through MAMUT-routing [12]. Table 1: The ten-instance set of the thread ladders. The handle column gives the short name used in the result tables. Reference values are checker-validated best-known solutions, or checker-exact optimality certificates where marked. The slice study of Section 4 uses a six-instance subset: the five marked with a dagger, plus RC207 (Dabia2013, n = 100). Handle

Family

Instance

Reference

R109 RC103† Rifki-27† Rifki-12 Vu-A5 Vu-A4† Lera-C2 Lera-RC1† SF Tokyo†

Dabia2013 Dabia2013 Rifki2020 Rifki2020 Vu2020 Vu2020 Lera2026 Lera2026 Poryos2026 Poryos2026

R109 RC103 Rifki-27 Rifki-12 Vu-A5-pB-d70-w120 Vu-A4-pB-d90-w150 Lera-C2_2_5-S3 Lera-RC1_10_5-S1 poryos-san_francisco-n100-hyb-bpr-light poryos-tokyo-n1000-hyb-bpr-heavy

certificate certificate best known best known certificate certificate best known best known best known best known

n 50 100 50 60 59 99 200 1000 100 1000

The panel was frozen after exploratory observations on a larger, unreported set. It was deliberately 1

Lera2026 is named in honor of Gonzalo Lera-Romero, whose open-source exact TDVRPTW solver [10] shaped our work. Lera-Romero is not an author of the family.

3

selected to remain computationally feasible while preserving diversity in family, size, reference status, and origin. We use the same panel for both encodings to preserve cell-by-cell pairing. The results are therefore descriptive of this panel rather than estimates of an average effect over TDVRPTW instances. All gaps are measured against a reference snapshot frozen before the campaign. Since this reference set evolves with our experiments, the absolute gaps are working measurements rather than final publication values, but comparisons across thread levels remain valid because every run uses the same snapshot.

2.2

The two Hexaly model encodings

Both encodings formulate the TDVRPTW with list decision variables in the Hexaly modeling API, following the general structure of Hexaly’s TDCVRPTW template [13]. Route sequences satisfy a partition constraint, vehicle capacity is imposed as a hard constraint, and customer and depot time windows are represented through a first-level total-lateness objective. The solver therefore minimizes the lexicographic pair (total lateness, total duration), with a free departure time from the depot for each route. The two encodings differ in their evaluation of time-dependent travel times, and this difference determines whether the search can use several threads. The external-function encoding (Tier 1). Arrival times are computed through external functions declared with create_double_external_function in the Python API. These functions call back into Python to evaluate the same piecewise-linear arrival-time data, with the same conventions, as our reference checker. This removes the travel-time discretization error of the second encoding, but the objectives are not bit-exact because the checker independently optimizes depot departure times. Their differences are small but nonzero, and checker values are authoritative throughout this report. The callback is side-effect free: it reads an immutable table while all other variables are local. Section 3 examines how this interface affects multi-threaded execution. The time-sliced encoding (Tier 2). Let V be the vertex set of the instance, i.e. the n clients together with a single depot vertex, so that |V| = n + 1, and let αij be the original arrival-time function of arc ⟨i, j⟩, giving the arrival time at j for a departure from i at a given time. Let [h0 , h1 ] be the travel-time horizon, let ψ ∈ N>0 be the slice count, i.e. the number of equal periods into which that horizon is divided, and let w = (h1 − h0 )/ψ be the resulting slice width. For arc ⟨i, j⟩ and slice k ∈ [0, ψ − 1]N , the model stores the original travel time at the slice midpoint µk = h0 + (k + 1/2)w, namely αij (µk ) − µk , in a constant |V| × |V| × ψ table. The midpoint evaluation follows the checker’s convention of taking the smallest ordinate at a duplicate piecewise-linear abscissa. A departure time tdep propagated along a route is rounded to the nearest integer using Python’s ties-to-even convention, then assigned to slice min{ψ − 1, max{0, ⌊(tdep − h0 )/w⌋}}. An exact internal boundary therefore enters the following slice, while h1 enters the final slice. A propagated departure outside the supported integer-time horizon has no defined lookup and the corresponding move is rejected. The travel time is frozen at the departure slice: the encoding neither accounts for crossing a boundary during traversal nor modifies the table to enforce FIFO, so adjacent slices can invert arrival order. Time windows, service times, demands and capacity retain their original values. The model follows the published TDCVRPTW template [13] and uses one list decision variable for each vehicle available to the solver. When an instance declares a fleet size, that value determines the number of list variables. For Poryos2026, whose files do not declare a fleet size, we allow up to n vehicles and therefore create n list variables. We remove the fleet-size level of the template’s lexicographic objective and replace its distance level with total route duration, bringing the native objective closer to the checker duration used in the campaign. Each route’s departure remains a continuous variable in the intersection of the travel-time horizon and depot time window instead of being fixed at the beginning of the horizon. Since the slice table approximates the original

4

travel-time functions and does not enforce the first-in-first-out (FIFO) property, the slice count ψ is a substantive modeling parameter studied in Section 4. We discretize travel times rather than speeds. For families generated from piecewise-constant speed profiles, integrating a discretized speed profile would preserve FIFO and can represent the original model exactly. It would, however, require evaluating a departure-dependent integral inside the search, precisely the operation that the native encoding must avoid. Freezing travel time at the departure slice retains a single native table lookup but introduces boundary-crossing errors and may violate FIFO. The slice count therefore controls model fidelity and is a modeling decision rather than a tuning detail. Hexaly 15.0 does not expose a best-solution event. We therefore poll the incumbent trajectory through a periodic callback whose tick period has a one-second lower bound, giving timestamps with an approximate one-second granularity for both encodings. We record a new incumbent whenever the native lexicographic objective has strictly improved since the previous tick.

2.3

Execution grid, pinning, and measurement

Each thread-scaling experiment combines the ten instances with requested thread counts ξ ∈ {1, 2, 4, 8, 16} and three seeds, for a total of 150 one-hour runs per encoding. The wall-clock budget includes data loading and model construction as well as the search itself. We stop at 16 threads to cover a meaningful scaling range while keeping the campaign computationally manageable. Each run starts one Hexaly process, pinned with taskset to its requested number of physical cores on the same 32-core node class. Core sets remain exclusive to a process, but processes can still share node-level resources such as caches and memory bandwidth. Since narrow configurations allow more processes to share a node than wide configurations, thread width remains partly confounded with node co-tenancy. We account for this limitation when interpreting the native thread ladder and use an independent replication to bound its likely effect (Section 5.1). We independently measure each complete process tree with GNU time, recording wall time, user and system CPU time, and peak memory use. Comparing CPU time with wall time reveals how many cores the process actually keeps busy, which is essential because the solver API reports the requested thread count rather than effective parallelism. We therefore base the resource analysis on measured process consumption rather than scheduler allocation, which also includes idle and fragmented cores.

2.4

Scoring and metrics

We report anytime solver performance through two complementary measures computed from the checker-valid incumbent trajectory: the final gap at the time limit and the normalized primal integral over the full run. The final gap describes where the search ends, while the primal integral rewards methods that find good feasible solutions early and retain them throughout the search. Together, they provide a balanced view of final and anytime quality. Lower values are better for both. We also report the time to the first checker-valid incumbent and use the range across the three seeds to describe dispersion. The reported trajectory is the best-so-far envelope of sampled routes accepted by the MAMUTrouting reference checker (mamut-routing-lib version 0.9.0) on the original travel-time functions. It contains routes captured after strict improvements in Hexaly’s native objective, plus the terminal route when it is checker-valid; rejected routes contribute nothing. The envelope is therefore checkervalid by construction, but it remains a sample of the states visited by the solver. Adding the terminal route does not change any score in these experiments because it never improves the preceding envelope. We nevertheless report terminal validity where relevant and reserve native objective values 5

for diagnostics. At the deadline TL = 3600 s, we measure end-of-run quality with the squeezed gap g ′ (zTL , z ∗ ) = (zTL − z ∗ )/(zTL + z ∗ ), where zTL is the best checker-valid value and z ∗ is the reference duration. Tables and figures call this quantity the final gap; it is not necessarily the gap of Hexaly’s terminal native solution. The value is zero when the run matches the reference and negative when it improves upon it. We set it to 1 when no checker-valid route was recorded. This bounded measure is a rescaling of the classic relative gap g(z) = (z − z ∗ )/z ∗ : g′ =

g , g+2

g=

2g ′ , 1 − g′

so the two gaps contain the same information. The bounded g ′ scale is suitable for aggregation across instances, while figures also provide the familiar percentage scale g. Anytime quality is measured by the normalized primal integral 1 PI (TL) = TL ′

Z TL

g ′ zbest (t), z ∗ dt,

0

where zbest (t) is the best checker-valid incumbent available at time t. Before the first valid incumbent, the gap is held at 1. Both performance measures therefore belong to (−1, 1]. For dispersion, the nonlinear gap transformation prevents a unique conversion between ranges: the figures show the pooled g ′ range and the corresponding g range recomputed from the seed endpoints. A triangle marks an unbounded g range caused by an absent valid incumbent.

2.5

Hardware and software

All experiments run on the grvingt cluster of the Grid’5000 testbed at Nancy [14]. We use its dual-socket 32-core Intel Xeon Gold 6130 nodes with 192 GiB of RAM. The software stack is Hexaly Optimizer 15.0 through its Python API with CPython 3.13.

3

The external-function encoding: one evaluator thread, by design

3.1

One active evaluator at every requested width

If the search used its allocated cores, process CPU time would grow with the requested thread count. Instead, the external-function encoding consumes one core at every width (Table 2), despite being pinned to the requested cores. All runs complete normally with checker-valid terminal solutions. Table 2: CPU accounting for the external-function encoding. CPU/wall remains at one occupied core regardless of the requested width. ξ

mean CPU/wall

allocated-core occupancy

1 2 4 8 16

1.00 1.00 1.00 1.00 1.00

100% 50% 25% 12.5% 6.25%

User and system CPU measurements confirm that this is not a monitoring artifact. Hexaly creates its worker threads, but only one evaluator receives work. The requested widths therefore describe five single-threaded configurations rather than a scaling experiment.

6

3.2

Why the Python callback is serialized

The Hexaly manual documents this behavior [15]. Python external functions are treated as callbacks from a Global Interpreter Lock (GIL) language, and the optimizer limits the effective search width to avoid harmful concurrent access. By contrast, C++, C#, and Java callbacks may be evaluated concurrently when the caller ensures thread safety [16]. The parameter API reports the width requested by the user rather than the effective width [17], so independent CPU accounting is required to observe the difference. The Python binding implements this safeguard explicitly: every externalfunction constructor marks the callback as fromGilLanguage, without inspecting the interpreter at runtime or providing a supported override. The native library therefore serializes evaluation because the function was created through the Python binding.

3.3

Diagnostic attempts

We tested four variants of the same wide configuration, combining stock and free-threaded CPython [18] with either the original binding or a diagnostic patch that clears fromGilLanguage. Per-thread CPU counters and stack dumps identify the active workers. These short, deliberately unsupported probes diagnose the execution mechanism and are excluded from the solution-quality comparison. Table 3: Diagnostic variants of the same wide run. The stock binding leaves one evaluator active under both interpreters. Clearing its GIL-language flag activates the worker set but produces a severe slowdown or a crash. Iteration counts use equal solver time; n/a denotes the crashed configuration. These unsupported variants are excluded from the campaign results. Interpreter

Binding

OS threads

Busy workers

CPU/wall

Iterations

Outcome

3.13 stock 3.13t free-threaded 3.13t free-threaded 3.13 stock

stock stock patched patched

17 17 32 32

1 of 16 1 of 16 n/a 16 of 16

1.00 1.00 1.01 1.78

1 968 906 5 565 n/a 39 007

feasible, no lateness no feasible solution crash after 13.8 s feasible, lateness violated

Worker traces show that the stock configuration has one active callback evaluator while the remaining workers sleep, ruling out contention among active search threads. A free-threaded interpreter does not change this state, which confirms that the binding flag rather than the runtime GIL state controls serialization. Clearing the flag activates the full worker set, but the stock interpreter then suffers a severe throughput collapse and produces an invalid terminal solution, while the free-threaded configuration crashes. None of these attempts provides a usable parallel Python configuration. The failed variants suggest GIL contention and expose a possible shared-state hazard in the binding’s process-global callback exception storage, but we did not isolate either mechanism with a minimal reproducer. Both therefore remain hypotheses. The probe establishes only the robust conclusion needed here: the supported Python interface uses one evaluator worker. It does not characterize Hexaly’s native parallel search or its C++ interface, which permits concurrent external functions.

3.4

Consequences for interpreting the ladder

Since the search uses one evaluator worker throughout, the rows of Table 4 do not form a scaling curve. The one-thread row is the representative baseline for this encoding. The other requested widths produce only modest changes in quality and no systematic reduction in seed dispersion. The pooled seed range remains stable across the requested widths (Table 4). This does not test Hexaly’s stabilization claim because its parallel diversification mechanism is inactive. Small ordered changes in quality, iteration count, and time to the first valid incumbent show that requested width

7

Table 4: Pooled results per requested thread level on the external-function encoding (30 runs each: 10 instances × 3 seeds; seeds pooled per instance first, instances weighted equally). One evaluator thread runs at every level, so these are five measurements of a single-threaded solver. Seed range is the mean over instances of the max–min spread of final g ′ across the three seeds. ξ

mean final g ′

mean PI′

mean seed range of g ′

mean first valid (s)

mean CPU/wall

1 2 4 8 16

0.0576 0.0569 0.0556 0.0548 0.0549

0.0760 0.0749 0.0726 0.0715 0.0713

0.0137 0.0135 0.0135 0.0132 0.0135

24.0 22.4 20.8 19.6 20.0

1.00 1.00 1.00 1.00 1.00

Hexaly, external-function encoding: solution quality vs requested threads (3600 s budget)

50%

0.15 0.10

20%

0.05

10%

0.00

5% 1%

1

2

4

8

0.30 0.25 0.20

50%

0.15 0.10

20%

0.05

10% 5% 1%

0.00

16

1

requested threads (log scale) R109 (n=50) RC103 (n=100) Rifki-27 (n=50)

100%

gap g

mean PI0 over seeds

0.20

gap g

mean final g 0 over seeds

0.35 0.25

2

4

8

16

requested threads (log scale)

Rifki-12 (n=60) Vu-A5 (n=59) Vu-A4 (n=99)

Lera-C2 (n=200) Lera-RC1 (n=1000)

SF (n=100) Tokyo (n=1000)

Figure 1: External-function encoding: mean final squeezed gap g ′ (left) and mean anytime metric PI′ (right) against the requested thread count, with three seeds per point and the common one-hour budget. Independent CPU accounting shows that one evaluator worker runs at every point. The curves therefore compare several requested configurations of the same single-worker search rather than parallel scaling. Both metrics change only modestly, with most visible movement concentrated on the largest instances. is not entirely inert, but they occur without additional CPU use and have no identified mechanism. Peak memory is likewise independent of width.

8

4

Choosing the slice count for the time-sliced encoding

The time-sliced encoding introduces the slice count ψ, which controls the discretization of the travel-time horizon. We select it before the thread ladder because scaling results are meaningful only for a sufficiently faithful model. The single-threaded configuration study compares coarse, intermediate, and fine discretizations on six diverse instances under the same one-hour budget. Five instances subsequently appear in the thread ladder, so this is informed configuration selection rather than out-of-sample validation.

4.1

The slice count affects checker feasibility

The main criterion for selecting the slice count is not the magnitude of the approximation error, but its effect on feasibility under the original travel-time functions. With a coarse discretization, a run may fail to record any incumbent accepted by the checker. Table 5 reports the mean final g ′ for every instance and slice count, where g ′ = 1 denotes the absence of a checker-valid recorded incumbent. Table 5: Time-sliced encoding: mean final g ′ by instance and slice count (mean over five seeds, 3600 s budget, single-threaded). A value of 1 means no checker-valid incumbent was recorded. Instance

n

ψ=5

ψ = 24

ψ = 96

∆96−5

RC103 RC207 Rifki-27 Vu-A4 Lera-RC1 Tokyo

100 100 50 99 1000 1000

0.0529 0.0575 0.0094 0.0157 1.0000 0.0162

0.2272 0.0436 0.0139 0.0098 0.8721 0.0132

0.0386 0.0473 0.0085 0.0099 0.1221 0.0146

−0.0143 −0.0103 −0.0009 −0.0058 −0.8779 −0.0016

The tight-window Lera-RC1 instance provides the clearest example: coarse discretizations often produce no checker-valid recorded incumbent, whereas the finest setting succeeds for every seed (Table 5). Similar failures also occur on smaller instances. The discretized model can admit schedules that are infeasible under the original travel-time functions, which is why all solutions are evaluated through the reference checker. At ψ = 96, every run records a checker-valid incumbent and the checker rejects fewer trajectory points than under the coarser discretizations. Occasional invalid terminal solutions do not affect the final-gap metric, which uses the best valid recorded incumbent. Table 6 and Figures 2 and 3 summarize the results. The large dispersion at the intermediate setting follows from feasibility failures rather than unstable quality among valid solutions. Table 6: Time-sliced encoding pooled per slice count (six instances × five seeds; seeds pooled per instance first, instances weighted equally). Rejected incumbents are trajectory points the checker refused, per run, and are the fidelity readout of the discretization. ψ

mean final g ′

mean PI′

mean seed range of g ′

mean first valid (s)

mean rejected incumbents

5 24 96

0.1919 0.1966 0.0402

0.2265 0.2123 0.0780

0.0102 0.2791 0.0193

116.3 39.9 85.1

352.3 349.6 193.3

4.2

Comparison of the two encodings at equal budget

For a direct comparison, Table 7 restricts both encodings to their common seeds and wall-clock budget, then evaluates them with the same checker. The retained ψ = 96 configuration outperforms

9

Hexaly, time-sliced encoding: solution quality vs slice count (3600 s budget)

500%

0.6 200%

0.4

100% 50%

0.2

20% 5%

0.0 5

24

500%

0.6 200%

0.4

100% 50%

0.2

20% 5%

0.0

96

5

slice count ψ (log scale) RC103 (n=100) Lera-RC1 (n=1000)

0.8

gap g

0.8

mean PI0 over seeds

1.0

gap g

mean final g 0 over seeds

1.0

24

96

slice count ψ (log scale) Tokyo (n=1000) Rifki-27 (n=50)

Vu-A4 (n=99)

RC207 (n=100)

Figure 2: Time-sliced encoding: mean final squeezed gap g ′ (left) and mean anytime metric PI′ (right) per instance against the slice count. Both metrics use the checker-valid recorded trajectory on the original travel-time functions. On the tight-window Lera-RC1 instance, g ′ = 1 at the coarsest setting denotes the absence of any checker-valid recorded incumbent rather than a large finite gap. The finest setting provides the most reliable feasibility and the strongest overall quality across both metrics. the external-function encoding on every shared instance, with the largest gains on the large instances. This conclusion therefore does not rely on choosing a different slice count for each case. Both encodings are scored by the best checker-valid point of their recorded trajectory (Section 2.4). This rule matters more for the approximation, which produces many rejected incumbents, than for the external-function model, whose native objective nearly coincides with the checker’s. The comparison therefore concerns the encodings as deployed with independent validation, not their native objectives alone. Table 7: Final g ′ of the time-sliced encoding against the external-function encoding, shared seeds {13, 17, 42}, both single-threaded at 3600 s, both scored by the checker on the true travel-time functions. A negative last column means the sliced encoding ends ahead. RC207 is outside the teninstance set and has no external-function arm. The slice-count columns come from the configuration study of this section, which is a separate campaign from the thread ladder of Section 5 and shares no run with it; the two are compared in Section 5.1. Instance

n

ψ=5

ψ = 24

ψ = 96

external functions

RC103 RC207 Rifki-27 Vu-A4 Lera-RC1 Tokyo

100 100 50 99 1000 1000

0.0534 0.0598 0.0085 0.0151 1.0000 0.0170

0.3524 0.0479 0.0158 0.0105 1.0000 0.0132

0.0395 0.0457 0.0083 0.0093 0.1280 0.0147

0.0741 n/a 0.0201 0.0184 0.2799 0.0325

min over ψ − external −0.0345 n/a −0.0118 −0.0092 −0.1519 −0.0193

This comparison affects how Hexaly should be represented in the broader campaign. At this budget, our external-function encoding is not its strongest configuration for the considered problem

10

final g range across seeds (percentage points)

final g 0 range across seeds

Hexaly, time-sliced encoding: seed-range of final g' vs slice count (dispersion)

1.0 0.8 0.6 0.4 0.2 0.0 5

24

96

20

triangles: unbounded range, a seed with no valid solution

15 10 5 0

5

slice count ψ (log scale) RC103 (n=100) Lera-RC1 (n=1000)

24

96

slice count ψ (log scale)

Tokyo (n=1000) Rifki-27 (n=50)

Vu-A4 (n=99)

RC207 (n=100)

Figure 3: Time-sliced encoding: seed range of final g ′ per instance against the slice count. The peak at ψ = 24 occurs when only some seeds record a checker-valid incumbent. Left panel: the range in g ′ . Right panel: the range in g. A cell containing a seed without a valid recorded incumbent has an unbounded range in g, represented by a triangle at the upper limit of the panel. class. Both arms of Table 7 are single-threaded, so the single-worker restriction of Section 3 cannot explain the difference: at one thread, the relevant cost is the per-evaluation overhead of calling back into Python, which the native slice lookup avoids. The restriction has a separate effect at wider settings, where it prevents the external-function encoding from reducing this difference through parallel search, as the time-sliced encoding does in Section 5.

4.3

Memory cost of ψ = 96

The discretized table has size |V| × |V| × ψ, so memory grows linearly with the slice count and quadratically with the number of vertices. It is negligible on the small instances but becomes a scheduling constraint on the largest ones (Table 8). The retained configuration nevertheless fits the available nodes, and its memory use changes little with thread count. On the largest instances, model construction also consumes a material part of the wall-clock budget. Table 8: Time-sliced encoding: peak resident set size (GNU time maximum RSS, max over the five seeds) by instance and slice count. Instance

n

ψ=5

ψ = 24

ψ = 96

RC103 RC207 Rifki-27 Vu-A4 Lera-RC1 Tokyo

100 100 50 99 1000 1000

76 MB 77 MB 83 MB 195 MB 2.1 GB 15.1 GB

85 MB 87 MB 86 MB 202 MB 3.1 GB 15.8 GB

127 MB 125 MB 97 MB 237 MB 8.5 GB 25.0 GB

In summary, the lower memory cost of ψ = 5 and ψ = 24 does not compensate for their occasional failure to produce checker-valid recorded incumbents. The ψ = 96 configuration records at least one valid incumbent for every instance and seed, gives the best or a near-best final quality throughout the study, and remains within the available memory budget. We consequently retain ψ = 96 for the

11

thread ladder of Section 5.

5

The thread ladder on the time-sliced encoding

5.1

Setup

This second ladder measures effective thread scaling. It reuses the instances, seeds, thread levels, wall-clock budget, and hardware class of the external-function ladder, enabling paired comparisons throughout, and fixes the slice count at ψ = 96 according to Section 4. Runs follow the execution and scoring protocol of Sections 2.3 and 2.4: each process is pinned to exclusive physical cores, monitored independently, and scored by the reference checker. Nodes are grouped by thread width and packed within their memory capacity. This prevents core overlap but leaves width partly confounded with co-tenancy, since narrow configurations place more processes on a node. The slice study independently repeats the single-threaded configuration under different host packing. Its mean final gaps remain within 10−3 of this ladder and differ negligibly compared with the gain from increasing the thread count (Tables 7 and 10). This check does not exclude a co-tenancy effect at wider levels, but it bounds its likely importance in the available comparison. Every run records a checker-valid incumbent. A small number of terminal solutions on the hardest instance are rejected, but no run is excluded because the metrics use the best checker-valid recorded incumbent.

5.2

Quality per thread level

Unlike the external-function model, the time-sliced encoding keeps the allocated cores close to fully occupied at every width (Figure 4). A modest dip at the intermediate width includes two clear outliers, but neither preprocessing, CPU accounting, nor pinning explains it. The available traces lack per-worker activity and therefore cannot identify the solver-internal cause. The important contrast is robust: native evaluation follows the full-occupancy diagonal, while Python callback evaluation remains at one core. The additional cores yield substantial quality gains (Table 9). From one to sixteen threads, the pooled final gap falls by about 25%, and the anytime metric improves in every paired run. Nearly every paired endpoint and every per-instance mean also improves. Quality continues to progress at the widest measured level, so no saturation is observed within this ladder. This is a wall-time comparison and the widest setting uses sixteen times the nominal process width. Table 9: Pooled results per thread level on the time-sliced encoding at ψ = 96 (30 runs each: 10 instances × 3 seeds; seeds pooled per instance first, instances weighted equally). Seed range is the mean over instances of the max–min spread of final g ′ across the three seeds. Unlike the external-function results in Table 4, the mean CPU/wall ratio follows the requested thread count. ξ

mean final g ′

mean PI′

mean seed range of g ′

mean first valid (s)

mean CPU/wall

1 2 4 8 16

0.0275 0.0263 0.0245 0.0224 0.0207

0.0527 0.0508 0.0473 0.0428 0.0412

0.0126 0.0072 0.0059 0.0040 0.0033

56.0 51.7 55.9 47.7 45.5

1.00 1.98 3.75 7.65 15.60

The gain is broad rather than confined to the largest instances: every instance ends better at sixteen threads than at one (Tables 10 and 11 and Figure 5). Intermediate levels are not always monotone, particularly on the hardest instance, but the overall direction is consistent across sizes. 12

CPU seconds per wall second

Hexaly, time-sliced encoding (ψ = 96): process-tree CPU/wall vs requested threads (3600 s budget) 24 23 22 21 20 1

2

4

8

16

requested threads (log scale) ideal (CPU/wall = ξ)

min-max over cells measured mean

fully serialized (CPU/wall = 1)

Figure 4: Time-sliced encoding: measured process-tree CPU per wall-clock second against the requested thread count (GNU time, whole process tree, 30 runs per level). The diagonal denotes full occupancy of the allocated cores. This is the contrast with Table 2, where the same measurement stays at 1 for every requested width. Table 10: Mean final g ′ by instance and thread level on the time-sliced encoding at ψ = 96 (mean over the three seeds). The last column is the difference between the ξ = 16 and ξ = 1 entries of the table. Instance

n

ξ=1

ξ=2

ξ=4

ξ=8

ξ=16

∆16−1

R109 RC103 Rifki-27 Rifki-12 Vu-A5 Vu-A4 Lera-C2 Lera-RC1 SF Tokyo

50 100 50 60 59 99 200 1000 100 1000

0.0146 0.0395 0.0083 0.0138 0.0050 0.0093 0.0347 0.1287 0.0062 0.0147

0.0135 0.0310 0.0066 0.0138 0.0013 0.0093 0.0323 0.1378 0.0036 0.0139

0.0113 0.0302 0.0064 0.0131 0.0020 0.0071 0.0299 0.1283 0.0030 0.0134

0.0074 0.0288 0.0048 0.0096 0.0011 0.0065 0.0296 0.1201 0.0028 0.0132

0.0060 0.0271 0.0041 0.0082 0.0004 0.0060 0.0247 0.1159 0.0016 0.0127

−0.0086 −0.0124 −0.0042 −0.0056 −0.0046 −0.0033 −0.0100 −0.0128 −0.0046 −0.0020

The gain is not explained by a larger reported search volume: multi-threaded runs report slightly fewer iterations than the single-threaded baseline. We use this counter only as a diagnostic because the documentation does not say whether it aggregates worker activity or counts synchronized search rounds. The result therefore rules out a simple increase in the reported iteration count, but it cannot establish a diversification mechanism. The one-thread results also place the scaling gain in perspective: changing from callback to native evaluation has a larger effect than widening the native search from one to sixteen threads (Table 4 and Section 4.2). Model encoding is therefore the first-order decision; thread count is the second.

13

Hexaly, time-sliced encoding (ψ = 96): solution quality vs requested threads (3600 s budget) 0.25

0.10 20%

0.08 0.06 10%

0.04

5%

0.02

2% 0.2%

0.00 1

2

4

8

0.20 0.15 0.10

20%

0.05

10% 5% 2%

0.00

16

1

requested threads (log scale) R109 (n=50) RC103 (n=100) Rifki-27 (n=50)

50%

gap g

mean PI0 over seeds

0.12

gap g

mean final g 0 over seeds

0.14

2

4

8

16

requested threads (log scale)

Rifki-12 (n=60) Vu-A5 (n=59) Vu-A4 (n=99)

Lera-C2 (n=200) Lera-RC1 (n=1000)

SF (n=100) Tokyo (n=1000)

Figure 5: Time-sliced encoding at ψ = 96: mean final squeezed gap g ′ (left) and mean anytime metric PI′ (right) per instance against the thread count, with three seeds per point and the common one-hour budget. Every instance ends better at sixteen threads than at one, and the anytime metric shows the same broad benefit from additional cores. Intermediate widths need not improve monotonically, but both panels support a substantial overall gain across the tested panel. Table 11: Mean PI′ by instance and thread level on the time-sliced encoding at ψ = 96 (mean over the three seeds).

5.3

Instance

n

ξ=1

ξ=2

ξ=4

ξ=8

ξ=16

∆16−1

R109 RC103 Rifki-27 Rifki-12 Vu-A5 Vu-A4 Lera-C2 Lera-RC1 SF Tokyo

50 100 50 60 59 99 200 1000 100 1000

0.0187 0.0520 0.0111 0.0172 0.0109 0.0126 0.0407 0.2519 0.0086 0.1029

0.0193 0.0478 0.0105 0.0164 0.0065 0.0129 0.0384 0.2408 0.0072 0.1086

0.0162 0.0434 0.0093 0.0150 0.0053 0.0107 0.0369 0.2196 0.0059 0.1109

0.0121 0.0403 0.0076 0.0126 0.0034 0.0098 0.0365 0.1989 0.0055 0.1015

0.0115 0.0358 0.0060 0.0107 0.0025 0.0093 0.0311 0.2029 0.0040 0.0986

−0.0072 −0.0162 −0.0051 −0.0065 −0.0084 −0.0033 −0.0096 −0.0490 −0.0046 −0.0043

Dispersion across seeds

Since the time-sliced encoding uses the allocated cores, its seed ranges provide a descriptive measure of stability. The pooled range is almost four times smaller at sixteen threads than at one, and every instance becomes less dispersed between these endpoints (Table 12 and Figure 6). Intermediate widths are not always monotone. Worst-seed outcomes improve together with the ranges. On the most difficult instance, additional threads mitigate an unfavorable seed more strongly than they improve the mean, which is valuable when selecting a practical configuration. The endpoint ranges are descriptively consistent with the stabilization mechanism described by Hexaly on this panel. Three seeds provide neither a reliable

14

Table 12: Range (max−min over the three seeds) of final g ′ by instance and thread level on the time-sliced encoding at ψ = 96. Instance

n

ξ=1

ξ=2

ξ=4

ξ=8

ξ=16

R109 RC103 Rifki-27 Rifki-12 Vu-A5 Vu-A4 Lera-C2 Lera-RC1 SF Tokyo

50 100 50 60 59 99 200 1000 100 1000

0.0094 0.0239 0.0079 0.0055 0.0024 0.0042 0.0139 0.0500 0.0059 0.0026

0.0108 0.0068 0.0034 0.0053 0.0012 0.0042 0.0068 0.0291 0.0006 0.0036

0.0062 0.0046 0.0053 0.0071 0.0032 0.0067 0.0052 0.0171 0.0018 0.0016

0.0039 0.0074 0.0029 0.0030 0.0022 0.0053 0.0057 0.0057 0.0025 0.0013

0.0054 0.0085 0.0015 0.0026 0.0008 0.0040 0.0027 0.0063 0.0005 0.0013

0.05 0.04 0.03 0.02 0.01 0.00 1

2

4

8

16

final g range across seeds (percentage points)

final g 0 range across seeds

Hexaly, time-sliced encoding (ψ = 96): seed-range of final g' vs requested threads (dispersion)

requested threads (log scale) R109 (n=50) RC103 (n=100) Rifki-27 (n=50)

12.5 10.0 7.5 5.0 2.5 0.0 1

2

4

8

16

requested threads (log scale)

Rifki-12 (n=60) Vu-A5 (n=59) Vu-A4 (n=99)

Lera-C2 (n=200) Lera-RC1 (n=1000)

SF (n=100) Tokyo (n=1000)

Figure 6: Time-sliced encoding at ψ = 96: seed range of final g ′ per instance against the thread count. The pooled range is almost four times smaller at sixteen threads than at one. The left panel reports g ′ ; the right reports the corresponding range in the classic relative gap g. variance estimate nor uncertainty for a population effect, and the deliberately selected instances do not justify generalization beyond the panel. Conversely, the stable ranges of Section 3.4 do not test the mechanism because that encoding remains single-worker.

5.4

Memory and time to first solution

Peak memory remains nearly independent of thread count across the panel. A wider run therefore consumes additional cores but little additional memory, and the budget established in Section 4.3 remains applicable. The first checker-valid incumbent also appears earlier on average at the widest setting, driven mainly by the large instances. Intermediate widths are not monotone, and one large urban instance changes little. On the difficult Lera instance, however, the earlier valid solution accompanies genuine additional CPU use and is consistent with a broader parallel search.

15

6

Discussion

The two encodings expose different aspects of the solver and must be interpreted separately. For the external-function encoding, the absence of scaling follows from the binding’s documented treatment of callbacks from a GIL language rather than from a limitation of the native solver. The binding marks the callback accordingly, after which one worker evaluates it and the others remain idle. Clearing the flag activates the workers but produces unreliable unsupported executions. The flag-toworker link is well supported; the detailed slowdown and failure mechanisms remain hypotheses. In practice, a supported Python external-function model should be scheduled, budgeted, and reported as single-threaded even when a wider configuration is requested. Independent CPU accounting is essential because the API exposes requested width, not effective parallelism. This conclusion applies to our Python interface rather than to Hexaly’s parallel search in general. The documentation explicitly allows concurrent external-function evaluation in C++, C# and Java, where thread safety becomes the caller’s responsibility; our callback is already side-effect free. Reimplementing the encoding in C++ would therefore make it possible to measure its native thread scaling. However, this would require substantial implementation work and would change the contender during the campaign, so we leave it for future work and do not speculate on its outcome. The same distinction is necessary when considering stabilization across seeds. The externalfunction encoding shows no reduction in dispersion, but its single-worker execution never activates the diversification mechanism; the stable pooled range of Table 4 therefore does not test the vendor’s statement. The time-sliced encoding, by contrast, makes effective use of the additional cores and provides the relevant experiment. Its high core occupancy accompanies broad improvements in final and anytime quality. At sixteen threads, the pooled final gap is about 25% lower and seed dispersion is almost four times smaller than at one thread. This pattern is consistent with Hexaly’s stabilization account on the tested panel, although the design does not estimate a population effect. Width remains partly confounded with node co-tenancy, but the independent single-threaded replication of Section 5.1 makes this effect negligible relative to the observed gain. These results do not change the single-core convention of the main solver comparison. They quantify a separate tradeoff: better and more stable solutions at equal wall time in exchange for up to sixteen times the nominal core allocation, with little additional memory.

7

Conclusion

This report studied the thread scaling of Hexaly Optimizer 15.0 on two TDVRPTW encodings. The Python external-function encoding uses one evaluator worker independently of the requested width. Source inspection, worker traces, and a flag intervention identify the binding’s GIL-language safeguard as the control. The diagnostic failures observed after bypassing it remain unexplained and do not support quality claims. This encoding must therefore be treated as single-threaded; its stable seed dispersion says nothing about multi-threaded stabilization. Requested width still shifts the search slightly, which we report as a secondary observation rather than a scaling result. The time-sliced encoding evaluates travel times natively and uses its allocated cores effectively. A separate configuration study led us to retain ψ = 96: coarser discretizations can fail checker validation, while this setting reliably produces valid incumbents and remains within the available memory budget. With this encoding, increasing the configuration from one to sixteen threads lowers the pooled final gap by about 25%, improves nearly every paired endpoint, and reduces seed dispersion by almost a factor of four. The gain is broad across the panel and comes mainly at the cost of additional cores rather than memory. These descriptive results support the quality and stabilization benefits of multi-threading when the model can exploit it, without establishing a population-wide effect.

16

Data availability The 390 solver runs behind every table and figure of this report are deposited as a public dataset [19]: 150 runs for each thread ladder and 90 for the slice-count study, each a JSON record carrying the configuration, the timing, the solver’s native statistics and the complete incumbent trajectory, together with the independent GNU time output for the same run. The deposit also contains the frozen reference snapshot of 2026-08-06 used to score every gap2 , so the reported gaps can be recomputed exactly rather than approximately. The instances are not duplicated there: they are distributed as checksummed artifacts through the MAMUT-routing benchmark platform [12], and each record identifies its instance by a path relative to that tree. The model implementations, the run driver and the analysis code are not released at this stage.

Acknowledgments We thank Maxime Rougier and the Hexaly support team for providing the academic license, for their prompt and detailed answers, and for the remarks on multi-threading that motivated this study. We also thank Romain Billot, Christine Solnon and Lina Fahed for supervising the PhD in which this work was conducted. The experiments presented in this report were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER, several universities and other organizations (see https://www.grid5000.fr). This work is funded by the French National Research Agency (ANR) as part of the MAMUT project, ANR-22-CE22-0016, “Machine learning And Matheuristics algorithms for Urban Transportation”.

Declaration of AI use Generative AI tools were used throughout the preparation of this work, including frontier models such as GPT-5.6 Sol (OpenAI) and Claude Fable and Sonnet 5 (Anthropic). They contributed to the experiment orchestration, the analysis tooling and the drafting of this report. The author reviewed and revised all outputs from these tools and takes full responsibility for the final content of the work.

References [1] Florian Rascoussier. KAYROS. Open-source anytime and exact solver for duration-minimization time-dependent vehicle routing. July 20, 2026. url: https://github.com/0nyr/kayros (visited on 08/09/2026). [2] Florian Rascoussier. KAYROS: An Anytime and Exact Open-Source Solver for DurationMinimization Time-Dependent Vehicle Routing. A Technical Report and a Case Study in Human-AI Engineering. 2026. arXiv: 2607.23116 [math.OC]. url: https://arxiv.org/abs/ 2607.23116 (visited on 08/09/2026). [3] Hexaly. Hexaly Optimizer. Proprietary mathematical optimization solver with academic licensing. 2026. url: https://www.hexaly.com/ (visited on 08/07/2026). [4] Said Dabia, Stefan Ropke, Tom Van Woensel, and Ton De Kok. “Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows”. In: Transportation Science 47.3 (2013), pp. 380–396. doi: 10.1287/trsc.1120.0445. [5] Marius M. Solomon. “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints”. In: Operations Research 35.2 (1987), pp. 254–265. doi: 10.1287/opre. 35.2.254. 2

Its entry set hashes to 5e9e489169d87cde8287700501d88ebea1b60afd3731b49e17827712e34b3563.

17

[6] Soumia Ichoua, Michel Gendreau, and Jean-Yves Potvin. “Vehicle Dispatching with TimeDependent Travel Times”. In: European Journal of Operational Research 144.2 (2003), pp. 379– 396. doi: 10.1016/S0377-2217(02)00147-9. [7] Omar Rifki, Nicolas Chiabaut, and Christine Solnon. “On the Impact of Spatio-Temporal Granularity of Traffic Conditions on the Quality of Pickup and Delivery Optimal Tours”. In: Transportation Research Part E: Logistics and Transportation Review 142 (2020), p. 102085. doi: 10.1016/j.tre.2020.102085. [8] Duc Minh Vu, Mike Hewitt, Natashia Boland, and Martin Savelsbergh. “Dynamic Discretization Discovery for Solving the Time-Dependent Traveling Salesman Problem with Time Windows”. In: Transportation Science 54.3 (2020), pp. 703–720. doi: 10.1287/trsc.2019.0911. [9] Jörg Homberger and Hermann Gehring. “Two Evolutionary Metaheuristics for the Vehicle Routing Problem with Time Windows”. In: INFOR: Information Systems and Operational Research 37.3 (1999), pp. 297–318. doi: 10.1080/03155986.1999.11732386. [10] Gonzalo Lera-Romero, Juan J. Miranda Bront, and Francisco J. Soulignac. “Linear Edge Costs and Labeling Algorithms: The Case of the Time-Dependent Vehicle Routing Problem with Time Windows”. In: Networks 76.1 (2020), pp. 24–53. doi: 10.1002/net.21937. [11] Florian Rascoussier. Poryos2026: An OpenStreetMap-Based Benchmark Family for Static and Time-Dependent Vehicle Routing. Benchmark data released under the Open Database License 1.0. July 22, 2026. url: https : / / github . com / ANR - MAMUT / MAMUT - routing / tree/9ef27d07ebb6b8697d8fd45daca05395e6f620a8/benchmarks/Poryos2026 (visited on 07/22/2026). [12] Florian Rascoussier and Adrien Pichon. MAMUT-routing. Open benchmark platform and reference checker for vehicle routing; HAL deposit hal-05629810. May 21, 2026. url: https: //hal.science/hal-05629810 (visited on 08/09/2026). [13] Hexaly. Time-Dependent Capacitated Vehicle Routing Problem with Time Windows (TDCVRPTW) model template. 2026. url: https : / / www . hexaly . com / templates / time dependent-routing-problem-with-time-windows-tdcvrptw (visited on 07/19/2026). [14] Grid’5000. Nancy: Hardware. Hardware reference for the grvingt cluster. 2026. url: https: //www.grid5000.fr/w/Nancy:Hardware (visited on 08/09/2026). [15] Hexaly. External and Black-Box Functions. Hexaly Optimizer documentation, version 15.0; sections “Thread-safety” and “Performance issues”. 2026. url: https://www.hexaly.com/ docs/last/mathematicaloperators/externalfunctions.html (visited on 08/09/2026). [16] Hexaly. HxExternalFunction. Hexaly Optimizer C++ API reference, version 15.0. 2026. url: https : / / www . hexaly . com / docs / last / cppapi / optimizer / hxexternalfunction . html (visited on 08/07/2026). [17] Hexaly. HxParam. Hexaly Optimizer C++ API reference, version 15.0. 2026. url: https: //www.hexaly.com/docs/last/cppapi/optimizer/hxparam.html (visited on 08/07/2026). [18] Sam Gross. PEP 703: Making the Global Interpreter Lock Optional in CPython. Free-threaded CPython builds, available from CPython 3.13 as an experimental interpreter. Jan. 9, 2023. url: https://peps.python.org/pep-0703/ (visited on 08/07/2026). [19] Florian Rascoussier. Thread Scaling of Hexaly on the Time-Dependent VRPTW: Raw Experiment Data. Version 1.0.0. 390 solver runs, frozen reference snapshot; released under CC BY 4.0. Zenodo, Aug. 10, 2026. doi: 10.5281/zenodo.21876741. url: https://zenodo.org/ records/21876741 (visited on 08/10/2026).

18

Related documents

• Thread Scaling of Hexaly on the TDVRPTW across Two Model Encodings. An Experimental Report: Binding Choice, Slice-Count Choice, and Two Thread Ladders#662469
• Thread Scaling of Hexaly on the TDVRPTW across Two Model Encodings. An Experimental Report: Binding Choice, Slice-Count Choice, and Two Thread Ladders#661419
• Dataset for Acceleration Techniques for Predictive TRANSP Simulations for Digital-Twin Between-Shot Analysis#1167678
• CVE-2026-26210 — CRITICAL 9.3#126467
• CVE-2026-25660 — CRITICAL 9.3#128186