Studies that use rivers in a last-mile delivery context are scarce. This research considers the first multimodal alternative based on a barge for parcel delivery activities. It proposes two sustainable network designs for a two-echelon distribution. The efficiency of scenarios is assessed through performance indicators. A three-stage decomposition heuristic is used. Allocation of the customers to the closest satellite at the first stage uses a non-supervised machine learning clustering method, 2D-k-means. The last two stages, comprising the two echelons routing, are solved using a heuristic based on the nearest neighbor procedure. The fixed costs decrease by 41% and energy consumption by 92% when applying a river transportation mode and e-cargo bikes in the distribution network’s first and second echelon, respectively. Future research avenues are to render the results more realistic with the consideration of other costs and a larger network.