In the last few decades, a vehicle routing problem (VRP) is one of the significant issues in order to increase efficiency and productivity in logistic and transportation systems. In this problem, there is a set of vehicle located in one or more depots to serve a set of customers with a deterministic demand. In this paper, a new mathematical model is introduced to maximize the customer satisfaction by minimizing the fleet cost, routes cost, and tardiness penalty of violating soft time windows. Soft time windows in serving customers are considered outside of hard time windows. This model belongs to a class of NP-hard problems that cannot be optimally solved within reasonably computational time. Thus, an efficient metaheuristic method based on simulated annealing (SA) is proposed. To improve the quality of SA, 1-Opt and 2-Opt genetic operators are introduced. A number of test problems are solved by this proposed SA in order to show its efficiency. The associated computational results are compared with the results obtained by the Lingo 6 software package.
)