This work considers a real-world Swap-Body Vehicle Routing Problem (SBVRP). A mixed Integer programming (MIP) formulation of SBVRP proposed. Constructive heuristic for generating an initial solution proposed. Two general variable neighborhood search heuristics implemented. Parallel general variable neighborhood search developed.