Hybridizing 0/1 Knapsack and Priority-Aware TSP for Vehicle Routing: an Applied Variant of the TSP with Profits
math.OC
Submitted: 2026-10-27
Updated: 2026-10-27
License: http://creativecommons.org/licenses/by/4.0/
The gist: Distribution logistics with capacity constraints and service priorities can be modeled as a variant of the TSP with Profits (TSPP)…
Abstract
Distribution logistics with capacity constraints and service priorities can be modeled as a variant of the 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 times p i squared), 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.
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise