供应网络中越库转运中心仓门分配问题研究

Truck Dock Assignment Problem for Crossdocks in Supply Networks

本文探讨一种带有时间窗口的仓门分配问题———车辆在转运中心进行货物装卸作业时如何在其时间窗口限制内有效的分配有限的仓门资源,以达到最佳运作效率。以往的研究结果表明该问题是强NP难题,因此本文针对该问题的特殊结构,提出一种新颖的整合了贪婪算法、遗传算法以及禁忌算法思想的混合启发式算法来有效的解决该问题。我们并将该混合启发式算法与遗传算法、禁忌算法以及CPLEX这三种方式的求解效果进行对比,其数值实验结果表明混合启发式算法在求解效果上有明显的优势。

An effective supply chain can help companies achieve international competitiveness.Many companies have tried to optimize their distribution activities in their supply chains by adopting the cross-docking logistics strategy.This strategy can effectively integrate inventory management and distribution activities.Cross-docking is a logistics practice of unloading materials from incoming transportation vehicles（e.g.truck,trailer or rail car） and loading these materials directly into outgoing transportation vehicles without holding storage in between.Cross-docking can significantly reduce inventory levels,inventory costs and cargo loss rates,speed up cash flows,and increase response time to market demand.Consequently,an effective cross-docking strategy can improve customer satisfaction and have significant,lasting impacts on the operational efficiency of supply chains.This study investigates cross-docking problems limited with a set of constraints.An Integer Programming Model is setup to analyze cross-docking problems.A Hybrid Meta-heuristic Algorithm（HMA） is designed to help solve these problems.A few constraints are constructed in order to effectively use these models to solve cross-docking problems.Each truck has a service time window,only within which the truck can occupy a dock.The number of docks is limited.The distance between docks varies.The number of cargos and the time window for each truck are different.The shipping distance between docks needs to be kept at the minimum level.The goals of these models are to assign docks to trucks so that cargos can be processed as efficiently as possible.Constraints,such as capacity and time window,will cause some cargos not to be shipped out.Resultant delayed deliveries can increase total logistics costs.An effective assignment of trucks can have impact on cross-docking operational efficiency and cost.The objective of this study is to design a cross-docking assignment strategy so that the optimal efficiency of cross-docking operations can be achieved while meeting operation constraints.We first describe cross-docking assignment problems for trucks,constraints and assumptions.We then introduce an an Integer Programming Model,its notations and decision variables.Second,we introduce the idea of designing a HMA and apply a Genetic Algorithm（GA） to locate a near optimal solution.Neighborhood Search（NS） and Tabu Search（TS） are applied in order to solve problems and improve the quality of solutions to these problems.After doing so,we explain how HMA works,including single-point crossover operator,two-point crossover operator,exchange mutation operator,repair strategy,neighborhood search strategy,etc.Numerical examples are used to compare the performance of HMA,CPLEX,GA and TS with respect to the efficiency of HMA.We not only show the setting of all parameters,but also develop three categories of experiments including large,medium and small scale instances.The results show that all of these four methods have similar performance for small scale problems in conditions that the time consumed of HMA is as much as GA,a little bit longer than TS,but shorter than CPLEX.For medium scale problems,the solution quality of HMA outperforms the others,and the ranking of time consumed is as the same as that of small scale problems.For large scale problems,HMA is slower than TS and GA,but still much faster than CPLEX.Moreover,both HMA and TS have the highest solution quality.In general,HMA has the best performance in the solution quality,and the time consumed by it is as much as GA,longer than TS,but much shorter than CPLEX.In summary,this paper investigates cross-docking assignment problems with the constraints of limited time window and cross-docking capacity constraints.Our proposed model develops an efficient HMA to overcome the weakness of previous cross-docking models.The numerical experiments show that HMA has the best performance in the solution quality.The finding indicates that this HMA is an efficient way to solve cross-docking problems,especially for a large numbers of trucks and docks.