In this paper, a Multiobjective Route-based Fuel Consumption Vehicle Routing problem (MRFCVRPs) is solved using a new variant of a Multiobjective Particle Swarm Optimization algorithm, the Parallel Multi-Start Non-dominated Sorting Particle Swarm Optimization algorithm (PMS-NSPSO). Three different versions of this algorithm are used and their results are compared with a Parallel Multi-Start NSGA II algorithm and a Parallel Multi-Start NSDE algorithm. All these algorithms use more than one initial populations of solutions. The Variable Neighborhood Search algorithm is used in all algorithm for the improvement of each solution separately. The Multiobjective Symmetric and Asymmetric Delivery Route-based Fuel Consumption Vehicle Routing Problem and the Multiobjective Symmetric and Asymmetric Pick-up Route-based Fuel Consumption Vehicle Routing Problem are the problems that are solved. The objective functions correspond to the optimization of the time needed for the vehicle to travel between two customers or between the customer and the depot and to the Route based Fuel Consumption of the vehicle considering the traveled distance, the load of the vehicle, the slope of the road, the speed and the direction of the wind, and the driver’sbehavior when the decision maker plans delivery or pick-up routes. A number of modified Vehicle Routing Problem instances are used in order to measure the quality of the proposed algorithms.