## 3 Solution Approach
### Re-Optimization Stage and VNS-TA Algorithm
#### 3.2.2 Shaking Process
* Step 3 Randomly generate 1 or 2. * Step 4 When 1 is generated, execute the following statements. * Step 4.1 Randomly select the number \(b\) of nodes to be exchanged, where \(1\leq b\leq 5\). * Step 4.2 Deal with extreme points. When \(i_{1}\geq n-b+2\), assign \(n-b+1\) to \(i_{1}\). When \(i_{2}\leq b-1\), assign \(b\) to \(i_{2}\). * Step 4.3 For \(newq\). If \(b=1\), exchange nodes \(i_{1}\) and \(i_{2}\). If \(b\geq 2\), exchange two client node fragments \(i_{1}\sim i_{1}+b-1\) and \(i_{2}-b+1\sim i_{2}\) without changing direction. Gain \(newq\). * Step 5 When 2 is generated, execute the following statements. * Step 5.1 Randomly select the number \(a\) of nodes of the client node fragment to be exchanged with a single client node, where \(2\leq a\leq 5\). * Step 5.2 Deal with the extreme points. When \(i_{2}\leq a-1\), assign \(a\) to \(i_{2}\). * Step 5.3 For \(newq\). Exchange the single node \(i_{1}\) and the node fragment \(i_{2}-a+1\sim i_{2}\) without changing direction. Gain \(newq\). * Step 6 Remove duplicate nodes in \(newq\) without changing the sequence order of the client nodes. * Step 7 Output \(newq\). * Integrated-cross-insert neighborhood and integrated-icross-insert neighborhood. The integrated-cross-insert neighborhood and integrated-icross-insert neighborhood are designed based on the ideas of the insert, cross-exchange and icross-exchange operators. The insert operator process is as follows: two points on the path are randomly selected, and one point (or node fragment) is inserted in front of or behind the other node. Note that the steps of the integrated-icross-insert neighborhood are nearly identical to those of the integrated-cross-insert neighborhood, except for the action of changing the direction of the node fragment before the insertion. The steps for the integrated-cross-insert neighborhood are as follows. * Step 1 Obtain the number \(n\) of all client nodes of path \(q\). * Step 2 Randomly select two different client nodes in \(q\), and assign the nodes to \(j_{1}\) and \(j_{2}\) according to the position order, where \(j_{1}\) and \(j_{2}\) are the two anchor points for the insertion operation to be performed. * Step 3 Randomly generate 1 or 2. * Step 4 When 1 is generated, execute the following statements. * Step 4.1 Randomly select the number \(b\) of client nodes to be inserted, where \(1\leq b\leq 5\). * Step 4.2 For \(q\). If \(j_{1}<n-b+2\), insert client nodes \(j_{1}\sim j_{1}+b-1\) between client nodes \(j_{2}\) and \(j_{2}+1\) to form a new path sequence \(newq\). Note that both single-node and multi-node insertions are included. * Step 4.3 Otherwise, assign \(q\) directly to \(newq\). * Step 5 When 2 is generated, execute the following statements. * Step 5.1 Randomly select the number \(a\) of client nodes to be inserted, where \(1\leq a\leq 5\). * Step 5.2 For \(q\). If \(j_{2}>a-1\), insert client nodes \(j_{2}-a+1\sim j_{2}\) between client nodes \(j_{1}\) and \(j_{1}+1\) to form a new path sequence \(newq\). * Step 5.3 Otherwise, assign \(q\) directly to \(newq\). * Step 6 Remove duplicate nodes in \(newq\) without changing the sequence order of the client nodes. * Step 7 Output \(newq\).