Optimization Of Time-Dependent Delivery Problem And Integrated Production-Delivery Problem For Perishable Products

There are many types of perishable products in our social practices and lives,which deteriorate over time after they are produced and thereby bring about a lot of difficulties in business decisions,especially in production and distribution planning.This thesis focus on the problems related to the distribution process,and studied two issues derived respectively from mass production and make-to-order mode for rapidly perishable commodity,that is,vehicle routing problems and integrated scheduling of production and distribution for perishable products.Further,the capacity limitations of the production and transportation are discussed detailedly to extend the above two issues.Accordingly,order selection decisions are incorporated into them to maximize the total revenue of decision makers.In addition,the traffic flow usually manifests a time-dependent pattern in urban areas,where the demands of customers account for a larger share of the total amount.To avoid unnecessary traffic jams,the time-dependent property of road network is factored into the above models in hope of decreasing deterioration loss of products and providing timely deliveries with larger total return.The specific studies are as follows:Firstly,with the time-dependency of road network considered,the distribution planning of perishable products and vehicle rerouting scheme for transportation delay are studied.At the initial routing stage,a time-dependent vehicle routing problem with time window is proposed based on a multigraph,which aims to minimize the total operating cost and deterioration loss of perishable products during transportation process.At the planning executing stage,a split delivery scheme is proposed for routing recourse when transportation delay is discovered in one or more routes,which respects the fact that total remaining delivery capacity is just equal to the total remaining demand of customers.Then,tabu search algorithms are devised to solve the two models with special types of neighborhood structures and operators.The effectiveness of the proposed models and algorithms is demonstrated by comparison of computation results of modified Solomon benchmark instances with ant colony optimization algorithm and global rescheduling method.Experiments results show that the disruption events can be recovered to a greater extent when disruption events occur earlier.Secondly,under the condition of insufficient delivery capacity and failure to serve all customers on time with intact products,the integrated optimization of customer selection and time-dependent vehicle routing problem is studied for distribution of perishable products.Based on the linearization of the time-dependent road traveling time and representation of two kinds of time windows,a mixed integer linear programming model is established with the objective of maximizing total customers' revenue and decision variables of vehicle departure times.Then,a hybrid ant colony algorithm(HACO)is proposed to solve it with three operators embedded into it.At last,a test dataset is constructed based on Solomon benchmark instances.The effectiveness of the proposed models and algorithms is demonstrated by comparison of computation results with IBM ILOG CPLEX Optimizer and HACO without LNS operator.The sensitive analyses indicate that the importance attached to regular customers can be reflected by a small value of the coefficient and provide management insights that more large vehicles can be used in high congestion regions while more small vehicles should be put into use in low congestion regions.Thirdly,with the time-dependent property of road network considered,the integrated optimization of production scheduling and vehicle routing problem is studied.A mixed integer nonlinear programming model is established with the objective to minimize the total operation cost including deterioration loss of perishable products and operations costs from vehicle dispatching and transportation process.Then,a hybrid genetic algorithm is proposed to solve the problem.An illustration of a small example indicates the effectiveness of the proposed model and algorithm.Computation results show that the number of customers served within their time windows declines as dynamics of road network increases when the time-dependent property of road network is not considered,and the total cost and deterioration loss of products can be decreased with more vehicles put into use.Finally,under the situation of insufficient production capacity and multi-site production lines,an integrated optimization of production scheduling and time-dependent vehicle routing problem with order selection is studied.A mixed integer nonlinear programming model is established with the objective to maximize the total revenue.According to the characteristics of the model,a hybrid iterated local search algorithm is proposed to solve it,where dynamic programing is inserted to select orders for batch delivery in each production site.Based on the dataset modified from Solomon benchmark instances,the effectiveness of the model and algorithm is demonstrated.Parameter analysis reveals that the revenue of accepted orders and the number of used vehicles are affected significantly by the fixed cost of vehicle.In summary,this thesis studied distribution planning of perishable products and integrated scheduling of production and delivery for rapidly perishable products in the time-dependent road network.According to the partition of operational capacity of supplier,these topics are extended to the integrated decision of order selection and vehicle routing problem when delivery capacity is insufficient,and integrated scheduling of production and delivery with order selection when production capacity is insufficient.These studies not only make up for the deficiencies of current decision models,but also provide a new direction for perishable product distribution from revenue management perspective.