Study On Dynamic Arc Routing Problem With Uncertain Time Variables

Arc routing problem is the hot topic and important research content in the transportation management field.Arc routing problem with time limit belongs to the capacitated arc routing problem(CARP),which has extensive practical applications.This paper focuses on the problem of daily highway maintenance and the dynamic capacitated arc routing problem with uncertain time(DCARPUT)is studied.The uncertainty of vehicles' travel time and service time on the road segments and dynamism of road network's states in the process of maintaining are considered.And the optimization goal is to obtain the minimum maintenance cost.Based on the uncertainty and dynamism of DCARPUT,two programming models with different recourse strategies are built.The multiple scenario approach based on event-driven strategy and the simulation-based optimization method are proposed respectively to solve the two models.The paper's main research contents and achievements are as follows:(1)DCARPUT is described and models are built according to the uncertain time variables and dynamic characteristics.Two different recourse strategies are also introduced based on the objective function.(2)For the programming model with recourse strategy 1,the delay recourse cost is considered and the uncertain time variables are defined as discrete distribution.A multiple scenario approach based on event-driven strategy is proposed so that the uncertain problem is converted into series of determined problems.When any vehicle reaches the starting point of an arc,the network states are triggered to update,so as the scenario pool,then vehicle routing plan is adjusted.(3)The programming model with recourse strategy 2 considers not only the delay recourse cost but also the overtime recourse cost,in which the uncertain time variables are defined as continuous distribution.In view of the fact that there exists stochastic variables in the objective function and constraint conditions,it's difficult to obtain satisfied solution by the analytic method.Therefore,simulation-based optimization method is introduced.Estimation value is got through the simulation process and is fed back to the optimization module for the further optimization.And according to the dynamic characteristics of road network,a fixed-increment time advance mechanism is put forward to continuously adjust the routing plan dynamically.The arc routing problem in this paper is based on the maintenance vehicle routing plan during the process of daily highway maintenance.According to the uncertain constraint conditions and dynamic elements faced in the actual maintenance process,vehicle routing plan is adjusted constantly to adapt to the dynamic effects of the environment.It has a guiding significance for practical applications.By the scientific planning means and accurate and effective decision methods,resource waste caused by the artificial decision can be reduced and higher demand for road safety and tight budget constraints can be met.