Privacy-Preserving Local Search for the Traveling Salesman Problem

Jun Sakuma, Shigenobu KobayashiInTech 2010 · DOI · OpenAlex

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.

Basic interaction between a Server (holding cost vectors) and a Searcher (holding city subsets).

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.

Various distributed scenarios for the TSP, including multi-server and multi-searcher configurations.

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

  1. 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.
  2. Blinded Random Shares: To prevent the searcher from inferring costs from the results, a random blinding factor is added to the encrypted difference.
  3. 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

Abstract

In this chapter, we specifically examine distributed traveling salesman problems in which the cost function is defined by information distributed among two or more parties. Moreover, the information is desired to be kept private from others. As intuitive situations in which distributed private information appears in combinatorial optimization problems, we take problems in supply chain management (SCM) as examples. In SCM, the delivery route decision, the production scheduling and the procurement planning are fundamental problems. Solving these problems contributes to improvement of the correspondence speed to the customer and shortening the cycle time(Vollmann, 2005; Handfield & Nichols, 1999). In the process of forming the delivery route decision and production schedule decision, the combinatorial optimization plays an important role. When the SCM is developed between two or more enterprises, information related to the stock, the production schedule, and the demand forecast must be shared among enterprises. Electronic Data Interchange (EDI), the standardized data exchange format over the network, is often used to support convenient and prompt information sharing1. Information sharing apparently enhances the SCM availability; however, all information related to the problem resolution must be disclosed to all participants to lay the basis for global optimization. Such information is often highly confidential and its disclosurewould be impossible in many cases. As more concrete examples, two scenarios are presented. These scenarios pose situations that appear to be unsolvable unless private information is shared. Scenario 1: Let there be a server EA that manages a route-optimization service and a user EB who tries to use this service. The user’s objective is to find the optimal route that visits points F1, ...,Fn chosen by himself. The user, however, does not like to reveal the list of visiting points to the server. The server manages a matrix of cost for traveling between any two points. The server does not like to reveal the cost matrix to the user, either. How can the user learn the optimal route without mutually revelation of private information? Note that this problem is obviously solved as the Traveling Salesman Problem (TSP) if either of traveling cost or visiting points is shared. As more complicated examples, a multi-party situation is described next. Scenario 2: Let there be two shipping companies EA and EB in two regionsA and B. Client EC requests that EA deliver freight to point F A 1 , ...,Fn in region A and also requests EB to deliver
BibTeX
@inproceedings{sakuma2010privacy,
  author = {Jun Sakuma and Shigenobu Kobayashi},
  title = {{Privacy-Preserving Local Search for the Traveling Salesman Problem}},
  booktitle = {InTech},
  year = {2010},
  doi = {10.5772/12933},
}
Figure