<p>This paper focuses on the Distributed Vehicle Routing Problem, a collaborative logistics challenge in which geographically dispersed companies aim to optimize their operations while preserving autonomy and data confidentiality. To address this problem, we propose a novel two-phase approach. The first phase employs a Hybrid Genetic Algorithm to optimize vehicle routing within each company while evaluating the potential benefits of collaboration. The second phase introduces a Hybrid Exchange Mechanism that facilitates selective customer exchanges between companies. This mechanism ensures data privacy and prioritizes high-cost customers for exchange based on a cost-driven strategy that balances exploration and exploitation. To consolidate the gains achieved through customer exchanges, a local search and perturbation procedure is embedded within the exchange mechanism, enabling fine-grained improvement of post-exchange solutions while escaping local optima through controlled diversification. To further enhance solution quality, a feedback-based improvement process is activated when progress stagnates, enabling dynamic refinement and robust performance across diverse instance types. Additionally, a profit-sharing scheme is integrated to guarantee that all participating companies benefit from the collaboration, thereby encouraging engagement. Experimental evaluations on benchmark datasets highlight the effectiveness and competitiveness of the proposed method compared to state-of-the-art techniques, underscoring its potential for modern decentralized logistics systems. </p>