Door-to-door Pickup And Delivery Service Design In Space-time-state Network

The online shopping market size continues to expand,the express delivery industry is developing rapidly,and the express delivery service model is becoming more diversified.The new service model of door-to-door pickup and delivery allows users to complete the delivery and pickup of goods without leaving home.Customers only need to make an appointment in advance on the mobile APP or corresponding website,specify the expected service time and other information,and wait for the courier to come to serve.After operators complete the receipt of the information,it will make a reasonable plan based on the customer’s pick-up or delivery quantity,space location,and expected service time.Operators not only need to provide services within the specified time of all customers to improve customer satisfaction,but also needs to do its best to reduce unnecessary detour distances to reduce operating costs.In response to this situation,this paper constructs a door-to-door delivery service model with a time window in the space-time-state network to find the lowest cost express car service path and provide planning and decision support for operators.First,this paper expands the actual road network into a space-time-state three-dimensional network to reduce model constraints.Since time sequence constraints and vehicle capacity constraints are implicit in the network architecture,there are only flow balance constraints,customer demand satisfaction constraints,visits constraints,maximum mileage constraints and binary constraints of independent variables in the model.In addition,the number of goods to be taken and the number of goods to be delivered in the state dimension are mutually restricted,and the solution whose sum of the two is greater than the vehicle capacity in the solution space is deleted in advance to narrow the search scope for subsequent solutions.Second,the augmented Lagrangian method combined with the block coordinate descent method is used to solve the symmetry and indecomposability problems.Since the subproblems use the same multipliers,using the standard Lagrangian method to decompose the model will cause symmetry problems.The quadratic penalty in the augmented Lagrangian method can effectively eliminate the symmetry problem.Further,using the block coordinate descent method can solve the indecomposability caused by the secondary penalty term.The two are used in combination to decompose the original problem into independent shortest path sub-problems.Then,the sub-problem is solved using forward dynamic programming algorithm,which is used to update the solution of each iteration of the block coordinate descent method.Each iteration only solves one sub-problem,while temporarily fixing the solutions of other sub-problems.After the solution of the sub-problem is updated,the new solution is immediately fixed for the solution of the next sub-problem.The upper bound of the model is given by the augmented Lagrangian function,and the lower bound of the model is given by the standard Lagrangian function without a secondary penalty term.The quality of the solution is evaluated by the Gap between the upper and lower bounds.Finally,using a four-node small network and the road network within the inner ring of Nanjing to verify the effectiveness of the model and algorithm.Two sets of experiments are designed on the four-node network.The first set proves the low cost of the service strategy in this paper compared with other service strategies in the existing research,and the second set proves that the model in this paper is applicable to both homogeneous and heterogeneous fleets.The road network within the inner ring of Nanjing proved the applicability of the algorithm to large-scale networks.Compared with the standard Lagrangian method,the augmented Lagrangian method combined with the block coordinate descent method has faster convergence speed and no symmetry problem.Therefore,the performance of this method is better than the standard Lagrangian method,and it is more suitable for large-scale vehicle routing problems.