Research On Soft-time Vehicle Routing Problem Based On Hybrid Ant Colony Algorithm

Vehicle Routing Problem(VRP)is one of hot topics in the field of combinatorial optimization.It has a wide range of application backgrounds and practical significance.With the requirement of continuous improvement to customer service,vehicle routing problems with time windows(VRPTW)attracted more and more attention.In this thesis,Static Vehicle Routing Problem with Soft Time Window(SVRPSTW)and Dynamic Vehicle Routing Problem with Soft Time Window(DVRPSTW)were studied.For SVRPSTW,aiming to minimize the total cost and to maximize customers' satisfaction,a bi-objective integer programming model is established.A Hybrid Ant Colony Optimization(HACO)is designed to solve it.An elitist-ant strategy is set up to explore the bi-objective functions respectively and to get the better non-dominant solutions.The evaporation factors are redefined to balance global and local search capabilities of the algorithm and to avoid premature convergence.NSGA-? is used to guide the bi-objective optimizing process,and a variable neighborhood search algorithm is used to expand the search space,in order to obtain the better Pareto solution set.The optimal parameter combination was determined by an orthogonal experiment,and the Solomon standard instances are used to test the performance of the algorithm.The simulation results show that the performance of HACO has a significant improvement.For DVRPSTW considering traffic conditions,the customer demand arrives dynamically,and the integer programming model is constructed with the goal of minimizing the total cost.The HACO algorithm is used to plan the path in both stages of initial planning stage and dynamic optimization stage.In the initial stage,the clustering algorithm was used to cluster the customers,divide different areas and set the initial pheromone distribution.In the dynamic optimization stage,in order to respond to customer requests as soon as possible,the updating mechanism of re-planning immediately after the occurrence of dynamic events is adopted.The current vehicle status information is set as virtual customer points when updating the path,the dynamic vehicle routing problem is transformed into instantaneous static vehicle routing problem,and then solved by HACO algorithm.The effectiveness of the algorithm is proved by the analysis of experimental results.The results of this thesis have certain reference value for the research of the solution algorithm of large-scale distribution service with time window.