## 3 Computational Problems and Algorithms
### Minimum Cost Problems  
**Capacitated Vehicle Routing Problem with Time Windows (c-vrtw)**. [PERSON] and [PERSON] [42] considered the following problem. We are given a set \(X=\{x_{1},\ldots,x_{n}\}\) of points (costumers) and a depot \(y\) on the Euclidean plane. Any customer \(x_{i}\in X\) has a demand \(d_{i}\). We are given an unbounded number of vehicles each with capacity \(q\). Each \(x\in X\) is assigned with time window \(T_{x}\). A feasible route is an ordered pair \(R_{j}=(P_{j},D_{j})\), where \(P_{j}=(y,x_{i_{1}},x_{i_{2}},\ldots,x_{i_{n}},y)\) represents the simple cycle taken by vehicle \(j\) in which \(T_{i_{\epsilon}}\leq T_{i_{\epsilon+1}}\) for any \(z\in[s]\), and \(D_{j}=(d_{1j},\ldots,d_{nj})\) in which \(d_{ij}\) is a part of the \(i\)-th customer demand covered by the route \(R_{j}\) and \(1\leq d_{ij}\leq d_{i}\). The goal is to find a set of simple cycles starting at \(y\) such that \(\sum_{i=1}^{n}d_{ij}\leq q\) for any rout \(R_{j}\), \(\sum_{j=1}^{K}d_{ij}=d_{i}\) for any customer \(x_{i}\), and minimizes \(\sum_{j=1}^{K}c(R_{j})=\sum_{j=1}^{K}\sum_{e\in E(P_{j})}c(e)\). For any \(\epsilon\in(0,1)\) and the total customer demand \(d\), [PERSON] and [PERSON] [42] provided a \((1+\epsilon)\)-approximation algorithm in time \(O(n\log d)\) any time provided the capacity \(q\) and the number \(p\) of time windows does not exceed \(2^{\log^{n}n}\) for some \(\delta=O(\epsilon)\). [PERSON] and [PERSON] [43] provided a \((1+\epsilon)\)-approximation algorithm for c-vrtw with a better running time than that of [42], which is \(O(n^{3}+\exp(\exp(\frac{1}{\epsilon})))\). [PERSON] and [PERSON] [44] further investigated c-vrtw when the number of depots is more than one and gave \((1+\epsilon)\)-approximation algorithm in time \(O(n^{3}+K^{O(\frac{1}{\epsilon})}\exp(\frac{1}{\epsilon^{3}}))\), where \(K\) is the number of depots. **Ordered Clustered Traveling Salesman Problem (oc-tsp)**. In this problem (also formalized in Figure 10 for the sake of clarify), a vehicle starting and ending at a given depot must visit a set of \(n\) points partitioned into \(K\) not necessarily disjoint clusters so that points of cluster \(k\) are visited prior to points of cluster \(k+1\), for \(k=1,2,\ldots,K-1\), and the total distance traveled is minimum. _Problem_: Ordered Clustered Traveling Salesman Problem (oc-tsp)  
_Input_: a complete undirected graph \(G=(V,E)\), not necessarily disjoint \(K+1\) clusters \(C_{i}\subseteq V\) (\(1\leq k\leq K\)), where \(\bigcup_{i=0}^{K+1}C_{i}=V,C_{0}=\{s\}\) consists of a single node \(s\) called depot and a cost function \(I:E\rightarrow\mathbb{R}^{\geq 0}\). _Feasible Solution_: Hamiltonian path \(P\) s.t. points of cluster \(k\) are visited prior to points of cluster \(k+1\), for \(k=1,2,\ldots,K-1\). _Goal_: \((I(P)=\sum_{e\in E(P)}I(e)\) minimized. **Figure 10**. Formalization of oc-tsp. Observe that [PERSON] et al. [45] provided \(\frac{5}{3}\)-approximation algorithm for oc-tsp when the clusters are disjoint which runs in \(O(n^{3})\) time. Furthermore, [PERSON] et al. [46] showed the following results for oc-tsp:* The starting and ending vertices in each cluster are given. A 1.9091-approximation algorithm is given [46] which is improved to 1.875 by [PERSON] and [PERSON] [47]. * The two ending vertices in each cluster are given. We are free to choose any one as the starting vertex and the other one as the ending vertex. A 1.8-approximation algorithm is given [46] which is improved to 1.714 by [PERSON] and [PERSON] [47]. * Only the starting vertex in each cluster is given. A 2.643-approximation algorithm is given [46] which is improved to 2.5 by [PERSON] et al. [48]. * End vertices are not specified. A 2.75-approximation algorithm is given [46], which is improved to 2.67 by [PERSON] and [PERSON] [47], improved to 2.167 by [PERSON] and [PERSON] [49], and improved to 1.9 by [PERSON] et al. [48]. **Minimum Cycle Cover Problem (mccp).