ATTENTION, LEARN TO SOLVE ROUTING PROBLEMS
Abstract
問題描述
車輛路徑問題（Vehicle Routing Problem, VRP）, 車輛路線問題最早是由Dantzig和Ramser于1959年首次提出，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個車隊(duì)負(fù)責(zé)分送貨物，組織適當(dāng)?shù)男熊嚶肪€，目標(biāo)是使得客戶的需求得到滿足，并能在一定的約束下，達(dá)到諸如路程最短、成本最小、耗費(fèi)時間最少等目的。
Daima:
https://github.com/MichelDeudon/encode-attend-navigate
https://github.com/mc-ride/orienteering
https://github.com/jordanamecler/PCTSP
https://github.com/rafael2reis/salesman
參數(shù)化一個模型,output一個排列,學(xué)習(xí)過程是使得這個排列的概率盡可能大.
構(gòu)建可行解的概率分布,優(yōu)化分布.
image.png
Attention
Attention model
model
iencoder
the encoder computes initial dh-dimensional node embeddings
image.png
image.png
decoder
RL
image.png
