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 (vi · pi2), and (ii) a priority bias in the Nearest Neighbor heuristic for the TSP, parameterized by α. 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 (vi/wi 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.
Related
- RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem
- Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes
- Robust Heterogeneous Vehicle Routing Optimization for Hazmat Transportation Under Time-Varying Risk
- Carbon-Aware Electric Vehicle Routing Problem with Decision-Focused Learning
- An Exact Branch-Price-and-Cut Algorithm for a Truck-as-Hub Vehicle Routing Problem with Drones
BibTeX
@misc{bezerra2026hybridizing,
title = {{Hybridizing 0/1 Knapsack and Priority-Aware TSP for Vehicle Routing: an Applied Variant of the TSP with Profits}},
author = {Aron da Silva Bezerra and Francisco Márcio Barboza},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36526},
eprint = {2610.36526},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36526},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Hybridizing 0/1 Knapsack and Priority-Aware TSP for Vehicle Routing: an Applied Variant of the TSP with Profits
AU - Aron da Silva Bezerra
AU - Francisco Márcio Barboza
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.36526
UR - https://arxiv.org/abs/2610.36526
AB - 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 · p_i^2), and (ii) a priority bias in the Nearest Neighbor heuristic for the TSP, parameterized by α. 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.
ER -