Multi-Commodity Periodic Vehicle Routing Problem Considering Stockout Penalty And Inventory Costs

In recent years,with the introduction of the new retail concept,the war of ecommerce has spread from the online to the offline.And the community convenience store has become the fiercest battlefield.Focusing on current Chinese convenience stores,whether it is a traditional Japanese convenience store or an emerging community convenience store,the biggest challenge for convenience stores is whether they are profitable.According to the data,community convenience stores have high gross profit but low revenue,and contain small inventory and slow replenishment.Therefore,how to quickly and effectively replenish different types of commodity in community convenience has become a key issue.So,it is very important to use computer technology to provide smart replenishment strategies for community convenience stores.This is also the main problem of this study,the multi-commodity periodic vehicle routing problem considering stockout penalty and inventory costs(MC-PVRPSI).There is some differences between the MC-PVRP-SI and the traditional periodic vehicle routing problem(PVRP).PVRP considers that the delivered goods are only a single type of commodity,and the demand satisfied by each visit is a fixed demand,and the objective is to minimize the total travel costs within the period.However,MCPVRP-SI considers that the delivered goods are multiple types of commodities,different types of commodities are allowed to be distributed in the same vehicle,and the requirements satisfied by each visit are set as decision variables,and the objective is to minimize the total cost of the vehicle driving,the penalty of shortage and the total cost of inventory within the period.For the researched question,Hybrid Genetic Algorithm(HGA)is designed to address the problem.Plenty of operators and heuristic approaches which are developed in terms of the specific constraints and depth optimization are embedded in HGA,including the education operator and the adjustment operator.The education operator is a variable neighborhood search with embedded local search,which is mainly used for path optimization for customers who visit in a single day.The adjustment operator is used to adaptively adjust the delivery demand based on the number of days visited.The objective of the algorithm is to minimize the total cost of the vehicle driving,the penalty of shortage and the total cost of inventory within the period.It is mainly divided into crossover,mutation,education,adjustment,and generation replacement.In order to verify the correctness and effectiveness of the HGA,we degenerate the HGA into an algorithm that contains a single commodity,without adjustment operator,and the objective is to minimize the total cost of the vehicle driving.And testing the algorithm by 20 benchmark instances of periodic vehicle routing problem with time windows(PVRPTW),and the average gap between the optimal solution and the best known solution(BKS)is 1.75%.Furthermore,the average gap between our optimal solution and Cplex's solution is 1.63% among small scale generated instances.The computational results explain the validity and effectiveness of HGA,and prove that our algorithm is competitive on both benchmark instances and generated instances in terms of the accuracy of solution and computational time.There are some sensitivity analysis for some factors in the algorithm after the numerical experiment.In the end,the paper presented some constructive comments to the fleet and the community convenience store respectively.