Multi-Period Inventory Routing Problems And Their Huristic Algrithms

The issue that how to coordinate many enterprises in the Supply Chain (SC) has become one of the vital points must be adressed in Supply Chain Management(SCM), beacause the competition among enterprises has been upgraded to that of SCs,being prompted by economic globalization and the rapid development of information technology. Vendor Managed Inventory (VMI) is a kind of model for adapting to collaration of multiple enterprises in SCM, which is useful in optimal allocatiing resources and cutting total logistics cost down.Inventory and transportation are the two main functions of logistics system, their expenses occupy about 2/3 of total logistics cost.The Inventory Routing Problem (IRP) which integrating the two main functions is one of the vital points that must be addressed in VMI.Based on studying relevant literature of IRP, the thesis claims that the researching on IRP in China is still in its initial stage,and lacks of deeply resraching on complex IRP. Starting from simple single-cycle IRP with discrete stochastic demand, and changing the constrains demand characteristics, or increasing planing period, or adding the frequency restrictions, or expansing level of topologyconstraints,four categories of practical IRPs, they are single-cycle IRP with discrete stochastic demand, short planning-period continuous-random demand IRP, rolling multi-cycle IRP, and multi-cycle three-echelon IRP, are analysesed in cost composition and modeling.Then the corresponding heuristic algorithms designed, and the models or algrithms are tested by some benchmarks.Only one-time transportation and inventory is considered in optimizing the single-cycle discrete stochastic demand IRP. The example testing has shown that the IRP have great varity impacted by demand characteristics, and the gap between capacity of vehicle and demand, and the gap between transportation cost and inventory cost. Later, a method of mean (expected) processing for the short planning period continuous stochastic demand IRP is used for constructing its mathematical model. After discussing the distributing point of time, distributiing volume, distributing priorities, a huristics algrithm is proposed with (s,S) inventory policy both in Distribution Center (DC) and any retailer. The satisfactory solution for the simulation example of the short planning period continuous stochastic demand IRP declares that, the results get from the model and huristics algritm is better than that of simple mean processing approach.Refered to a Tabu Search (TS)algrithm in literature for solving the Capacitated Vehicle Routing Problem (CVRP) proposed by a recent literature, and in order to improving its self-adapting property, an adjacent information and dynamically candidate-set size approach is designed for improving the TS algorithm.Test examples show that the modified TS algorithm is successful in saving about 50% of time when solving large-scale CVRP (the number of customers is more than 100). Learning from the general Vehicle Routing Problem (VRP) with modeling ideas, a rolling-period multi-cycle model is constructed for the two-echelon IRP, and base on "Greedy" ideas, a local search huristics algrithm is designed by using "maximum adjustment" and "minimum adjustment" alternately.Finally, by adding ordering cost in DC,the IRP is expaned from two-echelon to three-echelon, and its mathmatic model is prompted, using the ideas of inventory problem, with grouping the retailers into multi clusters which are regarded as many "big-retailers",this policy is termed Integer-Ratio Fixed-Partition policy. Combined with the "basic IRP," the three-echelon IRP is devided into two sub-problems,and its lower or uper bound is derived.Conducting solving probability analysis, a huristics algrithm is designed with intger ratio of transportation cost to inventory cost or invers.The ratio is used to reduce the solution space and to direct searching the optimal solution, designed to reduce the planning period (center purchase period) heuristic search algorithm. Simulation shows that Integer-Ratio Fixed-Partition policy has an efficiency of 80% or more, and it's better than that of Power-of-Two Fixed-Partition policy.