Abstract
We propose a manager-worker framework based on deep reinforcement learning totackle a hard yet nontrivial variant of Travelling Salesman Problem (TSP),\ie~multiple-vehicle TSP with time window and rejections (mTSPTWR), wherecustomers who cannot be served before the deadline are subject to rejections.Particularly, in the proposed framework, a manager agent learns to dividemTSPTWR into sub-routing tasks by assigning customers to each vehicle via aGraph Isomorphism Network (GIN) based policy network. A worker agent learns tosolve sub-routing tasks by minimizing the cost in terms of both tour length andrejection rate for each vehicle, the maximum of which is then fed back to themanager agent to learn better assignments. Experimental results demonstratethat the proposed framework outperforms strong baselines in terms of highersolution quality and shorter computation time. More importantly, the trainedagents also achieve competitive performance for solving unseen largerinstances.