In this chapter we address the problem of grouping orders into shipments for delivery that considers compatibility constraints as well as vehicle freight that is based on the direct distances to the farthest customers (PGOCCDD). This problem can be seen as a variant of the vehicle routing problem (VRP) that arises in the context of the last mile distribution to small stores and nanostores in developing countries, particularly in Latin America. Contrarily to the traditional VRP, in which the total distance traveled by vehicles is minimized, in our case the route costs depend solely on the direct distance to the delivery points that are located farthest with respect to the depot where vehicles originate. In addition, items to be delivered belong to categories of products that may not be compatible. To solve this problem, we propose a mathematical formulation to obtain exact solutions as well as a multi-start perturbation tabu (MSPT) neighborhood search heuristic that is composed of the greedy randomized adaptive search procedure (GRASP), tabu search (TS), and “iterated local search” (ILS). Our computational experiments show that the MSPT is competitive as it allowed us to obtain superior solutions in very short running times when compared to the exact method running for up to 5 hours in a high-performance computer.