Robust Optimization For Vehicle Routing Problem Under Demand Uncertainty

Logistics and distribution is a field that consumes a lot of manpower and material resources.This field has a large optimization space.This paper focuses on stochastic vehicle routing problem in the last mile of distribution.In the actual situation,distribution requirements of a company are stochastic.Stochastic factors include order location,service time,and so on.On the other hand,the familiarity of the driver to the route will directly affect its distribution efficiency.Service time at the zone of the driver will affect customer experience.Therefore,companies need robust vehicle routings under multi-day stochastic demands.This paper provides a general framework to describe robust vehicle routing problems under multiple scenarios.Firstly,considering the robustness of vehicle path under random factors,this paper introduces the concept of plan consistency of each scenario and proposes a vehicle path model with master plan consistency.The model is designed to give a master schedule and daily schedules for each day.The objective function of the model is to minimize the weighted total cost of all schedules.In addition to constraints that deterministic models will contain,our model also includes master schedule consistency constraints to ensure that vehicles' spatio-temporal paths deviation ratio between master schedule and daily schedules.This paper uses zone as the unit of demand.The zone center includes all needs within this area.Stochastic factors of the model are stochastic total service time,time window and total weight of the zone in different scenarios.Secondly,the vehicle routing problem is a NP-Hard problem.This problem becomes more complicated after introducing stochastic factors.Constraints of stochastic vehicle routing problem include integer constraints and a large number of marginal constraints which is also included in deterministic problems,as well as consistency constraints on vehicle paths between master schedule and sub-schedules.These two constraints couple vehicles in different schedules and different vehicles in the same schedule,which make the problem more difficult to solve.Therefore,this paper uses the Lagrangian relaxation method and the alternating direction method of multipliers(hereinafter collectively referred to as ADMM)to decompose the original problem and reconstruct the model.This paper first relaxes consistency constraints into the objective function by Lagrangian relaxation.Then we split the original problem into sub-problem of each schedule.Next,this article will use ADMM technology to relax the integer constraints in each schedule,and further split the multi-vehicles routing problem into the single vehicle routing sub-problem.This paper solves single vehicle routing sub-problems in order based on spatio-temporal-state network and dynamic programming method.Finally,this article uses Python programming to implement specific algorithms and do a lot of case analysis.In this paper,the concept of robust spatio-temporal path and the solution process of the model are described in detail through small examples.Then,this paper will give a convergence analysis under different scenario numbers and experimente on medium-scale networks.Finally,this article will build a practical case to verify the practicability of the model.Experiments show that the model has a good convergence effect.Compared with the model which does not consider consistency constraints,our model can give robust vehicle paths under multiple scenarios on the premise of a small increase in total cost.