This paper addresses the common joint replenishment and delivery (JRD) problem that occurs in a multi-item inventory system. An ε-optimal algorithm and a dual lower bound are proposed via deeply analyzing the mathematical properties of the model. The randomized numerical experiments show that the proposed ε-optimal algorithm outperforms the existing meta heuristics both in terms of both accuracy and efficiency, and the largest increase in accuracy can reach 31〖WTXT〗%〖WTBZ〗. The dual lower bound is very tight, with the gap averaging below 0.84〖WTXT〗%〖WTBZ〗. Moreover, the proposed ε-optimal algorithm is also very fast, and a 100-item instance can be solved in twenty-three seconds. In addition, the time complexity of the ε-optimal algorithm is analyzed. The ε-optimal algorithm can achieve O(n) polynomial-time complexity under real-world situations, which enriches the algorithmic design theory of the JRD research. Finally, the effect of coordinated delivery is analyzed. Experiments show that coordinated delivery can achieve cost reduction when the inventory management level of the central warehouse is higher than that of the retailers.