Abstract
In supply chain management (SCM), delivery route decisions and production scheduling are fundamental problems often solved using the Traveling Salesman Problem (TSP). However, when multiple enterprises collaborate, sharing sensitive information like stock levels, demand forecasts, or proprietary cost matrices is often impossible due to confidentiality. This paper examines distributed TSPs where cost functions are defined by information distributed among parties who wish to keep it private. We propose a privacy-preserving local search protocol that enables collaborative optimization without revealing sensitive data, achieving the same solution quality as standard algorithms.
Introduction
Collaborative optimization in SCM often hits a wall when it comes to data privacy. For instance, a user might want to find an optimal route for a set of cities without revealing those cities to a service provider, while the provider wants to keep its cost matrix confidential. This is known as a distributed TSP.
As scenarios become more complex—such as multi-party regional shipping collaborations—the need for a robust, privacy-preserving framework grows. These situations often appear unsolvable unless private information is shared, but cryptographic techniques offer a middle ground for multi-party coordination.
Methodology
The proposed protocol adapts the 2-opt local search heuristic into a privacy-preserving format. The key insight is that the algorithm only requires the relative comparison of route costs, not the absolute values. By only computing the encrypted costs for the edges that change between iterations, the complexity is reduced from $O(n^2)$ to $O(1)$ per comparison.
Cryptographic Framework
- Paillier Cryptosystem: This homomorphic encryption scheme allows the searcher to compute the encrypted difference between two routes using the server's encrypted cost matrix. Because it supports additive homomorphic operations, the searcher can sum the costs of edges in a route without ever seeing the raw numbers.
- Blinded Random Shares: To prevent the searcher from inferring costs from the results, a random blinding factor is added to the encrypted difference.
- Hybrid Secure Function Evaluation (SFE): Instead of a computationally expensive full-SFE implementation, SFE is used only for the final step: comparing the blinded shares to determine which route is shorter. This significantly boosts efficiency.
Experimental Results
The protocol was evaluated using benchmarks from TSPLIB, ranging from 195 to 1173 cities.
- Efficiency: The protocol is computationally feasible for real-world use. A 195-city instance (rat195) was solved in approximately 20 minutes, while a 575-city instance (rat575) took roughly 80-90 minutes.
- Accuracy: The privacy-preserving version is "identically behaved" to the standard 2-opt algorithm. It finds the exact same local optima, with error indices relative to the global optimum ranging from 8.6% to 15.4%.
- Communication: Communication overhead is manageable, as the large cost matrix is only transferred once at the start.
Conclusion
This research demonstrates that privacy-preserving local search is a viable solution for distributed combinatorial optimization. By leveraging the specific logic of the 2-opt heuristic, the protocol bypasses the traditional performance bottlenecks of Secure Function Evaluation. Future work will focus on mitigating potential information leakage from repeated comparisons and extending the protocol to parallelized metaheuristics.
Summary updated