COMPARATIVE ANALYSIS OF ALGORITHMS FOR SOLVING THE PENALIZED QUBO FORMULATION OF THE TWO ECHELON VEHICLE ROUTING PROBLEM ON A MACRO REGIONAL INSTANCE OF FOREST INDUSTRY LOGISTICS
Rodion S. Rogulin
Novgorod State University, Veliky Novgorod, Russian Federation
Keywords: QUBO, two echelon routing, 2E VRP, simulated annealing, genetic algorithm, penalty formulations, combinatorial optimization, forest industry logistics, fixed transportation costs
Abstract
This study investigates the computational efficiency of various optimization algorithms on the penalized QUBO (Quadratic Unconstrained Binary Optimization) formulation of the two echelon vehicle routing problem (2E VRP). The model includes variable and fixed transportation costs (cfix = 50 000 RUB per trip for vehicle activation) and is tested on a forest industry logistics instance covering the Ural and Siberian Federal Districts (UFD+SFD) with 207 nodes, 19 constituent entities of the Russian Federation, and N = 10,162 binary variables. It is established that the genetic algorithm (GA), including variants with initialization from a known feasible solution, systematically fails to reach feasibility on penalized QUBO landscapes of this scale. The reason is structural: a zero diagonal in the dominant linearization block W (accounting for 87 % of the variables) and the trap of the trivial minimum x = 0. In contrast, simulated annealing (SA) on the same Q matrix finds feasible solutions in all runs, improving the objective function by 55 % relative to the constructive heuristic. A hybrid approach is proposed: a three stage constructive heuristic “Feasibility First” generates an initial feasible solution in 1.7 seconds, after which SA optimizes it in the vicinity of the feasible region. The resulting FQUBO value is -13 197 240 (a gap of 11.6 % from the continuous relaxation) with all constraints fully satisfied. The reduction in total transportation cost (variable + fixed costs) compared to GA amounts to 65 %.
|
