# A Review: Machine Learning for Combinatorial Optimization Problems in Energy Areas
## 3 Learning to Solve COPs
### Problems
#### 3.2.3 Traveling Salesman Problems
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Problem** & **Method** & **Reference** & **Year** & **Description** & **Scale** \\ \hline \hline \multirow{8}{*}{S2V} & [PERSON] [76] & 2015 & Ptr-Net & \textless{}50 \\  & [PERSON] [85] & 2016 & Ptr-Net + & 20, 50, 100 \\  & [PERSON] [86] & 2018 & REINFORCE & \multirow{2}{*}{20, 50, 100} \\  & [PERSON] [86] & 2018 & attention+REINFORCE+2-opt & & 20, 50, 100 \\  & \multirow{2}{*}{[PERSON] [87]} & \multirow{2}{*}{2018} & \multirow{2}{*}{attention+Sinkhorn} & \multirow{2}{*}{20} \\  & & & Policy Gradient & \\  & & & Transformer+REIN & \\  & \multirow{2}{*}{[PERSON] [88]} & \multirow{2}{*}{2019} & \multirow{2}{*}{baseline relating to the best model} & \multirow{2}{*}{20, 50, 100} \\  & & & so far & \\  & [PERSON] [246] & 2020 & attention+REINFORCE & 20, 50, 100 \\ \hline \multirow{8}{*}{TSP} & [PERSON] [81] & 2017 & GNNs & 20 \\  & [PERSON] [95] & 2017 & Q-learning, & 50–2000 \\  & \multirow{2}{*}{G2V} & \multirow{2}{*}{[PERSON] [253]} & \multirow{2}{*}{2019} & GNNs + beam & \multirow{2}{*}{20, 50, 100} \\  & & & search & \\  & [PERSON] [233] & 2019 & GNNs, message & & \\  & [PERSON] [244] & 2019 & Graph pointer Network+hierarchical & 250, 500, 750, 1000 \\  & \multirow{2}{*}{[PERSON] [248]} & \multirow{2}{*}{2021} & transformer+AC & 20, 50, 100 \\ \hline \multirow{2}{*}{end-to-end} \multirow{2}{*}{Vlaste-lica [83]} & \multirow{2}{*}{2020} & an end-to-end \multirow{4}{*}{5, 10, 20, 40} \\  & & & trainable & \\ \multirow{2}{*}{end-to-end} \multirow{2}{*}{Vlaste-lica [83]} & \multirow{2}{*}{2020} & architecture & \multirow{2}{*}{5, 10, 20, 40} \\  & & & to learn cost terms & \\ \hline \multirow{2}{*}{game} & Kulkar-ni [92] & 2009 & Probability & \\  & \multirow{2}{*}{Shaha-dat [91]} & \multirow{2}{*}{2021} & Collectives & \multirow{2}{*}{3 depots, 3 vehicles} \\  & & & competitive game & \\ \multirow{2}{*}{} & \multirow{2}{*}{Shaha-dat [91]} & \multirow{2}{*}{2021} & among strategies & - \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Methods for TSP. Some RL improvement methods are proposed to solve TSP. [PERSON] et al. [97] proposed NeuRewriter to learn region-picking and rule-picking policies and improved a feasible solution by locally rewriting. They tested NeuRewriter on Capacitated VPR of sizes 20, 50, and 100. [PERSON] et al. [249] proposed to use RL to choose heuristic improvement operators, and the other class of operators, namely perturbation operators, was used to avoid the local optimum. [PERSON] et al. [248] proposed an attention mechanism-based architecture to choose a node pair for pairwise local operators without human guidance, which outperforms other deep models on TSP and CVRP instances. Game theoretic methods have also been applied in TSPs. [PERSON] et al. [92] proposed to solve MTSPs using probability collectives, where agents try to maximize their own utility, which is assigned by a global utility independently. They obtained good solutions in a short time on small-scale MTSPs. [PERSON] et al. [91] created a competitive game among strategies over TSPs. At each step, two strategies were compared, and the winner was used as a demonstration to the loser.