An integrated heuristic-seeded adaptive large neighborhood search for transportation problems:Theoretical analysis and empirical validation

Abstract

The Transportation Problem is considered to be among the fundamental optimization problems. In practice,however, it appears to be widely applied in logistics and operations research, though perhaps not in its full glory andcertainly only after some reality constraints, such as limited capacity or time, are brought to the table. Exact methods providean optimal solution; however, for larger instances, such methods may be slightly inefficient due to their computationalcomplexity that increases exponentially. Classical heuristics are fast algorithms but the solution they provide is not usuallyoptimal even if they are fast. Meta-heuristics require a lot of parameters and need to be finely tuned, similar to calibration.In this paper we propose the Heuristic-Seeded Adaptive Large Neighborhood Search (HS-ALNS) system, it mixes a costsensitive greedy seeding heuristic with an adaptive large neighborhood search framework, and it kind of helps the wholeprocess feel more responsive. The approach uses a kind of intelligent destroy and repair operators, they select what to do viaself-adaptive processes and, it also lets simulated annealing take over to accept the outcomes. In the end the paper kind offrames four main contributions: (1) full ablation experiments that show how heuristic seed methods really matter, (2) largerbenchmark sets, with extreme cases and pathological instances thrown in, (3) convergence proofs with a logarithmic coolingschedule that satisfies Hajek’s conditions, plus an explicit modeling of adaptive dynamics, and (4) empirical verification thatsupports the assumptions of Markov processes. The HS-ALNS approach gives near-optimal solutions, with better computetime, for every test problem we checked. It looks like it occurs in both the test cases studied through the benchmark instancesand in a large real-world distribution example case (ten source cities, thirty destination cities). Each of our conclusions ismathematically tested, and this is a comprehensive test rather than a cursory check. This means not only that we studyempirical tests for convergence but also perform proper statistical analysis with effect sizes included and multiple testingcorrections. Moreover, a comparison is made between the suggested model and one of the best-performing commercialsolvers available in the market, Gurobi. The benchmarking even includes problem instances of size 100×100, which tendto become quite critical. In general, all these results suggest that the framework suggested is reliable and computationallyefficient; however, of course, the actual results may vary based on constraints in practice.