Research On Heterogeneous Fleet Vehicle Routing Problem With Step Cost

As the logistics industry has developed to the new stage of "lower cost,higher efficiency" in China,enterprises are paying increasing attention to control logistics cost.In order to reduce logistics costs,tobacco companies adopt a logistics model of "outsourcing but independent decision-making".The step cost freight and heterogeneous fleet vehicles are two core features of this logistics model,meanwhile,some orders need to be split delivered and the maximum number of customers transported by a single vehicle is limited.The mathematical expression of the step cost freight is a piecewise function,which is usually difficult to solve.And there are only few studies on this problem,so it is of great practical significance and academic value to study the heterogeneous fleet vehicle routing problem with step cost.Based on the cigarette trunk logistics of tobacco industry enterprises,respectively,this paper proposes the Heterogeneous Fixed Fleet Vehicle Routing Problem with Step Cost and Time Window(SC-HFFVRPTW)and the Heterogeneous Fixed Fleet Vehicle Routing Problem with Step Cost,Time Window and Split Delivery(SC-HFFVRPTWSD).For the SC-HFFVRPTW,a mixed integer programming model is established aimed at the total cost minimizing.Based on the problem characteristic analysis,two key theorems are proposed and proved,according to which a step cost heuristic algorithm(SCH-I)is designed.Further on,an improved branch and price algorithm(IBAP)and a variable neighborhood search algorithm(VNS-I)are proposed.Among them,IBAP is used to obtain the exact solution,in which two branching strategies including arc branching and vehicle branching are designed,meanwhile,two accelerating strategies are put forward including maximizing the use of the solution to the subproblem and calling the subproblem solving algorithm sequentially.VNS-I is used to solve large-scale problems,and it includes a special encoding method and five valuable neighborhood structures.For the SC-HFFVRPTWSD,this paper establishes a mixed integer programming model with the goal of minimizing the total cost and proposed the order splitting rules based on the analysis of two key theorems mentioned above.Meanwhile,the step cost heuristic algorithm(SCH-Ⅱ)and the variable neighborhood search algorithm(VNS-Ⅱ)containing six neighborhoods are proposed.Finally,in order to analyze the effectiveness of algorithms,the generated benchmark and enterprise reference database are used to verify proposed algorithms.Result shows that the step cost heuristic algorithm,the improved branch and price algorithm and the variable neighborhood search algorithm can effectively solve the cases generated by the Solomen benchmark.At the same time,the results also show that the above algorithm has significant advantages when used to solve the tobacco trunk line logistics of BHZY Industrial Co.,Ltd.,which can save about 9%-15% of the logistics cost.In more detail,when solving the SC-HFFVRPTWSD,IBAP algorithm can obtain the optimal solution in both small and medium-scale and even in some large-scale cases,which shows the effect of the two accelerating measures and arc branching strategies in IBAP algorithm.In contrast,although SCH-I and VNS-I are inferior to IBAP in terms of solution quality,they have obvious time advantages in large-scale problems,and VNS-I has more advantages than SCH-I.Further,when solving the SC-HFFVRPTWSD,the solution quality of VNS-Ⅱ is significantly higher than that of SCH-Ⅱ,but SCH-Ⅱ has the time advantage.