Modeling and Solving the Vehicle Routing Problem with Step Cost Function and Loading Consideration: A case study

Vehicle Routing Problem (VRP) is one of the major problems in the transportation and distribution planning. In the most previous studies, the objective of VRP models was distance and vehicle related costs. However in many industrial cases along with routing distance, vehicle loading amount is a factor of cost function. In this paper, we formulate a mixed integer non-linear programming (MINLP) model for heterogeneous vehicle routing problem in which problem objective has nonlinear relation with routing distance. Then by analytical methods we reformulate the model as a mixed integer programming (MIP). In this model, at the first transportation cost rate is determined by step function. Then cost of each vehicle calculated by multiplying the transportation cost rate to its loading amount.
Similar to other VRP problems proposed model is also NP-hard. We develop constructive heuristic algorithm to obtain an approximate solution for this problem. This algorithm is developed based on creating a traveling salesman problem (TSP) tour and partitioning it into vehicle routs by heuristic methods. We name proposed algorithm as Salesman Rout Partitioning for Vehicles (SRPV).
In order to evaluation the effectiveness of SRPV algorithm we design 54 experiments in four scenarios. In one hand, lower and upper bounds for these experiments have been obtained by commercial optimization software Cplex 12.2. Besides, proposed heuristic are programmed and compiled using Matlab 2010. Furthermore effectiveness of SRPV algorithm is investigated by two measures, difference percentage and complexity percentage. Our findings indicate that SRPV algorithm sufficiently effective as constructive heuristic for considered type of vehicle routing problem.
Moreover, to demonstrate the practicality of proposed model and solution heuristic, we study an industrial case at FERGAZ Company. This company charges gas cylinders and distributes them among geographically dispersed customers. By using Cplex 12.2 we couldn’t find any feasible solution for FERGAZ’s problem, but approximate solution could be found by heuristic algorithm.