Load-dependent vehicle routing problem for chilled and frozen products delivery

This research investigates a class of vehicle routing problem (VRP) that considers load-dependent distance and route time window. The problem is motivated by a real case of delivering frozen and chilled products of suburban in Thailand. A mixed integer programming (MILP) model for the problem is formulated to minimize the total load-dependent distance. The model is derived from the energy-minimizing vehicle routing problem. A cluster-first route-second-based heuristic approach that employs a load-dependent saving algorithm in the clustering stage and an optimization model in the routing phase is developed for addressing large-scale instances. The performance of the mathematical model solved by a commercial solver and the heuristic algorithm is tested on 23 problem instances. In addition, to evaluate the impact of the vehicle capacity and route time restrictions on the solution, the problem instances are tested with four different combinations of these two parameters (case 1: 100 boxes, 9 hours, case 2: 100 boxes, 5 hours, case 3: 80 boxes, 9 hours, case 4: 80 boxes, 5 hours). The obtained results indicate that the heuristic algorithm can reach solutions with an average of 6.74%, 6.04%, 14.72 %, 10.74% off optimal for seven instances, four instances, seven instances, seven instances for case 1, 2, 3, and 4, respectively, and 12.46 %, 13.63%, 15.76%, 17.65% off the lower bound on 16 instances, 19 instances, 16 instances, 16 instances for case 1, 2, 3,4 respectively.