Abstract
In global logistics, finding the most cost-effective route—the Traveling Salesman Problem (TSP)—often involves multiple service providers. However, these providers are typically reluctant to share their proprietary cost matrices, hindering the discovery of an optimal "relay" route. This paper introduces the $k$-Relaying Traveling Salesman Problem ($k$-RTSP) and proposes a Two-level Secure Simulated Annealing (TSSA) protocol. By leveraging Secure Multiparty Computation (SMC) and homomorphic encryption, the protocol identifies the global minimum cost across multiple providers without compromising their private data. Experimental results demonstrate cost reductions of up to 36% compared to single-provider models.
Introduction
The classic Traveling Salesman Problem (TSP) is a cornerstone of logistics optimization. In a multi-provider environment, a client seeks the cheapest route through a set of cities. While individual shipping companies offer various rates, they treat their cost matrices as trade secrets. Traditional privacy-preserving optimization has focused on two-party scenarios where a single provider is chosen for the entire journey. This "winner-takes-all" approach is often inefficient.
The real-world opportunity lies in "relaying," where the optimal route might involve switching between different providers for different legs of the trip. The challenge is to find this globally optimal, multi-provider route without any party leaking specific pricing to competitors or the client.
Methodology
The authors address this challenge through the Two-level Secure Simulated Annealing (TSSA) protocol. This approach decomposes the $k$-RTSP into two nested optimization levels:
- Top-Level Optimization: Searches for the optimal sequence of cities (the tour).
- Bottom-Level Optimization: For a given sequence, it identifies the best company assignment for each leg.
Secure Computation Techniques
To maintain privacy, the protocol employs several cryptographic building blocks:
- Secure Scalar Product: Utilizing Paillier’s Homomorphic Cryptosystem, the total cost of a route is calculated. The homomorphic property allows parties to sum encrypted costs, ensuring that individual leg prices remain hidden.
- Secure Comparison: The algorithm uses FairplayMP to compare two encrypted costs. This is critical for the "acceptance" step in Simulated Annealing, allowing the system to decide whether to move to a new solution without decrypting the actual values.
- Semi-Honest Security: The protocol is proven secure under the semi-honest adversarial model, where parties follow the protocol but attempt to infer private information from the execution trace.
Experimental Evaluation
The TSSA protocol was evaluated using real-world datasets from the National Imagery and Mapping Agency, covering city coordinates in Canada, Japan, Italy, and China. The experiments scaled from 200 to 1,200 cities ($n$) with 2 to 12 shipping parties ($k$). Competitive cost matrices were generated by adding Gaussian noise to base Euclidean distances.
Key Results
- Cost Efficiency: The collaborative relay model achieved a "Cost Reduction Ratio" of 21% to 36% over the best single-provider scenarios, highlighting the economic value of cross-provider optimization.
- Accuracy: The heuristic error relative to the theoretical minimum remained low, typically between 2% and 20%, confirming the effectiveness of the TSSA approach.
- Scalability and Privacy Trade-offs: While the runtime grows polynomially, the computational overhead of privacy is significant. A 1,200-city problem requires between 1.5 hours (512-bit key) and 10 days (1024-bit key). While high, this is considered acceptable for strategic, long-term logistics planning.
Discussion and Conclusion
The TSSA protocol demonstrates that privacy-preserving technologies can act as an enabler for collaboration in competitive markets. By removing the trust barrier, companies can participate in joint optimizations that benefit the client while protecting market advantages. Furthermore, the probabilistic nature of Simulated Annealing provides an inherent layer of obfuscation against inference attacks.
Future work will focus on improving performance by adopting more modern SMC frameworks like Sharemind or PICCO. Additionally, hardening the protocol against "malicious" actors who might provide fraudulent data remains a critical area for further research.
Summary updated