Profitable Vehicle Routing Problem with Multiple Trips: Modeling and Variable Neighborhood Descent Algorithm

In this paper, we tackle a new variant of the Vehicle Routing Problem (VRP) which combines two known variants namely the Profitable VRP and the VRP with Multiple Trips. The resulting problem may be called the Profitable Vehicle Routing Problem with Multiple Trips. The main purpose is to cover and solve a more complex realistic situation of the distribution transportation. The profitability concept arises when only a subset of customers can be served due to the lack of means or for insufficiency of the offer. In this case, each customer is associated to an economical profit which will be integrated to the objective function. The latter contains at hand the total collected profit minus the transportation costs. Each vehicle is allowed to perform several routes under a strict workday duration limit. This problem has a very practical interest especially for daily distribution schedules with limited vehicle fleets and short course transportation networks. We point out a new discursive approach for profits quantification which is more significant than those existing in the literature. We propose four equivalent mathematical formulations for the problem which are tested and compared using CPLEX solver on small-size instances. Optimal solutions are identified. For large-size instance, two constructive heuristics are proposed and enhanced using Hill Climbing and Variable Neighborhood Descent algorithm based on a specific three-arrays-based coding structure. Finally, extensive computational experiments are performed including randomly generated instances and an extended and adapted benchmark from literature showing very satisfactory results.