# Urban Logistics through River: A Two-Echelon Distribution Model
## 3 Methodology  
The NP-hardness of the 2E-VRP represents a challenge for researchers because approximate algorithms such as heuristics and metaheuristics are needed to solve combinatorial optimization problems by finding feasible solutions. Decomposition strategies are used to solve large-scale real-world problems [40] and overcome the NP-hardness of the 2E-VRP. To solve this problem, a decomposition algorithm is proposed, as used in [41]. The problemis complex, so it is split into three subproblems ensuring the feasibility and the quality of the solution obtained (see Figure 1). The first subproblem is a 2D-\(k\)-means clustering to allocate the delivery points to predetermined satellites; this procedure is made before route optimization to reduce the computational complexity. We considered the latitude and the longitude of each customer's geographic location as \(k\)-means clustering groups customers into clusters based on the two-dimensional Euclidean distance [42; 43]. Let \(k\) be the number of defined clusters, which corresponds to the number of satellites in the distribution network. The centroid of each cluster \(k\) is chosen randomly. The data is analyzed, and the distances between each client and the centroids are determined. Then, for each element, the closest cluster centroid is assigned, and the new centroids of \(k\) clusters are updated. This method has to be repeated until all clients have been assigned to the appropriate cluster. Finally, the clustering results are kept and used to build the initial solution for the routing optimization. The second sub-problem determines the routing for the last-mile delivery from satellites to the customers. The third sub-problem proposes to find a set of routes for the first echelon from the depots to the corresponding satellites. The last two sub-problems were solved by an algorithm based on the NN search [44]. This procedure seeks to build Hamiltonian cycles through links to nearby neighbors. It has been frequently applied to solve the VRP efficiently, even in large-size instances [45; 46; 47]. To create the routes, we use the following steps:  
1. Define the first point of the route (depot or satellite);
2. If the first point is the depot, continue with step 4;
3. If the starting point is a satellite, begin the routing with step 4 in the satellite of the cluster \(i\);
4. Find the nearest node to the last node added to the path. If the nearest node is already in the path, then choose the next closest;
5. Repeat step 4 until the vehicle of the echelon reaches its maximum capacity;
6. Connect the last visited node to the depot or satellite (as appropriate) to form the tour. Calculate the distance traveled by the vehicle and the total route time;
7. If there are unvisited nodes, add one more vehicle and return to step 4;
8. If there are unvisited clusters, return to step 3 in cluster \(i+1\). The instances that were used to solve this problem were taken from a dataset previously proposed by [21], where a case study was presented to solve a parcel distribution problem in an urban delivery system. In this case, a small instance of 50 randomly distributed customers was generated within the city of Paris, France (Figure 2). In Paris, e-commerce accounts for 9.8% of retail trade. This generates 2.8 million weekly goods movements in the greater Paris metropolitan area. Many products sold through e-commerce are delivered to the consumer via carriers operating on the messenger system. These include all manufactured products. The transport of parcels requires a specific organization. The last mile is very important in this scheme, as the branch is not necessarily located in the direct vicinity of the consumer. In addition, the distribution network will have different characteristics in the first echelon. Two different transportation modes will be used to serve the satellites depending on the case.