This paper considers a profitable heterogeneous vehicle routing problem with cross-docking (PHVRPCD). In the real world, it is not possible to serve all customers and suppliers. Based on the purchasing cost and selling price of the products as well as the resource limitation, they will be in the plan only if it is profitable to serve them, so satisfying all demands is not necessary. Cost reduction has been considered in the previous studies as a main objective while neglecting the total profit. In this study, increasing the total profit of a cross-docking system is the main concern. For this purpose, a mixed-integer linear programming (MILP) model is used to formulate the problem mathematically. A new hybrid meta-heuristic algorithm based on modified variable neighborhood search (MVNS) with four shaking and two neighborhood structures and a genetic algorithm (GA) is presented to solve large-sized problems. The results are compared with those obtained with an artificial bee colony (ABC) and a simulated annealing (SA) algorithm. In order to evaluate the performance of the proposed algorithms, various examples of a real data set are solved and analyzed. The computational results reveal that in the small-size test problems, the hybrid algorithm is able to find optimal solutions in an acceptable computational time. Also, the hybrid algorithm needs less computational time than others and could achieve better solutions in large-size instances. Display omitted •A practical version of vehicle routing problem integrated with cross docking is modeled and defined.•Three meta-heuristic algorithms, nam-ely a hybrid GA with modified VNS, ABC and SA are designed to solve large-size problems.•A new heuristic algorithm is developed to generate high quality initial solutions.•Our proposed model and solution methods are evaluated in a set of real-world inspired instances.•It was proved that the proposed hybrid algorithm has acceptable performance and is significantly better than the others in this problem.