【如何運用量子電腦解決推銷員路線問題】
讓移動成本最小化的組合最佳化問題中有一個「推銷員路線問題」。假設某位推銷員在某地區會逐一訪問所有都市後再回到出發地。就像圖3.14 那樣。此時，求最短路徑的問題就是推銷員路線問題。這是非常有名的典型組合最佳化問題。
在物流領域中，推銷員路線問題 (Traveling Salesperson Problem, TSP) 是一種典型的組合最佳化問題，旨在找出拜訪多個都市一次並返回出發地的最短路徑 。量子電腦，特別是退火型量子電腦（易辛機），非常適合解決這類從龐大數字組合中尋求最佳解的問題。
運用量子電腦解決 TSP 的方式如下：
1. 問題公式化： 首先，將 TSP 轉換為易辛機可處理的二元變數二次多項式形式（易辛模型或QUBO形式）。
◦ 定義變數：引入二元變數 xi,a，當都市 i 在第 a 個順序被造訪時設為 1，否則為 0 。
◦ 建立目標函數（哈密頓算符）：這個函數包含欲最小化的目標和所有約束條件 。
總移動距離：目標函數中會有一項表示所有移動距離的總和 Σ di,j * xi,a * xj,a+1，目標是使其最小化 。
雙重約束：TSP 的核心是兩個必須滿足的約束，它們會以「懲罰項」的形式加入目標函數，若違反約束則能量值會升高 。
• 每個都市只造訪一次：確保每個都市 i 在所有造訪順序 a 中只被 xi,a=1 選取一次 。
• 每個順序只造訪一個都市：確保在每個造訪順序 a 中，只有一個都市 i 被選為 xi,a=1 。
這些懲罰項通常是基於變數組合的平方形式，並透過參數 A1 和 A2 控制其懲罰強度。
2. 量子運算執行： 退火型量子電腦透過量子退火 方法，尋找使上述目標函數能量最低（對應最佳路徑）的變數組合 。它們會透過物理位元間的耦合來模擬問題的相互作用。
3. 優勢與應用考量：
◦ 高速近似解：對於大規模的 TSP，古典電腦可能需要極長時間，而量子電腦能在數十至數百微秒內提供良好的近似解，這在許多實際物流應用中已足夠。
◦ 多樣化解法：即使古典電腦有高度優化的 TSP 演算法，易辛機提供多樣性的近似解，有助於在問題涉及無法完全公式化的複雜因素時，供人工從多個候選方案中進行選擇。
◦ 功能擴展：透過在目標函數中增加額外項，還能納入更複雜的條件，例如避免跨越特定地理邊界，或優先造訪某些地點 。
儘管目前在特定 TSP 問題上，易辛機相較於高度優化的古典演算法可能在純速度上不具壓倒性優勢 ，但其在處理組合最佳化問題的潛力及不斷演進的性能 ，使其成為物流最佳化未來的重要工具。
《量子電腦入門：從零開始了解未來運算革命》‧工藤和惠
文章標籤
全站熱搜
