Research On The Hybrid Heuristic Algorithm For The Inventory Routing Problem With Multiple Periods

Inventory routing problem(IRP),as the basic theory of logistics distribution system,is mainly devoted to studying how to deliver products to several retailers for suppliers.In this problem,both the delivery time as well as quantity and the delivery route of vehicles should be decided,and it aims to minimize the total cost,satisfying multiple constraints.The IRP with multiple periods under maximum-level delivery strategy(MPIR-ML)is one of IRP's varieties,but there is little research about it.The paper has studied the MPIR-ML and its related algorithms.In this article,the problem has been described with mathematical language,and the general model,the sub-loop elimination model and the relaxation model have been given.In the following,an iterative local search algorithm based on mixed integer programming(ILS-MP)has been proposed to solve MPIR-ML.ILS-MP has employed three neighborhood actions to adjust the routing structure,including the insertion and deletion of customer nodes and the exchange between two periods of the nodes' access state.In order to speed up the search,fast evaluations and neighborhood reduction strategies have been introduced to these three moves respectively.In addition,a MIP model is solved to obtain the best delivery quantity of customers,while the know algorithm LKH,which is developed to solve the travelling salesman problem,is used for getting route.By the way,the cache technology is applied to reduce the frequency of calls to LKH.Finally,the performance of the algorithm has been tested on the instance sets of different count of periods and customers,and the results have been compared with others.Compared to known algorithms BC and HAIR,ILS-MP can obtain optimal of small and medium scale instances with far better time behavior.While the results of large scale instances have obvious advantages,compared with MIP,DAIR and RIS-IM.In conclusion,the effectiveness of ILS-MP can be proved in terms of computation time and quality of solution.