Hybridizing 0/1 Knapsack and Priority-Aware TSP for Vehicle Routing: an Applied Variant of the TSP with Profits

Abstract

Distribution logistics with capacity constraints and service priorities can be modeled as a variant of the \emph{TSP with Profits} (TSPP), in which not all customers need to be visited and the selection of which customers to serve is part of the problem. This paper proposes an applied variant with two adaptations: (i) a 0/1 Knapsack objective function weighted by client priority squared ($v_i \cdot p_i^2$), and (ii) a priority bias in the Nearest Neighbor heuristic for the TSP, parameterized by $\alpha$. The approach is evaluated on a scenario with 14 customers and a 1,100~kg capacity, complemented by a comparative experimental protocol against the classical greedy heuristic ($v_i/w_i$ ordering) and an integer programming solver. Results on the base scenario show 9 customers served, 96.4\% capacity utilization, and R\$~18,392.60 revenue, with all 5 excluded customers being low-priority. A sensitivity analysis of the priority exponent justifies the quadratic choice. The limitations of the hierarchical decomposition are explicitly discussed.