Policies For Stochastic Dynamic Multi-Vehicles Pick-up And Delivery Problem

In recent years, logistics industry has grew rapidly in our country. It's overall scale has upgraded steady. Logistics industry has became the leading industry of the national economy and played an important role in social economy development. But logistics management is still relatively backward in our country. Logistics industry generally faces the problems of low specialized degree, high consuming, low efficiency, and so on. These lead to high logistics cost. Therefore, how to effectively reduce transportation costs, which account for about 50% of logistics costs, is critical to reduce logistics costs and to improve the level of logistics.The research object of this paper is pick-up and delivery problem in the process of transport under stochastic dynamic environment. According to the practical application, three expansions were proposed, which include the expansion of vehicle number from single-vehicle to multi-vehicles, the expansion of objective function from single-objective to multi-objectives, and the expansion of assumptions of demand distribution from uniform distribution to general distribution. To solve these expansion problems, some policies were put forward. The asymptotic properties of each policy were analyzed, and the performance of each policy was simulated. Main contents of this article are as follows:Firstly, single-objective stochastic dynamic multi-vehicles pick-up and delivery problem was studied. Lower bounds of expected system time of this problem were deduced by applying queuing theory in light traffic case and in heavy traffic case respectively. Two solving policies, including stochastic queue median policy and multi-depot stochastic queue median policy, were proposed to solve this problem in light traffic case. Stacker crane policy was proposed to solve this problem in heavy traffic case. The asymptotic properties of each policy were analyzed and the performance of each policy was simulated. To solve the problem that changes of traffic intensity affect solving quality, a solving policy, which is called region partitioning policy, was proposed. This policy is simultaneously suitable to the light and heavy traffic condition. The asymptotic properties of this policy were analyzed respectively in the case of light traffic and of heavy traffic. The effectiveness of this policy was simulated in both cases.Secondly, the mathematical model of multi-objectives stochastic dynamic multi-vehicles pick-up and delivery problem was established, with simultaneously minimizing expected waiting time of customers and of vehicles as the objective function. Two solving policies, the nearest neighbor policy and the stacker crane policy, were proposed to solve this problem. The upper bounds of these policies were calculated. Simulation was carried out to analyze the performance of these policies under different traffic intensity circumstances and to analyze the relationship between the objective function and parameters of each policy.Finally, to solve stochastic dynamic multi-vehicles pick-up and delivery problem with general distributions of demands, a solving policy, which is called region partitioning policy, is proposed. Based on the lower bounds of expected system time, the asymptotic properties of this policy were analyzed under light and heavy traffic circumstances respectively. To verify the effectiveness of region partitioning policy solving stochastic dynamic multi-vehicles pick-up and delivery problem with general distributions of demands, comparation of this policy, stochastic queue median policy and multi-depot stochastic queue median policy is simulated.