논문: Attention, Learn to Solve Routing Problems
https://arxiv.org/pdf/1803.08475.pdf
여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것
Finding optimal solution for all problem instances → Impossible
Finding acceptable solutions for relevant problem instances
→ use heuristics : next location should be nearby
Designing heuristics is a hard work
→ use deep learning (do not need feature engineering)
개별 Node를 Attention mechanism을 이용해서 개별 점들을 encode하고 이를 이용해서 point의 집합 전체를 표현하는 방법을 제안.
Transformer 과 유사하지만, positional encoding을 하지 않고, decoder의 input, output에 차이가 있다. TSP의 경우 노드 위치를 embedding으로 직접 사용하고, input 노드의 순서를 따로 모델링할 필요가 없기 때문에 positional encoding이 필요가 없다. → more
Decoder의 경우 모든 노드에서 생성된 encoder output만을 사용하는 것이 아니라 특정 처리를 해주어 함께 사용한다.
이외의 multi-head attention, position-wise feed forward network는 기존의 transformer와 같은 모델을 사용함

Encoder는 노드 전체의 embedding을 생성하며, decoder에서 방문할 노드의 순서를 정함