Rethinking Order-First Split-Second for Vehicle Routing Problems in Neural Combinatorial Optimization

Neural combinatorial optimization (NCO) has achieved promising performance in vehicle routing problems (VRPs), but how solution representation affects the learning process remains unclear. Inspired by the classical order-first, split-second strategy, we investigate whether neural routing models can benefit from generat- ing only customer orders while delegating route partitioning to an exact Split de- coder. We conduct a systematic comparison between direct route construction and customer-ordering policies with Split decoding under single-task learning, multi- task learning, and various generalization settings. Experiments are performed on synthetic instances, public benchmarks, larger problem sizes, and unseen combi- nations of routing constraints. The results show that replacing route construction with customer ordering does not provide consistent improvements. Although Split can always obtain the best feasible partition for a given customer order, it cannot modify an inappropriate order or recover information unavailable to the policy. The performance gap becomes more significant when constraints, such as hard time windows, strongly couple customer ordering and route planning. These find- ings indicate that reducing the number of neural decisions alone is insufficient to improve routing performance. Effective neural routing methods require joint consideration of solution representation, available information, and downstream optimization procedures.