Organizations: Hanyang University ERICA Campus · Nankai University · Zhejiang Normal University · Chaoyang University of Technology · Sun Yat-sen University
We study a stylized single-vehicle replenishment-routing problem in which the cities of a national logistics network are both demand points and supply points: a vehicle of limited capacity delivers to every city once, and when its load is insufficient for the next city it must detour to a city already served that can still supply goods. A 100-node benchmark is built from Korean population and geographic data, with the cities divided into 10 levels; the per-visit supply coefficient and the allowed number of stops decrease geometrically with the level. Building on matrix-based ant colony optimization, we keep the states of the whole colony in arrays, couple route construction with a fixed greedy replenishment-decoding policy, and evaluate the candidate moves of a local search in batches. With frozen parameters and 30 runs on seeds never used for tuning, the matrix-based ant colony search with the batch local search (MACO) reaches a mean total distance of 3081.7 km; a genetic algorithm equipped with the same local search at the same frequency reaches 3074.9 km (no significant difference), and a MAX-MIN ant system with the same local search 3142.2 km. Ablation identifies the batch local search as the main contributor to solution quality; a load-aware transition factor gives no significant gain. Within the parameter ranges tested, raising the supply coefficients of the cities below the top level shortens the route more than relaxing the stop limits, which are not binding here.
Figures & tables
Fig. 1: The 100 Korean cities and counties divided into 10 levels by population; darker and larger markers indicate higher levels, diamonds are counties. The right panel enlarges the Seoul capital area.
Level
Population ( 104 )
qℓ−1
Demand
Supply per stop
Vℓ
1
928.2–105.7
1.000
1588.9
1988.9
5
2
100.0–60.8
0.600
774.3
464.6
4
3
56.2–40.1
0.360
486.6
175.2
3
4
39.1–27.3
0.216
330.3
71.4
3
5
26.7–20.6
0.130
245.3
31.8
2
6
20.5–15.1
0.078
178.8
13.9
2
TABLE I: Parameters and statistics of the city levels (default parameters)
Fig. 2: One construction step on the whole colony: the transition weights of all ants form one matrix, the next nodes are chosen row by row, the detours of the ants that need a reload are evaluated as one detour matrix, and the ants that need none travel directly to their next nodes.
Fig. 3: Flowchart of MACO. Blue boxes are array operations on the whole colony; the dashed box details the synchronous construction and decoding.
MACO without local search (synchronous variant of ACS, Section IV-D)
MMAS [ 12 ]
none
q0=0 , ρ=0.1 on all arcs, iteration-best deposit (best-so-far every 5th iter.), τmax=1/(ρfgb) , τmin=τmax/(2n) , reset after 150 stagnant iter.
MMAS-LS
as MACO
MMAS with the batch local search
GA [ 21 ]
none
permutation encoding, population 50, binary tournament, OX ( pc=0.9 ), inversion ( pm=0.3 ), 2 elites, 10 seed routes among the initial individuals
TABLE II: Algorithms compared and their parameter settings (fixed before the reported runs)
Algorithm
Mean
Std
Best
Worst
Reloads
Time/s
p -value
MACO
3,081.7
60.8
2,970.7
3,208.3
5.5
9
–
MACO+ Φ
3,077.6
58.8
2,951.1
3,193.9
5.3
9
0.80≈
MMAS-LS
3,142.2
59.5
3,021.0
3,240.7
5.4
6
4.1×10−4+
GA-LS
3,074.9
60.0
2,995.2
3,187.5
5.0
3
0.62≈
ACS
3,381.8
114.6
3,204.2
3,652.4
5.5
24
3.2×10−11+
MMAS
3,303.6
71.3
3,156.2
3,434.1
5.8
25
5.8×10−11+
TABLE III: Results on the benchmark (30 independent runs, seeds 200–229, 3×105 evaluations; km)
Fig. 4: Performance of the algorithms on the benchmark (seeds 200–229).
Parameters of Φ
With local search
p
Without local search
p
LS gain
p
Φ≡1 (MACO)
3,083.9 ± 53.3
–
3,372.4 ± 125.5
–
8.6%
6.3×10−8
θ=1 , λ=1
3,051.4 ± 54.4
0.09
3,338.3 ± 118.8
0.52
8.6%
1.5×10−7
θ=1 , λ=2 (MACO+ Φ )
3,083.0 ± 52.2
0.83
3,360.0 ± 104.2
0.87
8.2%
6.3×10−8
θ=0.1 , λ=1
3,073.7 ± 36.4
0.47
3,685.6 ± 124.7
1.5×10−6
16.6%
6.3×10−8
θ=0.1 , λ=2
3,072.5 ± 50.0
0.48
3,703.7 ± 103.5
3.7×10−7
17.0%
6.3×10−8
TABLE IV: Ablation of the parameters θ , λ of the load-aware factor Φ and of the batch local search (seeds 200–219, 20 runs each, mean ± std, km)
Fig. 5: Best extended route found by MACO: (a) the route (solid: delivery order; dashed: detours to a served node for reloading; stars: reload stops), (b) the Seoul capital area, (c) the load on arrival at each stop. The lines are great-circle segments, not drivable routes.
Fig. 6: Effect of the supply ratio q and the stop ratio r on the total distance (mean ± standard deviation of 20 runs) and on the number of reload detours (mean), other parameters at their defaults.
Department of Industrial Engineering, Tsinghua University, Beijing 100084, P.R. China · School of Management Science and Engineering, Central University of Finance and Economics, Beijing 100081, P.R. China