Mathematical Modeling And Approximation Algorithm Design For Logistics-oriented Vehicle Routing Problems

In modern logistics industry,on one hand,logistics quality determines consumers' satisfaction.On the other hand,logistics enterprises have been facing with the problem of how to reduce logistics costs and increase economic profits.Logistics cost is the monetary transformation of all the kinds of labor consumed by space movement and time occupancy during the service,in which the optimization of vehicle routes directly affects consumers' satisfaction and logistics costs.Therefore,vehicle routing problem(VRP)arises therein.This problem is of great practical significance,and has been one of most challenging NPhard problems in combinatorial optimization.Logistics transportation has the following characteristics.The logistics environment among cities usually uses aircrafts,trains and freighters for transportation,where the one dimensional roads are such as airlines,railways and sea lanes.In the logistics environment inside a city,customer demands are transported by two echelons,where the first echelon is from depots to satellites,and the second echelon is from satellites to business points,which will be the depots in next level logistics.The logistics environment in final area is the final level in the whole logistics environment,in which demands are delivered from business points to their nearby customers.Because customers' locations in these areas are close,their distance can be reduced to Euclidean distance.Based on above characteristics,the dissertation proposes and models one dimensional VRP among cities,two-echelon VRP inside a city,Euclidean plane VRP in final area,and VRP under generalized objective function.Further,mathematical models are formulated,combinatorial properties are proved,and approximate algorithms are designed.Research content in the dissertation is as follows.1.Under the logistics environments among cities,one dimensional VRP is proposed in consideration of one dimensional roads,such as airlines,railways and sea lanes in maps.This problem takes depots,one dimensional roads,and vehicle capacity as input,whose objective function is to find the vehicle routes with the shortest total length,so that all the demands are visited within designated time windows,and hence service is fulfilled and logistics cost is minimized.For this problem,mathematical programming model is formulated,combinatorial structure is analyzed by employing properties of bin packing problem,and approximation scheme is designed.The approximation ratio of this algorithm is proved to infinitely approximate to that of the polynomial time approximation scheme when approaching the asymptotic condition.Therefore,under this condition,the algorithm is currently the most effective to solve one dimensional VRP.2.Under the logistics environments inside a city,adaptive two-echelon VRP is proposed by considering the paths from depots to business points,passing satellites or not.In the aspect of mathematical models,integer linear programming is formulated and extended to multiple echelons.In the aspect of combinatorial properties,lower bound of optimum solution is proposed and proved,which is better than the optimum solution of linear relaxation model of this problem.The subgradient algorithm is designed based on lower bound,whose efficiency is verified by experimental results.3.Under logistics environments in final area,proposed and models three categories of VRP on Euclidean plane,which are traveling salesman problem(TSP)with time windows,VRP with time windows,and VRP with multiple depots and time windows.Firstly,time windows are introduced into TSP on Euclidean plane,and path structure is analyzed to design polynomial time approximation scheme for this problem.Secondly,time windows are introduced into VRP on Euclidean plane,and quasi polynomial time approximation scheme for this problem is designed based on previous problem.Finally,multiple depots and time windows are introduced into VRP on Euclidean plane,and quasi polynomial time approximation scheme for this problem is designed based on previous problems.Theoretical and experimental analyses showed their efficiency.4.Considering the complex and various requirements on service objectives in modern logistics environments,VRP under generalized objective function is studied,in which the multi-factor influence maximization problem is proposed and modeled.This problem arises from the route planning for emergency supply delivery.Given multiple categories of supplies,locations and roads in a map,on which each category is allowed to be transported according to probability,this problem is to select a set of locations as supply centers,so that the vehicle routes starting from them will effectively cover the maximum number of locations on expected probability.Here,the effective covering at a location means all the categories must arrive at this location.To solve this problem,submodularity is proposed and proved,and then randomized greedy algorithm is designed.Both the theoretical and experimental analyses proved efficiency of this algorithm.