## 5 Methodology
### Heuristic Approach  
The development of the solution is divided into two phases, the first one is to generate the route of the auto-carrier and the second one the vehicle allocation in the auto-carrier, both phases are part of a main algorithm. In the first phase, the routes are obtained with the implementation of the Solomon I1 insertion heuristic, due to the logistics company is needed to obtain a solution to the VRPTW in fairly necessary time, given that the VRPTW is an NP-complete problem [28]. This routing process applies a methodology of cluster first, route second, i.e., first group by the dealership, to then build the route, which starts with the dealership that has the shortest and earliest time window, considering the allocation and capacity constraints. The following describes the application of the Solomon I1 insertion heuristic [4] and the vehicle loading process for allocation phase on this VRPTW. The routing algorithm builds a feasible solution by constructing one route at a time. At each iteration the algorithm decides which new dealership \(u^{*}\in U\) has to be inserted in the current solution, and between which adjacent dealership \(i(u^{*})\) and \(j(u^{*})\) the new dealership \(u^{*}\) has to be inserted on the current route. When choosing \(u^{*}\), the algorithm takes into account both the cost increase associated with the insertion of \(u^{*}\), and the delay in service time at dealerships following \(u^{*}\) on the route. The three steps of the algorithm are:  
**Step 0**. _(Initialization)_. The first route is initially \(R_{1}=\{0,i,0\}\), where \(i\) is the dealership with the shortest and earliest time window. In the allocation phase, if vehicle \(m\) of dealership \(i\) has a feasible assignment, then set \(k=1\), otherwise get the next vehicle from dealership \(i\) or next dealership with the shortest and earliest time window, until the allocation phase of the vehicle \(m\) is feasible. **Step 1**. Let \(R_{k}=\{i_{0},i_{1},\ldots,i_{m}\}\) be the current route, where \(i_{0}=i_{m}=0\), i.e., the NCSY. Set  
\[f1(i_{p-1},u,i_{p})=\alpha(r_{i_{p-1}u}+r_{ui_{p}}-\mu r_{i_{p-1}i_{p}})+(1- \alpha)(b_{i_{p}}^{u}-b_{i_{p}}) \tag{11}\]  
where \(0\leq\alpha\leq 1\), \(\mu\geq 0\) and \(b_{i_{p}}^{u}\) is the time when service begins at dealership \(i_{p}\) provided that dealership \(u\) is inserted between \(i_{p-1}\) and \(i_{p}\). For each unrouted dealership \(u\), compute its best feasible insertion position in route \(R_{k}\) as:  
\[f1(i(u),u,j(u))=\min_{p=1,\ldots,m^{\prime}}f1(i_{p-1},u,i_{p})\]  
where \(i(u)\) and \(j(u)\) are the two adjacent vertices of the current route between which \(u\) should be inserted. Determine the best unrouted customer \(u^{*}\) to be inserted yielding. \[f2(i(u^{*}),u^{*},j(u^{*}))=\max_{u}\{f2(i(u),u,j(u))\}\]  
where  
\[f2(i(u),u,j(u))=\lambda r_{0_{u}}-f1(i(u),u,j(u)) \tag{12}\]  
with \(\lambda\geq 0\). **Step 2**. Insert dealership \(u^{*}\) in route \(R_{k}\) between \(i(u^{*})\) and \(j(u^{*})\), in the allocation phase, if vehicle \(m\) of dealership \(u^{*}\) has a feasible assignment, then go back to **Step 1**, otherwise get the next vehicle from dealership \(u^{*}\) until the allocation phase of the vehicle \(m\) is feasible. If \(u^{*}\) does not exist, but there are still unrouted dealerships, set \(k=k+1\), initialize a new route \(R_{k}\) (as in **Step 0**) and go back to **Step 1**. Otherwise, **STOP**, a feasible solution has been found. The insertion heuristic tries to maximize the benefit obtained when servicing a dealership on the current route rather than on an individual route. For example, when \(\mu=\alpha=\lambda=1\), Equation (12) corresponds to the saving in distance from servicing dealership \(u\) on the same route as dealership \(i\) and \(j\) rather than using an individual route. The best feasible insertion place of an unrouted dealership is determined by minimizing a measure, defined by the Equation (11), of the extra distance and the extra time required to visit it.