Recent neural combinatorial optimization (NCO) methods have shown promising problem-solving ability without requiring domain-specific expertise. Most existing NCO methods use training and testing data with a fixed constraint value and lack research on the effect of constraint tightness on the performance of NCO methods. This paper takes the capacity-constrained vehicle routing problem (CVRP) as an example to empirically analyze the NCO performance under different tightness degrees of the capacity constraint. Our analysis reveals that existing NCO methods overfit the capacity constraint, and they can only perform satisfactorily on a small range of the constraint values but poorly on other values. To tackle this drawback of existing NCO methods, we develop an efficient training scheme that explicitly considers varying degrees of constraint tightness and propose a multiexpert module to learn a generally adaptable solving strategy. Experimental results show that the proposed method can effectively overcome the overfitting issue, demonstrating superior performance on the CVRP and CVRP with time windows (CVRPTW) with various constraint tightness degrees.

Recent neural combinatorial optimization (NCO) methods have shown promising problem-solving ability without requiring domain-specific expertise. Most existing NCO methods use training and testing data with a fixed constraint value and lack research on the effect of constraint tightness on the performance of NCO methods. This paper takes the capacity-constrained vehicle routing problem (CVRP) as an example to empirically analyze the NCO performance under different tightness degrees of the capacity constraint. Our analysis reveals that existing NCO methods overfit the capacity constraint, and they can only perform satisfactorily on a small range of the constraint values but poorly on other values. To tackle this drawback of existing NCO methods, we develop an efficient training scheme that explicitly considers varying degrees of constraint tightness and propose a multi-expert module to learn a generally adaptable solving strategy. Experimental results show that the proposed method can effectively overcome the overfitting issue, demonstrating superior performance on the CVRP and CVRP with time windows (CVRPTW) with various constraint tightness degrees.

Attention, learn to solve routing problems!

G.1 Monoids Monoids are one of the simplest algebraic structure.

This paper solves three NP-hard routing problems, traveling salesman problem (TSP), prize collecting TSP (PCTSP), and capacitated vehicle routing problem (CVRP). This section provides detailed descriptions of PCTSP and CVRP (for TSP, see section 3). The PCTSP is similar to TSP, while there are differences in that we do not have to visit all the nodes and that the destination is not the first node but the depot node, i.e., a tour is not a cycle. Let N be the number of nodes. The problem instance of PCTSP is s = {(xi,λi,µi)}N+1i=1, where the xi R2 is in 2D euclidean coordinates, λi R is the penalty of unvisited node, and µi R is the prize of visited node. The L(π|s) is the tour length, and λ(π|s) is the total penalty of the unvisited nodes.

In this section, we prove the Theorem 2.1, which states a problem P and its' orthogonal transformed problem Q(P) = {{Qxi}Ni=1,f}have identical optimal solutions if Qis orthogonal matrix: QQT = QTQ = I. As we mentioned in Section 2.2, reward R is a function of a1:T (solution sequences), ||xi xj||i,j {1,...N} (relative distances) and f (nodes features). And Let R (P)is optimal value of problem P: i.e. Then, the remaining proof is to show Q(P)has an identical solution set with P. Let optimal solution set Π (P) = {πi(P)}Mi=1, where πi(P)indicates optimal solution of P and M is the number of heterogeneous optimal solution. Conversely, For any πi(P) Π (P), they have sample optimal value with Q(P): R(πi(P);P) = R (P) = R (Q(P)) Thus, πi(P) Π (Q(P)).

Each AvehicleC starts sumofcityC, after again.

There are two more things to verify.

Notably, we offer fresh perspectives on how neural solvers can handle VRP constraints.